Challenging probability Q

(a) Find P(A(i)), i = 1, ..., n
P(A_i)=(1/2)^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)/C(2^n, 2) = (1/2)^(n-1)
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) let B(i) denote the event that A and B play each other in game i, i = 1, ..., 2^n-1 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
(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).