Ein zufälliger Spaziergang ist eine mathematische Formalisierung einer Schussbahn, die daraus besteht, aufeinander folgende zufällige Schritte zu machen. Zum Beispiel kann der durch ein Molekül verfolgte Pfad, als es in einer Flüssigkeit oder einem Benzin, dem Suchweg eines foraging Tieres, dem Preis eines schwankenden Lagers und der finanziellen Lage eines Spielers reist, alles als zufällige Spaziergänge modelliert werden. Der Begriff zufälliger Spaziergang wurde zuerst von Karl Pearson 1905 eingeführt. Zufällige Spaziergänge sind in vielen Feldern verwendet worden: Ökologie, Volkswirtschaft, Psychologie, Informatik, Physik, Chemie und Biologie. Zufällige Spaziergänge erklären die beobachteten Handlungsweisen von Prozessen in diesen Feldern, und dienen so als ein grundsätzliches Modell für die registrierte stochastische Tätigkeit.

Verschiedene verschiedene Typen von zufälligen Spaziergängen sind von Interesse. Häufig, wie man annimmt, sind zufällige Spaziergänge Ketten von Markov oder Prozesse von Markov, aber anderer sind mehr komplizierte Spaziergänge auch von Interesse. Einige zufällige Spaziergänge sind auf Graphen, anderen auf der Linie, im Flugzeug, oder in höheren Dimensionen, während einige zufällige Spaziergänge auf Gruppen sind. Zufällige Spaziergänge ändern sich auch hinsichtlich des Zeitparameters. Häufig ist der Spaziergang in der diskreten Zeit, und mit einem Inhaltsverzeichnis versehen durch die natürlichen Zahlen, als darin. Jedoch machen einige Spaziergänge ihre Schritte aufs Geratewohl Zeiten, und in diesem Fall wird die Position für das Kontinuum von Zeiten definiert. Spezifische Fälle oder Grenzen von zufälligen Spaziergängen schließen den Spaziergang des Alkoholikers und Flug von Lévy ein. Zufällige Spaziergänge sind mit den Verbreitungsmodellen verbunden und sind ein grundsätzliches Thema in Diskussionen von Prozessen von Markov. Mehrere Eigenschaften von zufälligen Spaziergängen, einschließlich des Streuungsvertriebs, erste Durchlasszeit und Begegnungsraten, sind umfassend studiert worden.

Gitter zufälliger Spaziergang

Ein populäres zufälliges Spaziergang-Modell ist das eines zufälligen Spaziergangs auf einem regelmäßigen Gitter, wo an jedem Schritt der Spaziergang zu einer anderen Seite gemäß etwas Wahrscheinlichkeitsvertrieb springt. Im einfachen zufälligen Spaziergang kann der Spaziergang nur zu benachbarten Seiten des Gitters springen. Im einfachen symmetrischen zufälligen Spaziergang auf einem lokal begrenzten Gitter sind die Wahrscheinlichkeiten des Spaziergangs, der irgendwelchen seiner Nachbarn springt, dasselbe. Das beste studierte Beispiel ist des zufälligen Spaziergangs auf dem d-dimensional Gitter der ganzen Zahl (manchmal hat das Hyperkubikgitter genannt).

Eindimensionaler zufälliger Spaziergang

Sich ein elementares Beispiel eines zufälligen Spaziergangs ist der zufällige Spaziergang auf dem Zahlenstrahl der ganzen Zahl, der an 0 anfängt und an jedem Schritt +1 oder 1 mit der gleichen Wahrscheinlichkeit bewegt.

Dieser Spaziergang kann wie folgt illustriert werden. Ein Anschreiber wird an der Null auf dem Zahlenstrahl gelegt, und eine schöne Münze wird geschnipst. Wenn es auf Köpfen landet, wird der Anschreiber eine Einheit nach rechts bewegt. Wenn es auf Schwänzen landet, wird der Anschreiber eine Einheit nach links bewegt. Nach fünf Flips ist es möglich, auf 1, −1, 3, −3, 5, oder −5 gelandet zu sein. Mit fünf Flips werden drei Köpfe und zwei Schwänze, in jeder Ordnung, auf 1 landen. Es gibt 10 Weisen, auf 1 oder −1 (durch das Schnipsen von drei Schwänzen und zwei Köpfen), 5 Weisen zu landen, auf 3 (durch das Schnipsen von vier Köpfen und einem Schwanz), 5 Weisen zu landen, auf −3 (durch das Schnipsen von vier Schwänzen und einem Kopf), 1 Weise zu landen, auf 5 (durch das Schnipsen von fünf Köpfen) und 1 Weise zu landen, auf −5 (durch das Schnipsen von fünf Schwänzen) zu landen. Sieh die Zahl unten für eine Illustration der möglichen Ergebnisse von 5 Flips.

Um diesen Spaziergang formell zu definieren, nehmen Sie unabhängige zufällige Variablen, wo jede Variable entweder 1 oder −1 mit einer 50-%-Wahrscheinlichkeit für jeden Wert ist, und Satz und Die Reihe der einfache zufällige Spaziergang aufgefordert werden. Diese Reihe (die Summe der Folge von 1s und 1s) gibt die spazieren gegangene Entfernung, wenn jeder Teil des Spaziergangs der Länge ein ist.

