# A frog from k lilypad either jumps to k+1 or k+2 lilypad. Find the probability that it reaches pad 7 if it is initially at pad 1.

Lilypads numbered $$1,2,3,\cdots$$ lie in a row in a pond. A frog is initially on pad $$1$$. From any pad $$k$$, the frog will jump to either pad number $$k+1$$ or $$k+2$$ with equal probability of $${1\over 2}$$. The probability that the frog visits pad $$7$$ is $${m\over n}$$ where ($$m,n$$) = $$1$$, Evaluate $$n-m$$.

Well I wanted to know as to how to attack this problem. I mean Probability = Number of favorable outcomes / Total Outcomes. What is the total outcomes here ?? What are the favorable outcomes ?? How to count them ??

• I suggest working recursively. A good path to $7$ must either be a good path to $6$ followed by one, or a good path to $5$ followed by two. And so on.. If needs be, you can simply enumerate all the good paths that way.
– lulu
Dec 30 '20 at 12:18
• You have a simple recursive relation of $P(K), P(K-1), P(K-2)$ Dec 30 '20 at 12:21

I might be wrong. It's happened before (once).

$$P($$ reaches pad $$7)$$ = $$1 - P(6 \to 8 \ |$$ reaches pad $$6)$$

$$\color{red}{= 1 - \frac12P(\text{ reaches pad 6 })}$$ [because assuming it reaches pad $$6,$$ it has $$\frac12$$ chance of landing on $$8$$.]

$$= 1 - \frac12(\ 1 - P(5\to7\ |$$ reaches pad $$5)\ )$$

$$\color{red}{ = 1 - \frac12(\ 1 - \frac12 P( \text{reaches pad } 5)\ )}$$

$$= 1 - \frac12(\ 1 - \frac12(\ 1 - P(4 \to 6|$$ reaches pad $$4\ )\ )\ )$$

$$\color{red}{= 1 - \frac12(\ 1 - \frac12(\ 1 - \frac12P(\text{reaches pad 4})\ )\ )}$$

$$= ...$$

$$\color{red}{= 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12P\left(\text{reaches pad 1}\ \right)\ \right)\ \right)\ \right)\ \right)\ \right)}$$

$$= 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12 \times 1\ \right)\ \right)\ \right)\ \right)\ \right)$$

$$= \frac{43}{64}$$.

Since $$(n,m) = (64,43) = 1,\ n - m = 64 - 43 = 21.$$

• This would agree with David Quinn's method if David Quinn had done it right. Dec 30 '20 at 13:31
• Also the same answer as jlammy, the Markov Chain guy. Dec 30 '20 at 13:34

It might help to model the process as a Markov Chain (though this isn't necessary).

Let $$p_n$$ be the probability that the frog hits lilypad $$n$$. Then $$p_n=\frac{1}{2}\left(p_{n-1}+p_{n-2}\right)$$, and $$p_1=1$$, $$p_2=\frac{1}{2}$$. At this point, you can either pump the recursion for $$n=7$$, or solve the relation to get $$p_n=\frac{2}{3}+\frac{1}{3}\left(-\frac{1}{2}\right)^{n-1}$$. Either way, you get $$p_7=\frac{43}{64}$$.

We can enumerate the number of pads the frog leaps over to get to pad 7:

Case 1$$1+1+1+1+1+1$$ 1 permutation, $$p=(\frac{1}{2})^6$$

Case 2 $$1+1+1+1+2$$ 5 permutations, $$p=5\times(\frac{1}{2})^5$$

Case 3 $$1+1+2+2$$

6 permutations, $$p=6\times(\frac{1}{2})^4$$

Case 4 $$2+2+2$$

1 permutations, $$p=(\frac{1}{2})^3$$

Total $$=\frac{43}{64}$$

• Case 4 should be $p=4\times(\frac12)^4$, I think. Dec 30 '20 at 13:08
• More importantly, the total distance from pad $1$ to pad $7$ is $6$, not $7$... Dec 30 '20 at 13:14
• Thanks @TonyK I will fix it Dec 30 '20 at 13:33