Swift Side Steps (10/7 – 10/20)
Camille is challenging you to a game where she creates 3 lanes and puts you in the middle initially. Then, on each wave she spawns monsters in 2 out of the 3 lanes which attacks you if you are on the same lane as them. You can dodge these monsters by moving left/right repeatedly. She is nice, so she has a \(\frac{1}{2}\) chance of not spawning the monsters in your lane and she has a \(\frac{1}{4}\) chance of not spawning the monsters on the other 2 lanes.
You are lazy, so you only press left/right the minimum number of times you needs to.
Let \(E_n\) be the expected number of times you have to press left/right in order to dodge \(n\) waves of attacks.
Compute
$$\sum_{n=0}^\infty \frac{E_n}{2^n}$$
Solution
Let \(A_n\) be the expected number of times you have to press left/right in order to dodge \(n\) waves of attacks where you start in the middle and \(B_n\) be the expected number of times you have to press left/right in order to dodge \(n\) waves of attacks where you start in one of the sides (Note that \(A_n = E_n\) and that the two sides are symmetric).
Then, we get the following equations
\begin{align*}
A_n &= \frac{1}{2}A_{n-1} + \frac{1}{2}(B_{n-1} + 1) \\
&= \frac{1}{2}A_{n-1} + \frac{1}{2}B_{n-1} + \frac{1}{2} \\
B_n &= \frac{1}{2}B_{n-1} + \frac{1}{4}(A_{n-1} + 1) + \frac{1}{4}(B_{n-1} + 2) \\
&= \frac{1}{4}A_{n-1} + \frac{3}{4}B_{n-1} + \frac{3}{4}
\end{align*}
with \(A_0 = B_0 = 0\).
Let \(A(x) = \sum_{n=0}^\infty A_n x^n\) and \(B(x) = \sum_{n=0}^\infty B_n x^n\). Then, using the two equations and the fact that \(\sum_{n=0}^\infty x^n = \frac{1}{1-x}\) we get
\begin{align*}
\frac{1}{2}A(x) + \frac{1}{2}B(x) + \frac{1}{2(1-x)} &= \frac{A(x)}{x} \\
\frac{1}{4}A(x) + \frac{3}{4}B(x) + \frac{3}{4(1-x)} &= \frac{B(x)}{x}
\end{align*}
Substituting \(x = \frac{1}{2}\) gives a simple two variable two equation which yields
$$A\left(\frac{1}{2}\right) = \frac{8}{7}$$
Note: The convergence is trivial since \(A_n \leq 2n\).