lean_workbook_plus_57364

Define $P_i$ to be the probability that the ant stays on the same side after $i$ more moves if the previous move stayed on the same side (top or bottom). Define $Q_i$ to be the probability that the ant stays on the same side after $i$ more moves if the previous move switched between top and bottom. After switching sides, the next move cannot, so $Q_i = P_{i-1}$ . We also have the recursion $P_{i+1} = \frac 12 P_i + \frac 12 (1-Q_i) = \frac 12 (P_i - P_{i-1} + 1)$ since with one-half probability it stays on the same side and with one-half probability, it switches sides and the probability that we return to the original is $1-Q_i$ . \n\n We wish to compute $\frac 23(1-P_7) + \frac 13 Q_7$ . It is easy to see that $P_1 = \frac 12$ and $P_2 = \frac 14$ . \n\n Now, using the recursion $P_{i+1} = \frac 12 P_i + \frac 12 (1-P_{i-1}) = \frac 12 (P_i - P_{i-1} + 1)$ we compute \n\n \begin{tabular}{c | c} n & P_n \ 1 & \frac 12 \ 2 & \frac 14 \ 3 & \frac 38 \ 4 & \frac{9}{16} \ 5 & \frac{19}{32} \ 6 & \frac{33}{64} \ 7 & \frac{59}{128} \ \end{tabular} \n\n at which point it is easy to compute $\frac 23(1-P_7) + \frac 13 Q_7 = \frac{17}{32}\rightarrow \boxed{049}.$