Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Contest Probabilities


Date: 10/10/98 at 05:10:43
From: Navid
Subject: Probability

Players are of equal skill, and in a contest the probability is 0.5 
that a specified one of the two contestants will be the victor. A 
group of 2^n players is paired off against another at random. The 
2^(n-1) winners are again paired off randomly, and so on, until a 
single winner remains. Consider two specified contestants, A and B, 
and define the events A(i), i<=n, and E by:
 
   A(i): A plays in exactly i contests
   E:    A and B ever play each other

   a) Find P(A(i)), i = 0, ..., n

   b) Find P(E)

   c) Let P(n) = P(E). Show that:
      P(n) = 1/(2^n - 1) +  (2^n - 2)/(2^n - 1) (1/4) P(n-1)

   d) Explain why a total of 2^n-1 games are played. Number these games 
      and let B(i) denote the event that A and B play each other in  
      game i, i = 1, ..., 2^n-1

   e) What is P(B(i))?

   f) Use part (e) to find P(E).


Date: 10/14/98 at 10:22:09
From: Doctor Anthony
Subject: Re: Probability

a) Find P(A(i)), i = 1, ..., n

The number of contestants halve for each round of the competition.

So the probability that any contestant will go out at first round is 
1/2. The probability of going out at the second round is 1/4; at the 
3rd round it is 1/8; and so on. Thus P(A(i)) = 0.5^(i).

b) Find P(E).

Since there are 2^n - 1 actual pairings against a possible C(2^n, 2) 
pairings, the chance that any two people meet is:

     2^n - 1          2^n - 1         2
   ----------- = ---------------- = ----- = 1/2^(n-1)
    C(2^n, 2)     2^n (2^n - 1)/2    2^n 

For example, if n = 5 there are 32 players and the number of possible 
pairs is C(32,2) = 496.

The probability that A and B will meet is 31/496 = 1/16 = 1/2^4

So the probability that A and B will meet is 1/2^(n-1)
    
c) Let P(n) = P(E). Show that:
    P(n) = 1/(2^n - 1) +  (2^n - 2)/(2^n - 1) (1/4) P(n-1)

In the first round A has 2^n - 1 possible adversaries, of whom one 
is B. So the probability that he will play B in the first round is 
1/(2^n - 1).

The probability that A will not play B in first round and 
that both A and B will go forward to the next round is 
[(2^n - 2)/(2^n - 1)](1/2)(1/2). 
 
In the next round there will be 2^(n-1) players and the probability 
that A and B will meet is now P(n-1).

So now we can see the connection between P(n) and P(n-1).

   P(n) =  1/(2^n - 1) +  (2^n - 2)/(2^n - 1) (1/4) P(n-1)
               |                       |
               |                       |
       meet in first round    don't meet in first round but do later 


d) Explain why a total of 2^n - 1 games are played.  

There are 2^n players and each game eliminates one player. So all 
together with just one winner we must eliminate 2^n - 1 players, and 
this requires 2^n - 1 games.

e) What is P(B(i))?

You cannot go through all the ways that A and B might meet in the ith 
game, but if you think globally, there is no reason why any particular 
pair should have any different probability of meeting in the ith game 
than any other pair. Since there are C(2^n,2) possible pairs, the 
probability that any pair will meet in the ith game is 1/C(2^n,2).

So P(B(i)) = 1/C(2^n,2) for all i = 1 to 2^n - 1
   
                   1                 2
           = --------------  =  ------------
             2^n(2^n - 1)/2     2^n(2^n - 1)

                      1
           =  ------------------  for all i = 1 to 2^n - 1
               2^(n-1) (2^n - 1)
               

f) Use part (e) to find P(E).

Clearly P(E) will simply be the sum of all the probabilities P(B(i)).

Since they are all equal, as shown in part (e), we simply multiply by    
(2^n - 1) to find the sum.

So P(E) = 1/2^(n-1), which agrees with the answer we gave in (b).

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Probability

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/