A game is played starting with 6 fair coins laid out with heads face up.
Each round consists of flipping all of the coins showing heads.
If fewer than half of the flipped coins come up heads the player loses.
Rounds continue until the player either loses or has one heads remaining.
The player wins by getting to one heads without losing.
What is the probability of winning this game?
Examples:
6→4→1 would be a loss. (1 is less than half of 4.)
6→5→3→2→2→2→1 would be a win.
5 point 10
10 print 1-fnPLose(6),(1-fnPLose(6))/1
20 end
30
40 fnPLose(N)
50 local Pl,H,Ph,Totph
60 Pl=0:if N=1 then goto 150
65 Totph=0
70 for H=0 to N-1
80 Ph=combi(N,H)//2^N
85 Totph=Totph+Ph
90 if H>=N//2 then
100 :Pl=Pl+Ph*fnPLose(H)
110 :else
120 :Pl=Pl+Ph
130 :endif
140 next H
145 Pl=Pl//Totph
150 return(Pl)
Note that the situation of all the tossed coins coming up heads had to be ignored to avoid an endless regression. This is legitimate as the transition to a lower value is essentially inevitable, and the normalization of the probabilities takes place in line 145 where the probability of losing from a given number of heads is increased by the factor of the reciprocal of the total probabilities accounted for by situations of a decrease in the number of heads.
The program finds
52//279 0.186379928315412186379928315412186379928315412185
meaning the probability is 52/279, or 0.186379928315412..., with the ellipsis starting the endless repetition with the 1863.
Simulation verification:
FOR tr = 1 TO 1000000
n = 6
loss = 0: win = 0
DO
hds = 0
FOR c = 1 TO n
h = INT(RND(1) * 2)
hds = hds + h
NEXT
IF hds < n / 2 THEN loss = 1 ELSE IF hds = 1 THEN win = 1
n = hds
LOOP UNTIL loss = 1 OR win = 1
losses = losses + loss
wins = wins + win
PRINT wins, losses, tr
NEXT tr
does a million trials, resulting in 186865 wins.
|
Posted by Charlie
on 2011-01-25 15:30:27 |