11
$\begingroup$

The question is as follows:

A and B participate in a tournament of "best of 7 games". It is equally likely that either A wins the game or B wins the game, or the game ends in a draw. What is the probability that A wins the tournament?

So I tried an approach like this. I made a table like: $$ \begin{array}{c|c} \text{Ways of Winning} & \text{Probability} \\ \hline \text{W W W W _ _ _} & (1/3)^4 \\ \color{red}{\text{W W W L }} \text{W _ _} & (1/3)^5\times 4 \\ \color{red}{\text{W W W L L }} \text{W _} & (1/3)^6\times \dfrac{5!}{3!\,2!} \\ \color{red}{\text{W W W L L L }} \text{W} & (1/3)^7\times \dfrac{6!}{3!\,3!} \\ \color{red}{\text{W W W D }} \text{W _ _} & (1/3)^5\times 4 \\ \color{red}{\text{W W W D L }} \text{W _} & (1/3)^6\times \dfrac{5!}{3!} \\ \color{red}{\text{W W W D L L }} \text{W} & (1/3)^7\times \dfrac{6!}{3!\,2!} \\ \vdots & \vdots \\ \color{red}{\text{W D D D D L }} \text{W} & (1/3)^7\times \dfrac{6!}{4!} \\ \color{red}{\text{W D D D D D }} \text{W} & (1/3)^7\times 6 \\ \color{red}{\text{W D D D D D D}} & (1/3)^7\times 7 \\ \end{array} $$ Here the W represents a win for A, L represents a loss while D represents a draw. If a character is in red, it means that it can be exchanged (rearranged) with the other characters in red. If in black, it's position is fixed. Underscores represent any value can be taken at that point.

The procedure I followed is that, for zero draws, I kept adding an extra red L before the last W and still letting A win the tournament. Then I added a red D, then kept adding a red L, again letting A win the tournament. I wrote all such arrangements in this fashion and wrote the corresponding probabilities and added them together. There were 16 such rows for me.

The answer i got was $651/3^7$ or $217/729$, but the answer given is $299/729$. They calculated it by subtracting the probability of a draw from one and then dividing it by two. I understand why they did it, what I don't understand is why our answers don't match!

So, what is wrong with my approach? Am i missing some cases? Or is totally scrap?

$\endgroup$
  • 2
    $\begingroup$ It is quite likely that you missed some cases, specifically $82/729$ of them. There are SO many cases that you're trying to count, it's easy to miss some. $\endgroup$ – vadim123 Jul 15 '16 at 15:31
  • 1
    $\begingroup$ Where in your list do you count the possibility of WWDDDDD? It seems you missed some cases afterall. $\endgroup$ – JMoravitz Jul 15 '16 at 15:47
  • $\begingroup$ @JMoravitz Yeah, I see that now. Well it seems that this method has an inherent problem. I just noticed that for the fourth last case WDDDW_, I took the last W black and the others red. But that misses a few cases like WDWDDD_. There is no simple way to include it too, so basically my method is scrap. Your answer corrects my method, and obviously the best method is the book's method! But all this gave me some good insights! So, thanks! $\endgroup$ – FreezingFire Jul 15 '16 at 16:49
  • $\begingroup$ Also, this is a good related question: math.stackexchange.com/q/172543/319620. $\endgroup$ – FreezingFire Jul 15 '16 at 16:57
10
$\begingroup$

The symmetry between $A$ and $B$ tells you that they each have the same chance of winning the tournament. If you can figure out the probability that the tournament is drawn, you can compute the chance that $A$ wins by taking half of the chance the tournament is not drawn. There are fewer cases to consider than you had to work with. This explains the book approach.

In your calculation, the second and third lines from the end are not correct. When $A$ does not win four games, there is no need for him to win the last game. For the next to last line, the chance that $A$ wins two and there are five draws should be $(\frac 13)^7{7 \choose 2}=(\frac 13)^7\frac {7!}{5!2!}$ because $A$ could have won any two. It looks like you have that problem in all the lines that do not result in $4$ wins for $A$.

$\endgroup$
  • 2
    $\begingroup$ Thank you for the answer! This really helped me realize the fault in my method (along with JMoravitz's comment). This reminds me, for the bazillionth time, "check if you are really including all the cases. Try damn hard to find a counterexample, or prove that there is no case missed"! $\endgroup$ – FreezingFire Jul 15 '16 at 16:52
6
$\begingroup$

Approach similarly to yours except allow the teams to continue playing games even after a winner is inevitable.

We have the following possibilities:

$\begin{array}{|c|c|c|}\hline W&L&D&\text{total arrangements}\\ \hline 1&0&6&7\\ \hline 2&0&5&21\\ 2&1&4&105\\ \hline 3&0&4&35\\ 3&1&3&140\\ 3&2&2&210\\ \hline 4&0&3&35\\ 4&1&2&105\\ 4&2&1&105\\ 4&3&0&35\\ \hline 5&0&2&21\\ 5&1&1&42\\ 5&2&0&21\\ \hline 6&0&1&7\\ 6&1&0&7\\ \hline 7&0&0&1\\ \hline \end{array}$

Each number on the right was found using multinomial coefficients. For example, 3 wins, 2 losses, and 2 draws can be done in $\binom{7}{3,2,2}=\frac{7!}{3!2!2!}=210$ ways.

Adding up the right column, we are left with $897$ possible equally likely cases in which the first player wins the tournament out of $2187$ possible. That is a probability of $\dfrac{299}{729}$, as expected.

As you can see, this was rather tedious, and the shortcut of recognizing it is equally likely for player 1 to end up the victor is equal to the probability of player two ending up the victor is much shorter.

$\endgroup$
  • $\begingroup$ Thank you for the answer! This covers up the shortcomings in my method well. But the book's method is definitely better. And cooler. $\endgroup$ – FreezingFire Jul 15 '16 at 16:53
4
$\begingroup$

Alternative route

Let $N_{A}$ denote the number of times that $A$ wins, and $N_{B}$ the number of times that $B$ wins.

Then:

  • $\Pr\left(\text{no winner}\right)=\sum_{k=0}^{3}\Pr\left(N_{A}=N_{B}=k\right)=3^{-7}\sum_{k=0}^{3}\frac{7!}{k!k!\left(7-k\right)!}$

  • $\Pr\left(A\text{ wins}\right)+\Pr\left(B\text{ wins}\right)+\Pr\left(\text{no winner}\right)=1$

  • $\Pr\left(A\text{ wins}\right)=\Pr\left(B\text{ wins}\right)$

This leads to:

$$\Pr\left(A\text{ wins}\right)=\frac{1}{2}\left[1-3^{-7}\sum_{k=0}^{3}\frac{7!}{k!k!\left(7-k\right)!}\right]=\frac{1794}{4374}=\frac{299}{729}$$

$\endgroup$
  • $\begingroup$ Actually this was the method followed by the book, but thank you for putting it here anyway! It can help others with the same question... :) $\endgroup$ – FreezingFire Jul 15 '16 at 16:54
  • 1
    $\begingroup$ It is not really an answer to your question (which has allready been answered nicely). I am glad, that is appreciated anyhow. $\endgroup$ – drhab Jul 15 '16 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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