Markow-Ketten in Python: Einsteiger-Tutorial

Eine Markow-Kette ist ein mathematisches System, in der Regel definiert als eine Sammlung zufälliger Variablen, die gemäß bestimmten Wahrscheinlichkeitsregeln von einem Zustand in einen anderen übergehen. Diese Übergänge erfüllen die Markow-Eigenschaft: Die Wahrscheinlichkeit, in einen bestimmten Zustand überzugehen, hängt ausschließlich vom aktuellen Zustand und der vergangenen Zeit ab – nicht von der Abfolge der vorherigen Zustände. Dadurch sind Markow-Prozesse gedächtnislos.

Du willst noch mehr Statistikthemen mit Python angehen? Schau dir den Kurs Statistical Thinking in Python von DataCamp an!

Dann legen wir los…

Warum Markow-Ketten?

Markow-Ketten werden in der Mathematik äußerst vielseitig eingesetzt. Sie finden breite Anwendung in Ökonomie, Spieltheorie, Kommunikationstheorie, Genetik und Finanzwesen. In der Statistik – insbesondere der Bayesschen Statistik – und in informationstheoretischen Zusammenhängen treten sie häufig auf. In realen Anwendungen dienen sie unter anderem dazu, Lösungen für Tempomat-Systeme in Fahrzeugen, Warteschlangen am Flughafen oder Wechselkurse zu modellieren. Der ursprünglich für die Google-Suchmaschine entwickelte PageRank-Algorithmus basiert auf einem Markow-Prozess. Auch Reddits Subreddit Simulator generiert Beiträge und Kommentare vollständig automatisiert mit Markow-Ketten – ziemlich cool!

Markow-Kette

Eine Markow-Kette ist ein Zufallsprozess mit der Markow-Eigenschaft. Ein Zufallsprozess (auch stochastischer Prozess) ist ein mathematisches Objekt, definiert als eine Sammlung zufälliger Variablen. Eine Markow-Kette besitzt entweder einen diskreten Zustandsraum (Menge der möglichen Werte der Zufallsvariablen) oder eine diskrete Indexmenge (häufig die Zeit) – entsprechend existieren viele Varianten. Üblicherweise bezeichnet der Begriff „Markow-Kette“ einen Prozess mit diskreten Zeitpunkten, also eine Diskrete-Zeit-Markow-Kette (DTMC).

Diskrete-Zeit-Markow-Kette

Eine Diskrete-Zeit-Markow-Kette beschreibt ein System, das bei jedem Schritt in einem bestimmten Zustand ist und sich zwischen den Schritten zufällig verändert. Die Schritte lassen sich als Zeitpunkte interpretieren (ebenso wären aber auch physische Distanzen oder andere diskrete Messgrößen möglich). Formal ist eine Diskrete-Zeit-Markow-Kette eine Folge von Zufallsvariablen X₁, X₂, X₃, … mit der Markow-Eigenschaft, d. h. die Wahrscheinlichkeit, in den nächsten Zustand zu wechseln, hängt nur vom aktuellen Zustand ab, nicht von früheren Zuständen. Mathematisch formuliert:

Pr( X_n+1 = x | X₁ = x₁, X₂ = x₂, …, X_n = x_n) = Pr( X_n+1 = x | X_n = x_n)

Wie du siehst, hängt die Wahrscheinlichkeit für X_n+1 nur vom unmittelbar vorhergehenden X_n ab. Das heißt: Die Kenntnis des aktuellen Zustands genügt, um die Wahrscheinlichkeitsverteilung des nächsten Zustands zu bestimmen – das ist bedingte Unabhängigkeit.

Die möglichen Werte von X_i bilden eine abzählbare Menge S, den Zustandsraum der Kette. Der Zustandsraum kann alles Mögliche sein: Buchstaben, Zahlen, Basketball-Ergebnisse oder Wetterzustände. Während der Zeitparameter in der Regel diskret ist, gibt es für den Zustandsraum einer Diskrete-Zeit-Markow-Kette keine allgemein anerkannten Beschränkungen; oft betrachtet man Prozesse auf beliebigen Zustandsräumen. In vielen Anwendungen nutzt man jedoch endliche oder abzählbar unendliche Zustandsräume, weil sie statistisch einfacher zu analysieren sind.

Modell

Eine Markow-Kette lässt sich als probabilistischer Automat darstellen (klingt komplizierter als es ist!). Die Zustandswechsel heißen Übergänge. Die zugehörigen Wahrscheinlichkeiten nennt man Übergangswahrscheinlichkeiten. Ein probabilistischer Automat integriert die Wahrscheinlichkeit eines Übergangs in die Übergangsfunktion und wird so zur Übergangsmatrix.

Du kannst dir das als Folge gerichteter Graphen vorstellen, deren Kanten im Zeitpunkt n mit den Wahrscheinlichkeiten beschriftet sind, von einem Zustand zur Zeit n in Zustände zur Zeit n+1 zu wechseln, Pr(X_n+1 = x | X_n = x_n). Das bedeutet: Wahrscheinlichkeit, in den Zustand X_n+1 zu gelangen, gegeben X_n. Die gleiche Information steckt in der Übergangsmatrix vom Zeitpunkt n zu n+1. Jeder Zustand im Zustandsraum erscheint genau einmal als Zeile und einmal als Spalte; jede Zelle gibt die Wahrscheinlichkeit an, vom Zeilen- in den Spaltenzustand überzugehen.