Die Erwartung dessen ist Null. D. h. der bösartige von allen Münzflips nähert sich Null als die Zahl der Flip-Zunahme. Das folgt durch das begrenzte Additivitätseigentum der Erwartung:

:

Eine ähnliche Berechnung, mit der Unabhängigkeit der zufälligen Variablen und der Tatsache dass, zeigt dass:

:

Das deutet an, dass, die erwartete Übersetzungsentfernung danach n Schritte, von der Ordnung dessen sein sollte. Tatsächlich,

:

Abstammung der Streuungsproportionalität

Wenn wir die Situation haben, wo die Wahrscheinlichkeiten des Bewegens entweder verlassen oder Recht gleich sind, und die Wahrscheinlichkeit davon, nach rechts aus insgesamt Schritten Schritte zu unternehmen, wird durch gegeben

:

da es mögliche Weisen gibt zu nehmen und Schritte nach rechts und verlassen beziehungsweise. Die Wahrscheinlichkeit, einigen dieser unabhängigen Schritte zu machen, ist 1/2, und so haben wir das Produkt. Jetzt ist der Erwartungswert davon, Schritte zu unternehmen

,

:

\begin {richten }\aus

&= \sum_ {k=0} ^N k \binom {N} {k }\\verlassen (\frac {1} {2 }\\Recht) ^N \\

&= \left (\frac {1} {2 }\\Recht) ^N \sum_ {k=0} ^N N \binom {n-1} {k-1} \\

&= \left (\frac {1} {2 }\\Recht) ^N N 2^ {n-1} \\

&= \frac {N} {2}.

\end {richten }\aus

</Mathematik>

Es ist allgemein der Fall das

: \begin {richten }\aus

&= \left (\frac {1} {2 }\\Recht) ^N \sum_ {k=0} ^N (k-1 + 1) N \binom {n-1} {k-1} \\

&= \left (\frac {1} {2 }\\Recht) ^N N\sum_ {k=0} ^N \left [(n-1) \binom {n-2} {k-2} + \binom {n-1} {k-1} \right] \\

&= \left (\frac {1} {2 }\\Recht) ^N N \left [(n-1) 2^ {n-2} + 2^ {n-1} \right] \\

&= \frac {N^2} {4} + \frac {N} {4}.

\end {richten }\aus</Mathematik>Es ist allgemein der Fall das :\begin {richten }\aus

&\\propto \sqrt {N}.

\end {richten }\aus</Mathematik>

Dieses Ergebnis zeigt, dass Verbreitung ganz eine unwirksame Weise wird, Lösungen wegen der Weise zu mischen, wie sich die Quadratwurzel für den großen benimmt.

Wie oft wird ein zufälliger Kreuz eine Grenzlinie, wenn erlaubt, spazieren gehen fortzusetzen, für immer spazieren zu gehen? Ein einfacher zufälliger Spaziergang darauf wird jeden Punkt eine unendliche Zahl von Zeiten durchqueren. Dieses Ergebnis hat viele Namen: das Bahnübergang-Phänomen, Wiederauftreten oder die Ruine des Spielers. Der Grund für den Nachnamen ist wie folgt: Ein Spieler mit einem begrenzten Betrag des Geldes wird immer verlieren, wenn er ein schönes Spiel gegen eine Bank mit einem unendlichen Betrag des Geldes spielen wird. Das Geld des Spielers wird einen zufälligen Spaziergang durchführen, und es wird Null an einem Punkt erreichen, und das Spiel wird zu Ende sein.

Wenn a und b positive ganze Zahlen sind, dann ist die erwartete Zahl von Schritten bis zu einem eindimensionalen einfachen zufälligen Spaziergang, der bei den 0 ersten Erfolgen b oder &minus;a anfängt, ab. Die Wahrscheinlichkeit, dass dieser Spaziergang b vorher a schlagen wird, ist, der aus der Tatsache abgeleitet werden kann, dass einfacher zufälliger Spaziergang ein Martingal ist.

Einige der Ergebnisse, die oben erwähnt sind, können aus Eigenschaften des Dreiecks des Pascal abgeleitet werden. Die Zahl von verschiedenen Spaziergängen von n geht, wo jeder Schritt +1 ist oder &minus;1 klar 2 ist. Für den einfachen zufälligen Spaziergang ist jeder dieser Spaziergänge ebenso wahrscheinlich. In der Größenordnung von S, um einer Nummer k gleich zu sein, ist es notwendig und genügend, dass die Zahl +1 im Spaziergang diejenigen &minus;1 durch k übertrifft. So ist die Zahl von Spaziergängen, die befriedigen, genau die Zahl von Weisen (n + k)/2 Elemente von einem n Element-Satz zu wählen (dafür, um Nichtnull zu sein, es ist notwendig, dass n + k, eine gerade Zahl sein), der ein Zugang im Dreieck des Pascal ist, das dadurch angezeigt ist. Deshalb, die Wahrscheinlichkeit, die dem gleich ist. Indem man Einträge des Dreiecks des Pascal in Bezug auf factorials vertritt und die Formel von Stirling verwendet, kann man gute Schätzungen für diese Wahrscheinlichkeiten für große Werte dessen erhalten.

