Professor X smokes a pipe. He carries two identical matchboxes, originally containing 20 matches each. When he lights his pipe, he chooses a matchbox at random and lights his pipe with one match and discards the used match.
There will eventually arise an occasion when he first selects a matchbox with only one match in it. At this point, what is the expected number of matches in the other box?
Keep in mind that when the professor "first selects a matchbox with only one match in it", he is, on that occasion, reducing the number of matches in that box to zero.
The probability that there will be 20 remaining in the other box is that of the first 20 matches all being chosen from the same box, which is 2*(1/2^20).
That there are 19 in the other box is the probability that exactly 1 of the first 20 is from that "other" box and the 21st is from the same box as the majority of the others. The probability of this is 2*C(20,1)*(1/2^21).
That there are 18 in the other box is the probability that exactly 2 of the first 21 were from the "other" box and the 21st is from the same box as the majority. This is 2*C(21,2)*(1/2^22).
In general then, the probability there are 20 - n remaining in the other box is
2*C(19+n,n)*(1/2^(20+n))
The first case, that there are 20 remaining in the "other" box, fits this as C(19,0) = 1.
To get the expected number remaining in the other box, we need multiply each such probability by the given number 20 - n and add all such contributions up.
The probabilities of the exact numbers of matches remaining in the other box are tabulated:
number probability expectation
remaining rational fraction decimal contribution
20 1/524288 0.000001907 0.000038147
19 5/262144 0.000019073 0.000362396
18 105/1048576 0.000100136 0.001802444
17 385/1048576 0.000367165 0.006241798
16 8855/8388608 0.001055598 0.016889572
15 5313/2097152 0.002533436 0.038001537
14 44275/8388608 0.005277991 0.073891878
13 82225/8388608 0.009801984 0.127425790
12 2220075/134217728 0.016540848 0.198490173
11 1726725/67108864 0.025730208 0.283032283
10 10015005/268435456 0.037308801 0.373088010
9 13656825/268435456 0.050875638 0.457880739
8 141120525/2147483648 0.065714365 0.525714923
7 10855425/134217728 0.080879219 0.566154532
6 51175575/536870912 0.095321937 0.571931619
5 57998985/536870912 0.108031528 0.540157640
4 2029964475/17179869184 0.118159484 0.472637935
3 1074687075/8589934592 0.125110042 0.375330125
2 4418157975/34359738368 0.128585321 0.257170641
1 4418157975/34359738368 0.128585321 0.128585321
The probabilities do add up to 1 and the expected value comes out to be 172308161025/34359738368 = 5.01482750478317029774188995361328125 (this is the exact terminating decimal, as the denominator is a power of 2).
10 for N=0 to 19
20 P=2*combi(19+N,N)//2^(20+N)
30 Expected=Expected+P*(20-N)
40 Totp=Totp+P
50 print 20-N,P;
60 print tab(40);using(1,9),P/1,P*(20-N)/1
100 next
105 print
110 print Totp,Expected,Expected/1
Simulation verification:
DEFDBL A-Z
FOR trial = 1 TO 1000000
mb(0) = 20
mb(1) = 20
DO
r = INT(RND(1) * 2)
mb(r) = mb(r) - 1
LOOP UNTIL mb(0) = 0 OR mb(1) = 0
v = mb(0) + mb(1)
tot = tot + v
n = n + 1
PRINT tot; n, tot / n
NEXT
produces as its last line of output:
5013755 1000000 5.013755
meaning that 5,013,755 matches were left in the "other" boxes when the trial was repeated a million times for a mean of 5.013755.
|
|
Posted by Charlie
on 2010-03-30 15:27:18 |
solution
