From Bowen Kerins comes a puzzle about pinball:
You’re playing a game of pinball that includes four lanes, each of which is initially unlit. Every time you flip the pinball, it passes through exactly one of the four lanes (chosen at random) and toggles that lane’s state. So if that lane is unlit, it becomes lit after the ball passes through. But if the lane is lit, it becomes unlit after the ball passes through.
On average, how many times will you have to flip the pinball until all four lanes are lit?
The following Markov model represents two lanes in this pinball game.
Let $t_k$ represent the number of flips it takes from $k$ lit lanes to get to 2 lit lanes.
$t_2 = 0$
$t_1 = 1 + \dfrac{1}{2}t_0 + \dfrac{1}{2}t_2$
$t_0 = 1 + t_1$
Solving yields
$$t_0 = E(2) = 4$$
The following Markov model represents three lanes in the pinball game.
$t_3 = 0$
$t_2 = 1 + \dfrac{2}{3}t_1 + \dfrac{1}{3}t_3$
$t_1 = 1 + \dfrac{1}{3}t_0 + \dfrac{2}{3}t_2$
$t_0 = 1 + t_1$
Solving yields
$$t_0 = E(3) = 10$$
The following Markov model represents $n$ lanes in the pinball game.
$t_n = 0$
...
$t_k = 1 + \dfrac{k}{n}t_{k-1} + \dfrac{n-k}{n}t_{k+1}$
...
$t_0 = 1 + t_1$
Unfortunately I could not find an explicit equation for $t_0$, or $E(n)$, to achieve the extra credit.
For four lanes:
$t_4 = 0$
$t_3 = 1 + \dfrac{3}{4}t_2 + \dfrac{1}{4}t_4$
$t_2 = 1 + \dfrac{2}{4}t_1 + \dfrac{2}{4}t_3$
$t_1 = 1 + \dfrac{1}{4}t_0 + \dfrac{3}{4}t_2$
$t_0 = 1 + t_1$
The first two equations yield:
$$t_3 = 1 + \dfrac{3}{4}t_2$$
Substituting into the second equation yields:
$$t_2 = 1 + \dfrac{2}{4}t_1 + \dfrac{2}{4}\cdot \left(1 + \dfrac{3}{4}t_2\right)$$
$$t_2\left(1 - \dfrac{6}{16}\right) = \dfrac{3}{2} + \dfrac{2}{4}t_1$$
$$t_2 = \dfrac{8}{5} \cdot\left(\dfrac{3}{2} + \dfrac{2}{4}t_1\right)$$
$$t_2 = \dfrac{12}{5} + \dfrac{4}{5}t_1$$
Substituting into the third equation yields:
$$t_1 = 1 + \dfrac{1}{4}t_0 + \dfrac{3}{4}\cdot\left(\dfrac{12}{5} + \dfrac{4}{5}t_1\right)$$
$$20t_1 = 20 + 5t_0 + 36 + 12t_1$$
$$8t_1 = 5t_0 + 56$$
$$t_1 = \dfrac{5}{8}t_0 + 7$$
Substituting in the fourth equation yields:
$$t_0-1 = \dfrac{5}{8}t_0 + 7$$
$$\dfrac{3}{8}t_0 = 8$$
$$t_0 = E(4) = \dfrac{64}{3}$$