Diese Beziehung mit dem Dreieck des Pascal wird für kleine Werte von n demonstriert. An Nullumdrehungen wird die einzige Möglichkeit sein, an der Null zu bleiben. Jedoch, an einer Umdrehung, gibt es eine Chance, auf &minus;1 oder eine Chance zu landen, auf 1 zu landen. An zwei Umdrehungen konnte sich ein Anschreiber an 1 zu 2 oder zurück zur Null bewegen. Ein Anschreiber an &minus;1, konnte sich zu &minus;2 oder zurück zur Null bewegen. Deshalb gibt es eine Chance, auf &minus;2, zwei Chancen zu landen, auf der Null und einer Chance zu landen, auf 2 zu landen.

Der Hauptgrenzwertsatz und das Gesetz des wiederholten Logarithmus beschreiben wichtige Aspekte des Verhaltens des einfachen zufälligen Spaziergangs darauf.

Als eine Kette von Markov

Ein eindimensionaler zufälliger Spaziergang kann auch auf als eine Kette von Markov geschaut werden, deren Zustandraum durch die ganzen Zahlen Für etwas Zufriedenheit Nummer p gegeben wird

:

Gaussian zufälliger Spaziergang

Ein zufälliger Spaziergang, der eine Schritt-Größe hat, die sich gemäß einer Normalverteilung ändert, wird als ein Modell für wirkliche Zeitreihe-Daten wie Finanzmärkte verwendet. Die Schwarze-Scholes Formel, um Auswahl-Preise zu modellieren, verwendet zum Beispiel einen gaussian zufälligen Spaziergang als eine zu Grunde liegende Annahme.

Hier ist die Schritt-Größe die umgekehrte kumulative Normalverteilung, wo 0  z  1 eine gleichförmig verteilte Zufallszahl ist, und μ und σ die Mittel- und Standardabweichungen der Normalverteilung beziehungsweise sind.

Für Schritte, die gemäß jedem Vertrieb mit der Null verteilt sind, bösartig und eine begrenzte Abweichung (nicht notwendigerweise gerade eine Normalverteilung) bedeutet die Wurzel Quadratübersetzungsentfernung, nachdem n Schritte ist

:

Höhere Dimensionen

Stellen Sie sich jetzt einen Alkoholiker vor, der zufällig in einer idealisierten Stadt spazieren geht. Die Stadt ist effektiv unendlich und in einem Quadratbratrost, und an jeder Kreuzung eingeordnet, der Alkoholiker wählt einen der vier möglichen Wege (einschließlich desjenigen er ist hergekommen) mit der gleichen Wahrscheinlichkeit. Formell ist das ein zufälliger Spaziergang auf dem Satz aller Punkte im Flugzeug mit Koordinaten der ganzen Zahl. Wird der Alkoholiker jemals zu seinem Haus von der Bar zurückkommen? Es stellt sich heraus, dass er wird. Das ist die hohe dimensionale Entsprechung vom Bahnübergang-Problem, das oben besprochen ist. Die Wahrscheinlichkeit des Zurückbringens in den Ursprung nimmt als die Zahl von Dimensionszunahmen ab. In drei Dimensionen nimmt die Wahrscheinlichkeit zu ungefähr 34 % ab. Eine Abstammung zusammen mit Werten von p werden (d) hier besprochen: Die Zufälligen Spaziergang-Konstanten von Pólya.

Die Schussbahn eines zufälligen Spaziergangs ist die Sammlung von Seiten, die es, betrachtet als ein Satz mit der Missachtung dazu besucht hat, als der Spaziergang den Punkt erreicht hat. In einer Dimension ist die Schussbahn einfach alle Punkte zwischen der minimalen Höhe der Spaziergang erreicht und dem Maximum (beide, sind durchschnittlich, auf der Ordnung von n). In höheren Dimensionen hat der Satz interessante geometrische Eigenschaften. Tatsächlich bekommt man einen getrennten fractal, der ein Satz ist, der stochastische Selbstähnlichkeit auf großen Skalen ausstellt, aber auf kleinen Skalen kann man "Zackigkeit" beobachten, die sich aus dem Bratrost ergibt, auf dem der Spaziergang durchgeführt wird. Die zwei Bücher von Lawler, der unten Verweise angebracht ist, sind eine gute Quelle zu diesem Thema.

Beziehung zum Prozess von Wiener

Ein Wiener-Prozess ist ein stochastischer Prozess mit dem ähnlichen Verhalten zur Brownschen Bewegung, dem physischen Phänomen einer Minutenpartikel, die sich in einer Flüssigkeit verbreitet. (Manchmal wird der Prozess von Wiener "Brownsche Bewegung" genannt, obwohl das genau genommen eine Verwirrung eines Modells mit dem Phänomen ist, das wird modelliert.)

Ein Wiener-Prozess ist die kletternde Grenze des zufälligen Spaziergangs in der Dimension 1. Das bedeutet, dass, wenn Sie einen zufälligen Spaziergang mit sehr kleinen Schritten nehmen, Sie eine Annäherung an einen Prozess von Wiener (und, weniger genau, an die Brownsche Bewegung) bekommen. Um genauer zu sein, wenn die Schritt-Größe ε ist, muss man der Länge L/ε spazieren gehen, um einem Prozess-Spaziergang von Wiener der Länge L näher zu kommen. Da die Schritt-Größe zu 0 neigt (und die Zahl von Schritten proportional zunimmt), läuft zufälliger Spaziergang zu einem Prozess von Wiener in einem passenden Sinn zusammen. Formell, wenn B der Raum aller Pfade der Länge L mit der maximalen Topologie ist, und wenn M der Raum des Maßes über B mit der Norm-Topologie ist, dann ist die Konvergenz in der RaumM. Ähnlich ist ein Prozess von Wiener in mehreren Dimensionen die kletternde Grenze des zufälligen Spaziergangs in derselben Zahl von Dimensionen.

Ein zufälliger Spaziergang ist ein getrennter fractal (eine Funktion mit Dimensionen der ganzen Zahl; 1, 2...), aber eine Prozess-Schussbahn von Wiener ist ein wahrer fractal, und es gibt eine Verbindung zwischen den zwei. Nehmen Sie zum Beispiel einen zufälligen Spaziergang, bis er einen Kreis des Radius r Zeiten die Schritt-Länge schlägt. Die durchschnittliche Zahl von Schritten, die es durchführt, ist r. Diese Tatsache ist die getrennte Version der Tatsache, dass ein Prozess-Spaziergang von Wiener ein fractal der Dimension von Hausdorff 2 ist.

In zwei Dimensionen, der durchschnittlichen Zahl von Punkten hat derselbe zufällige Spaziergang an der Grenze seiner Schussbahn ist r. Das entspricht der Tatsache, dass die Grenze der Schussbahn eines Prozesses von Wiener ein fractal der Dimension 4/3, eine von Mandelbrot vorausgesagte Tatsache mit Simulationen ist, aber sich nur 2000 erwiesen

hat

durch Lawler, Schramm und Werner.

Ein Wiener-Prozess genießt viele symmetries zufälliger Spaziergang tut nicht. Zum Beispiel ist ein Prozess-Spaziergang von Wiener invariant zu Folgen, aber zufälliger Spaziergang ist nicht, da der zu Grunde liegende Bratrost ist nicht (zufälliger Spaziergang ist invariant zu Folgen durch 90 Grade, aber Prozesse von Wiener sind invariant zu Folgen durch, zum Beispiel, 17 Grade auch). Das bedeutet, dass in vielen Fällen Probleme auf dem zufälligen Spaziergang leichter sind, durch das Übersetzen von ihnen zu einem Prozess von Wiener, das Beheben des Problems dort, und dann das Übersetzen zurück zu lösen. Andererseits sind einige Probleme leichter, mit zufälligen Spaziergängen wegen seiner getrennten Natur zu lösen.

Zufälliger Spaziergang und Prozess von Wiener können verbunden, nämlich auf demselben Wahrscheinlichkeitsraum auf eine abhängige Weise manifestiert werden, die sie zwingt, ziemlich nah zu sein. Das einfachste solche Kopplung ist das Einbetten von Skorokhod, aber anderer bestehen genauere Kopplungen ebenso.

Die Konvergenz eines zufälligen Spaziergangs zum Prozess von Wiener wird vom Hauptgrenzwertsatz kontrolliert. Für eine Partikel in einer bekannten festen Position an t = 0 sagt der Lehrsatz uns, dass nach einer Vielzahl von unabhängigen Schritten im zufälligen Spaziergang die Position des Spaziergängers gemäß einer Normalverteilung der Gesamtabweichung verteilt wird:

:

wo t die Zeit ist, hat seit dem Anfang des zufälligen Spaziergangs vergangen, ist die Größe eines Schritts des zufälligen Spaziergangs, und ist die zwischen zwei aufeinander folgenden Schritten vergangene Zeit.

Das entspricht der Funktion von Green der Verbreitungsgleichung, die den Prozess von Wiener kontrolliert, der demonstriert, dass, nach einer Vielzahl von Schritten, der zufällige Spaziergang zu einem Prozess von Wiener zusammenläuft.

Im 3D ist die Abweichung entsprechend der Funktion des Grüns der Verbreitungsgleichung:

:Indem

man diese Menge mit der zur Position des zufälligen Spaziergängers vereinigten Abweichung gleichmacht, erhält man den gleichwertigen Diffusionskoeffizienten, der für den asymptotischen Prozess von Wiener zu betrachten ist, zu dem der zufällige Spaziergang nach einer Vielzahl von Schritten zusammenläuft:

: (gültig nur im 3D)

Bemerkung: Die zwei Ausdrücke der Abweichung entsprechen oben dem Vertrieb, der zum Vektoren vereinigt ist, der die zwei Enden des zufälligen Spaziergangs im 3D verbindet. Die Abweichung, die zu jedem Bestandteil vereinigt ist, oder ist nur ein Drittel dieses Werts (noch im 3D).

Anomale Verbreitung

In unordentlichen Systemen wie poröse Medien und fractals kann zu, aber zu nicht proportional sein. Die Hochzahl wird die anomale Verbreitungshochzahl genannt und kann größer oder kleiner sein als 2.

Anwendungen

Der folgende ist einige Anwendungen des zufälligen Spaziergangs:

• In der Volkswirtschaft ist die "zufällige Spaziergang-Hypothese" an Musteraktienpreise und andere Faktoren gewöhnt. Empirische Studien haben einige Abweichungen von diesem theoretischen Modell besonders in kurzfristigen und langfristigen Korrelationen gefunden. Sieh Aktienkurse.
• In der Bevölkerungsgenetik beschreibt zufälliger Spaziergang die statistischen Eigenschaften des genetischen Antriebs
• In der Physik werden zufällige Spaziergänge als vereinfachte Modelle der physischen Brownschen Bewegung und Verbreitung wie die zufällige Bewegung von Molekülen in Flüssigkeiten und Benzin verwendet. Sieh zum Beispiel Verbreitungsbeschränkte Ansammlung. Auch in der Physik, den zufälligen Spaziergängen und etwas selbst spielen aufeinander wirkende Spaziergänge eine Rolle in der Quant-Feldtheorie.
• In der mathematischen Ökologie werden zufällige Spaziergänge verwendet, um individuelle Tierbewegungen zu beschreiben, Prozesse von biodiffusion, und gelegentlich zur Musterbevölkerungsdynamik empirisch zu unterstützen.
• In der Polymer-Physik beschreibt zufälliger Spaziergang eine ideale Kette. Es ist das einfachste Modell, um Polymer zu studieren.
• In anderen Feldern der Mathematik wird zufälliger Spaziergang verwendet, um Lösungen der Gleichung von Laplace zu berechnen, das harmonische Maß, und für verschiedene Aufbauten in der Analyse und combinatorics zu schätzen.
• In der Informatik werden zufällige Spaziergänge verwendet, um die Größe des Webs zu schätzen. In der Konferenz des World Wide Web 2006, Bar-yossef u. a. veröffentlicht ihre Ergebnisse und Algorithmen für dasselbe.
• In der Bildsegmentation werden zufällige Spaziergänge verwendet, um die Etiketten (d. h., "Gegenstand" oder "Hintergrund") zu bestimmen, um mit jedem Pixel zu verkehren. Dieser Algorithmus wird normalerweise den zufälligen Spaziergänger-Segmentationsalgorithmus genannt.

In allen diesen Fällen wird gegen zufälligen Spaziergang häufig die Brownsche Bewegung ausgewechselt.

• In der Gehirnforschung sind zufällige Spaziergänge und verstärkte zufällige Spaziergänge an Musterkaskaden des Neurons gewöhnt, das im Gehirn schießt.
• In der Visionswissenschaft, fixational Augenbewegungen werden durch einen zufälligen Spaziergang gut beschrieben.
• In der Psychologie erklären zufällige Spaziergänge genau, dass die Beziehung zwischen der Zeit eine Entscheidung und die Wahrscheinlichkeit treffen musste, dass eine bestimmte Entscheidung getroffen wird.
• Zufällige Spaziergänge können an die Probe von einem Zustandraum gewöhnt sein, der unbekannt oder sehr groß ist, um zum Beispiel eine zufällige Seite vom Internet oder, für die Forschung von Arbeitsbedingungen, einem zufälligen Arbeiter in einem gegebenen Land aufzupicken.

:*When diese letzte Annäherung wird in der Informatik verwendet, es ist als Kette von Markov Monte Carlo oder MCMC für den kurzen bekannt. Häufig erlaubt die Stichprobenerhebung von einem komplizierten Zustandraum auch, eine probabilistic Schätzung der Größe des Raums zu bekommen. Die Schätzung der dauerhaften von einer großen Matrix von Nullen und war das angepackte Verwenden des ersten Hauptproblems dieser Annäherung.

• Zufällige Spaziergänge sind auch an massive Beispielonline-Graphen wie soziale Online-Netze gewöhnt gewesen.
• Im Radionetzwerkanschluss ist ein zufälliger Spaziergang an die Musterknotenbewegung gewöhnt.
• Bakterien von Motile beschäftigen sich mit einem voreingenommenen zufälligen Spaziergang.
• Zufällige Spaziergänge sind an das Musterspielen gewöhnt.
• In der Physik unterliegen zufällige Spaziergänge der Methode der Bewertung von Fermi.

Varianten von zufälligen Spaziergängen

Mehrere Typen von stochastischen Prozessen sind betrachtet worden, die den reinen zufälligen Spaziergängen ähnlich sind, aber wo der einfachen Struktur erlaubt wird, mehr verallgemeinert zu werden. Die reine Struktur kann durch die Schritte charakterisiert werden, die definiert durch den unabhängigen seiend sind, und hat identisch zufällige Variablen verteilt.

