Another probability question from my textbook

Suppose that we have a tennis tournament with 32 players. Players are matched in a completely random fashion, and we assume that each player always has probability 1/2 to win a match. What is the probability that two given players meet each other during the tournament.

• I am trying to teach myself probability. Just to clarify, not exactly a student looking for homework solutions - but still a student – user669083 Jan 23 '12 at 22:29

Easy general answer for $n$ players in a knockout tournament (and here $n=32$):

There are $\dfrac{n(n-1)}{2}$ potential pairs for matches.

To have one winner, $n-1$ players must be knocked out, so there are $n-1$ actual matches.

So the probability that a particular pair actually have a match is $\dfrac{n-1}{{n(n-1)/2}} = \dfrac{2}{n}$.

• Very elegant!  – Rasmus Jan 24 '12 at 7:27
• yes it seems to be most elegant one. – user669083 Jan 24 '12 at 16:15

Hint 1: Consider the number of other players a particular player meets with what probability: one other with probability $1/2$; two others with probability $1/4$; three others with probability $1/8$; etc.

Hint 2: What is the expected number of other players a particular player meets?

Hint 3: How does Hint 2 relate to the original question?

Answer: $$\dfrac{1 \times \dfrac{1}{2} + 2 \times \dfrac{1}{2^2} + 3 \times \dfrac{1}{2^3} + 4 \times \dfrac{1}{2^4} + 5 \times \dfrac{1}{2^4}}{31} = \dfrac{1}{16}$$

• probably you are at the right path but still not getting your solution. What is wrong with what Rasmus thought ? – user669083 Jan 23 '12 at 22:52
• still stuck guys. Help please. – user669083 Jan 23 '12 at 23:02
• Shouldn't his expected number of players be 1*1+2*1/2+3*1/4+4*1/8+5*1/16. Because he definitely meets one person in first round. He meets the second person with a probability of half and so on... – user669083 Jan 24 '12 at 17:26
• @user669083: He cannot go further than the 5th round because the tournament is over, so the probability of finishing in the 5th round is $1/2^4$ rather than the $1/2^5$ it would be if there were further rounds. – Henry Jan 24 '12 at 18:58
• not exactly what I asked. I said he is definitely meeting one in round one. So probability of that should be 1 not 1/2, then same with meeting 2 people should be half. If he reaches 2nd round, he will meet two people by then. Your answer is correct. I am just trying to increase my understanding. – user669083 Jan 24 '12 at 21:52

I get $$\frac{1}{31} +\frac{30}{31}\frac{1}{4}\left(\frac{1}{15} +\frac{14}{15}\frac{1}{4}\left(\frac{1}{7} +\frac{6}{7}\frac{1}{4}\left(\frac{1}{3} +\frac{2}{3}\frac{1}{4}\right)\right)\right)$$ which equals $\dfrac{1}{16}=6.25\%$. Not sure if this is the most elegant solution, though.

• I thought the same but the answer is 1/16 ? – user669083 Jan 23 '12 at 22:48
• @user669083: You are right. I just forgot the factor $\frac{2}{3}$. – Rasmus Jan 23 '12 at 23:01
• See my later answer for a more general and less arithmetic solution. – Henry Jan 23 '12 at 23:42