Programming

Simulation of Random Walk Hypothesis (using Python)

The Random Walk Hypothesis (as stated in Feynman’s Lectures) has always troubled me. Maybe the problem lies in my basic understanding of probability. Whatever it is, I can’t seem to get a grip on it.

There is a man who tosses a coin. If heads, he moves one step forward. If tails, he moves one step backward. Where will he end up after N number of tosses? Let us call his final distance as D. We are considering a sufficiently large N, i.e. N → ∞. We might think that D → 0, since eventually the number of heads and number of tails will balance out (both of their probabilities being equal). That is not the case.

For example,

when N=2, we might easily to get 2 heads and 0 tails, so D=2.
when N=50, we might get 28 heads and 22 tails, so D=6.
when N=1000, 520 heads and 480 tails, D=40.
and so on…

The above numbers are just speculations using common sense. Note that D does not decrease, but is rather likely to increase at a slow rate, with increasing N. Due to the difference in rates of increasing, the quantity D/N is likely to decrease with increasing N.

Hence, D/N → 0 when N → ∞.

The Random Walk Hypothesis states that the expectation value of D () should be √N. You can see that it agrees with the condition: D/N → 0 for N → ∞. The mathematical proof is simple too. What bothers me is that this expectation value is seldom reflected in experiments.

In the following simulation, I’ve assumed that Python’s randomness generating skills are good enough for the task. Any number of experiments can be performed. Each experiment will consist of an user-defined number of steps. The program will calculate the distance in each experiment, and display the number of experiments which matched the theory, and the absolute average distance. Ultimately it will state whether the average experiment agrees with the theory or not. I’ve allowed a standard error of 10%.

import random
pos=0
apos=0.0
sum=0
avg=0.0
noe=0
cnt=0
noe=input("Enter number of experiments: ")
steps=input("Enter number of steps per experiment: ")
print "Performing experiments..."
for a in range(0,noe):
    for i in range(0,steps):
        j=random.randint(0,1)
        if j==1:
            pos+=1
        else:
            pos-=1
    sum=sum+abs(pos)
    apos=abs(pos)*1.0
    if apos<=(1.1*(steps**(0.5))) and apos>=(0.9*(steps**(0.5))):
        cnt=cnt+1
    pos=0
noe=noe*1.0
avg=sum/noe
print "Expected value of distance: %d"%(steps**(0.5))
print "Number of experiments agreeing with the theory = %d"%cnt
print "Absolute average distance: "+ str(avg)
if cnt>=(noe-cnt):
    print "The average experiment satisfies the theory."
else:
    print "The average experiment disagrees with the theory."

Sample Output:

Enter number of experiments: 50
Enter number of steps per experiment: 1000000
Performing experiments…
Expected value of distance: 1000
Number of experiments agreeing with the theory = 4
Absolute average distance: 801.32
The average experiment disagrees with the theory.

As you can see, the average experiment with N = 1 million steps each failed to agree with the theory. But the average distance (801.32) looks promisingly close to 1000, so higher values of N might work. It’ll take a long time to execute though.

7 thoughts on “Simulation of Random Walk Hypothesis (using Python)

  1. I’m currently in 12th standard and have the KVPY scholarship, so I might join an IISER. I’m interested mostly in physics and programming. Are programming courses taught there? If so what are the languages taught?

    1. I can speak for IISER-Kolkata. We had a Python course in our first year. But it was mostly a course on how to analyse problems in Physics using Python, so they taught us whatever we required for that particular purpose. In third year, we are having C (as a Math course, mostly involving data structures) and FORTRAN (as a Physics course, probably for solving problems in Physics again).

      The course structure changes from year to year, so I can’t say for sure what you will be having if you join IISER-K. But remember that science is always the main focus in IISERs, not programming. Programming can easily be learnt on your own.

  2. Riju, I had used a similar method for HWP simulations in semester 4. I had constructed a graph between error amount and number of experiment in order to show the effects of genetic drift. Anyway, good work

    1. Rohan and I planned the same thing for the Bio presentation. But later we gave it up because Guha sir said programs will be strictly marked.

  3. You don’t need to increase the number of steps (in fact you could decrease the number of steps to save computation time). You need to increase the number of experiments and you will converge towards root(N).

Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s