Irrfahrt (Stochastik)

Feste Schrittweite

Bei der eindimensionalen Irrfahrt mit fester Schrittweite bilden die einzelnen Schritte einen Bernoulli-Prozess, das heißt, eine Folge von unabhängigen Bernoulli-Versuchen.

Eine beliebte Veranschaulichung lautet wie folgt (siehe auch Drunkard’s Walk): Ein desorientierter Fußgänger läuft in einer Gasse mit einer Wahrscheinlichkeit ${\displaystyle p>0}$ einen Schritt nach vorne und mit einer Wahrscheinlichkeit ${\displaystyle 1-p>0}$ einen Schritt zurück. Seine zufällige Position nach ${\displaystyle n}$ Schritten wird mit ${\displaystyle X_{n}}$ bezeichnet, ohne Einschränkung sei seine Startposition ${\displaystyle X_{0}=0}$. Dann ist also ${\displaystyle X_{n+1}=X_{n}+1}$ oder ${\displaystyle X_{n+1}=X_{n}-1}$ für alle ${\displaystyle n}$.

Wie groß ist die Wahrscheinlichkeit ${\displaystyle P(X_{n}=x)}$, dass er sich genau im ${\displaystyle n}$-ten Schritt an der Stelle ${\displaystyle x}$ befindet? Antwort: Der Fußgänger hat insgesamt ${\displaystyle n=k+l}$ Schritte gemacht, davon ${\displaystyle k}$ Schritte nach vorne und ${\displaystyle l}$ Schritte zurück. Seine Position nach ${\displaystyle n}$ Schritten ist also ${\displaystyle X_{n}=k-l=k-(n-k)=2k-n}$ und die Wahrscheinlichkeit dafür lautet

${\displaystyle P(X_{n}=k-l)=P(X_{n}=2k-n)={n \choose k}p^{k}(1-p)^{n-k}={k+l \choose k}p^{k}(1-p)^{l}}$,

denn die Anzahl der Schritte nach vorne folgt einer Binomialverteilung.

Symmetrische Irrfahrt mit fester Schrittweite

Oft interessiert man sich speziell für die ungerichtete oder symmetrische Irrfahrt mit ${\displaystyle p=1-p={\tfrac {1}{2}}}$. Dies ist auch die einzige Parameterwahl, die zu einer rekurrenten Markow-Kette führt, das heißt, dass der Läufer unendlich oft zum Ursprung zurückkehrt. Die aufsummierten Zufallsvariablen sind dann alle Rademacher-verteilt.

Wenn die Schritte mit ${\displaystyle d_{1},d_{2},d_{3},\ldots ,d_{n}}$ bezeichnet werden, gilt ${\displaystyle d_{i}=1}$ oder ${\displaystyle d_{i}=-1}$ für alle ${\displaystyle 1\leq i\leq n}$ und

${\displaystyle X_{n}=d_{1}+d_{2}+d_{3}+\ldots +d_{n}=\sum _{i=1}^{n}d_{i}}$.

Für den Erwartungswert der Schritte gilt jeweils

${\displaystyle \operatorname {E} (d_{i})=1\cdot p+(-1)\cdot (1-p)=1\cdot {\tfrac {1}{2}}+(-1)\cdot \left(1-{\tfrac {1}{2}}\right)=0}$.

Des Weiteren ist die Wahrscheinlichkeitsverteilung der zurückgelegten Strecke symmetrisch um ${\displaystyle x=0}$, und auch der Erwartungswert ist

${\displaystyle \operatorname {E} (X_{n})=\operatorname {E} \left(\sum _{i=1}^{n}d_{i}\right)=\sum _{i=1}^{n}\operatorname {E} (d_{i})=0}$.

Das mittlere Vorankommen des Fußgängers kann man dann nur durch den mittleren quadratischen Abstand vom Ausgangspunkt, also durch die Varianz der Binomialverteilung beschreiben: ${\displaystyle \operatorname {Var} (X_{n})=\operatorname {E} (X_{n}^{2})-\operatorname {E} (X_{n})^{2}}$. Wegen ${\displaystyle \operatorname {E} (X_{n})=0}$, ${\displaystyle \operatorname {E} (d_{i})=0}$ und ${\displaystyle \operatorname {E} (d_{i}^{2})=\operatorname {E} (1)=1}$ für alle ${\displaystyle 1\leq i\leq n}$ folgt daraus (vergleiche Gleichung von Bienayme):

