Probability of winning 10 times in 12 matches

[FranzDiCoccio]

<Moderator's note: Moved from a technical forum and thus no template.>

Hi all,
I'm looking at an exercise in probability and I have a little doubt. So the exercise goes like this:
"Two players are playing against each other. They have the same probability of winning a single game. In order to win the match a player needs to win ten games. What is the probability that one of the players wins in 12 or less games?"

The probability that one of the player wins 10 out of 12 matches is pretty easy, but I think that this problem is more complex than that, although the final answer is hardly different.

The number of outcomes in 12 matches is $2^{12}$. However, I think that some of these outcomes should be discarded, on account that there is no need of further games since one of the players already won.
Specifically the one instance where one of the players wins all 12 games, and the 12 instances where one of the players wins 11 out of 12 matches.
Thus, one should take into account only $2^{12}-13$ possible outcomes.
In
$$\binom{12}{10}= 66$$
of these outcomes one player wins 10 games and loses two.

So, I'd say that the probability the problem is asking for is

$$\frac{1}{2^{12}-13}\binom{12}{10}$$

which is almost the same as the fraction of 10 victories in 12 games, i.e.
$$\frac{1}{2^{12}}\binom{12}{10}$$

Does this make sense?

I also obtained the number of successful games as the number of 10 victories in 10 games (1) plus the number of 9 victories in 10 games, assuming that the 11th is a victory (10) plus the number of 9 victories in 11 games (assuming the 12th is a victory): $1+10+ 11\cdot 10/2=66$.
I'm not sure on how counting the total number of games in a similar fashion.

Any insight is appreciated.
Thanks a lot!

 

[kuruman]

I would use the binomial distribution to calculate the probabilities of winning exactly 10 games in 10 tries, in 11 tries, in 12 tries and then add the 3 probabilities.

 

[mathwonk]

