I recently came across the following probability problem:
- You have a counter on the first square of a finite-length board
- You flip a coin: if heads, you move the counter forwards 1 square; if tails, move forwards 2 squares
- You keep flipping until you reach the end of the board
If $P(i)$ is the probability of landing on board square number $i$, for what value of $i>1$ is the value of $P(i)$ maximized?
Having manually calculated probabilities for $i=2,3,4,5,6,...$ is it clear (and intuitive) that $P(2)$ maximizes the quantity $P(i)$. Are there any nice ways (recursion, perhaps?) of demonstrating this analytically / algebraically?
I will assume you start on square $0$.
Note that $P(1) = \frac{1}{2}$ and $P(2) = \frac{3}{4}$. Then, we have the following recurrence:
$$P(i) =\frac{P(i-1)}{2} + \frac{P(i-2)}{2}, P(1) = \frac{1}{2}, P(2) = \frac{3}{4}$$
This is because we have probability of $\frac{1}{2}$ of jumping forward $2$ spaces from square $i - 2$ and a probability of $\frac{1}{2}$ of jumping forward $1$ space from square $i - 1$.
Using this, we will now prove by induction that $P(2)$ must be maximal.
Assume $P(i), P(i-1) < P(2)$ for some $i\geq 4$, and then note:
$$P(i + 1) = \frac{P(i) + P(i - 1)}{2}\leq\max\big(P(i), P(i-1)\big) < 2$$
Then, since $P(3) = \frac{5}{8} < \frac{3}{4}$ and $P(4) = \frac{11}{16} < \frac{3}{4}$, we have that $P(i) < P(2)$ for all $i \geq 3$ and $P(1) < P(2)$, so $\boxed{P(2)\text{ is maximal.}}$