Zufälliger Spaziergang auf Graphen

Ein zufälliger Spaziergang der Länge k auf einem vielleicht unendlichen Graphen G mit einer Wurzel 0 ist ein stochastischer Prozess mit zufälligen solchen Variablen dass und

ist ein Scheitelpunkt gewählt gleichförmig aufs Geratewohl aus den Nachbarn dessen.

Dann ist die Zahl die Wahrscheinlichkeit, dass ein zufälliger Spaziergang der Länge k, an v anfangend, an w endet.

Insbesondere wenn G ein Graph mit der Wurzel 0 ist, ist die Wahrscheinlichkeit, dass - Schritt zufälliger Spaziergang zu 0 zurückkehrt.

Nehmen Sie an, jetzt wo unsere Stadt nicht mehr ein vollkommener Quadratbratrost ist. Wenn unser Alkoholiker einen bestimmten Verbindungspunkt erreicht, pickt er zwischen den verschiedenen verfügbaren Straßen mit der gleichen Wahrscheinlichkeit auf. So, wenn der Verbindungspunkt sieben Ausgänge hat, wird der Alkoholiker zu jedem mit der Wahrscheinlichkeit ein siebenter gehen. Das ist ein zufälliger Spaziergang auf einem Graphen. Wird unser Alkoholiker sein Haus erreichen? Es stellt sich heraus, dass unter ziemlich milden Bedingungen die Antwort noch ja ist. Zum Beispiel, wenn die Längen aller Blöcke zwischen a und b sind (wo a und b irgendwelche zwei begrenzten positiven Zahlen sind), dann wird der Alkoholiker fast sicher sein Haus erreichen. Bemerken Sie, dass wir nicht annehmen, dass der Graph planar ist, d. h. die Stadt Tunnels und Brücken enthalten kann. Eine Weise, dieses Ergebnis zu beweisen, verwendet die Verbindung zu elektrischen Netzen. Nehmen Sie eine Karte der Stadt und legen Sie einen Ein-Ohm-Widerstand auf jedem Block. Messen Sie jetzt den "Widerstand zwischen einem Punkt und Unendlichkeit". Wählen Sie mit anderen Worten eine Nummer R und nehmen Sie alle Punkte im elektrischen Netz mit der Entfernung, die größer ist als R von unserem Punkt, und schließen Sie sie zusammen an. Das ist jetzt ein begrenztes elektrisches Netz, und wir können den Widerstand von unserem Punkt bis die verdrahteten Punkte messen. Bringen Sie R in die Unendlichkeit. Die Grenze wird den Widerstand zwischen einem Punkt und Unendlichkeit genannt. Es stellt sich heraus, dass der folgende wahr ist (ein elementarer Beweis kann im Buch von Doyle und Snell gefunden werden):

Lehrsatz: Ein Graph ist vergänglich, wenn, und nur wenn der Widerstand zwischen einem Punkt und Unendlichkeit begrenzt ist. Es ist nicht wichtig, welcher Punkt gewählt wird, wenn der Graph verbunden wird.

Mit anderen Worten, in einem vergänglichen System, einzige Bedürfnisse, einen begrenzten Widerstand zu überwinden, um zur Unendlichkeit von jedem Punkt zu kommen. In einem wiederkehrenden System ist der Widerstand von jedem Punkt bis Unendlichkeit unendlich.

Diese Charakterisierung des Wiederauftretens und der Vergänglichkeit ist sehr nützlich, und spezifisch erlaubt es uns, den Fall einer Stadt zu analysieren, die im Flugzeug mit den begrenzten Entfernungen gezogen ist.

Ein zufälliger Spaziergang auf einem Graphen ist ein ganz besonderer Fall einer Kette von Markov. Verschieden von einer Kette von General Markov genießt der zufällige Spaziergang auf einem Graphen ein Eigentum genannt Zeitsymmetrie oder Umkehrbarkeit. Grob sprechend, bedeutet dieses Eigentum, auch genannt den Grundsatz des ausführlichen Gleichgewichtes, dass die Wahrscheinlichkeiten, um einen gegebenen Pfad in einer Richtung oder im anderen zu überqueren, eine sehr einfache Verbindung zwischen ihnen haben (wenn der Graph regelmäßig ist, sind sie gerade gleich). Dieses Eigentum hat wichtige Folgen.

Wenn sie

in den 1980er Jahren anfängt, ist viel Forschung in in Verbindung stehende Eigenschaften des Graphen zu zufälligen Spaziergängen eingetreten. Zusätzlich zur elektrischen Netzverbindung, die oben beschrieben ist, gibt es wichtige Verbindungen zur isoperimetric Ungleichheit, sieht mehr hier, funktionelle Ungleichheit wie Sobolev und Ungleichheit von Poincaré und Eigenschaften von Lösungen der Gleichung von Laplace. Ein bedeutender Teil dieser Forschung wurde Graphen von Cayley begrenzt erzeugter Gruppen konzentriert. Zum Beispiel ist der Beweis von Dave Bayer und Persi Diaconis, die 7 Schlurfen riffeln, genug, um ein Spiel Karten zu mischen (sieh mehr Details unter dem Schlurfen) ist tatsächlich ein Ergebnis über den zufälligen Spaziergang auf der Gruppe S, und der Beweis verwendet die Gruppenstruktur auf eine wesentliche Weise. In vielen Fällen tragen diese getrennten Ergebnisse dazu vor, oder werden aus Sammelleitungen abgeleitet und Liegen Gruppen.

