Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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!
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.)
From $x=7,$ there is an equal chance of reaching $x=4$ and $x=10$.
(score $\frac{1}{2}$ for the $10$ drop).
From $x=4$, there is an equal chance of reaching $x=3$ and $x=5$.
From $x=5$, there is an equal chance of reaching $x=0$ and $x=10$.
(score $\frac{1}{8}$ for the $0$ drop and for the $10$ drop $\to \frac{5}{8}$).
From $x=3$, (now at $\frac{1}{4}$ chance) the probabilities are reversed compared to $x=7$.
(score $\frac{5}{32}$ for the $0$ drop $\to \frac{9}{32}$ and score $\frac{1}{32}$ for the $10$ drop $\to \frac{21}{32}$).
The remaining probability $\frac{2}{32}$ is assigned to $x=7$, so discard and rebase:
Probability of reaching $0$ is $\frac{9}{30} = \frac{3}{10}$ and probability of reaching $10$ is $\frac{21}{30} = \frac{7}{10}$
This is NOT what I would call slick..... so probably not the answer you're looking for. :-)
A more generic answer:
For an ant at each (mid) position $x$, the probability of reaching, say, the high-number end $p(x)$ can be calculated after one step as $p(x) = 0.5 (p(x-1) + p(x+1))$. So each probability is the average of the adjacent position probabilities.
Since we know that $p(0)=0$ and $p(10) = 1$, we can show the linear nature of the probabilities in between as follows:
Set $p(1) = a$. Then because of the average effect above, we can see that $p(2)= 2a, p(3)= 3a, \ldots, p(10)=10a=1$. So $a=0.1$ and the probability of reaching the high end is $p(x)=0.1x$ - in this specific case, p(7) = 0.7 chance of reaching the high end and $1-0.7=0.3$ chance of reaching the low end.
This translates into a general solution for any length of line and any start position; if the high-end drop is at $x=52$ and the ant starts at $x=37$, the probability of reaching the high end is $\frac{37}{52}$ and the probability of reaching the low end is $\frac{15}{52}$.
Lemma: the probability that the ant has stopped converges to 1. Proof: if the ant moves right 10 times in a row, it must stop. Waiting for 10N moves gives N independent chances for this to happen. $\square$
The ant's expected (i.e. average) position remains at 7. Therefore, at any point in time,
P(ant has stopped)*E(ant's position | ant has stopped) + P(ant is still moving)*E(ant's position | ant is still moving) = 7.
The lemma implies P(ant has stopped) converges to 1, thus P(ant is still moving) converges to 0. Also, E(ant's position | ant is still moving) is bounded inside [0,10]. This is the answer to Ypnypn's objection - if the ant started outside the boundaries, then this expected value would no longer necessarily be bounded, and this step of the argument would fail.
But it is bounded, so the term P(ant is still moving)*E(ant's position | ant is still moving) converges to 0. Therefore, the other term P(ant has stopped)*E(ant's position | ant has stopped) converges to 7. The result follows.
The simple approach is to see it as a coin flipping game where one player starts with $3$, the other with $7$, and the winner of each flip collects $1$ from the loser. As each flip is fair, the game is fair. As the person who starts with $3$ wins with $10$, he must win $0.3$ of the time.
Yes !! This is not a proof.
But, as an proxy for a mathematical solution (of which there are several already) we could take a look to a Python script which may test many iterations of a model of this problem. It produced probabilities closer to 0.3 and 0.7 for increasing number of tests. The code of the script goes as follows:
import random
b = 0
e = 0
coord = 7
lower = 0
upper = 10
iters = 0
error = 0
doiters = 10**6 # Number of trials (ant stopped).
print( "testing for %15s loops" % ('{:,}'.format(doiters)))
while iters < doiters:
# If the limit is changed to +1 the loop
# below this one will reflect the errors.
while coord > lower and coord < upper:
coord += random.randint(0, 1)*2-1
# If the ant has reached any of the limits,
# it has stopped, count each of the possible stop points.
if coord == upper:
e += 1
elif coord == lower:
b += 1
else:
error += 1
coord = 7
iters += 1
print "Errors in count", error
endline="The ant stopped at %3d : %3.6f%% and at %3d : %3.6f%%"
print( endline % ( lower, float(b)/iters, upper, float(e)/iters ) )
After several test runs, which oscillated around 0.3 and 0.7, the longest test for 100.000.000 iterations (several minutes) produced an output of:
The ant stopped at 0 : 0.300027375 and at 10 : 0.699972625
One abstract and fun way to attack this is to consider the following:
Suppose there is an ant on the real line, moving in some continuous manner such that it is equally likely to move upwards or downwards - i.e. any path they could take is equally likely as the reflection of that path over their current position. Moreover, suppose that the probability that they never pass through $0$ or $1$ is zero.
Clearly, our current scenario falls under this category, since if we only care about what order the path passes through points of the form $\frac{a}{10}$, the symmetries still guarantee it will pass from there to $\frac{a+1}{10}$ or $\frac{a-1}{10}$ with equal probability, ignoring repetitions of $\frac{a}{10}$ - so our problem is, in a sense, a quotient of the one defined above.
If we let $P(x)$ for $x\in[0,1]$ be the probability that, if the ant starts at $x$, the ant will reach $1$ before it reaches $0$, then we clearly have: $$P(0)=0$$ $$P(1)=1$$ and by the symmetry and the fact that almost all paths pass one of these numbers $$P\left(\frac{1}2\right)=\frac{1}2.$$ However, then we can use symmetry again to suppose that if the ant starts at $x=\frac{1}4$, it will equally likely reach $\frac{1}2$ and $0$ - hence the probability it will reach $1$ first is the average of $P(0)$ and $P\left(\frac{1}2\right)$ which is $\frac{1}4$. We can similarly find that $P\left(\frac{3}4\right)=\frac{3}4$. In fact, we can repeat this to show that if $x$ is a dyadic rational, then $P(x)=x$.
The dyadic rationals are dense and $P$ is obviously continuous hence $P(x)=x$ and, for this particular case, $P(\frac{7}{10})=\frac{7}{10}$.
The ant will reach 0 with a probability of $\frac{3}{10}$, and 10 with a probability of $\frac{7}{10}$.
Let $p(n)$ be the probability of reaching $0$ from point $n$. By symmetry, we see that for small $x$,
$p(n) = \frac{p(n-x)+p(n+x)}{2}$
That is, the chance of reaching 0 from a point is the average of the chance of reaching 0 from any two equidistant points.
So
$p(7) = \frac{p(4)+p(10)}{2}$ = $\frac{p(4)}{2}$
and
$p(4) = \frac{p(3)+p(5)}{2}$ = $\frac{p(3)+\frac{1}{2}}{2}$
But again by symmetry, we can see that
$p(n) = 1 - p(10 - n)$
So
$p(7) = 1 - p(3)$
Therefore,
$p(4) = 2*p(7) = \frac{p(3)+\frac{1}{2}}{2}$
$2*p(7) = \frac{1-p(7)+\frac{1}{2}}{2}$
$4*p(7) = \frac{3}{2} - p(7)$
$5*p(7) = \frac{3}{2}$
$p(7) = 3/10$
The answer is that the ant will reach the leftmost spot with a probability of $\frac{3}{10}$, and the rightmost spot with a probability of $\frac{7}{10}$.
This is an instance of the Gambler's Ruin problem. According to the problem's statement, the probability of an ant reaching a point of distance $d_1$ compared to another point of distance $d_2$ is $\frac{d_2}{d_1 + d_2}$. Generally this formula is obtained by evaluating the limit of a Markov chain (as the Gambler's Ruin problem is usually used as a classical example of an application of Markov chains in the first place), but there seems to be a more elegant way of resolving this specific case as hinted by xnor.
Other answerers seem to have given more elegant solutions, so I will leave this one as is.
Suppose the odds of reaching a specific end from point x are f(x). From point x, a random move takes you to x-1 50% of the time and x+1 50% of the time. So f(x) = f(x-1)/2 + f(x+1)/2. That is, your odds at a given point are the average of the odds for the points either side. Since the points are evenly spaced, f(x) must therefore be linear.
One end has a chance of zero (you already found the other honey drop) and the other has a chance of one (you have made it). Since the line conveniently starts at x=0, your chances of reaching the high end are proportional to your distance along the line, and your chances of reaching the low end are whatever remains from 1.
From x=7 therefore, 0.7 chance of reaching +10, and 0.3 chance of reaching 0.
As has previously been pointed out, given that that, at every step, the ant moves left or right with equal probability (or not at all if they find honey), it is clear that the expected position of the ant after $n$ steps equals the expected position after $n-1$ steps, and, by induction, the initial position of the ant, which is $7$.
If we let $p_i(n)$ be the probability that the ant is at position $i$ after $n$ steps, then we can take the expected value as: $$7=\sum_{i=0}^{10}i\cdot p_i(n).$$ Then, if we let $P(n)=p_1(n)+p_2(n)+\ldots +p_9(n)$, we can bound the above as (noting that there was a $0\cdot p_0(n)$ term from the sum which we dropped since it it is $0$): $$10\cdot p_{10}(n) + 1\cdot P(n) \leq 7 \leq 10\cdot p_{10}(n) + 9\cdot P(n)$$ or alternatively: $$P(n)\leq 7-10\cdot p_{10}(n) \leq 9P(n).$$ However, from any position between $0$ and $10$, the probability of the ant finding honey in $5$ steps or less is at least $\frac{1}{16}$, it is clear that $P(n+5)<\frac{15}{16}P(n)$ and hence $P(n)$ goes to $0$ as $n$ goes to $\infty$. The bound above squeezes the middle term and implies then that $$\lim_{n\rightarrow\infty}7-10\cdot p_{10}(n)=0$$ which rearranges to the desired result: $$\lim_{n\rightarrow\infty}p_{10}(n)=\frac{7}{10}$$ that is, after arbitrarily many steps, the probability that the ant finds the honey at $x=10$ is $\frac{7}{10}$. Since the ant almost certainly stops, the probability that they find the honey at $0$ is $\frac{3}{10}$.
This post solely exists to provide formal & elementary justification of the proof presented in Ross Milikan and David Richerby's answers. One may note that my argument relies only on the fact that the positions of the ant remain bounded - that is, we don't have to worry about probabilities going to zero but their influence on the expected value not going to zero - like, if there was only honey at $x=10$, the ant would almost surely stop there, despited their expected position being $7$ - the problem would be that very large negative positions would be possible, with small probability, and this would drag the expected value down. However, as it happens, the boundedness of the domain means that we cannot spread out an arbitrarily small probability to create arbitrarily large change in expected value, hence the argument holds.
A slick solution is to let $P(n)$ be the probability that the ant finds the honey at $x=10$ if it starts at position $n$. Clearly $P(0)=0$ and $P(10)=1$. Moreover, since the ant moves left or right with equal probability, it follows that, for $n$ strictly between $0$ and $10$: $$P(n)=\frac{1}2\left(P(n-1)+P(n+1)\right)$$ which is equivalent to saying that $(n-1,P(n-1))$, $(n,P(n))$, and $(n+1,P(n+1))$ are collinear. Given that, for instance $(n-2,P(n-2))$ and $(n+1,P(n+2))$ are both on the line of $(n,P(n))$ and $(n-1,P(n-1))$, it follows that all four of those points are collinear - and quickly from there that all the $(n,P(n))$ for $n$ between $0$ and $10$ (inclusive) line on a single line - and thus on the line containing $(0,0)$ and $(10,1)$. Thus $P$ is linear and $$P(n)=\frac{n}{10}$$ and the probability that the ant finds the honey at $x=10$ is: $$P(7)=\frac{7}{10}$$
Here's a generalisation of David Richerby's answer, which I believe eliminates the problem pointed out by Ypnypn.
Let's say the ant starts at point $a$ on the real line, and we're looking at the finite interval $[a-m,a+n]$ for some real numbers $m,n$. Eventually the ant must break out of this interval (with probability 1); on which side is it more likely to do so? At the moment when it first breaks out, it's still at point $a$ on average (because it always is), but we know it's either at point $a-m$ or point $a+n$ (with probabilities $p$ and $1-p$, say). So $p(a-m)+(1-p)(a+n)=a$, which $\Rightarrow a+n-p(m+n)=a\Rightarrow p=\frac{n}{m+n}$.
Specifically, in our problem we have $a=7,m=7,n=3$. So when the ant breaks out of the interval $[0,10]$ (i.e. when it reaches honey), it has a 30% chance of doing so at $0$ and a 70% chance of doing so at $10$.
Is this slick and rigorous enough for you, xnor? I hope so, because I've just spent a long time pondering the problem in order to come up with this! ;-)
I'm expanding Joffan's second answer here to highlight it as a different approach that is still completely rigorous, uses only basic algebra, and handles the conditional stopping issue. (I'm not saying it's better than the other correct answers.)
Let $p_i$ denote the probability of reaching the high end before the low end starting from position $i$. We know $p_0 = 0$ and $p_{10} = 1$ and we want to find $p_7$. We also know that $p_i = \tfrac{1}{2}(p_{i-1}+p_{i+1})$ for $1 \le i \le 9$. Let's multiply that last one by 2 and rearrange to get $p_{i+1} = 2p_i - p_{i-1}$.
We could solve this linear recurrence directly with some machinery (or induction) but instead let's use basic algebra to rewrite everything in terms of $p_1$. At each step I'm just using the recurrence and things we know up to that point:
$$\begin{array} \\ p_2 &= 2p_1 - p_0 &= 2 \cdot p_1 - 0 &= 2p_1 \\ p_3 &= 2p_2 - p_1 &= 2 \cdot 2p_1 - p_1 &= 3p_1 \\ p_4 &= 2p_3 - p_2 &= 2 \cdot 3p_1 - 2p_1 &= 4p_1 \\ p_5 &= 2p_4 - p_3 &= 2 \cdot 4p_1 - 3p_1 &= 5p_1 \\ p_6 &= 2p_5 - p_4 &= 2 \cdot 5p_1 - 4p_1 &= 6p_1 \\ p_7 &= 2p_6 - p_5 &= 2 \cdot 6p_1 - 5p_1 &= 7p_1 \\ p_8 &= 2p_7 - p_6 &= 2 \cdot 7p_1 - 6p_1 &= 8p_1 \\ p_9 &= 2p_8 - p_7 &= 2 \cdot 8p_1 - 7p_1 &= 9p_1 \\ p_{10} &= 2p_9 - p_8 &= 2 \cdot 9p_1 - 8p_1 &= 10p_1 \\ \end{array} $$
Now we use the last line along with $p_{10} = 1$ to conclude that $p_1 = \tfrac{1}{10}$ and thus $p_7 = \tfrac{7}{10}$.
Re: David Richerby's answer and the apparent exception provided by Ypnypn.
The posed question is a markov chain with absorbing states at 0 and 10. In Ypnypn's example, of 'what if the honey positions were at 9 and 10', the absorbing states of the markov chain change to 9 and 10. Since the starting position is to the left of both the absorbing states, there is now only one absorbing state (it becomes impossible to reach x = 10 since it terminates once it reaches x = 9), and David Richerby's solution does not generalise to this case.
A general solution (x = starting position, l = leftmost honeydrop, r = rightmost honeydrop, where l is less than or equal to r).
There are three possibilities. x < l (one absorbing state: l), x > r (one absorbing state: r) or l < x < r (two absorbing states: l and r). The first case (case 1) is the one posed by Ypnypn, while the latter (case 3) is the case posed in the original question.
Case 1 (x < l): given sufficient time, the probability of reaching l is 100% (since l is the only absorbing state).
Case 2 (x > r): given sufficient time, the probability of reaching r is 100% (since r is the only absorbing state).
Case 3 (l < x < r): given sufficient time, the probability of reaching r equals (x-l)/(r-l) and the probability of reaching l equals 1 - ((x-l)/(r-l)).
So, in this particular case, as others have stated, the probability of reaching 10 is (7-0)/(10-0) = 70% and 0 is 1 - 0.7 = 30%.
I can't find any way to embed formulas so my apologies for the aesthetically unpleasing answer.
The answer has been given many times over so here's my thought process:
If the ant is at position X between positions A and B with an equal chance to travel in either direction...
A - - - - - - X - - B
... then the odds of reaching the end of either side first is the ratio of the length of that side to the length of the entire line. For the AXB example, that means the odds of reaching A first is given by $$\frac{(B-A)-(X-A)}{(B-A)}$$
which simplifies to just $$\frac{B-X}{B-A}$$
and the odds of reaching B first is therefore $$[1-\frac{B-X}{B-A}]$$
Here's an elementary proof that the probability the ant reaches the honey is one
First an estimate:
We have $\frac{1}{2^{2n}}{2n \choose n} = \frac{(2n)!}{2^n n! 2^n n!} = \frac{1\cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 4 \cdot 6 \cdots (2n)} = \prod_{k=1}^{n} \frac{2k-1}{2k}$
Let's estimate this. First note that $\prod_{k=1}^{n} \frac{2k-1}{2k} \leq \prod_{k=1}^{n} \frac{2k}{2k+1}$
Therefore $\left(\prod_{k=1}^{n} \frac{2k-1}{2k}\right)^2 \leq \prod_{k=1}^n \frac{2k-1}{2k} \prod_{k=1}^{n} \frac{2k}{2k+1} = \prod_{j=1}^{2n} \frac{j}{j+1} = \frac{1}{2n+1}$
Therefore $\frac{1}{2^{2n}} {2n \choose n} \leq \frac{1}{\sqrt{2n+1}}$ (In fact, by Stirling's formula, it goes like $\frac{1}{\sqrt{n\pi}}$)
Now consider an ant on the number line as in the question, but with no stopping places. I'll show that it must at some point exit any given finite section with probability one. This shows the ant in the question reaches the honey with probability one (because it cannot have a nonzero probability of staying within $[1,9]$ for all time).
The probability that after $2n$ steps the Ant is at a specific position $2k$ steps away from its original position is $\frac{1}{2^{2n}} {2n \choose n-k} \leq \frac{1}{2^{2n}}{2n \choose n}$ (note you must have $n+k$ steps in one direction and $n-k$ steps in the other direction to get there).
Therefore the probability you are within $2M$ steps of your starting position after $2n$ steps ($2M+1$ possibilities) is at most $\frac{2M+1}{\sqrt{2n+1}}$. Fixing $M$, this gets arbitrarily small as $n$ gets large. Thus you must exit any finite box with probability one.
Now a simple expected value of the position argument as in David Richerby's or Ross Millikan's post gives the answer to the question.
Well, the probabilities were already counted, so I'll just post my "slick short solution".
The ant starts at $7$. It will move left or right with $1/2$ probability and it will take him $3$ steps to reach $10$ ($8-9-10$) and $7$ steps to reach $0$ ($6-5-4-3-2-1-0$). So probabilities are indeed $30\%$ to reach $0$ and $70\%$ to reach $10$
In the interest of a simple, elegant solution:
Let $P(x)$ be the probability that the ant will stop at 10 before stopping at 0 given an initial starting point of $0\le x\le10$.
$P(0) = 0$ because it's already at 0.
$P(10) = 1$ because it's already at 10.
$P(5) = \frac12$ because the ant is equally likely to move in either direction, and both stopping points are equally far apart, neither can be favored.
$P(x)$ is a curve through these three co-linear points. Occam's razor says that $P(x)$ is a line segment starting at the origin with slope $\frac1{10}$. Therefore $P(7) = \frac7{10}$.
or
$P(x)$ is a step function with equal sized steps because the ant makes equal length steps. Therefore $P(7) = \frac7{10}$.
Permission is hereby given to reuse this framework in another answer with a slightly more rigorous proof than any above. I'm making this CW in case anyone else wants to chime in with a similarly spirited "proof".
Lets take a logical / mathematical approach
Assuming the ant' current position is 7, we'll count the probability of reaching 10.
In above all possible combinations - the ant, in 1 scenario out of 8, reached 10 from 7.
P(E) = n(E)/n(S) = 1/8
Similarly, probability of moving to 0 from 7 = 1/128
(Previous explanation)
Probability (p) of a move at any particular side (L/R) = 1/2
p of next move, at any particular side = 1/2 .... and so on ...
from 7 to 10 - it needs three moves - and as these events are mutually exclusive -> probability = 1/2 * 1/2 * 1/2 = 1/8 (or 0.125)
from 7 to 0 - probability = 1/2*1/2*1/2*1/2*1/2*1/2*1/2 = 1/128 (or 0.0078125)
EDIT - I am clarifying a bit on the doubt raised by @xnor:
One remote possibility - the ant can go to 8 in first move, return back to 7 in second move - which will make it move in SHM (Simple Harmonic Motion) and thus even after a million moves - it would be be still at 7.
That's where the Probability comes into picture. Probability NEVER guarantees that an event will occur. e.g. In the dice game, it is entirely possible that user can keep throwing dice again and again for an hour - but he doesn't get a 6 (or any number for that matter) in first 100 throws ........ probability of that will be (5/6)(5/6)(5/6)... (total 100 times) = 0.0000000100622
As the selection of direction of move is mutually exclusive (.. left (-1) or right (+1), with 'equal chance'..), calculation will be as follows:
Here we just calculate the odds of achieving the result. THIS IS HOW PROBABILITY WORKS. On negative/impractical side, its entirely possible that ant keep moving left/right whole of its life and never reach a honey point.
for total probability of reaching to point - we will multiply all three ... total probability = 1/8 = 0.125
Means for moves made, chances of not reaching honey point (10) are 124 out of 125, chances of reaching honey point is 1 out of 125 (Note - this works on basis of Permutations and Combinations - you can get it verified by a maths professor).
