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:


132330
138360
230982
658422
845906


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

random.seed(157)
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))
L.append(pos)
plt.scatter(X,L,s=10,color=colors[i])

ax = plt.axes()
ax.set_xlim(-10,X[-1]+10)
plt.savefig('example1.png')




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

random.seed(7)
# 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()
ax.set_xlim(0,22)
ax.set_ylim(0,8)
for k in c:
n = log(c[k]/log(2))
r = plt.Rectangle((k,0),
width=1,height=n,
facecolor='magenta')
ax.add_patch(r)

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