## 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:

 `132330138360230982658422845906`

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, sysfrom math import logimport numpy as npimport matplotlib.pyplot as pltimport Counterrandom.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, sysfrom math import logimport numpy as npimport matplotlib.pyplot as pltimport Counterrandom.seed(7)# 1D walkpos = 0L = 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')`