C++: Random Walk 1D - Numerische Berechnung der Rückkehrwahrscheinlichkeit

Der nachfolgende C++-Code implementiert den eindimensionalen Random Walk und berechnet numerisch die Wahrscheinlichkeit, dass der Walker nach einer bestimmten Anzahl von Schritten t wieder an seine Startposition zurückkehrt. Dafür werden für jede Schrittanzahl t (0 < t < max_T) N Durchläufe mit t Sequenzen simuliert. Ist nach genau t Schritten die ursprüngliche Position wieder erreicht, so gilt der Durchlauf als erfolgreich, andernfalls als fehlgeschlagen. Der Quotient von der Anzahl an erfolgreichen Versuchen und der Gesamtzahl an Durchläufen N gibt bei ausreichend großem N eine gute Näherung für die Rückkehrwahrscheinlichkeit nach t Sequenzen wieder.

 

 
using namespace std;
 
int const N = 10000; //Number of walks for each t
int const max_T = 100; //Max value for t
 
int make_rand() {
    int random = rand() % 2; 
    return random;
}
 
double do_random_walk(int T, int nr) {
    int success = 0;
 
    for (int n = 0; n < nr; n++) {
        int pos = 0;
        for (int i = 0; i < T; i++) {
            // update T times
            int random = make_rand();
            if (random == 1) {
                pos = pos + 1;
            }    
            else {
                pos = pos - 1;
            }
            //cout << pos << endl;
 
        }
        if (pos == 0) {
            success++;
        }
    }
 
    return (double)success/(nr); 
}
 
int main(int argv, char** argc) {
    srand ( time(NULL) );
    for (int t = 2; t <= max_T; t=t+2) {
        double prob = do_random_walk(t, N);
        cout << t << "\t" << prob << endl;
    }
}
 

 

Man beachte, dass der Algorithmus ungerade Werte von t überspringt, da  aufgrund der Symmetrie in der Diskretisierung des Raums und der gleichen Sprungwahrscheinlichkeiten in beide Richtungen eine Rückkehr zur ursprünglichen Position ausschließlich nach einer geraden Anzahl von Schritten möglich ist.

Eine graphische Darstellung der vom Programm generierten numerischen Werte offenbart die Asymptotik hinter dem Wahrscheinlichkeitsverlauf für große Schrittzahlen t.

random walk 1d

Der abgebildete Verlauf wird der theoretischen Erwartung gerecht. Diese ist gegeben durch \(P(x_{2t} = 0) = (\frac{1}{2})^{2t} {2t \choose t }\). Ihre Struktur wird durchsichtig, wenn man den Random Walk interpretierend in ein gewöhnliches Bernoulli-Experiment übersetzt, beispielsweise in das t-fache Werfen einer Münze, die mit jeweils einer Wahrscheinlichkeit von exakt 50% Kopf oder Zahl anzeigt. Ein erfolgreicher Random Walk ist genau dann eingetreten, wenn der Münzwürf nach t-Würfen genau so oft mit Zahl wie mit Kopf ausgegangen ist, d.h. wenn der Walker genau so viel Schritte nach rechts wie nach links ausgeführt hat. Nur dann kann und muss er an seine ursprüngliche Position zurückgekehrt sein.

Im Gegensatz zu einer gleichförmigen Bewegung nimmt bei einem eindimensionalen Random Walk nicht der nach t Schritten erwartete Abstand \(<x_{t}>\), sondern \(<x_{t}^{2}>\) linear mit der Schrittzahl t zu. Dies ergibt sich aus der stochastischen Bewegungsgleichung \[x_{t+1} = x_t + R \] mit dem Positionswechsel \(R = \pm 1\) bei gleichwahrscheinlichem Sprung nach links bzw. rechts. Es gilt: \[<R> =\frac{1}{2}(1+(-1)) = 0 \\ <R^2> =\frac{1}{2}(1^2+(-1)^2) = 1\] Setzt man die beiden Werte in \[<x_{t+1}^2> = <x_{t}^2> + 2 <x_t> <R> + <R^2>\] ein, so folgt \[<x_{t+1}^2> = <x_{t}^2> + 1.\] Dies Bedeutet für \(x_0 = 0\): \[x_0 = 0 \\ <x_{1}^2> = <x_{0}^2> + 1 = 1 \\ <x_{2}^2> = 2 \\ <x_{3}^2> = 3 \\ etc.\]


2016-01-20 21:12:15