Irrfahrt (Stochastik)

mathematisches Modell für eine Bewegung, bei der die einzelnen Schritte zufällig erfolgen
(Weitergeleitet von Random walk)

Eine (zufällige oder stochastische) Irrfahrt[1] (auch Random Walk[2], seltener zufällige Schrittfolge[3], Zufallsbewegung[3] oder Zufallsweg[3]) 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.

Simulation einer zweidimensionalen Irrfahrt mit 229 Schritten und einer zufälligen Schrittweite aus dem Intervall [−0,5;0,5] für x- und y-Richtung
Zweidimensionale symmetrische Irrfahrt mit 25000 Schritten

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 The Problem of the Random Walk aus dem Jahr 1905.[4] Die deutsche Bezeichnung Irrfahrt wurde von George Pólya erstmals im Jahr 1919 in der Arbeit Wahrscheinlichkeitstheoretisches über die „Irrfahrt“ verwendet.[5]

Definition

Bearbeiten

Sei   eine Folge von unabhängigen Zufallsvariablen mit Werten in  , die alle dieselbe Wahrscheinlichkeitsverteilung besitzen. Dann heißt der durch

 

definierte stochastische Prozess   eine Irrfahrt in   oder d-dimensionale Irrfahrt.[6][7] Hierbei ist   deterministisch, häufig wird   gewählt. Eine Irrfahrt ist also ein diskreter Prozess mit unabhängigen und stationären Zuwächsen.

Begrifflichkeiten

Bearbeiten

Eine Realisierung einer Irrfahrt liefert einen zufälligen Pfad. Solche Realisierungen von Irrfahrten können durch Monte-Carlo-Simulationen simuliert werden.[8]

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)[9] genannt.

Eindimensionaler Fall

Bearbeiten
 
Übergangsgraph der eindimensionalen symmetrischen Irrfahrt
 
Acht Realisierungen (Zufallspfade) einer einfachen eindimensionalen Irrfahrt mit Start in 0. Die Grafik zeigt die aktuelle Position in Abhängigkeit von der Nummer des Schrittes.

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

Bearbeiten

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   einen Schritt nach vorne und mit einer Wahrscheinlichkeit   einen Schritt zurück. Seine zufällige Position nach   Schritten wird mit   bezeichnet, ohne Einschränkung sei seine Startposition  . Dann ist also   oder   für alle  .

Wie groß ist die Wahrscheinlichkeit  , dass er sich genau im  -ten Schritt an der Stelle   befindet? Antwort: Der Fußgänger hat insgesamt   Schritte gemacht, davon   Schritte nach vorne und   Schritte zurück. Seine Position nach   Schritten ist also   und die Wahrscheinlichkeit dafür lautet

 ,

denn die Anzahl der Schritte nach vorne folgt einer Binomialverteilung.

Symmetrische Irrfahrt mit fester Schrittweite

Bearbeiten

Oft interessiert man sich speziell für die ungerichtete oder symmetrische Irrfahrt mit  . 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   bezeichnet werden, gilt   oder   für alle   und

 .

Für den Erwartungswert der Schritte gilt jeweils

 .

Des Weiteren ist die Wahrscheinlichkeitsverteilung der zurückgelegten Strecke symmetrisch um  , und auch der Erwartungswert ist

 .

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:  . Wegen  ,   und   für alle   folgt daraus (vergleiche Gleichung von Bienayme):

 .

Die Standardabweichung   ist die Quadratwurzel aus der Varianz, also gilt  .[10]

Rückkehr zum Start bei fester Schrittweite

Bearbeiten

Die Wahrscheinlichkeit, dass sich der Fußgänger bei einer symmetrischen Irrfahrt mit   im  -ten Schritt wieder am Start befindet, ist gleich der Wahrscheinlichkeit, dass der Fußgänger   Schritte nach vorne und   Schritte zurück gemacht hat:

 .

