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 log₂ 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')