Eine gute Verweisung für den zufälligen Spaziergang auf Graphen ist das Online-Buch von Aldous, und sich Füllen. Weil Gruppen das Buch von Woess sehen.

Wenn der Übergang-Kern selbst (gestützt auf einer Umgebung) dann zufällig ist, wird der zufällige Spaziergang einen "zufälligen Spaziergang in der zufälligen Umgebung" genannt. Wenn das Gesetz des zufälligen Spaziergangs die Zufälligkeit dessen einschließt, wird das Gesetz das ausgeglühte Gesetz genannt; andererseits, wenn, wie befestigt, gesehen wird, wird das Gesetz ein gelöschtes Gesetz genannt. Sieh das Buch von Hughes oder die Vortrag-Zeichen von Zeitouni.

Wir können an Auswahl jedes möglichen Randes mit derselben Wahrscheinlichkeit wie Maximierung der Unklarheit (Wärmegewicht) lokal denken. Wir konnten es auch allgemein - im maximalen Wärmegewicht zufälligen Spaziergang (MERW) tun wir wollen, dass alle Pfade, oder mit anderen Worten ebenso wahrscheinlich sind: Für jeden zwei Scheitelpunkte ist jeder Pfad der gegebenen Länge ebenso wahrscheinlich. Dieser zufällige Spaziergang hat viel stärkere Lokalisierungseigenschaften.

Aufeinander selbstwirkende zufällige Spaziergänge

Es gibt mehrere interessante Modelle von zufälligen Pfaden, in denen jeder Schritt von der Vergangenheit auf eine komplizierte Weise abhängt. Alle sind komplizierter, um analytisch zu lösen, als der übliche zufällige Spaziergang; dennoch ist das Verhalten jedes Modells eines zufälligen Spaziergängers erreichbare Verwenden-Computer. Beispiele schließen ein:

• Der Selbstvermeiden-Spaziergang (Madras und Slade 1996).

Der Selbstvermeiden-Spaziergang der Länge n auf Z^d ist der zufällige N-Schritt-Pfad, der am Ursprung anfängt, Übergänge nur zwischen angrenzenden Seiten in Z^d macht, nie eine Seite wieder besucht, und gleichförmig unter allen diesen Pfaden gewählt wird. In zwei Dimensionen, wegen des Selbstabfangens, ist ein typischer Selbstvermeiden-Spaziergang sehr kurz, während in der höheren Dimension es außer allen Grenzen wächst.

Dieses Modell ist häufig in der Polymer-Physik (seit den 1960er Jahren) verwendet worden.

• Der Schleife-gelöschte zufällige Spaziergang (Gregory Lawler).
• Der verstärkte zufällige Spaziergang (Robin Pemantle 2007).
• Der Erforschungsprozess.
• Der Mehragent zufälliger Spaziergang.

Aufeinander bezogene Langstreckenspaziergänge

Aufeinander bezogene Langstreckenzeitreihen werden in vielen biologischen, klimatologischen und Wirtschaftssystemen gefunden.

• Herzschlag registriert
• Das Nichtcodieren von DNA-Folgen
• Flüchtigkeitszeitreihe von Lagern
• Temperaturaufzeichnungen um den Erdball

Heterogene zufällige Spaziergänge in einer Dimension

Heterogene zufällige Spaziergänge in einer Dimension können entweder diskrete Zeit oder dauernde Zeit haben. Der Zwischenraum ist auch entweder getrennt oder dauernd, und es ist entweder begrenzt oder ohne Grenzen. In einem getrennten System sind die Verbindungen unter angrenzenden Staaten. Die Triebkräfte sind entweder Markovian, Semi-Markovian, oder sogar nicht-Markovian abhängig vom Modell. Heterogene zufällige Spaziergänge in 1D haben Sprung-Wahrscheinlichkeiten, die von der Position im System und/oder den verschiedenen Wahrscheinlichkeitsdichte-Funktionen der springenden Zeit (JT) (PDFs) abhängen, die von der Position im System abhängen.

Bekannte wichtige Ergebnisse in einfachen Systemen schließen ein:

• In symmetrischem Markovian zufälliger Spaziergang die Funktion des Grüns (hat auch den PDF des Spaziergängers genannt), um Staat zu besetzen, bin ich Gaussian in der Position und habe eine Abweichung, die wie die Zeit klettert. Dieses Ergebnis hält in einem System mit der diskreten Zeit und dem Raum noch auch in einem System mit der dauernden Zeit und Raum. Dieses Ergebnis ist für Systeme ohne Grenzen.
• Wenn es eine einfache Neigung im System gibt (d. h. eine unveränderliche Kraft an das System in einer besonderen Richtung angewandt wird), ist die durchschnittliche Entfernung des zufälligen Spaziergängers von seiner Startposition mit der Zeit geradlinig.

