The Four Lily Pad Problem

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$)?

Let's solve this in two different ways: (a) one directly from the probability distributions and some easy combinatorics; and (b) from the Markov chain properties that we will then expand in the Extra Credit portion.

The most straightforward way of solving this is by looking at all of the possible transitions from pad $2$ to pad $1.$ Obviously in the first jump you have a $1/2$ probability of everlasting happiness on pad $1.$ If not, then you will have to make your way back to pad $2$ and try again, at some future point. In order to end up back on pad $2$ we will need a jump to pad $3$ followed by a jump back from pad $3$ to pad $2.$ The probability of this round trip occuring is $\frac{1}{2} \times \frac{1}{3} = \frac{1}{6}.$ So we can only arrive on paradise pad $1$ as the result of an odd numbered jump from pad $2$ to pad $1$, with some number of round trips, say $k$, between pads $2$ and $3$ intervening. So the the probability of landing on lily pad $1$ on the $(2k+1)$th jump is $\frac{1}{2 \cdot 6^k},$ meaning that the total probability of ever landing on lily pad $1$ having started on lily pad $2$ is $$p = \sum_{k=0}^\infty \frac{1}{2 \cdot 6^k} = \frac{1}{2} \frac{1}{1 - \frac{1}{6}} = \frac{3}{5} = 60 \%.$$

Of course another way of looking at the situation is that your location on pads $1,$ $2,$ $3,$ or $4$ can be modeled by a Markov chain with transition matrix given by $$T = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 1/3 & 0 & 2/3 \\ 0 & 0 & 0 & 1 \end{pmatrix} ,$$ where $T_{ij}$ is the probability of starting of pad $i$ and going to pad $j$. Obviously, pads $1$ and $4$ are absorbing, recurrent states of this Markov chain, while pads $2$ and $3$ are transient. We can then transform our transition matrix by reordering the states to put it into a canonical block form, so that now the rows and columns represent pads $3,$ $2,$ $1,$ and $4$, respectively: $$\hat{T} = \begin{pmatrix} 0 & 1/3 & 0 & 2/3 \\ 1/2 & 0 & 1/2 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} Q & R \\ 0 & I \end{pmatrix}.$$ The fundamental matrix of this Markov chain is $$N = (I - Q)^{-1} = \begin{pmatrix} 1 & -1/3 \\ -1/2 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} \frac{6}{5} & \frac{2}{5} \\ \frac{3}{5} & \frac{6}{5} \end{pmatrix}.$$ The resulting absorption probabilities are given by $$P = NR = \begin{pmatrix} \frac{6}{5} & \frac{2}{5} \\ \frac{3}{5} & \frac{6}{5} \end{pmatrix} \begin{pmatrix} 0 & \frac{2}{3} \\ \frac{1}{2} & 0 \end{pmatrix} = \begin{pmatrix} \frac{1}{5} & \frac{4}{5} \\ \frac{3}{5} & \frac{2}{5} \end{pmatrix}$$ where $P_{ij}$ is the probability of starting on lily pad $4-i$ and ending up at lily pad $\frac{5 + (-1)^j 3}{2}$ for $i, j = 1, 2.$ So in particular, the probability of starting on pad $2$ and ending up living a life of happiness on pad $1$ forever is, again, $P_{21} = 60\%.$