A ladybug lands on the 12 of a clock, and every second she moves randomly to a neighbouring number, either one step clockwise or one step counterclockwise. Each time she touches a number, we are colouring it red. What is the probability that the very last number to get coloured is the 6?
At first glance, it seemed like $6$, being the farthest point from $12$, should have a special probability. It also seemed like my intuition was wrong.
The simplest solution is to run the experiment twenty thousand times and see what happens.
IMPORTANT
No ladybugs were harmed during the making of this post.
Run the simulation a few times and see how she reaches the last number. It looks a bit random at first. Once you are tired of playing around, click Run 10000x to see the probability distribution emerge.
TIP
Spam the Run 10000x button.
The probability that $6$ is the last number colored is converging to $\sim 9.09%$ or $1/11$. So is the probability for every number!
Why?
To understand that, let’s look at what must happen for any number to be the last one visited.
Think of the clock as a cycle of $12$ nodes. The ladybug starts at $12$ (position $0$) and at each step moves to a neighboring number with equal probability.
For any number $k$ to be the last visited, the ladybug must:
- First reach one of its neighbors (either $k-1$ or $k+1$)
- Then travel all the way around the clock to reach the other neighbor
- Only then, finally, step onto $k$
This maps to the Gambler’s Ruin problem.
Picture a gambler who starts with $x$ dollars. Each round, she flips a fair coin: heads, she wins a dollar; tails, she loses one. She keeps playing until she either goes bankrupt ($0$ dollars) or hits her target ($n$ dollars).
The probability of reaching $n$ before $0$ is:
$$ P(\text{reach } n \text{ before } 0 \mid \text{start at } x) = \frac{x}{n} $$
Start with $1$ dollar and try to reach $11$? Your odds are $1/11$. Not great.
Our ladybug is doing the exact same thing: moving randomly with equal probability in either direction. Let’s apply this to position $6$.
Step 1: The ladybug must first reach either $5$ or $7$ (without visiting $6$).
By symmetry (the clock is symmetric around the $12$-$6$ axis), there’s a $50%$ chance she reaches $5$ first and $50%$ chance she reaches $7$ first.
Step 2: Say she reaches $5$ first (having visited $12, 1, 2, 3, 4$ along the way). For $6$ to be last, she must now go all the way around the clock ($5 \to 4 \to 3 \to 2 \to 1 \to 12 \to 11 \to 10 \to 9 \to 8 \to 7$), before stepping onto $6$.
From position $5$, she’s $1$ step away from $6$ and $10$ steps away from $7$ (going the long way). Sound familiar? She’s our gambler, starting with $1$ dollar and trying to reach $11$ before going broke. Using the formula:
$$ P(\text{reach 7 before 6} \mid \text{start at 5}) = \frac{1}{11} $$
Step 3: Combining both cases:
$$ \begin{aligned} P(6 \text{ is last}) &= P(\text{reach 5 first}) \cdot P(\text{reach 7 before 6} \mid \text{at 5}) \\[3ex] &\quad + P(\text{reach 7 first}) \cdot P(\text{reach 5 before 6} \mid \text{at 7}) \\[3ex] &= \frac{1}{2} \cdot \frac{1}{11} + \frac{1}{2} \cdot \frac{1}{11} \\[3ex] &= \boxed{\frac{1}{11}} \end{aligned} $$
The same argument works for every number (except $12$, of course, which is already visited at the start).
For any number $k$ to be last, you must reach one of its neighbors first, then go the long way around ($10$ steps) before taking the short way ($1$ step) to $k$. The “long way” is always $10$ steps, and the “short way” is always $1$ step, regardless of which number you’re considering.
Once you’ve visited one neighbor of a number, you’ve necessarily visited all the other numbers on that side of the clock. The structure is the same for every position.
$$ P(k \text{ is last}) = \frac{1}{11} \quad \text{for all } k \in {1, 2, 3, …, 11} $$
The positions aren’t symmetric in terms of distance from $12$ but they are symmetric in terms of the structure of the random walk reaching them last.
Thanks to the smart people on the YouTube comment section, without whom I would not have been able to piece this together.
As I was exploring solutions to this problem, I came across Austin Z. Henley’s blog post where he also made a simulation!