Two players until one player wins three games in a row. Each player will win with probability $\frac{1}2$. How many games will they play?

Question

QUESTION: Suppose two equally strong tennis players play against each other until one player wins three games in a row. The results of each game are independent, and each player will win with probability $\frac{1}2$. What is the expected value of the number of games they will play?

---

MY APPROACH: I have tried to set up some kind of recurrence relation here but could not succeed.. Observe that there can be at most a winning streak of $2$. A winning streak of $3$ means that the game ends.. If we assume that the number of $1$ game winning streak is $x$ and the number of $2$ game winning streak is $y$ then $x+y+1$ obviously yields the desired answer..

Note: A $1$ game winning streak simply means that they win alternately.. Since each one of them has a $50\%$ chance of winning therefore we can do this..

Now, somehow, we have to find the value of $x$ and $y$.. But here I am stuck.. With so less information, neither can I set up a recurrence relation, nor do I see any way to compute two variables..

Any help will be much appreciated.. :)

Answer 1

Recurrence works fine.

All we care about is the length of the current win streak, we don't even care who has been winning. Accordingly, let $E_i$ denote the expected number of games it will take if one player currently has a winning streak of length $i$. The answer we seek is $E_0$.

We get: $$E_2=\frac 12\times 1+\frac 12\times (1+E_1)=1+\frac 12\times E_1$$

Similarly $$E_1=1+\frac 12\times (E_1+E_2)$$ and $$E_0=1+ E_1$$

This is easily solved and yields $$\boxed {E_0=7}$$

Answer 2

Suppose the winner of the last game is on a $1$-game streak. How many more games until someone is on a $2$-game streak? This is just a geometric random variable with parameter $1/2$, so has expectation $2$.

Now, once someone is on a $2$-game streak, either they get a $3$-game streak next game, or you go back to someone being on a $1$-game streak. So from a $1$-game streak, after an expected $3$ games either someone completes a $3$-game streak or you are back where you started. The number of times this happens before you get a $3$-game streak is also exponential with parameter $1/2$, so has expectation $2$. Crucially, the number of stages of this form you have to go through is independent of the length of each stage. So the total time for all stages has expectation $2\times 3=6$. This is the expected time from the position where someone is on a streak of $1$, i.e. the expected number of games needed after the first game, so the total expectation is $7$.

Answer 3

This is a very interesting question because it has a very interesting answer. The answer is actually through Fibonacci sequence.

Call the players Player 0 and Player 1, represent Player 0 winning as 0 and Player 1 winning as 1. We can focus on only player 1. Since the probability is 1/2, anything true for one player will be symmetrically true for the other player. Let's start with discussing cases first and then probabilities later. How many ways are there for Player 1 to win it at 3 games? We can easily say that it is only 1: 111 How many ways are there for 4 games? Only 1: 0111 How many for 5? Only 2: 10111, 00111 How many for 6? Only 3: 010111, 110111, 100111 7? Only 5: 0110111, 0010111, 1010111, 0100111, 1100111 8? Only 8: 00110111, 10110111, 10010111, 01010111, 11010111, 00100111, 10100111, 01100111

Now you can start to notice a pattern here: In each case, we multiply the previous number, but subtract the ones that get 3 consecutive wins. The number that we subtract depends on the last 2 games. There are only 4 possible cases: 00, 01, 10, 11. We subtract for the ones 00 and 11. How can we determine how many of them are there? This is easily done. Since we know that we are repeating 2 games, we know that this could only be the number of solutions for 2 games ago. For example, for 6 games, there are only 3 possible cases: 010111, 110111, 100111. Hence from this, we can deduct that there are 3 subtraction cases at number 8: 11010111, 00110111, 00100111. Notice that what we do is switch the winner of the last game and repeat it one time.

Now, we can turn this into a formula: For any number of games m, the possible cases $N_m$ can be calculated as $N_{m+1}$=$2N_{m}$-$N_{m-2}$. Do you see what this formula is??? It is another version of Fibonacci Sequence! We can show it inductively: If for some m, $N_m$=$N_{m-1}$+N{m-2}$,then $$ N_{m+1}=2N_m-N_{m-2}=N_m+N_m-N_{m-2}=N_m+N_{m-1}+N_{m-2}-N_{m-2}=N_m+N_{m-1} $$

For $m=6, N_6=3, N_5=2, N_4=1, N_6=N_5+N_4$.

Thus, we have shown that for any number of games m, the number of possible cases for a series ending for a player 1 victory is determined by $$ N_m=N_{m-1}+N_{m-2} $$

If we denote nth number of Fibonacci series as F(n), then the formula becomes, $$ N_m=F(m-2) $$

Now, we can calculate the probability of the Player 1 winning the series at m games as $$ P_1=\frac{N_m}{2^m}=\frac{F(m-2)}{2^m} $$ This was just for one player, now we have to multiply it by two to get the probability of the game ending by any player. $$ P_m=2P_1=2\frac{F(m-2)}{2^m} $$ For the expected value $E_m$, we multiply by m $$ E_m=P_m*m=2\frac{F(m-2)*m}{2^m} $$

The total expected value is $$ \sum_{m=1}^\infty E_m=\sum_{m=1}^\infty 2\frac{F(m-2)*m}{2^m} $$ Now, all we need to do is turn this recursive formula into a general one by using Binet's formula :

$$ F(m)=\frac{Φ^{m}-φ^{m}}{\sqrt5} $$ where $Φ=\sqrt5+1$ and $φ=\sqrt5-1$

If we calculate it accordingly, the answer is 7. There are many more interesting facts about this problem, but I don't have time to discuss all of it. For example, the solution for any n number of deciding games is calculated always by n-1 step Fibonacci numbers. For 3 games, 2-step Fibonacci numbers are the Fibonacci numbers that we know it. 4 games is calculated by Tribonacci numbers and etc.

Hence, you can also calculate that for any number of deciding games n, the expected number of games is always $E_n=2^n-1$. For n=3, the answer was 7, for n=4 the answer is 15 and so on. To me, this was a very interesting result about the relationship of Fibonacci numbers and powers of 2. Which is also always equal to $F_{n}(n+1)$.

$F_2(4)=3$ $F_3(5)=7$ $F_4(6)=15$ etc. Pretty cool.