Wenn

• sie das Erreichen einer Entfernung L von der Startposition in einem begrenzten Zwischenraum der Länge L mit einer unveränderlichen Kraft versucht, ist die Zeit, um diese Entfernung zu erreichen, mit der Länge L Exponential-: wenn das Bewegen gegen die Kraft, und mit der Länge L geradlinig ist: wenn man sich mit der Kraft bewegt. Ohne Kraft:.

In völlig heterogenem Halbmarkovian zufälliger Spaziergang in einem getrennten System von L (> 1) Staaten, die Funktion des Grüns wurde im Raum von Laplace gefunden (verwandeln sich Laplace von einer Funktion wird mit, definiert). Hier wird das System im Laufe der springenden Zeit (JT) PDFs definiert: Das Anschließen setzt i mit dem Staat j fest (der Sprung ist vom Staat i). Die Lösung basiert auf der Pfad-Darstellung der Funktion des Grüns, berechnet wenn einschließlich aller Pfad-Wahrscheinlichkeitsdichte-Funktionen aller Längen:

Hier, und. Außerdem in Eq. ,

und,

mit,

^ {L-1-2 (i-c) }\\Bar {f} _ {k_c} (s)

</Mathematik> |} }\

und,

Für L=1. Das Symbol [L/2], der im oberen erscheint, das in in eq gebunden ist. ist die Fußboden-Operation (herum zur Null). Schließlich, der Faktor in eq. hat dieselbe Form wie in in eqs. - noch wird es auf einem Gitter berechnet. Gitter wird vom ursprünglichen Gitter durch die Einnahme daraus der Staaten i und j und die Staaten zwischen ihnen, und dann das Anschließen der erhaltenen zwei Bruchstücke gebaut. Für Fälle, in denen ein Bruchstück ein einzelner Staat ist, wird dieses Bruchstück ausgeschlossen; nämlich ist Gitter das längere Bruchstück. Wenn jedes Bruchstück ein einzelner Staat ist.

Gleichungen - halten für irgendwelchen 1D semi-Markovian zufälliger Spaziergang in einer L-Zustandkette, und bilden die allgemeinste Lösung in einer ausführlichen Form für zufällige Spaziergänge in 1d.

Siehe auch

• Sich verzweigender zufälliger Spaziergang
• Brownsche Bewegung
• Gesetz des wiederholten Logarithmus
• Flug von Lévy
• Flug von Lévy foraging Hypothese
• Schleife-gelöschter zufälliger Spaziergang
• Selbst das Vermeiden des Spaziergangs

Bibliografie

• David Aldous und Jim Fill, umkehrbare Ketten von Markov und zufällige Spaziergänge auf Graphen,

http://stat-www.berkeley.edu/users/aldous/RWG/book.html

• William Feller (1968), Eine Einführung in die Wahrscheinlichkeitstheorie und seine Anwendungen (Band 1). Internationale Standardbuchnummer 0-471-25708-7

:Chapter 3 dieses Buches enthält eine gründliche Diskussion von zufälligen Spaziergängen einschließlich fortgeschrittener Ergebnisse mit nur elementare Werkzeuge.

• Barry D. Hughes (1996), Zufällige Spaziergänge und zufällige Umgebungen, Presse der Universität Oxford. Internationale Standardbuchnummer 0-19-853789-1
• James Norris (1998), Ketten von Markov, Universität von Cambridge Presse. Internationale Standardbuchnummer 0-521-63396-6
• Springer Pólya (1921), "stirbt Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend Irrfahrt im Strassennetz", Mathematische Annalen, 84 (1-2):149-160, März 1921.
• Freund Révész (1990), Zufälliger Spaziergang in zufälligen und nichtzufälligen Umgebungen, Internationale Standardbuchnummer von World Scientific Pub Co 981-02-0237-7
• Wolfgang Woess (2000), Zufällige Spaziergänge auf unendlichen Graphen und Gruppen, Flächen von Cambridge in der Mathematik 138, Universität von Cambridge Presse. Internationale Standardbuchnummer 0-521-55292-3
• Mackenzie, Dana, "Die Maßnahme des Wildesten Tanzes auf der Erde", Wissenschaft, Vol ergreifend. 290, am 8. Dezember 2000.
• Aspekte von G. Weiss und Anwendungen des Zufälligen Spaziergangs, Nordholland, 1994.
• D. Ben-Avraham und S. Havlin, Verbreitung und Reaktionen in Fractals und Disordered Systems, Universität von Cambridge Presse, 2000.
• "Numb3rs Blog." Abteilung der Mathematik. Am 29. April 2006. Nordöstliche Universität. Am 12. Dezember 2007

http://www.atsweb.neu.edu/math/cp/blog/?id=137&month=04&year=2006&date=2006-04-29.

Links

• Die zufälligen Spaziergang-Konstanten von Pólya
• Zufälliger Spaziergang in Java Applet
• Zufälliger Spaziergang Java Applet 2
• Numb3rs Blog