An ant walks on a number line, starting at location $x=7$. Each second, it randomly moves one space either left ($-1$) or right ($+1$), with equal chance. At $x=0$ and $x=10$ are drops of honey; the ant stops moving when it reaches one of them. What are the respective probabilities of it stopping at each one?
There's multiple ways to compute the answer, but I like this as a puzzle because there's a slick short solution. So, try to find the cleanest solution you can!
Answer
The elegant solution is to use what's called a martingale and the optional stopping theorem. Doing this formally requires a little care but, somewhat informally, we can reason as follows.
Ignore for the moment the fact that the ant stops when he finds the honey and allow him to move as far to the left and right as he wants. In this case, after any number of steps, the ant is, on average, still at position 7. So, even if you're not watching the ant, any time I say "Now!", you can still say "On average, he's at position seven."
Now, suppose I reveal to you that the ant was eating honey when I said, "Now!" On average, he's still at position 7. With some probability $p$, he's at 0 and with probability $1-p$, he's at 10. His average position is given by $A=p\times0 + (1-p)\times 10=7$. We can now solve for $p$.
Solution. The ant is at 0 with probability $\tfrac{3}{10}$ and at 10 with probability $\tfrac{7}{10}$.
(For a more rigorous justification of why we can safely condition on the ant having stopped, see Lopsy's answer.)
No comments:
Post a Comment