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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.