Hat die Markow-Kette N mögliche Zustände, ist die Matrix N×N groß; der Eintrag (I, J) ist die Wahrscheinlichkeit, von Zustand I nach Zustand J zu wechseln. Zusätzlich muss die Übergangsmatrix stochastisch sein, d. h. die Einträge jeder Zeile summieren sich genau zu 1. Warum? Weil jede Zeile eine eigene Wahrscheinlichkeitsverteilung darstellt.

Das Modell ist also charakterisiert durch einen Zustandsraum, eine Übergangsmatrix mit den Übergangswahrscheinlichkeiten und eine Anfangsverteilung über dem Zustandsraum.

Ganz schön viele Worte, oder?

Schauen wir uns ein einfaches Beispiel an, um die Konzepte greifbar zu machen:

Wenn Cj traurig ist – was selten vorkommt –, geht sie entweder joggen, verdrückt Eiscreme oder macht ein Nickerchen.

Aus historischen Daten wissen wir: Wenn sie einen traurigen Tag verschläft, ist es am nächsten Tag zu 60% wahrscheinlich, dass sie joggen geht, zu 20% bleibt sie im Bett und zu 20% isst sie Eiscreme.

Wenn sie traurig ist und joggen geht, liegt die Wahrscheinlichkeit bei 60%, dass sie auch am nächsten Tag joggen geht, bei 30% schlemmt sie Eiscreme und nur zu 10% schläft sie am nächsten Tag.

Wenn sie an einem traurigen Tag Eiscreme isst, ist die Chance, am nächsten Tag wieder Eiscreme zu essen, nur 10%; zu 70% geht sie joggen und zu 20% schläft sie am nächsten Tag.

Die im Zustandsdiagramm dargestellte Markow-Kette hat 3 mögliche Zustände: Schlaf, Joggen, Eiscreme. Die Übergangsmatrix ist also 3×3 groß. Beachte: Die von einem Zustand ausgehenden Pfeile summieren sich stets zu genau 1; entsprechend müssen sich die Einträge jeder Zeile der Übergangmatrix zu 1 addieren – sie repräsentieren eine Wahrscheinlichkeitsverteilung. In der Übergangsmatrix leisten die Zellen dasselbe wie die Pfeile im Zustandsdiagramm.

Jetzt, wo du das Beispiel kennst, hast du ein Gefühl für die Konzepte rund um Markow-Ketten. Aber wie nutzt du diese Theorie im Alltag?

Mit dem Beispiel kannst du Fragen beantworten wie: „Ausgehend vom Zustand Schlaf, wie groß ist die Wahrscheinlichkeit, dass Cj nach zwei traurigen Tagen im Zustand Joggen ist?“

Rechnen wir das aus: Um von Schlaf zu Joggen zu kommen, kann Cj erst im ersten Schritt (bzw. am ersten Tag) bei Schlaf bleiben und im zweiten Schritt zu Joggen wechseln (0,2 · 0,6); oder sie wechselt am ersten Tag zu Joggen und bleibt dort am zweiten (0,6 · 0,6); oder sie wechselt im ersten Schritt zu Eiscreme und im zweiten zu Joggen (0,2 · 0,7). Also beträgt die Wahrscheinlichkeit: ((0,2 · 0,6) + (0,6 · 0,6) + (0,2 · 0,7)) = 0,62. Es gibt also eine 62%‑Chance, dass Cj nach zwei traurigen Tagen im Zustand Joggen ist, wenn sie im Zustand Schlaf gestartet ist.

Hoffentlich zeigt dir das, welche Fragen sich mit einem Markow-Ketten-Netzwerk beantworten lassen.

Mit diesem Verständnis wird es auch leichter, einige wichtige Eigenschaften von Markow-Ketten zu erfassen:

• Reduzierbarkeit: Eine Markow-Kette heißt irreduzibel, wenn man von jedem Zustand jeden anderen erreichen kann. Anders gesagt: Es existiert zwischen beliebigen zwei Zuständen eine Folge von Schritten mit positiver Wahrscheinlichkeit.
• Periodizität: Ein Zustand ist periodisch, wenn die Kette nur in ganzzahligen Vielfachen einer Zahl größer als 1 in diesen Zustand zurückkehren kann. Startest du in Zustand „i“, kann die Kette also nur in Vielfachen der Periode „k“ nach „i“ zurückkehren; k ist das größte solche Integer. Zustand „i“ ist aperiodisch, wenn k = 1, und periodisch, wenn k > 1.
• Transienz und Rekurrenz: Ein Zustand „i“ heißt transient, wenn es – ausgehend von „i“ – eine von null verschiedene Wahrscheinlichkeit gibt, nie wieder nach „i“ zurückzukehren. Andernfalls ist Zustand i rekurrent (oder persistent). Ein rekurrenter Zustand heißt positiv rekurrent, wenn die erwartete Rückkehr in endlich vielen Schritten erfolgt, andernfalls null-rekurrent.
• Ergodizität: Ein Zustand „i“ heißt ergodisch, wenn er aperiodisch und positiv rekurrent ist. Sind in einer irreduziblen Markow-Kette alle Zustände ergodisch, heißt die Kette ergodisch.
• Absorbierender Zustand: Ein Zustand i heißt absorbierend, wenn er nicht verlassen werden kann. Formal: Zustand „i“ ist absorbierend, wenn p_ii = 1 und p_ij = 0 für i ≠ j. Kann jeder Zustand einen absorbierenden Zustand erreichen, spricht man von einer absorbierenden Markow-Kette.

