Bei einem eindimensionalen Random Walk bewegt sich ein Punkt entlang einer Achse, das sei hier eine Höhenachse, wobei der Punkt bei jedem Zeitschritt mit einer Wahrscheinlichkeit 50 % eine Einheit nach oben und einer Wahrscheinlichkeit 50 % eine Einheit nach unten geht. Ein Höhen-Zeit-Diagramm würde einen Verlauf zeigen, der einem Börsenkurs ähnlich ist. Also eine Abfolge von Zacken nach oben und unten, mit jeweils zufälliger Länge. Die Berechnung von Random Walks (in drei Dimensionen) ist zum Beispiel in der Mechanik von Gasen von Bedeutung.

Eine interessante Variation, wenn auch ohne naheliegenden physikalischen Bezug, ist der Random Walk mit Boden. Hier geht der Punkt bei jedem Zeitschritt mit der Wahrscheinlichkeit p nach oben und 1-p nach unten, wobei p < 50 % sein soll (Tendenz zu Abstieg). Zusätzlich gilt, dass sobald die Höhe h = 0 erreicht wird, der Punkt mit der Wahrscheinlichkeit p auf die Höhe h = 1 steigt oder mit der Wahrscheinlichkeit 1-p auf der Höhe h = 0 bleibt (kein weiterer Abstieg möglich). Angenommen man lässt diesen Random Walk beginnend ab h = 0 laufen und prüft zu einem späteren Zeitpunkt die Höhe. Wie wahrscheinlich ist es, den Punkt auf Höhe h = 0 zu finden? Auf Höhe h = 1? Auf Höhe h = 2?

Das Problem lässt sich gut lösen, wenn man die Übergänge zwischen den Zuständen genauer betrachtet. Die Wahrscheinlichkeit, auf Höhe h zu sein, sei q(h). Auf diese Höhe kann der Punkt einmal durch Aufstieg aus der Höhe h-1 kommen oder durch Abstieg aus der Höhe h+1. Die Wahrscheinlichkeit, dass der Punkt auf Höhe h-1 ist und dann aufsteigt, ist q(h-1)*p. Die Wahrscheinlichkeit, auf Höhe h+1 zu sein und abzusteigen, ist q(h+1)*(1-p). Es gilt also für alle h außer h = 0:

q(h) = q(h-1)*p + q(h+1)*(1-p)

Die Höhe h = 0 wird nur durch Verbleiben auf h = 0 mit Wahrscheinlichkeit 1-p und Abstieg aus Höhe h = 1 erreicht. Daraus ergibt sich analog:

q(0) = q(0)*(1-p) + q(1)*(1-p)

Das lässt sich iterativ lösen. Alternativ und eleganter kann man den exponentiellen Ansatz q(h) = q(0)*x^h machen und erhält durch Einsetzen in die Gleichung für q(h) eine quadratische Gleichung für x, aus welcher x = p/(1-p) folgt. Die Wahrscheinlichkeit, den Punkt auf Höhe h zu finden, ist also:

q(h) = q(0)*(p/(1-p))^h

Das Problem ist noch nicht gelöst. Die Wahrscheinlichkeit des Aufstiegs p ist als bekannt vorrausgesetzt. Die Höhe h wird jeweils gewählt. Unbekannt ist aber noch die Wahrscheinlichkeit, den Punkt auf der Höhe h = 0 vorzufinden, q(0). Ist dieser Wert einmal bekannt, folgen die Wahrscheinlichkeiten für alle anderen Höhen. q(0) lässt sich durch eine einfache Überlegung ermitteln. Zu jedem Zeitpunkt muss der Punkt auf einer Höhe sein. Die Summe aller Wahrscheinlichkeiten muss also 1 = 100 % sein (Normierung).

[Summe über alle h] q(h) = q(0)*(1+x+x^2+x^3+…) = 1

Mit der Summenformel für die geometrische Reihe:

q(0)*(1+x+x^2+x^3+…) = q(0)*1/(1-x) = 1

Mit x = p/(1-p) und Umformung nach q(0):

q(0) = (1-2*p)/(1-p)

Damit ist das Problem gelöst. Aus der Wahrscheinlichkeit des Aufstiegs p lässt sich berechnen, mit welcher Wahrscheinlichkeit man den Punkt auf Höhe h = 0 vorfindet (oder etwas schöner gesagt, welchen Anteil der Zeit der Punkt auf der Höhe h = 0 verbringt) und daraus lässt wiederum der entsprechende Wert für jede andere Höhe berechnen. Vor einem Beispiel noch die Herleitung der mittleren Höhe. Da bekannt ist, mit welcher Wahrscheinlichkeit eine bestimmte Höhe eingenommen wird, lässt sich relativ schmerzlos die mittlere Höhe des Punktes berechnen:

m = 0*q(0)+1*q(1)+2*q(2)+3*q(3)+…

m = q(0)*(1*x+2*x^2+3*x^3+…)

Aus der Summenformel für Summen über Terme der Form h*x^h, siehe im verlinkten Wiki-Eintrag im Abschnitt “Verwandte Summenformel 1”, folgt die kompakte Form:

m = q(0)*x/(x-1)^2

Mit x = p/(1-p) und viel Umformung:

m = p/(1-2*p)

Ein Beispiel: Ein Punkt bewegt sich nach den Regeln des Random Walks mit Boden entlang einer Höhenachse, wobei der Punkt bei jedem Zeitschritt mit einer Wahrscheinlichkeit p = 0,4 = 40 % aufsteigt und mit 1-p = 0,6 = 60 % absteigt. Der Punkt wird damit q(0) = (1-2*0,4)/(1-0,4) = 0,33 = 33 % der Zeit auf der Höhe h = 0 verbringen. Die Zeit auf beliebiger Höhe h ist q(h) = 0,33*(0,4/(1-0,4))^n = 0,33*0,67^h. Auf Höhe h = 1 wird er also 22 % der Zeit verbringen, auf h = 2 den Anteil 15 % der Zeit, etc … Die mittlere Höhe des Punktes im Laufe der Bewegung ist m = 0,4/(1-2*0,4) = 2.

Der obige Lösungsansatz ist in derselben Form häufig in der Theorie von Warteschlangen zu finden. Auch dort erfolgen die Übergänge stets in benachbarte Zustände. In den Zustand n Kunden in der Schlange kommt man entweder durch Zugang eines Kunden aus dem Zustand n-1 Kunden oder Abfertigung eines Kunden aus dem Zustand n+1 Kunden, wobei im Gegensatz zum Random Walk hier auch der Verbleib im Zustand n Kunden möglich ist. Der Ansatz für die iterative Ermittlung der Wahrscheinlichkeiten des Auffindens der Schlange im Zustand n Kunden hat die Form:

q(n) = q(n)*pv + q(n-1)*pz + q(n+1)*pa

Wobei die Wahrscheinlichkeiten für Verbleib pv, Zuwachs pz oder Abnahme pa wiederum aus der Ankunftsrate und Abfertigungsrate der Kunden berechnet werden und darüber hinaus auch andere Effekte modellieren können (z.B. Tendenz von Kunden zu Vermeidung langer Schlangen). Nimmt man zu der iterativen Gleichung noch die Normierung [Summe über alle n] q(n) = 1 hinzu, dann lässt sich das Problem in der Regel vollständig lösen.