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
Math Forum Home || Math Library || Quick Reference || Math Forum Search