Tipp: Wenn du eine visuelle Erklärung zu Markow-Ketten möchtest, besuche diese Seite.

Markow-Ketten in Python

Lass uns das obige Beispiel in Python umsetzen. In der Praxis würdest du wahrscheinlich eine Bibliothek verwenden, die Markow-Ketten effizienter kapselt, aber der Code hilft dir beim Einstieg…

Importieren wir zuerst die benötigten Bibliotheken.

import numpy as np
import random as rm

Definieren wir nun die Zustände und ihre Wahrscheinlichkeiten: die Übergangsmatrix. Denk daran: Die Matrix ist 3×3 groß, weil es drei Zustände gibt. Außerdem legst du die möglichen Übergänge fest – das geht ebenfalls mit Matrizen.

# The statespace
states = ["Sleep","Icecream","Run"]

# Possible sequences of events
transitionName = [["SS","SR","SI"],["RS","RR","RI"],["IS","IR","II"]]

# Probabilities matrix (transition matrix)
transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]

Stelle unbedingt sicher, dass sich die Wahrscheinlichkeiten zu 1 summieren. Und es schadet nicht, Fehlermeldungen auszugeben – zumindest beim Coden!

if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
    print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;)")

All is gonna be okay, you should move on!! ;)

Jetzt kommt der eigentliche Teil. Mit numpy.random.choice ziehst du eine Zufallsprobe aus der Menge möglicher Übergänge. Die meisten Argumente sind selbsterklärend; p ist die optionale Wahrscheinlichkeitsverteilung für die Auswahlmenge – hier also die entsprechende Zeile der Übergangsmatrix.

# A function that implements the Markov model to forecast the state/mood.
def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    print("Start state: " + activityToday)
    # Shall store the sequence of states taken. So, this only has the starting state for now.
    activityList = [activityToday]
    i = 0
    # To calculate the probability of the activityList
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1  
    print("Possible states: " + str(activityList))
    print("End state after "+ str(days) + " days: " + activityToday)
    print("Probability of the possible sequence of states: " + str(prob))

# Function that forecasts the possible state for the next 2 days
activity_forecast(2)

Start state: Sleep
Possible states: ['Sleep', 'Sleep', 'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12

Du erhältst eine zufällige Folge möglicher Übergänge samt ihrer Wahrscheinlichkeit – ausgehend vom Zustand Sleep. Erweitere das Programm, indem du es einige Hundert- oder Tausendmal mit demselben Startzustand durchläufst. So kannst du die erwartete Wahrscheinlichkeit ermitteln, in einem bestimmten Zustand zu enden. Schreiben wir die Funktion activity_forecast entsprechend um und fügen Schleifen hinzu…

def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    activityList = [activityToday]
    i = 0
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1    
    return activityList

# To save every activityList
list_activity = []
count = 0

# `Range` starts from the first count up until but excluding the last count
for iterations in range(1,10000):
        list_activity.append(activity_forecast(2))

# Check out all the `activityList` we collected    
#print(list_activity)

# Iterate through the list to get a count of all activities ending in state:'Run'
for smaller_list in list_activity:
    if(smaller_list[2] == "Run"):
        count += 1

# Calculate the probability of starting from state:'Sleep' and ending at state:'Run'
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")

The probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%

Wie nähern wir uns den erwarteten 62% an?

Hinweis: Das ist das „Gesetz der großen Zahlen“. Es besagt, dass sich die relativen Häufigkeiten gleich wahrscheinlicher Ereignisse angleichen – allerdings nur bei genügend vielen Versuchen. Mit zunehmender Anzahl an Experimenten konvergiert das Verhältnis der tatsächlich beobachteten Ergebnisse gegen das theoretisch erwartete Verhältnis.

Markow State of Mind

Damit sind wir am Ende des Tutorials zu Markow-Ketten. Du hast Markow-Ketten kennengelernt und einige ihrer Eigenschaften gesehen. Einfache Markow-Ketten gehören zu den Grundlagen, um mit Data Science in Python durchzustarten. Wenn du mehr Ressourcen zum Einstieg in Statistik mit Python suchst, schau dir diese Seite an.

Du möchtest weitere praxisnahe Fallstudien mit Statistik in Python erkunden? Sieh dir die Kurse Case Studies in Statistical Thinking oder Network Analysis in Python von DataCamp an.