Für große   ergibt sich mit der Stirlingformel der Grenzwert

 

Der Fußgänger kehrt immer irgendwann zum Startpunkt zurück, d. h. die Summe dieser Wahrscheinlichkeiten für alle   ist gleich 1. Dies folgt aus der Divergenz der Reihe:[11][12]

 

Verallgemeinerung mit zufälliger Schrittweite

Bearbeiten
 
Fünf Pfade einer eindimensionalen Irrfahrt mit zufälliger Schrittlänge, die im Intervall [-1/2,1/2] gleichverteilt ist

Eine erste Verallgemeinerung besteht darin, dass bei jedem Schritt eine zufällige Schrittlänge zugelassen ist. Wenn die einzelnen Schritte   unabhängig sind mit dem Erwartungswert   und der Varianz  , gilt wegen der Linearität des Erwartungswertes für die Position   nach   Schritten:

 

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

 

Der Erwartungswert   und die Varianz   hängen nicht von der Verteilung der Schritte   ab.

Die nebenstehende Abbildung zeigt beispielsweise fünf Simulationen für   Schritte mit einer Schrittlänge, die im Intervall   gleichverteilt ist. In diesem Fall beträgt die Standardabweichung für jeden Schritt  . Der Erwartungswert der Endposition einer derartigen Zufallsbewegung nach   Schritten ist 0, und die Standardabweichung der Endposition beträgt  . Die Standardabweichung ist als rote Linie ober- und unterhalb des Erwartungswertes eingezeichnet.

Abstand von der Startposition

Bearbeiten

Um den Erwartungswert des Betrags   des Abstands von der Startposition zu berechnen, wird die Verteilung von   benötigt. Die standardisierte Zufallsvariable

 

hat den Erwartungswert   und die Varianz  . Wenn die Einzelschritte unabhängig sind und dieselbe Wahrscheinlichkeitsverteilung besitzen, konvergiert die Verteilungsfunktion von   nach dem zentralen Grenzwertsatz für   punktweise gegen die Standardnormalverteilung. Mit deren Dichtefunktion   ergibt sich folgender Erwartungswert:

 

Damit erhält man für große   als Näherung für den Erwartungswert des Abstandes von der Startposition[13]

 

Ungleichungen für die eindimensionale Irrfahrt

Bearbeiten

Es sei   die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall   am Ausgangspunkt befindet. Dann existieren zwei Konstanten   und  , sodass für genügend große   und   mit   folgende Ungleichung gilt:[14]

 

Allgemeiner Fall

Bearbeiten

Ungleichungen für die zweidimensionale Irrfahrt

Bearbeiten

Es sei   die Wahrscheinlichkeit, dass sich das Teilchen im Zeitintervall   am Ausgangspunkt befindet. Dann existiert eine Konstante  , sodass für genügend große   und   mit   folgende Ungleichung gilt:

 

Außerdem existiert eine Konstante  , sodass für genügend große   und   mit   folgende Ungleichung gilt:[14]

 

Satz von Pólya

Bearbeiten
Dimension   Rückkehrwahrscheinlichkeit zum Start[15]
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   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  , dann gilt:

  • Für   und   ist   rekurrent, es ist also   für alle  . Die symmetrische einfache Irrfahrt kehrt also fast sicher zu ihrem Startpunkt zurück und tut dies damit auch unendlich oft.
  • Für   ist   transient, es ist also   für alle  . Somit kehrt die symmetrische einfache Irrfahrt fast sicher nur endlich oft zu ihrem Startpunkt zurück.[15]

Anwendungen

Bearbeiten

Anwendung in der Wahrscheinlichkeitstheorie

Bearbeiten

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.[16] Ein weiterer Anwendungsbereich ist die Modellierung von Finanzmarktzeitreihen unter der Annahme, dass eine der Irrfahrt-Hypothesen zulässig ist.[2]

Anwendung in der Physik

Bearbeiten

