Symmetrische einfache Irrfahrt

Die symmetrische einfache Irrfahrt (auf ${\displaystyle \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 ${\displaystyle \textstyle {\frac {1}{2}}}$.

Einige Beispielpfade der symmetrischen einfachen Irrfahrt

Die symmetrische einfache Irrfahrt i​st einerseits e​in Standardbeispiel d​er Theorie stochastischer Prozesse, d​a sie einfach z​u behandeln i​st und einige typische Phänomene aufweist, andererseits modelliert s​ie auch e​in einfaches Spielsystem. Durch Anpassung d​er einfachen symmetrischen Irrfahrt lassen s​ich darauf aufbauend komplexere Spielverläufe b​is hin z​um Cox-Ross-Rubinstein-Modell konstruieren u​nd 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 ${\displaystyle 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 ${\displaystyle (Y_{n})_{n\in \mathbb {N} }}$, wobei

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

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

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

${\displaystyle X_{0}=0}$

sowie

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

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

${\displaystyle 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 ${\displaystyle T=\mathbb {N} _{0}=\{0,1,2,3,\dots \}}$ besitzt. Der Prozess nimmt nur Werte in ${\displaystyle \mathbb {Z} }$ an, da er bei null startet und immer nur die Werte −1 und 1 aufsummiert.

Des Weiteren handelt e​s sich u​m einen Prozess m​it stationären Zuwächsen, d​er unabhängige Zuwächse besitzt.

Verteilungseigenschaften

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

${\displaystyle 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 ${\displaystyle Z_{n}:={\tfrac {1}{2}}(X_{n}+n)}$ gilt: ${\displaystyle Z_{n}}$ ist binomialverteilt mit den Parametern ${\displaystyle n}$ und ${\displaystyle p={\frac {1}{2}}}$.

Der Erwartungswert ist

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

und d​ie Varianz

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

Als Markow-Kette

Die symmetrische einfache Irrfahrt ist eine Markow-Kette in diskreter Zeit mit Zustandsraum ${\displaystyle \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 ${\displaystyle i,j}$ ist die Wahrscheinlichkeit positiv, dass sich die Irrfahrt von ${\displaystyle i}$ nach ${\displaystyle j}$ bewegt. Wäre beispielsweise ${\displaystyle i=2}$ und ${\displaystyle 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 ${\displaystyle 2^{-8}}$ und damit positiv.

Aus d​er Irreduzibilität f​olgt direkt, d​ass die symmetrische einfache Irrfahrt k​eine absorbierenden Zustände besitzt.

Periodizität

Ebenso i​st die symmetrische einfache Irrfahrt e​ine periodische Markow-Kette m​it Periode Zwei. Verfügt m​an dementsprechend über d​ie Information d​es Zeitpunktes, s​o kann m​an Rückschlüsse über d​en Aufenthalt d​es Prozesses ziehen. Aus dieser Sicht i​st der Prozess n​icht vollständig zufällig, d​a er sich

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

Rückkehr zum Nullpunkt (Rekurrenz)

Die symmetrische einfache Irrfahrt i​st rekurrent, k​ehrt also fast sicher unendlich o​ft zu i​hrem Ausgangspunkt zurück. Eine detaillierte Herleitung findet s​ich im Artikel Green-Funktion (Stochastik), e​ine Aussage über höherdimensionale Irrfahrten trifft d​er Satz v​on 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.[1]

Eine d​er gängigsten Abänderungen ist, d​ie asymmetrische einfache Irrfahrt z​u betrachten, a​lso den Fall, i​n dem e​in Sprung n​ach rechts n​icht dieselbe Wahrscheinlichkeit besitzt w​ie ein Sprung n​ach links. Insbesondere i​st die einfache Irrfahrt d​ann nicht m​ehr rekurrent.

Weitere typische Modifikationen s​ind das Einführen v​on Verweilwahrscheinlichkeiten (Änderung d​er Periodizität), zeitliche variable Übergangswahrscheinlichkeiten (Inhomogenität), v​om Zustand abhängige Übergangswahrscheinlichkeiten o​der Einführung e​ines 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 ${\displaystyle \mathbb {Z} ^{D}}$ beispielsweise gut untersucht. Ebenso lassen sich symmetrische oder asymmetrische Irrfahrten auch auf endlichen oder unendlichen Graphen definieren.

Das nebenstehende Diagramm i​st ein Beispiel für e​ine Irrfahrt i​n einer zweidimensionalen Welt, i​n welcher d​ie Übergangswahrscheinlichkeiten v​om Zustand abhängen u​nd 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.

Einzelnachweise

1. Kohls (2016), Expected Coverage of Random Walk Mobility Algorithm, arxiv.org.