Can You Hop to the Lily Pad?

You’re a frog whose lifelong dream has been to make it to lily pad number 1. Do you have what it takes to realize this dream, or will random hopping lead you astray?

Fiddler
Probability
Puzzle
Author

Guillaume Gilles

Published

January 27, 2025

This week’s Fiddler on the Proof dives into a playful puzzle about lily pads and a frog hopping around—can you figure out where it will land?

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

This puzzle can be solved using Markov chains.

graph LR
  A((Pad 1))
  style A fill:#9DC183
  B((Pad 2)) -- 1/2 --> A
  style B fill:#9DC183
  C((Pad 3)) -- 2/3 --> D((Pad 4))
  style C fill:#9DC183
  style D fill:#9DC183
  C -- 1/3 --> B
  B -- 1/2 --> C
  D -- 1 --> D
  A -- 1 --> A

Pads 1 and 4 are absorbing states (once you reach them, you stay there forever), while pads 2 and 3 are transient states (you can leave them). Let’s define:

  • \(P_2\): the probability of eventually reaching pad 1 starting from pad 2.
  • \(P_3\): the probability of eventually reaching pad 1 starting from pad 3.

Step 1: Probability equations

Starting from pad 2, there is an equal \(\frac{1}{2}\) chance of jumping to pad 1 or pad 3:

  • If the frog jumps to pad 1, the journey is complete, so the contribution to \(P_1\) is \(\frac{1}{2} \cdot 1\).
  • If the frog jumps to pad 3, the probability of eventually reaching pad 1 depends on \(P_3\), with a contribution of \(\frac{1}{2} \cdot P_3\).

Thus: \[ P_2 = \frac{1}{2} + \frac{1}{2} \cdot P_3. \]

From pad 3, the frog has a \(\frac{1}{3}\) chance of hopping back to pad 2, where the probability of reaching pad 1 is \(P_2\). If the frog instead jumps to pad 4 (with probability \(\frac{2}{3}\)), the probability of reaching pad 1 is \(0\).

Therefore: \[ P_3 = \frac{1}{3} \cdot P_2. \]

Step 2: Solve for \(P_2\)

Substitute \(P_3 = \frac{1}{3} \cdot P_2\) into the equation for \(P_2\): \[ P_2 = \frac{1}{2} + \frac{1}{2} \cdot \left( \frac{1}{3} \cdot P_2 \right). \]

Simplify: \[ P_2 = \frac{1}{2} + \frac{1}{6} \cdot P_2. \]

Rearrange to isolate \(P_2\): \[ P_2 \cdot \left( 1 - \frac{1}{6} \right) = \frac{1}{2}. \]

\[ P_2 \cdot \frac{5}{6} = \frac{1}{2}. \]

Solve for \(P_2\): \[ P_2 = \frac{1}{2} \cdot \frac{6}{5}. \]

\[ P_2 = \frac{3}{5}. \]

The probability of eventually reaching pad 1 starting from pad 2 is: \[ \frac{3}{5} \]

Back to top