[Math] Random Walk on Clock Hands

markov chainsprobability distributionsprobability theoryrandom walkuniform distribution

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.

Best Answer

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.

Related Question