12
$\begingroup$

Flora the frog starts at $0$ on the number line and makes a sequence of jumps to the right. In any one jump, independent of previous jumps, Flora leaps a positive integer distance $m$ with probability $\frac{1}{2^m}$. What is the probability that Flora will eventually land at $10$? (AMC 12A 2023/17)

Solution 1 says:

At any point, the probabilities of landing at $10$ and landing past $10$ are exactly the same. Therefore, the probability must be $\frac{1}{2}$.

If you apply any of solutions 2(recursion), 3 (combinations), or 7(induction), then solution 1 follows. But is there some elaboration of solution 1 that does not include 2, 3, or 7. Or some really elegant way to solve the question?

$\endgroup$
4
  • $\begingroup$ I think you are right, solution 1 is nonsense and would receive zero marks on an exam $\endgroup$
    – Andrew
    Commented Nov 12, 2023 at 5:16
  • $\begingroup$ There is nothing special about $10$. In Flora's progress rightwards, each position has a probability $\frac12$ of being landed on and $\frac12$ of not being landed on, independently of which previous or later positions are landed on: this is equivalent to the geometric distribution for the lengths of jumps. You could take any parameter for the geometric distribution $p(1-p)^{m-1}$ probability for the length of jumps and get an equivalent result: each position has the same probability $p$ of being landed on, independently of what happens at the other positions; here $p=\frac12$. $\endgroup$
    – Henry
    Commented Nov 12, 2023 at 15:28
  • $\begingroup$ @Henry I know the geometric distribution as the probability of the k^th trial being a success in k independent, identically distributed Bernoulli trials. How do I apply that in the context of this problem? Perhaps a full fledged answer? $\endgroup$
    – Starlight
    Commented Nov 12, 2023 at 16:59
  • $\begingroup$ @Starlight I have tried $\endgroup$
    – Henry
    Commented Nov 12, 2023 at 17:07

2 Answers 2

Reset to default
22
$\begingroup$

The idea in Solution 1, although not explicitly stated, is that if the frog has not reached or passed $10$, irrespective of how much further Flora needs to go, the probability that the next jump causes Flora to land exactly on $10$, is the same as the probability that Flora lands on a number strictly greater than $10$, because $$\frac{1}{2^k} = \sum_{m=k+1}^\infty \frac{1}{2^m}$$ for any nonnegative integer $k$. As a result, no matter the current position, the state of the frog is such that there is always an equal probability of stopping on $10$ or stopping beyond $10$. So for the initial position, before any jump has been made, the same must be true, so it must be $1/2$.

$\endgroup$
4
  • 4
    $\begingroup$ This solution is truly, next-level clever. $\endgroup$
    – Starlight
    Commented Nov 12, 2023 at 5:57
  • 3
    $\begingroup$ There is still some hidden induction here though. The probability of landing exactly on 10 (or whatever) and landing beyond it are equal, but they are not necessarily 1/2, since it's also possible to land on some integer less than 10. You need a slightly subtle inductive argument to show that that doesn't matter and it still comes out to 1/2 in the end. $\endgroup$
    – N. Virgo
    Commented Nov 13, 2023 at 8:58
  • $\begingroup$ @N.Virgo condition on the largest integer below 10 visited. From here the (unconditional) probabilities of next going to exactly 10 or higher than 10 were equal, so the probabilities conditioned on the next integer visited being at least 10, which clearly sum to $1$, are also equal. $\endgroup$
    – Especially Lime
    Commented Nov 13, 2023 at 9:21
  • 1
    $\begingroup$ I don't think there is induction. The proof simply says that the probability of definitely failing, and definitely winning, is the same at every step. $\endgroup$
    – Per Alexandersson
    Commented Nov 13, 2023 at 14:51
6
$\begingroup$

Based on comments:

There is nothing special about $10$ or even $\frac12$.

In the process which is Flora's progress rightwards, each position has a probability $p$ of being landed on and a probability $1-p$ of not being landed on, independently of which previous or later positions are landed on. The number of hits in an interval has a binomial distribution, and has a Bernoulli distribution for a single position. (This is the discrete equivalent of a Poisson process, where the number of hits in an interval has a Poisson distribution.)

This is equivalent to the geometric distribution for the lengths of jumps with probability $p(1−p)^{m−1}$ for a jump of length $m$, independent of other jumps. (In a continuous Poisson process you would get an exponential distribution for the length of jumps.)

In this question $p=1-p=\frac12$, so this is the probability of landing on position $10$ and also the probability of landing on any other particular position.

$\endgroup$
2
  • $\begingroup$ You have given the results, but not really shown they are arrived at. In particular, how do you establish that p=1-p=1/2 $\endgroup$
    – Starlight
    Commented Nov 12, 2023 at 17:57
  • 1
    $\begingroup$ @Starlight The constant ratio as $m$ increases is what marks this as geometric distribution. If $p(1−p)^{m-1}=\frac1{2^m}$ for all positive integer $m$ then $1-p=\frac12$ (consider the ratios) and so $p=\frac12$ too. $\endgroup$
    – Henry
    Commented Nov 12, 2023 at 18:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .