Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
My bad, edited. –  Matt May 1 '12 at 2:46
    
If you start enumerating the possibilities you will see patterns, which will enable you to write down the sum that evaluates to $E[X]$; the sum may be of a type well-known to combinatorialists and amenable to summation. –  Gerry Myerson May 1 '12 at 2:54
    
the probabilty that team A wins in 5 is negative binomial, the probability that some team team wins in 5 is just twice that. –  mike May 1 '12 at 11:13

1 Answer 1

up vote 1 down vote accepted

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}. $$

share|improve this answer
    
why $t(..)=1+0.5t(..)$, and how did you checked your result, and why isn't the answer $\sum_{k=4}^{\infty}k\binom k4 (0.5)^k=18$? –  ADG Nov 27 at 4:53
    
@eaxdpiotnyeantial "why t(..)=1+0.5t(..)" Well, what can I say? This is the point of the whole answer to explain why. "and how did you checked your result" I did not, I provided a formula for the OP to check their own computations against it. "and why isn't the answer... 18" Why should it? Note that every series lasts at least 4 games and at most 7 games hence a mean number of games per series of 18 would be surprising. –  Did Nov 27 at 7:43
    
so would you help me please :( here(link)? –  ADG Nov 28 at 16:57
    
@eaxdpiotnyeantial Which part of [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$] do you fail to understand? One is at the partial scores $xy$, one plays one game, then the partial scores become $(x+1)y$ or $x(y+1)$, each with probability $\frac12$, thus $t(x,y)$ is related to the value of $t$ at these two other pairs. What is unclear in this? –  Did Nov 28 at 17:23
    
OK ${}{}{}{}{}$ –  ADG Nov 28 at 17:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.