#
# cubewalk
# Random walk on the cube
# Computes return time to start vertex
#
from random import randint
# How many trials (times to walk)
trials = 10000
# results is a dictionary that holds pairs (return time, frequency)
results = dict()
max = 0 # track the maximum walk length seen
for trial in range(trials):
# start walk at [0,0,0]
v = [0,0,0]
n=0
# walk until get back to [0,0,0]
while n == 0 or v != [0,0,0]:
i = randint(0,2)
v[i] = 1-v[i]
n += 1
# update the results dictionary.. may need to add a new key
if n in results:
results[n] += 1
else:
results[n] = 1
if n > max:
max = n
# print histogram
histwidth = 80
divisor = trials/histwidth
for i in range(2,max+1,2):
print "%2d" % i,
if i not in results:
print
else:
if results[i]/divisor == 0:
print '.'
else:
print 'o'*(results[i]/divisor)
# print stats
totalsteps = 0
for i in range(2,max+1,2):
if i in results:
totalsteps += results[i]*i
print 'Average walk length:', totalsteps/float(trials)