Irrfahrt (Stochastik)
Eine (zufällige oder stochastische) Irrfahrt<ref>{{#invoke:Vorlage:Literatur|f}}</ref> (auch Random Walk<ref name="Lex">{{#invoke:Vorlage:Literatur|f}}</ref>, seltener zufällige Schrittfolge<ref name="Sube-1345">Ralf Sube: Physik: N-Z, S. 1345.</ref>, Zufallsbewegung<ref name="Sube-1345" /> oder Zufallsweg<ref name="Sube-1345"/>) ist ein mathematisches Modell für eine Verkettung zufälliger Bewegungen. Es handelt sich um einen stochastischen Prozess in diskreter Zeit mit unabhängigen und identisch verteilten Zuwächsen.
Irrfahrtmodelle eignen sich für nichtdeterministische Zeitreihen, wie sie beispielsweise in der Finanzmathematik zur Modellierung von Aktienkursen verwendet werden. Mit ihrer Hilfe können auch die Wahrscheinlichkeitsverteilungen von Messwerten physikalischer Größen verstanden werden.
Der englische Begriff Random Walk geht zurück auf Karl Pearsons Aufsatz {{#invoke:Vorlage:lang|flat}} aus dem Jahr 1905.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Die deutsche Bezeichnung Irrfahrt wurde von George Pólya erstmals im Jahr 1919 in der Arbeit Wahrscheinlichkeitstheoretisches über die „Irrfahrt“ verwendet.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
Definition
Sei <math>(Z_1, Z_2, \dotsc)</math> eine Folge von unabhängigen Zufallsvariablen mit Werten in <math>\R^d</math>, die alle dieselbe Wahrscheinlichkeitsverteilung besitzen. Dann heißt der durch
- <math>X_n = x_0 + \sum_{j=1}^n Z_j, \qquad n \in \N_0</math>
definierte stochastische Prozess <math>(X_n)_{n \in \N_0}</math> eine Irrfahrt in <math>\R^d</math> oder d-dimensionale Irrfahrt.<ref>Bert Fristedt, Lawrence Gray: A modern approach to probability theory. Birkhäuser, Boston/Basel/Berlin 1997, ISBN 978-0-8176-3807-8, S. 165 ({{#if: 5D5O8xyM-kMC
| {{#if: {{#if: ||1}} {{#if: 5D5O8xyM-kMC ||1}}
| <0|&pg={{#if:|RA{{{Band}}}-}}PA165|&pg=165}}{{#if:|&q=}}#v=onepage|{{#if:|&pg=|}}{{#if:|&q=}}}}{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}|{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}}} {{#if:|{{#invoke:WLink|getEscapedTitle|{{{Linktext}}}}}|eingeschränkte Vorschau}}{{#if:|| in der Google-Buchsuche}}{{#ifeq:|US|-USA}}{{#if: 5D5O8xyM-kMC |{{#invoke: Vorlage:GoogleBook|fine |id=5D5O8xyM-kMC |errN=Parameter „BuchID“ hat falsche Länge |errC=Parameter „BuchID“ enthält ungültige Zeichen |errH=# in der „BuchID“ |errP=Parameterzuweisungen in der „BuchID“ |class=editoronly |cat={{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}} |template= Vorlage:Google Buch}}
}}
| Es darf nur genau einer der beiden Parameter „Suchbegriff“ oder „BuchID“ ausgefüllt werden. Bitte beachte die in der Vorlage:Google Buch befindliche Dokumentation und prüfe die verwendeten Parameter.{{#ifeq: 0 | 0 | }}}}
| Es muss mindestens einer der beiden Parameter „Suchbegriff“ oder „BuchID“ ausgefüllt werden. Bitte beachte die in der Vorlage:Google Buch befindliche Dokumentation und prüfe die verwendeten Parameter.{{#ifeq: 0 | 0 | }}}}{{#invoke:TemplatePar|check
|all=
|opt= Suchbegriff= BuchID= Seite= Band= SeitenID= Hervorhebung= Linktext= Land= KeinText=
|cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}}
|template= Vorlage:Google Buch
|format=
}}{{#if:|{{#if:{{#invoke:WLink|isBracketedLink|{{{Linktext}}}}}|}}}}).</ref><ref>Achim Klenke: Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag, Berlin/Heidelberg 2012, ISBN 978-3-642-36017-6, S. 445.</ref> Hierbei ist <math>x_0</math> deterministisch, häufig wird <math>x_0 = 0 \in \R^d</math> gewählt. Eine Irrfahrt ist also ein diskreter Prozess mit unabhängigen und stationären Zuwächsen.
Begrifflichkeiten
Eine Realisierung einer Irrfahrt liefert einen zufälligen Pfad. Solche Realisierungen von Irrfahrten können durch Monte-Carlo-Simulationen simuliert werden.<ref>Theory and Applications of Monte Carlo Simulations. (2013). Seite 229 Google Books</ref>
Man kann Irrfahrten analog auch in Riemannschen Mannigfaltigkeiten definieren. Bei Irrfahrten auf Graphen spricht man von Zufallspfaden.
Eine Verallgemeinerung einer Irrfahrt mit korrelierten Zuwächsen wird korrelierte Irrfahrt (engl.: correlated random walk)<ref>{{#invoke:Vorlage:Literatur|f}}</ref> genannt.
Eindimensionaler Fall
Die symmetrische einfache Irrfahrt ist ein grundlegendes Einführungsbeispiel, das auf mehrere Dimensionen erweitert und verallgemeinert werden kann; er hat aber bereits selbst zahlreiche konkrete Anwendungen.
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 <math>p >0</math> einen Schritt nach vorne und mit einer Wahrscheinlichkeit <math> 1-p >0</math> einen Schritt zurück. Seine zufällige Position nach <math>n</math> Schritten wird mit <math>X_n</math> bezeichnet, ohne Einschränkung sei seine Startposition <math>X_0=0</math>. Dann ist also <math>X_{n+1}=X_n+1</math> oder <math>X_{n+1}=X_n-1</math> für alle <math>n</math>.
Wie groß ist die Wahrscheinlichkeit <math>P(X_n = x)</math>, dass er sich genau im <math>n</math>-ten Schritt an der Stelle <math>x</math> befindet? Antwort: Der Fußgänger hat insgesamt <math>n = k+l</math> Schritte gemacht, davon <math>k</math> Schritte nach vorne und <math>l</math> Schritte zurück. Seine Position nach <math>n</math> Schritten ist also <math>X_n=k-l=k-(n-k)=2k-n</math> und die Wahrscheinlichkeit dafür lautet
- <math>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</math>,
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 <math>p = 1-p = \tfrac{1}{2}</math>. 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 <math>d_1, d_2, d_3, \ldots, d_n</math> bezeichnet werden, gilt <math>d_i = 1</math> oder <math>d_i = -1</math> für alle <math>1 \leq i \leq n</math> und
- <math>X_n = d_1 + d_2 + d_3 + \ldots + d_n = \sum_{i=1}^n d_i </math>.
Für den Erwartungswert der Schritte gilt jeweils
- <math>\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</math>.
Des Weiteren ist die Wahrscheinlichkeitsverteilung der zurückgelegten Strecke symmetrisch um <math>x=0</math>, und auch der Erwartungswert ist
- <math>\operatorname{E}(X_n) = \operatorname{E}\left(\sum_{i=1}^n d_i\right) = \sum_{i=1}^n \operatorname{E}(d_i) = 0</math>.
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: <math>\operatorname{Var}(X_n) = \operatorname{E}(X_n^2) - \operatorname{E}(X_n)^2</math>. Wegen <math>\operatorname{E}(X_n) = 0</math>, <math>\operatorname{E}(d_i) = 0</math> und <math>\operatorname{E}(d_i^2) = \operatorname{E}(1) = 1</math> für alle <math>1 \leq i \leq n</math> folgt daraus (vergleiche Gleichung von Bienayme):
- <math>\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_id_j\right) = \sum_{i=1}^n \operatorname{E}(d_i^2) + \sum_{1\leq i<j\leq n} 2\operatorname{E}(d_id_j) = \sum_{i=1}^n 1 + \sum_{1\leq i<j\leq n} 2 \cdot 0 = n</math>.
Die Standardabweichung <math> \sigma(X_n) </math> ist die Quadratwurzel aus der Varianz, also gilt <math> \sigma(X_n) = \sqrt{\operatorname{Var}(X_n)} = \sqrt{n} </math>.<ref>Franz Embacher, Universität Wien: Random Walk in einer Dimension</ref>
Rückkehr zum Start bei fester Schrittweite
Die Wahrscheinlichkeit, dass sich der Fußgänger bei einer symmetrischen Irrfahrt mit <math>p = 1-p = \tfrac{1}{2}</math> im <math>2n</math>-ten Schritt wieder am Start befindet, ist gleich der Wahrscheinlichkeit, dass der Fußgänger <math>n</math> Schritte nach vorne und <math>n</math> Schritte zurück gemacht hat:
- <math>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}}</math>.
Für große <math>n</math> ergibt sich mit der Stirlingformel der Grenzwert
- <math> \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.</math>
Der Fußgänger kehrt immer irgendwann zum Startpunkt zurück, d. h. die Summe dieser Wahrscheinlichkeiten für alle <math>n</math> ist gleich 1. Dies folgt aus der Divergenz der Reihe:<ref>The University of Chicago: Simple Random Walk</ref><ref>Elizabeth G. Ombrellaro, The University of Chicago: Random walks and the probabality of returning home</ref>
- <math>\sum_{n = 1}^\infty P(X_{2n} = 0) = \infty.</math>
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 <math>d_i</math> unabhängig sind mit dem Erwartungswert <math>\operatorname{E}(d_i)=0</math> und der Varianz <math>\operatorname{Var}(d_i)=\sigma^2</math>, gilt wegen der Linearität des Erwartungswertes für die Position <math>X_n</math> nach <math>n</math> Schritten:
- <math>\operatorname{E}(X_n) = \sum_{i=1}^n \operatorname{E}(d_i) = 0</math>
und für die Varianz wegen der Unabhängigkeit der Einzelschritte
- <math>\operatorname{Var}(X_n) = \sum_{i=1}^n \operatorname{Var}(d_i) = n \sigma^2.</math>
Der Erwartungswert <math>\operatorname{E}(X_n)</math> und die Varianz <math>\operatorname{Var}(X_n)</math> hängen nicht von der Verteilung der Schritte <math>d_i</math> ab.
Die nebenstehende Abbildung zeigt beispielsweise fünf Simulationen für <math>n=300</math> Schritte mit einer Schrittlänge, die im Intervall <math>[-0{,}5;0{,}5]</math> gleichverteilt ist. In diesem Fall beträgt die Standardabweichung für jeden Schritt <math> \sigma= \tfrac{1}{\sqrt{12}} \approx 0{,}28868 </math>. Der Erwartungswert der Endposition einer derartigen Zufallsbewegung nach <math>n</math> Schritten ist 0, und die Standardabweichung der Endposition beträgt <math>\sqrt{n} \cdot \sigma =\sqrt{n/12}</math>. Die Standardabweichung ist als rote Linie ober- und unterhalb des Erwartungswertes eingezeichnet.
Abstand von der Startposition
Um den Erwartungswert des Betrags <math>|X_n|</math> des Abstands von der Startposition zu berechnen, wird die Verteilung von <math>X_n</math> benötigt. Die standardisierte Zufallsvariable
- <math>Y_n = \frac{X_n}{\sqrt{n} \, \sigma}</math>
hat den Erwartungswert <math>0</math> und die Varianz <math>1</math>. Wenn die Einzelschritte unabhängig sind und dieselbe Wahrscheinlichkeitsverteilung besitzen, konvergiert die Verteilungsfunktion von <math>Y_n</math> nach dem zentralen Grenzwertsatz für <math>n \to \infty</math> punktweise gegen die Standardnormalverteilung. Mit deren Dichtefunktion <math>f(x)</math> ergibt sich folgender Erwartungswert:
- <math>\lim_{n\to\infty} \operatorname{E}(|Y_n|) = \int_{-\infty}^{\infty} |x| f(x) \,\mathrm dx = 2 \int_0^{\infty} x f(x) \,\mathrm dx = 2 \int_0^{\infty} x \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}x^2} \,\mathrm dx = \sqrt{\frac{2}{\pi}} \int_0^{\infty} x e^{-\frac{1}{2}x^2} \,\mathrm dx = \sqrt{\frac{2}{\pi}} \left[ -e^{-\frac{1}{2}x^2} \right]_0^{\infty} = \sqrt{\frac{2}{\pi}} .</math>
Damit erhält man für große <math>n</math> als Näherung für den Erwartungswert des Abstandes von der Startposition<ref>Vgl. für feste Strittweite: {{#if: | {{{author}}} | Eric W. Weisstein }}: Random Walk-1-Dimensional. In: MathWorld (englisch). {{#if: RandomWalk1-Dimensional | {{#ifeq: {{#property:P2812}} | RandomWalk1-Dimensional | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref>
- <math>\operatorname{E}(|X_n|) = \sqrt{n} \, \sigma \, \operatorname{E}(|Y_n|) \approx \sqrt{\frac{2n}{\pi}} \, \sigma.</math>
Ungleichungen für die eindimensionale Irrfahrt
Es sei <math>\sum_{k=a}^{b-1} P(0,k)</math> die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall <math>[a, b-1]</math> am Ausgangspunkt befindet. Dann existieren zwei Konstanten <math>c_1</math> und <math>c_2</math>, sodass für genügend große <math>a</math> und <math>b</math> mit <math>0 < a < b</math> folgende Ungleichung gilt:<ref name=":0">Itai Benjamini, Robin Pemantle, Yuval Peres, University of Pennsylvania: RANDOM WALKS IN VARYING DIMENSIONS</ref>
- <math>c_1\sqrt\frac{b-a}{b} \leq \sum_{k=a}^{b-1} P(0,k) \leq c_2\sqrt\frac{b-a}{b}</math>
Allgemeiner Fall
Ungleichungen für die zweidimensionale Irrfahrt
Es sei <math>\sum_{k=a}^{b-1} P(0,k)</math> die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall <math>[a, b-1]</math> am Ausgangspunkt befindet. Dann existiert eine Konstante <math>c_1</math>, sodass für genügend große <math>a</math> und <math>b</math> mit <math>0 < a < b</math> folgende Ungleichung gilt:
- <math>c_1\frac{\log\left(\frac{b}{a}\right)}{\log(b)} \leq \sum_{k=a}^{b-1} P(0,k)</math>
Außerdem existiert eine Konstante <math>c_2</math>, sodass für genügend große <math>a</math> und <math>b</math> mit <math>0 < 2a < b</math> folgende Ungleichung gilt:<ref name=":0" />
- <math>\sum_{k=a}^{b-1} P(0,k) \leq c_2\frac{\log\left(\frac{b}{a}\right)}{\log(b)}</math>
Satz von Pólya
| Dimension <math> D </math> | | Eric W. Weisstein }}: Pólya's Random Walk Constants. In: MathWorld (englisch). {{#if: PolyasRandomWalkConstants | {{#ifeq: {{#property:P2812}} | PolyasRandomWalkConstants | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref> |
|---|---|
| 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 <math>x</math> 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 <math> P(x):= P (\{ \text{ Es gibt ein } n \geq 1 \; \text{ so dass } X_n=x \} \; | \; X_0=x) </math>, dann gilt:
- Für <math> D =1 </math> und <math> D=2 </math> ist <math> X^D </math> rekurrent, es ist also <math> P(x)=1 </math> für alle <math> x </math>. Die symmetrische einfache Irrfahrt kehrt also fast sicher zu ihrem Startpunkt zurück und tut dies damit auch unendlich oft.
- Für <math> D \geq 3 </math> ist <math> X^D </math> transient, es ist also <math> P(x)< 1 </math> für alle <math> x </math>. Somit kehrt die symmetrische einfache Irrfahrt fast sicher nur endlich oft zu ihrem Startpunkt zurück.<ref name=":1" />
Anwendungen
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.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Ein weiterer Anwendungsbereich ist die Modellierung von Finanzmarktzeitreihen unter der Annahme, dass eine der Irrfahrt-Hypothesen zulässig ist.<ref name="Lex" />
Anwendung in der Physik
Die Eigenschaft <math>\mathrm{Var}(X_n) = n</math> für <math>n \in \N</math> einer Irrfahrt <math>(X_n)_{n\in \N_0}</math> 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.
Anwendung in der statistischen Mechanik
{{#if: statistische Mechanik|{{#ifexist:statistische Mechanik|
|{{#if: |{{#ifexist:{{{2}}}|
|{{#if: |{{#ifexist:{{{3}}}|
|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}
Ist <math>P(x,t)</math> die Wahrscheinlichkeit, das Teilchen an der Stelle <math>x</math> zum Zeitpunkt <math>t</math> zu finden und <math>\Gamma</math> die Anzahl der Schritte pro Zeitintervall. Die zeitliche Entwicklung von <math>P(x,t)</math> kann wie folgt beschrieben werden: Es ergibt sich ein Zuwachs der Wahrscheinlichkeit durch Schritte, die mit der Wahrscheinlichkeit <math>w(x_1 \rightarrow\ x_2)</math> für ein Schritt von <math>x_1</math> nach <math>x_2</math> vorkommen, von einem der benachbarten Orte <math>x_1 + 1</math> und <math>x_1 - 1</math> und einen Abfluss durch Schritte vom Ort <math>x_1</math> zu einem der Nachbarn <math>x_1 + 1</math> und <math>x_1 - 1</math>. Daraus ergibt sich die Mastergleichung
- <math>{\partial \over \partial t}P(x,t) = P(x+1,t) W(x+1 \rightarrow\ x) + P(x-1,t) W(x-1 \rightarrow\ x) - P(x,t) W(x \rightarrow\ x+1) - P(x,t) W(x \rightarrow\ x-1)</math>
wobei <math>W(x \rightarrow\ x+1) = W(x \rightarrow\ x-1) = W(x+1 \rightarrow\ x) = W(x-1 \rightarrow\ x) = \frac{\Gamma}{2}</math>.<ref>Prof. Heermann, Universität Heidelberg: Ein Beispiel: Der Random Walk</ref>
Siehe auch
- Gaußkette
- PageRank
- Anomale Diffusion
- Irrfahrten mit selbstmeidenden Pfaden
- Satz von Donsker
Literatur
- Rick Durrett: Probability: Theory and Examples. 4. Auflage. Cambridge University Press, Cambridge u. a. 2010, ISBN 978-0-521-76539-8, Kapitel 4. Random Walks.
- Norbert Henze: Irrfahrten und verwandte Zufälle. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-01850-4.
- Barry D. Hughes: Random Walks and Random Environments: Volume 1: Random Walks. Oxford University Press, USA 1995, ISBN 0-19-853788-3.
- {{#invoke:Vorlage:Literatur|f}}
- Frank Spitzer: Principles of Random Walk. 2. Auflage. Springer-Verlag, New York u. a. 1976, ISBN 0-387-95154-7.
Einzelnachweise
<references />