Random Walk

Simulation eines zweidimensionalen Random Walk mit 229 Schritten und einer zufälligen Schrittweite aus dem Intervall [−0,5;0,5] für x- und y-Richtung
Zweidimensionaler symmetrischer Random Walk mit 25000 Schritten

Ein Random Walk[1] (auch (zufällige oder stochastische) Irrfahrt[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. Random-Walk-Modelle eignen sich für nichtdeterministische Zeitreihen, wie sie beispielsweise in der Finanzmathematik zur Modellierung von Aktienkursen verwendet werden (siehe Random-Walk-Theorie). Mit ihrer Hilfe können auch die Wahrscheinlichkeitsverteilungen von Messwerten physikalischer Größen verstanden werden. Der Begriff 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]

Realisierungen von Random walks können durch Monte-Carlo-Simulationen simuliert werden[6].

Definition

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

definierte stochastische Prozess ein Random Walk in oder ein d-dimensionaler Random Walk.[7][8] Hierbei ist deterministisch, häufig wird gewählt. Ein Random Walk ist also ein diskreter Prozess mit unabhängigen und stationären Zuwächsen.

Eine Realisierung eines Random Walks liefert einen zufälligen Pfad.

Man kann Random Walks oder Irrfahrten analog auch in Riemannschen Mannigfaltigkeiten definieren. Bei Irrfahrten auf Graphen spricht man von Zufallspfaden.

Eine Verallgemeinerung eines Random Walk mit korrelierten Zuwächsen wird korrelierter Random walk (correlated random walk)[9] genannt.

Eindimensionaler Fall

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

Der einfache eindimensionale Random Walk (siehe auch 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. Beim eindimensionalen Random Walk 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.

Oft interessiert man sich speziell für den ungerichteten oder symmetrischen Random Walk 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 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

Die Wahrscheinlichkeit, dass sich der Fußgänger bei einem symmetrischen Random Walk 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

Fünf Pfade eines eindimensionalen Random-Walks 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. 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 . Die Standardabweichung einer derartigen Zufallsbewegung mit Schritten beträgt dann Einheiten. Sie ist als rote Linie für positive und negative Entfernungen eingezeichnet. Um diese Strecke wird sich der Fußgänger im Mittel fortbewegen. Die relative Abweichung konvergiert gegen 0, die absolute Abweichung wächst hingegen unbeschränkt.

Allgemeiner Fall

Satz von Pólya

Dimension Rückkehrwahrscheinlichkeit zum Start[13]
11
21
30.340537
40.193206
50.135178
60.104715
70.0858449
80.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.[13]

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.[14] Ein weiterer Anwendungsbereich ist die Modellierung von Finanzmarktzeitreihen, siehe dazu auch Random-Walk-Theorie.[1]

Anwendung in der Physik

Die Eigenschaft

eines Random Walk 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

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 .[15]

Ungleichungen für den eindimensionalen Random Walk

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:[16]

Ungleichungen für den zweidimensionalen Random Walk

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:[16]

Literatur

  • Norbert Henze: Irrfahrten und verwandte Zufälle. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-01850-4.
  • 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.
  • 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.
  • Frank Spitzer: Principles of Random Walk. 2. Auflage. Springer-Verlag, New York u. a. 1976, ISBN 0-387-95154-7.
  • Barry D. Hughes: Random Walks and Random Environments: Volume 1: Random Walks. Oxford University Press, USA 1995. ISBN 0-19-853788-3.

Siehe auch

Einzelnachweise

  1. a b Horst Rinne: Taschenbuch der Statistik. 4. Auflage. Harri Deutsch, Frankfurt am Main 2008, ISBN 978-3-8171-1827-4, S. 408–410.
  2. 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.
  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. Theory and Applications of Monte Carlo Simulations. (2013). Seite 229 Google Books
  7. 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).
  8. Achim Klenke: Wahrscheinlichkeitstheorie. 3. Auflage. Springer-Verlag, Berlin/Heidelberg 2012, ISBN 978-3-642-36017-6, S. 445.
  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. a b Eric W. Weisstein: Pólya's Random Walk Constants. In: MathWorld (englisch).
  14. 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.
  15. Prof. Heermann, Universität Heidelberg: Ein Beispiel: Der Random Walk
  16. a b Itai Benjamini, Robin Pemantle, Yuval Peres, University of Pennsylvania: RANDOM WALKS IN VARYING DIMENSIONS

Auf dieser Seite verwendete Medien

Uebergangsgraph random walk.png
Autor/Urheber: Moritz Kohls, Lizenz: CC0
Übergangsgraph des symmetrischen Random Walk
Random walk 25000.gif
Autor/Urheber: László Németh, Lizenz: CC0
Animated random walk with 25000 steps, see the full resolution SVG image.
Randomwalk2rp.png
Autor/Urheber: Anton (rp) 2005, Lizenz: CC BY-SA 3.0
2D Random walk mit 229 Schritten der Schrittlänge 0,5.
Random Walk example.svg
Autor/Urheber: Morn (talk), Lizenz: GFDL
Eight different random walks.
Randomwalk1rp.png
Autor/Urheber: Anton (rp) 2005, Lizenz: CC BY-SA 3.0
1D Random walk mit 100 Schritten der Schrittlänge 0,5.