Saturday, March 20, 2010

Random walk in 1D

This is a post about 1D random walks. For example, the first graphic is a plot of step number versus distance away from the origin for six independent chains. The code is in the first listing below. I realized when doing this plot that I need to look into generating "rainbow" colors in matplotlib, but I want to go ahead and put this up without that for now. I did a similar example in R in a previous post.

Now, the problem (as posed by Grinstead and Snell) is to investigate what happens at longer times. In the second code example, we run a random walk for a long time (1E7 steps) and record the step number each time the walk returns to 0. The plot shows the number of steps between returns to 0, as a histogram. Both axes are scaled as log2 of the value.

The walk can wander quite far away from 0 (and for a long time). The list of the largest number of steps between successive visits to 0 is:


The log-log plot looks like some kind of exponential decay. And we always come back. The value for the last interval between visits to 0 is 4.

The code uses the Counter class from here.

import random, sys
from math import log
import numpy as np
import matplotlib.pyplot as plt
import Counter

X = range(1000)
colors = list('bgrcmk')
for i in range(len(colors)):
pos = 0
L = [pos]
for x in X[1:]:
pos += random.choice((-1,1))

ax = plt.axes()

import random, sys
from math import log
import numpy as np
import matplotlib.pyplot as plt
import Counter

# 1D walk
pos = 0
L = list()
N = int(1e7)
for i in range(N):
pos += random.choice((-1,1))
if pos == 0: L.append(i)

L = [L[i] - L[i-1] for i in range(1,len(L))]
print L[-1]
c = Counter.Counter(L)
for k in sorted(c.keys()):
print str(k).rjust(8), c[k]

L = [np.floor(log(k)/log(2)) for k in L]
c = Counter.Counter(L)
print c.most_common()

ax = plt.axes()
for k in c:
n = log(c[k]/log(2))
r = plt.Rectangle((k,0),

D = {'fontsize':'large'}
ax.set_ylabel('log n',D)
ax.set_xlabel('log steps between 0',D)

No comments: