27
$\begingroup$

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!

$\endgroup$
  • 6
    $\begingroup$ This is just a variation of the Gambler's Ruin problem. $\endgroup$ – Joe Z. Mar 23 '15 at 22:14
  • 3
    $\begingroup$ +1; questions like this add to the site's arsenal, even if they are old hat for people like @JoeZ. Watch out for Martin nominating this for the Second Least Inspired Puzzle of the Year though! :-p $\endgroup$ – Rand al'Thor Mar 23 '15 at 23:18
  • 1
    $\begingroup$ @JoeZ. The game of Nim. $\endgroup$ – Rand al'Thor Mar 23 '15 at 23:29
  • 3
    $\begingroup$ @JoeZ. But, in this case, the gambler wins honey with probability 1! I wish I could be that gambler. $\endgroup$ – David Richerby Mar 24 '15 at 10:25
  • 2
    $\begingroup$ @DavidRicherby: No, my friend, there are people above the number line, betting on which spot the ant will reach first. They are the real gamblers. $\endgroup$ – Joe Z. Mar 24 '15 at 16:23

19 Answers 19

22
$\begingroup$

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.)

$\endgroup$
  • 7
    $\begingroup$ The doesn't make much sense. Let's say the honey was at points 9 and 10, and he's at 9 with probability $p$. According to your logic, $A = p \times 9 + (1 - p) \times 10 = 7$, so $p = 3$ and $1-p = -2$. But in truth $p = 1$ and $1-p = 0$. $\endgroup$ – Ypnypn Mar 24 '15 at 15:26
  • 4
    $\begingroup$ More generally, you're assuming that the new information that the ant was eating honey doesn't change the average. Why must this be the case? $\endgroup$ – Ypnypn Mar 24 '15 at 15:28
  • $\begingroup$ @Ypnypn In some cases the new information about eating honey changes the average; in some, it doesn't (an even clearer example of this is if the only honey is at 10). I'll check exactly why your change to the problem violates the optional stopping theorem and get back to you. The key point will be that, with the honey at 9 and 10, you didn't start between the two spots so you can never reach one of them. $\endgroup$ – David Richerby Mar 24 '15 at 15:52
  • $\begingroup$ This seems like the same thing I was saying in Ross Millikan's answer. $\endgroup$ – Joe Z. Mar 24 '15 at 16:31
  • $\begingroup$ @Ypnypn That's a good parody-example that shows you have to be careful with conditioning on stopping. David, have you have made any progress in resolving this? $\endgroup$ – xnor Mar 25 '15 at 21:03
13
$\begingroup$

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}$.

$\endgroup$
  • 3
    $\begingroup$ That first part is probably the best proof I've seen in a while that is mathematical but completely logical and easy to follow. +1 $\endgroup$ – mdc32 Mar 24 '15 at 1:12
  • $\begingroup$ "Therefore the probability is linear across the $x$ values..." I'm not sure what reasoning you're using, there. If, for example, the ant moves to the left with probability $\tfrac13$ and to the right with probability $\tfrac23$ then the equation becomes $p(x)=\tfrac13p(x-1)+\tfrac23p(x+1)$, which is still a linear equation but the solution is no longer linear: the ant is exponentially more likely to move a distance $d$ to the right than move the same distance to the left. $\endgroup$ – David Richerby Mar 24 '15 at 10:02
  • $\begingroup$ If wishes were horses, beggars would ride... Yes, if the situation were different, the outcome would also be different. It's the specific case where the probability in each direction is balanced that leads to a linear spread of probabilities. I'll try to clarify the answer. $\endgroup$ – Joffan Mar 24 '15 at 14:56
  • $\begingroup$ I think it may have gotten lost in the fray that the second "generic" answer is also rigorously correct. I've expanded on it here. $\endgroup$ – finsternis Apr 5 '15 at 17:27
11
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm awarding this answer the bounty for the crucial observation that the ant remains bounded, which combines with probability 1 of stopping to make the non-stopping possibility eventually negligible. This is the patch that makes the expectation/fairness proof work. Meelo's answer also makes much the same argument. $\endgroup$ – xnor Apr 7 '15 at 1:42
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was thinking that too, but I couldn't figure out how to make it mathematically rigorous. $\endgroup$ – Joe Z. Mar 23 '15 at 23:41
  • $\begingroup$ If you wanted to think about it in terms of the ant, you could say that the ant is already $7/10$ of the way to the second point already, so it has a $7/10$ probability of going there with this randomized process. $\endgroup$ – Joe Z. Mar 23 '15 at 23:42
  • 1
    $\begingroup$ @JoeZ.: I don't find that convincing, as I could conceive that the probability would be proportional to the inverse square of the distance you want to go (as a random walk). $\endgroup$ – Ross Millikan Mar 24 '15 at 0:21
  • 1
    $\begingroup$ It may be worth making explicit that "fair" = "expected value is 0" = "expected end money of one player is 3" - it took me a second to see that this is rigorous, in any case. $\endgroup$ – Milo Brandt Mar 24 '15 at 0:21
  • $\begingroup$ @RossMillikan: I suppose that's true. And it was Meelo's comment that made me see how the reasoning goes. $\endgroup$ – Joe Z. Mar 24 '15 at 0:22
7
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ This isn't a "slick short solution" by any stretch of the imagination! ;-) $\endgroup$ – Rand al'Thor Mar 24 '15 at 10:12
  • 1
    $\begingroup$ Simulation is a smart first step when trying to analyze this sort of system. Once you have a decent idea what the answer is, it's much easier to prove it! $\endgroup$ – David Richerby Mar 24 '15 at 10:17
  • 1
    $\begingroup$ I think the OP was looking for a slick short mathematical solution - probably the one in @DavidRicherby's answer. This answer is slick and short if you have a computer, but imagine you're on a desert island and you haven't got a computer to do the grunt work of calculation for you! ;-) I'll +1 anyway, so that I don't look like too much of a mathematician-looking-down-his-nose-at-programmers snob... $\endgroup$ – Rand al'Thor Mar 24 '15 at 10:21
  • 1
    $\begingroup$ @Akiiino It seems unlikely that "0.300027375 and 0.699972625" is the real answer. So, first, you're using your big human pattern-spotting brain to say "I bet it's really 0.3 and 0.7," which is more based on liking round numbers than on mathematics. Second, you've not demonstrated that running the thing ten million times produces a good estimate of the true answer: you've not demonstrated that the answer has stabilized around those numbers for example. Third, even stabilization isn't necessarily enough: for example, if you compute the first ten million terms of... $\endgroup$ – David Richerby Mar 24 '15 at 10:22
  • 1
    $\begingroup$ ... $\sum_{n\geq 0}\tfrac1n$, it'll look like it's stabilized but, actually, the sum diverges to infinity. So, what you've done is provided some good evidence that the answer is likely to be 0.3 and 0.7 but you've not actually shown it really is that. $\endgroup$ – David Richerby Mar 24 '15 at 10:23
6
$\begingroup$

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}$.

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I feel like there should be a solution more elegant than this one. Off to Google! $\endgroup$ – Joe Z. Mar 23 '15 at 23:34
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The elegant method is to use a martingale and the optional stopping theorem. See my answer. $\endgroup$ – David Richerby Mar 24 '15 at 9:58
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ My apologies for posting 3 answers to one question in half an hour. I liked the question and, unfortunately, came up with three separate answers that didn't feel related enough to live together. I swear I'm done now! $\endgroup$ – Milo Brandt Apr 4 '15 at 21:45
2
$\begingroup$

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! ;-)

$\endgroup$
  • $\begingroup$ How exactly does this eliminate the problem for Ypnypn's example? Note that in that example, the ant still stops at the honey with probability 1, as 1D random walks do. $\endgroup$ – xnor Apr 2 '15 at 23:52
  • $\begingroup$ @xnor Because in this example with general $m$ and $n$, it's more clear that knowing the ant is at one of these two arbitrary points (which could just as easily be replaced with any other points one on either side of $a$) doesn't change its average position. I know the honey probability is still 1, but doesn't the generalisation make a difference to the argument? $\endgroup$ – Rand al'Thor Apr 3 '15 at 9:32
1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thanks; I did consider tabulating the process but I didn't do it immediately so I would probably never have bothered. $\endgroup$ – Joffan Apr 5 '15 at 18:12
  • $\begingroup$ Thanks, that looks much nicer with the realignment of equations. $\endgroup$ – finsternis Apr 6 '15 at 22:11
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to the site. The MathJax tutorial will teach you all about embedding formulas. $\endgroup$ – dmitch Apr 3 '15 at 16:55
0
$\begingroup$

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".

$\endgroup$
0
$\begingroup$

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}]$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please edit with proper LaTex :-) $\endgroup$ – ABcDexter Sep 8 '15 at 10:37
-1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Why do steps correspond to probabilities? $\endgroup$ – xnor Apr 3 '15 at 9:02
  • $\begingroup$ that's not an answer... i think that's probably what everyone noticed. $\endgroup$ – the4seasons Apr 4 '15 at 14:20
-3
$\begingroup$

Lets take a logical / mathematical approach

Assuming the ant' current position is 7, we'll count the probability of reaching 10.

  1. After 1st move, total options for its current position will be 2 -> 6 or 8 (it can go L/R from 7).
  2. After 2nd move, total options for its current position will be 4 -> (5,7) or (7,9)
  3. After 3rd move, total options for its current position will be 8 -> (4,6) or (6,8) or (6,8) or (8,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:

  1. In first move (from 7), it may go left or right (towards 10). chances of moving towards 10 = 1/2 (50%)
  2. In second move (from 8), it may go left or right (towards 10). chances of moving towards 10 = 1/2 (again 50%)
  3. In third move (from 9), it may go left or right (towards 10).
    chances of moving towards 10 = 1/2 (again 50%)

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).

$\endgroup$
  • $\begingroup$ But an ant doesn't have to get to the honey directly; it could move back and forth. $\endgroup$ – xnor Apr 3 '15 at 9:02
  • $\begingroup$ Good point. 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. $\endgroup$ – Raúl Apr 3 '15 at 9:09
  • 1
    $\begingroup$ Sorry, but this is wrong. The chance of reaching honey point 0 is 3/10 and the chance of reaching honey point 10 is 7/10 - see the other answers, which are correct but haven't yet reached the standard of rigor and/or slickness sought by xnor. $\endgroup$ – Rand al'Thor Apr 3 '15 at 9:55
  • 2
    $\begingroup$ @Raúl Well if you want us to pick apart the logic, here's a start. "In our case, probability of ant (starting @ 7 &) remaining at 7 after 4 moves = 1/2 * 1/2 * 1/2 * 1/2 = 1/16" -- completely false. You're ignoring the multiple paths the ant can take back to its origin--specifically 4C2 of them (llrr, lrrl, rrll, rllr, lrlr, rlrl). So after 4 moves, the ant has 6/16 chance of being back where it started. $\endgroup$ – dmitch Apr 4 '15 at 4:12
  • 1
    $\begingroup$ @Raúl yes, the probability the ant reaches square 10 in three moves is 1/8. But the question is asking what's the probability the ant reaches square 10 before square 0 in any number of moves. So to that 1/8 you have to add the probability it reaches square 10 in exactly 5 moves, and the probability it reaches square 10 in exactly 7 moves, and infinitely many more. And if that's not complicated enough, once you reach 17 moves, you have to start subtracting out the probability that it went to square 0, then to square 10 (because 17 moves is enough to go straight to 0, then back to 10). $\endgroup$ – dmitch Apr 4 '15 at 6:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.