Question: Let $L(N)$ be the length of the longest run of consecutive heads or tails in $N$ tosses of a fair coin. So, for example, if $N=7,$ and the outcomes are $HHTHHHT$, then $L=3$ in this case. What is $E[L(5)] - E[L(4)]?$
I can solve the problem with answer $\frac{5}{16}$ by listing out all possibles cases for $L(4)$ and $L(5).$
For example, if $L(4) = 2,$ then there are $8$ possibilities $$HHTT, \, HHTH, \, THHT, \, HTHH$$ and we swap $T$ and $H$ to get the remaining $4$ possibilities.
However, I think this is not the most efficient method to solve this question.
Imagine this is an interview question where we have no access to pen and paper. How would one solve this question without listing out all cases?
Here is an alternate way, which still requires listing some but not all cases. IMHO for $L(4)$ vs $L(5)$ this is just barely doable without pen and paper, but YMMV.
$E[L(5) - L(4)]$ is equivalent to asking: what is the probability that the $5$th coin $C_5$ actually increases the longest run by $1$? Since we allow both runs of Heads or Tails, the situation is symmetric, so without loss of generality we can assume $C_5=H$.
(Case A) If the $4$th coin $C_4=T$, then $C_5=H$ cannot increase the longest run.
(Case B) If $C_4=H$, then $C_5=H$ increases the length of the final run, but does it increase the longest run?
(Case B1) If the sequence was $TTTH, HTTH, HHTH$ then adding $C_5=H$ does not increase the longest run.
(Case B2) If the sequence was $**HH$ ($4$ cases, the $*$'s are wildcards) or $THTH$, then adding $C_5=H$ does increase the longest run.
Therefore, $E[L(5)-L(4)] =$ prob of increasing the longest run $=Prob(Case\ B2) = 5/16$.