Can You Hop to the Lily Pad?

A frog starts on pad $2$ among four pads. Pad $1$ is a permanent home; pad $4$ is a permanent trap. From pad $2$ it jumps to $1$ or $3$, each with probability $\tfrac12$; from pad $3$ it jumps to $2$ with probability $\tfrac13$ or to $4$ with probability $\tfrac23$. What is the probability it ends up home on pad $1$?

The Fiddler, Zach Wissner-Gross, January 24, 2025(original post)

Solution

Let $h_k$ be the probability of reaching pad $1$ from pad $k$. Then $h_2=\tfrac12+\tfrac12 h_3$ and $h_3=\tfrac13 h_2$ (a jump to pad $4$ loses). Substituting, $$h_2=\tfrac12+\tfrac12\cdot\tfrac13 h_2 \implies \tfrac56 h_2=\tfrac12 \implies h_2=\boxed{\tfrac35}.$$

The computation

Hop the actual frog: start a large batch on pad $2$ and let each one jump under the stated rules until it is absorbed at pad $1$ (home) or pad $4$ (trap); the home fraction lands on $\tfrac35$.

import numpy as np
rng = np.random.default_rng(0)
pad = np.full(2_000_000, 2)
while np.isin(pad, (2, 3)).any():
    at2, at3 = pad == 2, pad == 3
    pad[at2] = np.where(rng.random(at2.sum()) < 0.5, 1, 3)        # 2 -> 1 or 3
    pad[at3] = np.where(rng.random(at3.sum()) < 1 / 3, 2, 4)      # 3 -> 2 or 4
print((pad == 1).mean())          # ~0.6  (= 3/5)

Extra Credit

Now the pond has pads $1,2,3,\dots$ forever, and from pad $k$ the frog jumps down to $k-1$ with probability $\tfrac1k$ and up to $k+1$ with probability $\tfrac{k-1}{k}$. Starting on pad $2$, what is the probability it ever reaches pad $1$?

Solution

With $\Delta_k=h_{k+1}-h_k$, the balance $p_k(h_k-h_{k-1})=q_k(h_{k+1}-h_k)$ and $p_k/q_k=\tfrac1{k-1}$ give $\Delta_k=\Delta_1/(k-1)!$, so $$h_n=1+\Delta_1\sum_{m=0}^{n-2}\frac1{m!}.$$ The upward drift ($q_k\to1$) makes the walk transient, so $h_\infty=0$, forcing $\Delta_1=-1/e$ and $$h_2=1-\frac1e\approx\boxed{0.6321}.$$ (The official extra-credit value is paywalled; this closed form is my own.)

The computation

Walk the infinite-pond frog directly: from pad $k$ step down with probability $\tfrac1k$, else up, and record whether it ever touches pad $1$ before drifting off (capped at a high pad). The reached fraction matches $1-1/e$.

import numpy as np
rng = np.random.default_rng(0)
k = np.full(2_000_000, 2); reached = np.zeros_like(k, bool); alive = np.ones_like(k, bool)
for _ in range(4000):
    reached |= alive & (k == 1); alive &= k != 1
    i = alive
    step = np.where(rng.random(i.sum()) < 1.0 / k[i], -1, 1)
    k[i] += step; alive &= k <= 3000
    if not alive.any(): break
print(reached.mean(), 1 - 1 / np.e)        # 0.6324  0.63212