We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps.
If you start at 1 what is the expected number before you hit 12?
Well, the answer is 11 according to the simulations I ran. I know to return to 1, or from any number back to itself, it would be 12 because of the properties of the invariant distribution; so if you start at a certain position in the long run you can expect to come back once every 12 times. The invariant distribution is uniform across the 12 states. I can't explain it beyond that case though. I got ~20 steps on average to get the hands to move from 1 to 11.
$\endgroup$2 Answers
$\begingroup$These are not problems on a circle but on the linear interval of integers $$L=\{0,1,2,\ldots,12\},$$ where the hand $12$ is represented by both states $0$ and $12$, and every other hand by the state with its number. Starting from $k$ in $L$, the mean number of steps $t_k$ that the symmetric simple random walk needs to hit $0$ or $12$ is $$t_k=k(12-k),$$ hence your simulations giving $t_1=11$ and $t_2=20$ (since hitting $11$ starting from $1$ on the clock is equivalent to hitting $12$ starting from $2$) are accurate.
To show this, the standard method is to consider the whole collection $(t_k)_{0\leqslant k\leqslant12}$ simultaneously. Then, $$t_0=t_{12}=0,$$ and the (simple) Markov property of the random walk after one step yields $$t_k=1+\tfrac12(t_{k-1}+t_{k+1}),$$ for every $1\leqslant k\leqslant11$. Solving this $13\times13$ affine system yields the desired formula.
$\endgroup$ 0 $\begingroup$from random import random
import matplotlib.pyplot as plt
import numpy as np
from __future__ import division
% matplotlib inline
r=12
lt=[0]*r
x,y=[],[]
count,pos=0,0
flag=False
n=10000
lc=[]
for i in range(n): while not flag: count+=1 if random()<.5: pos+=1 else: pos+=-1 pos%=r lt[pos]=1 if sum(lt)==12: flag=True lc.append(count) count=0 flag=False lt=[0]*r pos=0
plt.plot(lc)
print np.average(lc)~67.04525 as far as I found
How: I just built an array of 12 0's and a random variable uniformly distributed and I just defined when this variable is less than .5 it steps clockwise one position or else the other way around. (turning 0 in the n-position into 1)
Counting the number of steps it took for all the 0's to become 1 and repeating this 10000 times y arrived that result.
Feel free to run this code at jupyter notebook online
$\endgroup$ 1
