Statistics

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).