Two athletic teams play a series of games; the first team to win $4$ games is declared the overall winner. Each team has a probability of $.5$ of winning each game. What is the expected number of games played?
My question is what is the best way to solve this problem?
I guess I could approach it like:
$P(X = 4) = 2(.5)^{4}$ (two shots of $1$ team winning $4$ straight)
and enumerating each possibility from $X=4$ to $X=7$, then solving for $E[X]$, but what about large values of this problem like first to $50$ wins or something?
Best Answer
A general strategy is to compute the expected number of games $t(xy)$ played until a team is declared the winner, starting from every possible partial score of $x$ games won by a player vs $y$ games won by the other one. Then the expected total number of games is $t(00)$.
Some simple remarks: (i) $t(xy)=t(yx)$ by symmetry; (ii) $t(x4)=0$ for every $0\leqslant x\leqslant3$; (iii) looking at the result of the first game played yields a relation between $t(xy)$ and $t((x+1)y)$ and $t(x(y+1))$, for each $xy$.
Starting from the highest possible partial scores and going backwards, one gets successively, using remarks (i), (ii) and (iii), $$t(33)=1,\quad t(23)=1+\tfrac12t(33)=\tfrac32,\quad t(22)=1+t(23)=\tfrac52, $$ $$t(13)=1+\tfrac12t(23)=\tfrac74,\quad t(03)=1+\tfrac12t(13)=\tfrac{15}8, $$ $$ t(12)=1+\tfrac12t(13)+\tfrac12t(22)=\tfrac{25}8,\quad t(02)=1+\tfrac12t(03)+\tfrac12t(12)=\tfrac72, $$ $$ t(11)=1+t(12)=\tfrac{33}8,\quad t(01)=1+\tfrac12t(11)+\tfrac12t(02)=\tfrac{77}{16}, $$ and, finally, $t(00)=1+t(01)=\frac{93}{16}$.
Edit: To check this result, note that $$ t(00)=\frac{2{3\choose 0}2^3\cdot4+2{4\choose 1}2^2\cdot5+2{5\choose 2}2^1\cdot6+{6\choose 3}2^0\cdot7}{2{3\choose 0}2^3+2{4\choose 1}2^2+2{5\choose 2}2^1+{6\choose 3}2^0}. $$