Symmetrische einfache Irrfahrt

Einige Beispielpfade der symmetrischen einfachen Irrfahrt

Die symmetrische einfache Irrfahrt (auf $\mathbb {Z}$) ist ein spezieller stochastischer Prozess in der Wahrscheinlichkeitstheorie und das einfachste Beispiel einer Irrfahrt. Anschaulich ist eine symmetrische einfache Irrfahrt ein stochastischer Prozess, der bei 0 startet und dann mit jedem neuen Zeitschritt von seiner aktuellen Position entweder auf die nächstgrößere oder die nächstkleinere ganze Zahl springt. Dabei ist die Wahrscheinlichkeit, nach oben oder nach unten zu springen, gleich groß, also $\textstyle {\frac {1}{2}}$.

Die symmetrische einfache Irrfahrt ist einerseits ein Standardbeispiel der Theorie stochastischer Prozesse, da sie einfach zu behandeln ist und einige typische Phänomene aufweist, andererseits modelliert sie auch ein einfaches Spielsystem. Durch Anpassung der einfachen symmetrischen Irrfahrt lassen sich darauf aufbauend komplexere Spielverläufe bis hin zum Cox-Ross-Rubinstein-Modell konstruieren und untersuchen.

Zugrunde liegende Idee

Der symmetrischen einfachen Irrfahrt liegt die Idee eines Spiels mit einer Münze zugrunde. Die Münze ist als fair angenommen, zeigt also mit einer Wahrscheinlichkeit von $p={\tfrac {1}{2}}$ Kopf und mit derselben Wahrscheinlichkeit Zahl. Der Spieler wirft die Münze wiederholt. Dabei erhält der Spieler einen Punkt, wenn die Münze „Kopf“ zeigt, und verliert einen Punkt, wenn sie „Zahl“ zeigt. Zu Beginn besitzt der Spieler null Punkte. Der zeitliche Verlauf des Punktestands des Spielers ist dann die symmetrische einfache Irrfahrt. Die Bezeichnung „symmetrisch“ rührt daher, dass „Kopf“ und „Zahl“ gleich wahrscheinlich sind, der Punktestand des Spielers befindet sich daher symmetrisch verteilt um den Startpunkt.

Definition

Gegeben seien eine unabhängig und identisch verteilte Folge von Zufallsvariablen $(Y_{n})_{n\in \mathbb {N} }$, wobei

$P(Y_{n}=1)=0,5=P(Y_{n}=-1)$

ist, die $Y_{n}$ sind also Rademacher-verteilt.

Dann heißt der zeitdiskrete stochastische Prozess $X=(X_{n})_{n\in \mathbb {N} _{0}}$ mit Werten in $\mathbb {Z}$ definiert durch

$X_{0}=0$

sowie

$X_{n}=\sum _{i=1}^{n}Y_{i}$

die symmetrische einfache Irrfahrt. Äquivalent kann der Prozess auch durch die Startverteilung $P(X_{0}=0)=1$ und die Übergangswahrscheinlichkeiten

$P(X_{n+1}=i|X_{n}=j)={\begin{cases}{\tfrac {1}{2}}&{\text{ falls }}i=j+1\\{\tfrac {1}{2}}&{\text{ falls }}i=j-1,\\0&{\text{sonst}}\end{cases}}$

definiert werden.

Eigenschaften

Bei der symmetrischen einfachen Irrfahrt handelt es sich um einen zeitdiskreten stochastischen Prozess, da er die Indexmenge $T=\mathbb {N} _{0}=\{0,1,2,3,\dots \}$ besitzt. Der Prozess nimmt nur Werte in $\mathbb {Z}$ an, da er bei null startet und immer nur die Werte −1 und 1 aufsummiert.

Des Weiteren handelt es sich um einen Prozess mit stationären Zuwächsen, der unabhängige Zuwächse besitzt.

Verteilungseigenschaften

Die Wahrscheinlichkeit, dass $X_{n}$ den Wert $k\in \{-n,\dotsc ,n\}$ annimmt, ist gegeben durch

$P(X_{n}=k)={\begin{cases}{\binom {n}{(n-k)/2}}2^{-n},&{\text{wenn }}n-k{\text{ gerade ist,}}\\0,&{\text{ sonst.}}\end{cases}}$

Für $Z_{n}:={\tfrac {1}{2}}(X_{n}+n)$ gilt: $Z_{n}$ ist binomialverteilt mit den Parametern $n$ und $p={\frac {1}{2}}$.

Der Erwartungswert ist

$\operatorname {E} (X_{n})=0$