Die Eigenschaft   für   einer Irrfahrt   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

Bearbeiten

Ist   die Wahrscheinlichkeit, das Teilchen an der Stelle   zum Zeitpunkt   zu finden und   die Anzahl der Schritte pro Zeitintervall. Die zeitliche Entwicklung von   kann wie folgt beschrieben werden: Es ergibt sich ein Zuwachs der Wahrscheinlichkeit durch Schritte, die mit der Wahrscheinlichkeit   für ein Schritt von   nach   vorkommen, von einem der benachbarten Orte   und   und einen Abfluss durch Schritte vom Ort   zu einem der Nachbarn   und  . Daraus ergibt sich die Mastergleichung

 

wobei  .[17]

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • 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.
  • P. H. Müller (Hrsg.): Lexikon der Stochastik – Wahrscheinlichkeitsrechnung und mathematische Statistik. 5. Auflage. Akademie-Verlag, Berlin 1991, ISBN 978-3-05-500608-1, Irrfahrt (random walk), S. 174–176.
  • Frank Spitzer: Principles of Random Walk. 2. Auflage. Springer-Verlag, New York u. a. 1976, ISBN 0-387-95154-7.

Einzelnachweise

Bearbeiten
  1. P. H. Müller (Hrsg.): Lexikon der Stochastik – Wahrscheinlichkeitsrechnung und mathematische Statistik. 5. Auflage. Akademie-Verlag, Berlin 1991, ISBN 978-3-05-500608-1, Irrfahrt (random walk), S. 174–176.
  2. a b Horst Rinne: Taschenbuch der Statistik. 4. Auflage. Harri Deutsch, Frankfurt am Main 2008, ISBN 978-3-8171-1827-4, S. 408–410.
  3. a b c Ralf Sube: Physik: N-Z, S. 1345.
  4. Karl Pearson: The Problem of the Random Walk. In: Nature. Band 72, Nr. 1865, Juli 1905, S. 294, doi:10.1038/072294b0.
  5. Georg Pólya: Wahrscheinlichkeitstheoretisches über die „Irrfahrt“. In: Mitteilungen der Physikalischen Gesellschaft Zürich. Band 19, 1919, S. 75–86.
  6. Bert Fristedt, Lawrence Gray: A modern approach to probability theory. Birkhäuser, Boston/Basel/Berlin 1997, ISBN 978-0-8176-3807-8, S. 165 (eingeschränkte Vorschau in der Google-Buchsuche).
  7. Achim Klenke: Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag, Berlin/Heidelberg 2012, ISBN 978-3-642-36017-6, S. 445.
  8. Theory and Applications of Monte Carlo Simulations. (2013). Seite 229 Google Books
  9. Eric Renshaw, Robin Henderson: The Correlated Random Walk. In: Journal of Applied Probability. Band 18, Nr. 2, S. 403–414, doi:10.2307/3213286.
  10. Franz Embacher, Universität Wien: Random Walk in einer Dimension
  11. The University of Chicago: Simple Random Walk
  12. Elizabeth G. Ombrellaro, The University of Chicago: Random walks and the probabality of returning home
  13. Vgl. für feste Strittweite: Eric W. Weisstein: Random Walk-1-Dimensional. In: MathWorld (englisch).
  14. a b Itai Benjamini, Robin Pemantle, Yuval Peres, University of Pennsylvania: RANDOM WALKS IN VARYING DIMENSIONS
  15. a b Eric W. Weisstein: Pólya's Random Walk Constants. In: MathWorld (englisch).
  16. P. H. Müller (Hrsg.): Lexikon der Stochastik – Wahrscheinlichkeitsrechnung und mathematische Statistik. 5. Auflage. Akademie-Verlag, Berlin 1991, ISBN 978-3-05-500608-1, Irrfahrt (random walk), S. 174–175.
  17. Prof. Heermann, Universität Heidelberg: Ein Beispiel: Der Random Walk