${\displaystyle \operatorname {Var} (X_{n})=\operatorname {E} (X_{n}^{2})=\operatorname {E} \left(\left(\sum _{i=1}^{n}d_{i}\right)^{2}\right)=\operatorname {E} \left(\sum _{i=1}^{n}d_{i}^{2}+2\sum _{1\leq i<j\leq n}d_{i}d_{j}\right)=\sum _{i=1}^{n}\operatorname {E} (d_{i}^{2})+\sum _{1\leq i<j\leq n}2\operatorname {E} (d_{i}d_{j})=\sum _{i=1}^{n}1+\sum _{1\leq i<j\leq n}2\cdot 0=n}$.

Die Standardabweichung ${\displaystyle \sigma (X_{n})}$ ist die Quadratwurzel aus der Varianz, also gilt ${\displaystyle \sigma (X_{n})={\sqrt {\operatorname {Var} (X_{n})}}={\sqrt {n}}}$.

Rückkehr zum Start bei fester Schrittweite

Die Wahrscheinlichkeit, dass sich der Fußgänger bei einer symmetrischen Irrfahrt mit ${\displaystyle p=1-p={\tfrac {1}{2}}}$ im ${\displaystyle 2n}$-ten Schritt wieder am Start befindet, ist gleich der Wahrscheinlichkeit, dass der Fußgänger ${\displaystyle n}$ Schritte nach vorne und ${\displaystyle n}$ Schritte zurück gemacht hat:

${\displaystyle P(X_{2n}=n-n)=P(X_{2n}=0)={2n \choose n}\left({\tfrac {1}{2}}\right)^{n}\left(1-{\tfrac {1}{2}}\right)^{2n-n}={2n \choose n}\cdot {\frac {1}{2^{2n}}}={\frac {(2n)!}{(n!)^{2}\cdot 2^{2n}}}}$.

Für große ${\displaystyle n}$ ergibt sich mit der Stirlingformel der Grenzwert

${\displaystyle \lim _{n\to \infty }P(X_{2n}=0)=\lim _{n\to \infty }{\frac {(2n)!}{(n!)^{2}\cdot 2^{2n}}}=\lim _{n\to \infty }{\frac {{\sqrt {2\pi \cdot 2n}}\;\left({\frac {2n}{\mathcal {e}}}\right)^{2n}}{\left({\sqrt {2\pi n}}\;\left({\frac {n}{\mathcal {e}}}\right)^{n}\right)^{2}\cdot 2^{2n}}}=\lim _{n\to \infty }{\frac {2{\sqrt {\pi n}}\;\left({\frac {2n}{\mathcal {e}}}\right)^{2n}}{{2\pi n}\;\left({\frac {n}{\mathcal {e}}}\right)^{2n}\cdot 2^{2n}}}=\lim _{n\to \infty }{\frac {1}{\sqrt {\pi n}}}=0.}$

Der Fußgänger kehrt immer irgendwann zum Startpunkt zurück, d. h. die Summe dieser Wahrscheinlichkeiten für alle ${\displaystyle n}$ ist gleich 1. Dies folgt aus der Divergenz der Reihe:

${\displaystyle \sum _{n=1}^{\infty }P(X_{2n}=0)=\infty .}$

Verallgemeinerung mit zufälliger Schrittweite

Eine erste Verallgemeinerung besteht darin, dass bei jedem Schritt eine zufällige Schrittlänge zugelassen ist. Wenn die einzelnen Schritte ${\displaystyle d_{i}}$ unabhängig sind mit dem Erwartungswert ${\displaystyle \operatorname {E} (d_{i})=0}$ und der Varianz ${\displaystyle \operatorname {Var} (d_{i})=\sigma ^{2}}$, gilt wegen der Linearität des Erwartungswertes für die Position ${\displaystyle X_{n}}$ nach ${\displaystyle n}$ Schritten:

${\displaystyle \operatorname {E} (X_{n})=\sum _{i=1}^{n}\operatorname {E} (d_{i})=0}$

und für die Varianz wegen der Unabhängigkeit der Einzelschritte

${\displaystyle \operatorname {Var} (X_{n})=\sum _{i=1}^{n}\operatorname {Var} (d_{i})=n\sigma ^{2}.}$

Der Erwartungswert ${\displaystyle \operatorname {E} (X_{n})}$ und die Varianz ${\displaystyle \operatorname {Var} (X_{n})}$ hängen nicht von der Verteilung der Schritte ${\displaystyle d_{i}}$ ab.

Die nebenstehende Abbildung zeigt beispielsweise fünf Simulationen für ${\displaystyle n=300}$ Schritte mit einer Schrittlänge, die im Intervall ${\displaystyle [-0{,}5;0{,}5]}$ gleichverteilt ist. In diesem Fall beträgt die Standardabweichung für jeden Schritt ${\displaystyle \sigma ={\tfrac {1}{\sqrt {12}}}\approx 0{,}28868}$. Der Erwartungswert der Endposition einer derartigen Zufallsbewegung nach ${\displaystyle n}$ Schritten ist 0, und die Standardabweichung der Endposition beträgt ${\displaystyle {\sqrt {n}}\cdot \sigma ={\sqrt {n/12}}}$. Die Standardabweichung ist als rote Linie ober- und unterhalb des Erwartungswertes eingezeichnet.

Abstand von der Startposition

Um den Erwartungswert des Betrags ${\displaystyle |X_{n}|}$ des Abstands von der Startposition zu berechnen, wird die Verteilung von ${\displaystyle X_{n}}$ benötigt. Die standardisierte Zufallsvariable

${\displaystyle Y_{n}={\frac {X_{n}}{{\sqrt {n}}\,\sigma }}}$

hat den Erwartungswert ${\displaystyle 0}$ und die Varianz ${\displaystyle 1}$. Wenn die Einzelschritte unabhängig sind und dieselbe Wahrscheinlichkeitsverteilung besitzen, konvergiert die Verteilungsfunktion von ${\displaystyle Y_{n}}$ nach dem zentralen Grenzwertsatz für ${\displaystyle n\to \infty }$ punktweise gegen die Standardnormalverteilung. Mit deren Dichtefunktion ${\displaystyle f(x)}$ ergibt sich folgender Erwartungswert:

${\displaystyle \lim _{n\to \infty }\operatorname {E} (|Y_{n}|)=\int _{-\infty }^{\infty }|x|f(x)\,\mathrm {d} x=2\int _{0}^{\infty }xf(x)\,\mathrm {d} x=2\int _{0}^{\infty }x{\frac {1}{\sqrt {2\pi }}}e^{-{\frac {1}{2}}x^{2}}\,\mathrm {d} x={\sqrt {\frac {2}{\pi }}}\int _{0}^{\infty }xe^{-{\frac {1}{2}}x^{2}}\,\mathrm {d} x={\sqrt {\frac {2}{\pi }}}\left[-e^{-{\frac {1}{2}}x^{2}}\right]_{0}^{\infty }={\sqrt {\frac {2}{\pi }}}.}$

Damit erhält man für große ${\displaystyle n}$ als Näherung für den Erwartungswert des Abstandes von der Startposition

${\displaystyle \operatorname {E} (|X_{n}|)={\sqrt {n}}\,\sigma \,\operatorname {E} (|Y_{n}|)\approx {\sqrt {\frac {2n}{\pi }}}\,\sigma .}$

Ungleichungen für die eindimensionale Irrfahrt

Es sei ${\displaystyle \sum _{k=a}^{b-1}P(0,k)}$ die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall ${\displaystyle [a,b-1]}$ am Ausgangspunkt befindet. Dann existieren zwei Konstanten ${\displaystyle c_{1}}$ und ${\displaystyle c_{2}}$, sodass für genügend große ${\displaystyle a}$ und ${\displaystyle b}$ mit ${\displaystyle 0<a<b}$ folgende Ungleichung gilt:

${\displaystyle c_{1}{\sqrt {\frac {b-a}{b}}}\leq \sum _{k=a}^{b-1}P(0,k)\leq c_{2}{\sqrt {\frac {b-a}{b}}}}$

Ungleichungen für die zweidimensionale Irrfahrt

Es sei ${\displaystyle \sum _{k=a}^{b-1}P(0,k)}$ die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall ${\displaystyle [a,b-1]}$ am Ausgangspunkt befindet. Dann existiert eine Konstante ${\displaystyle c_{1}}$, sodass für genügend große ${\displaystyle a}$ und ${\displaystyle b}$ mit ${\displaystyle 0<a<b}$ folgende Ungleichung gilt:

${\displaystyle c_{1}{\frac {\log \left({\frac {b}{a}}\right)}{\log(b)}}\leq \sum _{k=a}^{b-1}P(0,k)}$

Außerdem existiert eine Konstante ${\displaystyle c_{2}}$, sodass für genügend große ${\displaystyle a}$ und ${\displaystyle b}$ mit ${\displaystyle 0<2a<b}$ folgende Ungleichung gilt:

${\displaystyle \sum _{k=a}^{b-1}P(0,k)\leq c_{2}{\frac {\log \left({\frac {b}{a}}\right)}{\log(b)}}}$

Satz von Pólya

Dimension ${\displaystyle D}$	Rückkehrwahrscheinlichkeit zum Start
1	1
2	1
3	0.340537
4	0.193206
5	0.135178
6	0.104715
7	0.0858449
8	0.0729126

Nach dem Satz von Pólya ist die Rückkehrwahrscheinlichkeit zum Start für einen vorgegebenen Startpunkt ${\displaystyle x}$ für 1 Dimension und für 2 Dimensionen gleich 1 und für 3 oder mehr Dimensionen kleiner als 1. Ist die Wahrscheinlichkeit für eine Rückkehr zum Startpunkt eines Gitters mit D Dimensionen definiert als ${\displaystyle P(x):=P(\{{\text{ Es gibt ein }}n\geq 1\;{\text{ so dass }}X_{n}=x\}\;|\;X_{0}=x)}$, dann gilt:

• Für ${\displaystyle D=1}$ und ${\displaystyle D=2}$ ist ${\displaystyle X^{D}}$ rekurrent, es ist also ${\displaystyle P(x)=1}$ für alle ${\displaystyle x}$. Die symmetrische einfache Irrfahrt kehrt also fast sicher zu ihrem Startpunkt zurück und tut dies damit auch unendlich oft.
• Für ${\displaystyle D\geq 3}$ ist ${\displaystyle X^{D}}$ transient, es ist also ${\displaystyle P(x)<1}$ für alle ${\displaystyle x}$. Somit kehrt die symmetrische einfache Irrfahrt fast sicher nur endlich oft zu ihrem Startpunkt zurück.

Anwendung in der Wahrscheinlichkeitstheorie

Irrfahrten sind ein Objekt der Wahrscheinlichkeitstheorie, deren Eigenschaften bei den Gesetzen der großen Zahlen, dem zentralen Grenzwertsatz, dem Gesetz vom iterierten Logarithmus und den Null-Eins-Gesetzen verwendet werden. Sie finden beispielsweise Anwendung in der Bedienungstheorie und der Erneuerungstheorie. Ein weiterer Anwendungsbereich ist die Modellierung von Finanzmarktzeitreihen unter der Annahme, dass eine der Irrfahrt-Hypothesen zulässig ist.

Anwendung in der Physik

Die Eigenschaft ${\displaystyle \mathrm {Var} (X_{n})=n}$ für ${\displaystyle n\in \mathbb {N} }$ einer Irrfahrt ${\displaystyle (X_{n})_{n\in \mathbb {N} _{0}}}$ ist ein wichtiges Ergebnis, mit dem eine charakteristische Eigenschaft von Diffusionsprozessen und brownscher Molekularbewegung wiedergefunden wird: Das mittlere Quadrat des Abstands eines diffundierenden Teilchens von seinem Ausgangsort wächst proportional zur Zeit.