if the p[layers are A and B, then it is not clear to me whether you are asking for the probability that A wins in 10 games, or whether either A or B wins in 10 games. i.e. i do not know when you ask about "one player", you mean a specific one, or just either one.

 

[FranzDiCoccio]

if the p[layers are A and B, then it is not clear to me whether you are asking for the probability that A wins in 10 games, or whether either A or B wins in 10 games. i.e. i do not know when you ask about "one player", you mean a specific one, or just either one.

Hi. This is not very clear to me either, because the phrasing in the exercise is ambiguous in my opinion.
I'm interested in both cases, but let's start with one single player.

 

[FranzDiCoccio]

Hi kuruman,
thanks for your input. I still have some doubts, though.

For instance, when calculating the probability of winning 10 games out of 11 using the binomial distribution, I suspect I'm counting at least one outcome too many, i.e. the one where the first 10 tries are won. That should not be counted, because the eleventh game is pointless in that case. I mean, 11 tries are necessary only if one of the first ten games is lost. A similar argument should apply with 12 tries.
My idea is that I should

• enumerate all the possible outcomes assuming that 12 games are played;
• eliminate the outcomes that won't occur, because there is no need of further games
• count how many of the previously enumerated outcomes are won by one of the players.

Probably this is too finicky, and in the end the result would be very similar to the number of ways of winning 10 games when 12 games are played, no matter what. But rigorously it's not exactly the same, right?
I have the feeling that adding the probabilities would also be approximately correct, in the same sense. Or maybe my interpretation of your suggestion is too naive.

 

[FranzDiCoccio]

I'm thinking maybe I should concentrate on the probability that neither player wins 10 times in 12 games. One minus that should be the answer...
I'm going to try that.

 

[Ray Vickson]

Hi kuruman,
thanks for your input. I still have some doubts, though.

For instance, when calculating the probability of winning 10 games out of 11 using the binomial distribution, I suspect I'm counting at least one outcome too many, i.e. the one where the first 10 tries are won. That should not be counted, because the eleventh game is pointless in that case. I mean, 11 tries are necessary only if one of the first ten games is lost. A similar argument should apply with 12 tries.
My idea is that I should

• enumerate all the possible outcomes assuming that 12 games are played;
• eliminate the outcomes that won't occur, because there is no need of further games
• count how many of the previously enumerated outcomes are won by one of the players.

Probably this is too finicky, and in the end the result would be very similar to the number of ways of winning 10 games when 12 games are played, no matter what. But rigorously it's not exactly the same, right?
I have the feeling that adding the probabilities would also be approximately correct, in the same sense. Or maybe my interpretation of your suggestion is too naive.

You could compute the probability that player A wins 9 games in 10 tries, then wins game 11; that would give the probability that player A wins exactly on game 11. Can you see how to do something similar to get the probability that A wins on game 12?

 

[kuruman]

Hi kuruman,
thanks for your input. I still have some doubts, though.

Your doubts are well taken. I have to think about it some more. @Ray Vickson's suggestion is a good way to proceed if my thinking does not pan out.

 

[StoneTemplePython]

Hi kuruman,
thanks for your input. I still have some doubts, though.

For instance, when calculating the probability of winning 10 games out of 11 using the binomial distribution, I suspect I'm counting at least one outcome too many, i.e. the one where the first 10 tries are won. That should not be counted, because the eleventh game is pointless in that case. I mean, 11 tries are necessary only if one of the first ten games is lost. A similar argument should apply with 12 tries.
My idea is that I should

• enumerate all the possible outcomes assuming that 12 games are played;
• eliminate the outcomes that won't occur, because there is no need of further games...

your instincts are close but do not do these eliminations. Your question has echoes to the problem of points.

As Fermat (almost) asked, what harm is it to let them play 12 games? (Note you could get into trouble with this logic if allowed games played was $\geq 20$, why? But then again, if total games played were $\geq 20$, since your game has no ties, then someone must have won at this point -- a pidgeon hole-- so it would not be an issue.)

And instead of enumerating the 12 games, you should know what the distribution of 12 coin tosses (bernouli trials) looks like as it has already been mentioned. Take a look at that distribution and...
- - - -
The other suggestions should work as well, though this approach has some visual appeal.

 

[FranzDiCoccio]

Ok, I'm trying to combine Ray Vickson's and StoneTemplePython's suggestions.

One of the players can win 10 games straight, and that can happen in only one way, with probability $2^{-10}$.
Then one of the players can win 9 of the first 10 games, and the 11th. That can happen in 10 possible ways, with probability $2^{-11}$ (equal probability of winning or losing).
Also, one of the players can win 9 of the first 11 games, and the 12th. That can happen in $11\cdot 10/2$ possible ways, with probability $2^{-12}$.

Adding the probabilities, as kuruman suggests, gives
$$ \frac{1}{2^{10}}+ \frac{10}{2^{11}}+ \frac{11\cdot 10}{2^{13}}=\frac{79}{2^{12}}\approx0.0193 $$

This is slightly larger than my previous results
$$\frac{1}{2^{12}-13}\binom{12}{10}\approx 0.0162 $$
and
$$\frac{1}{2^{12}}\binom{12}{10}\approx 0.0161 $$

I guess this is because in the last two I'm assuming that the strings of 10, 11 and 12 games are equally probable.

It seems to be a matter of normalization. I have to admit that it's still not clear to me what is the correct normalization in a case like this, where the number of games is not fixed.

I'm kind of obsessing about this because the exercise says something like "the first player who wins ten games wins the match" and asks for the probability that one player wins the match in 12 games or less. Without these constraints (i.e. if they play 12 times no matter if one of them has already won) I would go for the last formula.

 

[Ray Vickson]

Ok, I'm trying to combine Ray Vickson's and StoneTemplePython's suggestions.

One of the players can win 10 games straight, and that can happen in only one way, with probability $2^{-10}$.
Then one of the players can win 9 of the first 10 games, and the 11th. That can happen in 10 possible ways, with probability $2^{-11}$ (equal probability of winning or losing).
Also, one of the players can win 9 of the first 11 games, and the 12th. That can happen in $11\cdot 10/2$ possible ways, with probability $2^{-12}$.

Adding the probabilities, as kuruman suggests, gives
$$ \frac{1}{2^{10}}+ \frac{10}{2^{11}}+ \frac{11\cdot 10}{2^{13}}=\frac{79}{2^{12}}\approx0.0193 $$

This is slightly larger than my previous results
$$\frac{1}{2^{12}-13}\binom{12}{10}\approx 0.0162 $$
and
$$\frac{1}{2^{12}}\binom{12}{10}\approx 0.0161 $$

I guess this is because in the last two I'm assuming that the strings of 10, 11 and 12 games are equally probable.

It seems to be a matter of normalization. I have to admit that it's still not clear to me what is the correct normalization in a case like this, where the number of games is not fixed.

I'm kind of obsessing about this because the exercise says something like "the first player who wins ten games wins the match" and asks for the probability that one player wins the match in 12 games or less. Without these constraints (i.e. if they play 12 times no matter if one of them has already won) I would go for the last formula.

I think that what StoneTemplePython was getting at was to look at is as a problem with 12 tosses, and in which you just disregard all tosses after player A has won 10 times. In other words, the probability you want could be written as $P(X \geq 10)$, where $X$ has a binomial distribution with parameters $n = 12$ and $p = 1/2$. That would give you
$$\begin{array}{lcl}\text{Answer} &= &P(X=10)+P(X=11)+P(X=12) \\
&=& \displaystyle {12 \choose 10} \frac{1}{2^{12}} + {12 \choose 11} \frac{1}{2^{12}} + {12 \choose 12} \frac{1}{2^{12}} = \frac{79}{4096}
\end{array},$$
exactly as you obtained in your first calculation.

 

[FranzDiCoccio]

[...]
exactly as you obtained in your first calculation.

Ok, the result is the same. Cool!

The interpretation of $P(X=10)$ should be "the probability of obtaining exactly $X$ successes in $n$ trials" (with $n=12$ and $p=1/2$).

So $P(X\geq 10)$ would be "the probability of obtaining at least $X$ successes in $n$ trials".

When put in that way I sort of see why this could work, although I am not yet very clear on the mathematical details of why my perhaps intuitive calculation gives the same result as the sum of binomial distrubutions. Using the binomial coefficients, the first of "my" formulas reads

$$ \binom{10}{10} \frac{1}{2^{10}}+ \binom{10}{9} \frac{1}{2^{11}}+ \binom{11}{9} \frac{1}{2^{12}} $$

I'll think about that, and check the equality for other choices of $X$.

One last question: suppose the exercise asks for the probability that any of the two players wins in 12 tries or less. In that case it would be sufficient to multiply the above probability by two, right? These are independent outcomes...

 

[StoneTemplePython]

although I am not yet very clear on the mathematical details of why my perhaps intuitive calculation gives the same result as the sum of binomial distrubutions.

With respect to mathematical details, there are basically 2 approaches -- the first using sets and the second using a picture (a 'recombining tree' actually).

- - - -
viewpoint 1
Focusing only on probability of player 1 getting to 10 wins (and we can double probabilities at the end by symmetry to include player 2 as well),

there are 3 compound events of interest here

$A_1 := p_1 \text{ wins 10th game on game 10}$
$A_2 := p_1 \text{ wins 10th game on game 11}$
$A_3 := p_1 \text{ wins 10th game on game 12}$

It's convenient mathematically to homongenize the length of the the sequence of simple events to be 12 in all cases. (Put differently, it is convenient to make each possible string of 0s and 1s be length 12.) This isn't required, but it is very convenient so that's what I've done. You should verify that e.g. for $A_1$ the result of winning the 10th game on game 10 doesn't change whether the sequence stops at 10 tosses, or at 11 or at 12. This is the "it doesn't hurt to play longer" argument.

you should also verify that these events are mutually exclusive, e.g. it is impossible for $p_1$ to win the 10th game on game 10 and also to have the 10th win on game 11, for any sequence of simple events (i.e. any sequence of coin tosses). You either win the 10th game on game 10 or on game 11 or neither -- there is no overlap. Mutual exclusivity is quite powerful and gives you

$Pr\{A_1 \cup A_2 \cup A_3\} = P\{A_1\} + P\{A_2\} + P\{A_3\}$
- - -
now when you look at the $n = 12$ binomial distribution, what does $P\big( X=12\big)$ consist of? For anything there it *must* be the case that (a subset of) $A_1$ occurred --why?. What does $P\big( X=11\big)$ consist of... it must be the case that (a subset of) $A_1$ and/or $A_2$ occurred (more technically -- the union of some subsets of $A_1$ and $A_2$) -- again why? . What does $P\big( X=10\big)$ consist of -- the union of some subset of $A_1$ and some subset of $A_2$ and all of $A_3$. (For completeness you should run the argument the other way and verify that $A_1$ ends up in $X \geq 10$ and $A_2$ ends up in $X \geq 10$ and $A_3$ ends up in $X \geq 10$). This means that $\{A_1 \cup A_2 \cup A_3\}$ is characterized completely by $X\geq 10$ (and vice versa).

It's a little sloppy linguistically on my part, but you can look at that $X=10$ and ask what kind of outcome / compound events underly this and ask similar questions about $X=11$ and $X=12$. The compound events of getting exactly $x$ wins for $p_1$ after 12 tosses are mutually exclusive. Confirm this point. Again mutual exclusivity is powerful which means that we can take the probability of the union of the events to be the sum of probabilities...so summing probabilities over all $Pr\{X =10\} + Pr\{X =11\}+ Pr\{X =12\} = Pr\{X \geq 10\}$ is precisely that same as the probability of union of underlying events, but based on the prior paragraph that is exactly $Pr\{A_1 \cup A_2 \cup A_3\}$ and hence is the answer.

- - - -
viewpoint 2
Perhaps a more compelling alternative than the above events based argument is to draw a picture as a lattice (recombining tree). This is also quite helpful for visualizing what's going on here. As it turns out, this can also be quite useful for computing some underlying probabilities (which is how Pascal would approach the problem).

- - - -
additional idea:
for something like
$A_1 := p_1 \text{ wins 10th game on game 10}$

what this the probability of that happening over 10 coin tosses only? Call it $\gamma$. Now suppose probability of 'heads' on anyone of these independent identically distributed 'coin tosses' is $q$.

So what happens to this probability if we allow 11 tosses to happen but we are interested specifically in the event of winning 10 games on game 10?

In that case the total probability
$= q\gamma +(1-q)\gamma = \gamma(q + 1-q) = \gamma$

So there is no change if we allow 11 games (i.e. one extra toss) in our model. And what about over 12 tosses? Then the total probability is $\gamma q^2 + \gamma (1-q)^2 + 2 q(1-q) = \gamma\big(q + (1-q)\big)^2 = \gamma \big(1\big) = \gamma$

so there is no change aka 'no harm' if we homogenize the results to be 12 plays.

 

[FranzDiCoccio]

StoneTemplePython,
thanks a lot for the detailed explanation!
Right now I clearly see your latter explanation ("additional idea"), but I definitely want get the whole picture. I'll have to work on the first part !
Also, I'll definitely look into recombining trees of viewpoint 2.

Thanks again, this is all really interesting! (and also thanks to all other people contributing!)
Franz

 

[FranzDiCoccio]

Hi, me again. I was able to prove the equivalence of the two different formulas giving $79/2^{12}$ using a couple of identities for the binomial coefficients I found out on the Wikipedia page. The second is actually a particular case of a more general sum identity.
Since it would take me some time to write it down in LaTeX I'm attaching an image of my calculation. It's just 3 steps. I'm using twice the first identity and once the second.
I wonder if this result could be generalized to something like
$$ \sum_{m=k}^{n-1} 2^{n-m-1} \binom{m}{k-1} = \sum_{m=k+1}^{n-1} \binom{n}{k} $$
with $k>n/2$. I do not think I've seen something like that among the identities listed by the Wikipedia page, but if there something like that, it's listed somewhere.

 

[StoneTemplePython]

Hi, me again. I was able to prove the equivalence of the two different formulas giving $79/2^{12}$ using a couple of identities for the binomial coefficients I found out on the Wikipedia page. The second is actually a particular case of a more general sum identity.
Since it would take me some time to write it down in LaTeX I'm attaching an image of my calculation. It's just 3 steps. I'm using twice the first identity and once the second.
I wonder if this result could be generalized to something like
$$ \sum_{m=k}^{n-1} 2^{n-m-1} \binom{m}{k-1} = \sum_{m=k+1}^{n-1} \binom{n}{k} $$
with $k>n/2$. I do not think I've seen something like that among the identities listed by the Wikipedia page.

I'm not quite sure what you're aiming for here? You certainly can use two different ways of modeling / solving the same problem to generate combinatorial identities. If that's of interest, go for it. It isn't really needed though.

Can I suggest that tackling a simpler problem may be useful? In particular, it maybe be instructive to try and re-run what I said against a simpler problem involving 'only' 11 games, i.e.

simpler problem: "Two players are playing against each other. They have the same probability of winning a single game. In order to win the match a player needs to win ten games. What is the probability that one of the players wins in 11 or less games?"

(Once you have a nice intuitive bridge between 10 and 11, you can fairly easily generalize to the 12 problem... ).

 

[FranzDiCoccio]

Hi,
It's only that I was surprised at the fact that the two very different formulas above give the same result. I tried playing around with the identities and it really took me a surprisingly little time to work that out. I guess I was excited about that, and I wanted to share "my" finding (surely it has been figured out long ago).

I am aware that what I did is pretty specific. I want to understand the general principles underlying the problem, and I'll look at what you suggest.

 

[StoneTemplePython]

Hi,
It's only that I was surprised at the fact that the two very different formulas above give the same result. I tried playing around with the identities and it really took me a surprisingly little time to work that out...

In general I think its a great idea to find a problem you are interested in, and try to beat a dead horse by solving it many different ways. Thats how you get new insights and ideas. So kudos.

- - - -
a bit of history: Pascal and Fermat were quite surprised that their very different approaches to solving the problem of points gets the same solution. Fermat's approach is pretty close to what I suggested, and Pascals is this 'recombining tree' I've been mentioning off hand.