1

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.. :)

Especially Lime
  • 40,828
Stranger Forever
  • 1,313
  • @lulu Okay.... But I have doubt.. $E(A,A,2)$ means that $A$ has won the last two games and it is $A's$ turn now.. So the probability of winning the first game is half and the second game is also half.. So, since $A$ has to compulsorily win them, isn't it $\frac{1}2 . \frac{1}2 = \frac{1}4$.. From where do you get $(1+E(B,B,1))$ ? – Stranger Forever Aug 07 '20 at 07:07
  • My comment was needlessly complex, as we don't actually care who holds the current winning streak. (Also in the first version of the comment I was considering different rules then the ones you wanted, so I deleted the comment). I posted something simpler below. – lulu Aug 07 '20 at 07:10
  • @lulu Yes.. I am trying to get what your answer wants to say.. – Stranger Forever Aug 07 '20 at 07:13
  • here is a duplicate question (phrased differently). – lulu Aug 07 '20 at 07:17

3 Answers3

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

Especially Lime
  • 40,828
2

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

lulu
  • 70,402
  • I have just one doubt.. discussed in the comment above... – Stranger Forever Aug 07 '20 at 07:10
  • 1
    My earlier comment pertained to a different rule set than you wanted (so I deleted that comment). What doubt do you have for the argument I presented here? If the current win streak is $1$, say, then with equal probability either the current winner wins again, moving us to $E_2$ or the current winner loses, keeping us in $E_1$ and in either case we have played one game. – lulu Aug 07 '20 at 07:13
  • Oh yes!! Thank you so much.. – Stranger Forever Aug 07 '20 at 07:16
  • The addition of $1$ in every recurrence denotes that they are playing one game right?.... But what does that $\frac{1}2 \times 1$ in $E_2$ mean? – Stranger Forever Aug 07 '20 at 07:24
  • 1
    For the first equation I wrote I considered two paths, according to who won. If the current streak holder wins it takes $1$ game to finish. If the current streak holder loses it takes $1+E_1$ games to finish, and both paths have probability $\frac 12$ of occurring. – lulu Aug 07 '20 at 07:25
  • Oh I get it.. Thanks again.. – Stranger Forever Aug 07 '20 at 07:27
  • Just a minor correction.. From the grammar of your definition I feel that what we need is not $E_0$ but $E_3$ because there cannot be a $0$ streak.. is it not? Or am I getting it wrong again? – Stranger Forever Aug 07 '20 at 07:33
  • $E_3$ would be $0$....that would represent the expected length of time it takes to take to a win streak of $3$ given that you are starting with a win streak of $3$. At the start there is no win streak. That's the only state in which there is no win streak. So, from the start we want $E_0$. Of course $E_0=1+E_1$ since it is certain that somebody will win the first game and we'll then get a win streak of $1$. – lulu Aug 07 '20 at 11:10
  • Check out the duplicate question I linked to above. Convince yourself that this is the same question. At a glance, the solutions posted there are broadly similar to mine but maybe the different phrasing will be useful. – lulu Aug 07 '20 at 11:12
0

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.

Enver Utku BATUR
  • 1