| |
BGonline.org Forums
Two ways to get the limiting probability
Posted By: Bob Koca In Response To: Solution and related problem (Bob Koca)
Date: Friday, 12 April 2019, at 3:00 a.m.
Method 1: Prove a rule for P(N) and then take limit:
Let P(N) be the probability of a split if there are 2^N players.
P(1) = 0.
If one has calculated P(k) one can find P(k+1) by observing that there is a chance of (2^k- 1/(2^(k+1)-1) that the players are in the same half of the draw and a chance of (2^k/(2^(k+1)-1) that the players are in opposite halves. If they are in the same half we have reduced the problem to the previous case. If they are in opposite halves then their results are independent until a possible finals so can directly calculate split chance as P(both win exactly 0 OR both win exactly 1 OR both win exactly 2 OR ... both win exactly k-1) H = (1/4) + (1/16) + (1/64) + ... 1/[(2)^(2k-2)]
Thus a recurrence is
P(N) = (2^k- 1/(2^(k+1)-1) P(N-1) + (2^k/(2^(k+1)-1)H
Use it to calculate a few values and conjecture that P(N) = ( 2^(N-1) -1)/(3*2^(N-1)) which can then be proved by induction (left as an exercise for the reader).
The limit of that as N -> infinity is 1/3.
Maik's combinatorial explanation might make things a little easier here.
METHOD 2: Relate to a more easily solved situation and argue that it approaches that in the limit.
Suppose that instead of playing in a tournament that the two players just flip coins until a Tail (think of that as a loss) is obtained. The chance that they take the same number of flips is P(both take exactly one flip OR both take exactly 2 flips OR ....) = 1/4 + 1/16 + 1/64 + ... That is a geometric sum with first term 1/4 and ratio 1/4 which gives a sum of 1/3. Alternatively one could reason that 1/4 of the time they both get a tail on the first flip which gives a tie, 1/2 of the time the results are different which gives no tie, and 1/4 of the time they both get a head which gives a repeat of the sitution. Thus P = 1/4 + (1/4)P. Solving gives P = 1/3.
Why does that not give the probability of a split in a toruney with two players? There is a maximum to number of games that would be played and if they happen to play each other the result of which player wins is no longer independent. As N -> infinity though the probability of the two players playing each other and the probability of running out of games to play (by winning the tournament) both go to zero so in the limit chance of a split is 1/3.
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.