Can You Hop to the Lily Pad?

Fiddler

From Michael Coffey comes a hoppin’ good puzzle:

You are a frog in a pond with four lily pads, marked “1” through “4.” You are currently on pad 2, and your goal is to make it to pad 1. From any given pad, there are specific probabilities that you’ll jump to another pad:

• Once on pad 1, you will happily stay there forever.

• From pad 2, there’s a 1-in-2 chance you’ll hop to pad 1, and a 1-in-2 chance you’ll hop to pad 3.

• From pad 3, there’s a 1-in-3 chance you’ll hop to pad 2, and a 2-in-3 chance you’ll hop to pad 4.

• Once on pad 4, you will unhappily stay there forever.

Given that you are starting on pad 2, what is the probability that you will ultimately make it to pad 1 (as opposed to pad 4)?

Solution

Let $P_k$ be the probability the frog lands on pad $k$ after the starting position.

1. $P_1 = \frac{1}{2} + \frac{1}{2}P_2$

2. $P_2 = \frac{1}{3}P_3$

3. $P_3 = \frac{1}{2} + \frac{1}{2}P_2$

4. $P_4 = \frac{2}{3}P_3$

Equation 1 yields $P_2 = 2P_1 - 1$.

Substituting that into Equation 2 yields $P_3 = 3(2P_1 - 1)$.

Substituting that and $P_4 = 1-P_1$ into Equation 4:

\begin{align*} 1-P_1 &= \frac{2}{3}\big(3(2P_1 - 1)\big) \\ 1-P_1 &= 4P_1 - 2 \\ 3 &= 5P_1 \\ \end{align*}

Answer

The probability that the frog ultimately lands on lily pad 1 is

$$\boxed{\frac{3}{5}}$$

Extra Credit

From Michael Coffey also comes some Extra Credit:

Once again, you are a frog in a pond. But this time, the pond has infinitely many lily pads, which are numbered “1,” “2,” “3,” etc. As before, you are currently on pad 2, and your goal is to make it to pad 1, which you would happily stay on forever.

Whenever you are on pad k, you will hop to pad k−1 with probability 1/k, and you will hop to pad k+1 with probability (k−1)/k.

Now, what is the probability that you will ultimately make it to pad 1?

Solution

Let $P_k$ be the probability the frog lands on pad $k$ after the starting position.

• $P_1 = \frac{1}{2} + \frac{1}{2}P_2$

• $P_2 = \frac{1}{3}P_3$

• $P_3 = \frac{1}{2} + \frac{1}{2}P_2 + \frac{1}{4}P_4$

• $P_4 = \frac{2}{3}P_3 + \frac{1}{5}P_5$

• ...

• $P_{k-1} = \frac{k-3}{k-2}P_{k-2}$

• $P_k = \frac{k-2}{k-1}P_{k-1}$

\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & \dots & 0 & 0 & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 & \dots & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{4} & 0 & \frac{3}{4} & \dots & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{5} & 0 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \dots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \dots & 0 & \frac{k-3}{k-2} & 0 \\ 0 & 0 & 0 & 0 & 0 & \dots & \frac{1}{k-1} & 0 & \frac{k-2}{k-1} \\ 0 & 0 & 0 & 0 & 0 & \dots & 0 & 0 & 1 \\ \end{bmatrix}

I multiplied

\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & \dots & 0 & 0 & 0 \\ \end{bmatrix}

by the above matrix raised to the 100^th power for $4 \le k \le 100$.

For $19 \le k$, the value is consistently $0.6321205588285576$.

Answer

I'm quite certain the answer is $\boxed{1-\frac{1}{e}} = 0.6321205588285576...$ but I do not know why.

Rohan Lewis

2025.01.27

Code can be found here.