A random walk on a clock is a random walk on $\mathbb{Z}_{12}$, the set of integers modulo 12, identified with the numbers (hours) displayed on a clock.
If at a step s
the unique hand of our experimental clock is pointing the hour h
, then at the next step, with probability 1/2, it jumps to one of the adjacent hours.
Starting at s=0 from h=12, we simulate the random walk, $W_s$, until $s$ is equal to the cover time of the clock, that is to the first time at which all hours have been visited by the clock pointer.
By Lovasz, Random Walks on Graphs: A Survey, pag. 6-7, the expected cover time of the clock is equal to 12*(12-1)/2=66.
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import random as rnd
plt.rcParams['figure.figsize']=6,6
from matplotlib import animation
from JSAnimation import IPython_display #https://github.com/jakevdp/JSAnimation
def RandWalkClock():
pi=np.pi
t=np.linspace(0,1, 200)
z=np.exp(2*pi*t*1j) #unit circle as the clock
theta=np.array([k*pi/6 for k in range(12)])
w=np.exp(theta*1j) # position of hours on the circle
def hour_gen():#generates hour the clock is pointing
visit=12*[0]
h= 3# the initial position of the clock pointer is 3*pi/6=pi/2, i.e. it's 12 o'clock
while sum(visit)<12:
yield h%12
visit[h%12]=1
if rnd.random()<0.5:
h-=1
else:
h+=1
def animate(k):
v.set_UVC(0.97*w[k].real,0.97*w[k].imag)
return v
fig = plt.figure()
ax = fig.add_subplot(111, xlim=(-1.2, 1.2), ylim=(-1.2, 1.2), aspect='equal')
ax.plot(z.real, z.imag, 'b', lw=2)#plot the circle as the clock
ax.plot(0.98*w.real, 0.98*w.imag, 'bs')# mark hours
X=[0]
Y=[0]
ax.plot(X, Y, color=(0, 0, 0), marker='o') #origin of the clock pointer
v=ax.quiver( X, Y, [], [], color=(0, 0, 0), scale_units='xy', angles='xy',
scale=1, linewidth=.1)
anim=animation.FuncAnimation(fig, animate, frames=hour_gen, blit=True,
interval=120, repeat=False)#draws a new frame every interval=120 milliseconds
return anim
anim=RandWalkClock()
plt.xlabel('To start animation, click the right black triangle')
IPython_display.display_animation(anim, default_mode='once')
from IPython.core.display import HTML
def css_styling():
styles = open("./custom.css", "r").read()
return HTML(styles)
css_styling()