und die Varianz

$\operatorname {Var} (X_{n})=n$.

Als Markow-Kette

Die symmetrische einfache Irrfahrt ist eine Markow-Kette in diskreter Zeit mit Zustandsraum $\mathbb {Z}$. Dies folgt direkt aus der Definition mittels Übergangswahrscheinlichkeiten. Genauer ist sie eine homogene Markow-Kette (da sich die Übergangswahrscheinlichkeiten nicht ändern) und eine Markow-Kette erster Ordnung, da die Übergangswahrscheinlichkeiten nur von dem aktuellen Zustand abhängen und nicht noch von weiteren, vorher besuchten Zuständen beeinflusst werden.

Irreduzibilität

Die symmetrische einfache Irrfahrt ist eine irreduzible Markow-Kette, das heißt für zwei beliebige, vorgegebene ganze Zahlen $i,j$ ist die Wahrscheinlichkeit positiv, dass sich die Irrfahrt von $i$ nach $j$ bewegt. Wäre beispielsweise $i=2$ und $j=10$, so könnte der Prozess in 8 Zeitschritten von 10 nach 2 wandern, indem er sich achtmal nach links bewegt. Die Wahrscheinlichkeit dafür wäre $2^{-8}$ und damit positiv.

Aus der Irreduzibilität folgt direkt, dass die symmetrische einfache Irrfahrt keine absorbierenden Zustände besitzt.

Periodizität

Ebenso ist die symmetrische einfache Irrfahrt eine periodische Markow-Kette mit Periode Zwei. Verfügt man dementsprechend über die Information des Zeitpunktes, so kann man Rückschlüsse über den Aufenthalt des Prozesses ziehen. Aus dieser Sicht ist der Prozess nicht vollständig zufällig, da er sich

• zu geraden Zeitpunkten $n=0,2,4,6,\dots$ immer auf den geraden Zahlen $\{\dots ,-4,-2,0,2,4,\dots \}$ befindet.
• zu ungeraden Zeitpunkten $n=1,3,5,7\dots$ immer auf den ungeraden Zahlen $\{\dots ,-3,-1,1,3,\dots \}$ befindet.

Rückkehr zum Nullpunkt (Rekurrenz)

Die symmetrische einfache Irrfahrt ist rekurrent, kehrt also fast sicher unendlich oft zu ihrem Ausgangspunkt zurück. Eine detaillierte Herleitung findet sich im Artikel Green-Funktion (Stochastik), eine Aussage über höherdimensionale Irrfahrten trifft der Satz von Pólya.

Abwandlungen

Übergangsgraph einer einfachen begrenzten symmetrischen Irrfahrt in zwei Dimensionen. Exemplarisch sind die Übergangswahrscheinlichkeiten für die Zustände 1, 5 und 6 abgebildet.

Eine der gängigsten Abänderungen ist, die asymmetrische einfache Irrfahrt zu betrachten, also den Fall, in dem ein Sprung nach rechts nicht dieselbe Wahrscheinlichkeit besitzt wie ein Sprung nach links. Insbesondere ist die einfache Irrfahrt dann nicht mehr rekurrent.

Weitere typische Modifikationen sind das Einführen von Verweilwahrscheinlichkeiten (Änderung der Periodizität), zeitliche variable Übergangswahrscheinlichkeiten (Inhomogenität), vom Zustand abhängige Übergangswahrscheinlichkeiten oder Einführung eines Gedächtnisses (Markow-Kette höherer Ordnung).

Eine weitere klassische Verallgemeinerung ist die Formulierung der einfachen symmetrischen Irrfahrt oder einer ihrer Modifikationen in höheren Dimensionen. So ist die symmetrische einfache Irrfahrt auf $\mathbb {Z} ^{D}$ beispielsweise gut untersucht. Ebenso lassen sich symmetrische oder asymmetrische Irrfahrten auch auf endlichen oder unendlichen Graphen definieren.

Das nebenstehende Diagramm ist ein Beispiel für eine Irrfahrt in einer zweidimensionalen Welt, in welcher die Übergangswahrscheinlichkeiten vom Zustand abhängen und der Graph endlich ist.

Literatur

• Achim Klenke: Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag, Berlin Heidelberg 2013, ISBN 978-3-642-36017-6, doi:10.1007/978-3-642-36018-3. 
• David Meintrup, Stefan Schäffler: Stochastik. Theorie und Anwendungen. Springer-Verlag, Berlin Heidelberg New York 2005, ISBN 3-540-21676-6, doi:10.1007/b137972.