From: dnk@OMIT.cs.mu.oz.au
In "Martin Gradwell" writes:
> David wrote in message
> news:bmlcrc$imn$1@mulga.cs.mu.OZ.AU...
> > "Andrew Au Ying Hung" wrote in message
> news:bmi1t5$i3q$1@mulga.cs.mu.OZ.AU...
> > > Dear all,
> > >
> > > Here is a simple question of probability that I tried hard for a
> half
> > > day with no result.
> > >
> > > Given a game of tossing coin, not until the recent three tosses have
> exactly
> > > two heads up, I will keep tossing.
> > > What is the expectation of the number of toss I have the made?
> > >
> > > The problem looks simple, but it turns out quite hard to solve, at
> > > least, for me. Please spend a little time to try it out ^^
> >
> > Scratching around with pen and paper over lunch, I got 31/6 .
> > (I'm rusty on this sort of math, so no guarantees on that value)
> > Here's my assumptions and a brief outline of the logic ...
> >
> > We need at least 3 tosses because we seek a pattern of length 3.
> > Any one of the sequences THH, HTH, and HHT terminates the game.
> > The coin toss is assumed to be fair.
> >
> > Consider the situations where we have made (at least) 2 tosses but
> > the game has not yet terminated. With equal probability (1/4)
> > the last two tosses must be one of the sequences TT, TH, HT or HH.
> The error here is in the phrase "with equal probability". If we
> had no knowledge about the recent state of the game, then these
> four possibilities would indeed be equiprobable. But we are
> considering the situation where the game has not yet terminated.
> Since the game only terminates when there has been a preponderance
> of heads, the fact that it hasn't terminated suggests the likelihood
> that there has been a preponderance of tails.
You're right that the these 4 cases aren't equiprobable in general,
but they are equiprobable after throwing 2 tosses. I miss-stated
that but I don't believe it affects the analysis below.
> There are 8 possible sequences of 3 coin tosses to start the game off:
> ttt,tth,tht,thh,htt,hth,hht,hhh, and of these four (thh,hth,hht,hhh)
> end the game straight away.
No, HHH does not terminate the game, because the requirement is
"exactly two heads up" of the last 3, not at least 2.
> In the remaining 4 cases (ttt,tth,tht,htt) the last 2
> tosses are tt, th, or ht.NOT hh. And tt is twice as likely as th or ht
> because it occurs in two cases, and they each occur in only one.
> The chances of tt, th and ht are 0.5, 0.25 and 0.25 respectively.
If it hasn't terminated after 3 tosses, the chances of TT, TH, HT and
HH are 0.4, 0.2, 0.2 and 0.2 respectively.
> Now consider the case where the game has been played for a
> long time without terminating. Not very likely, but it needs to be
> considered. The game will approach an equilibrium state in which
> TT is twice as likely as TH, which in turn is twice as likely as HT.
> So the chances of tt, th and ht are 4/7, 2/7and 1/7 respectively.
I don't think so. If we make a toss and the game doesn't terminate,
then TT becomes either TT or TH with equal probability, TH must
become HT, and HT must become TT. HH must become HH. The probability
of getting a continuous sequence of H's becomes vanishingly small,
and the ratio of HT to TH to TT is given by successive triples from
the following sequence, which certainly doesn't converge to 1:2:4 .
1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872 1278 1873 ...
> The longer the game is played without terminating, the closer the
> probabilities will get to this equilibrium state, but they'll never get
> there exactly.
They converge to an(other) equilibrium, sure, with vanishing probability.
> In short, it is indeed a complicated problem. The best way to
> "solve" it is probably to run a simulation. There are similarities
> to a problem made famous by Marilyn Vos Savant, the Monty
> Hall problem, but that was simpler because it always terminated
> after a small number of steps.
I still suspect that the analysis below is correct. The recurrence
relations do not depend on the miss-stated equiprobability assumption.
It is only used to combine the results to get the overall expectation,
in a way that is valid because equiprobability applies after 2 tosses.
> >
> > Let Xtt, Xth, Xht and Xhh be the expected number of tosses till
> > game termination starting from each of these situations. Considering
> > what will happen on the next toss, we can write the equations:
> >
> > Xtt = 1 + (Xtt + Xth)/2
> > Xth = 1 + (Xht + 0 )/2
> > Xht = 1 + (Xtt + 0 )/2
> > Xhh = 1 + (0 + Xhh)/2
> >
> > i.e., In state TT, then after one more toss there's an equal chance
> > of T (giving state TT again) and of H (giving state TH), and so forth.
> >
> > Solving these recurrence relations, we get:
> >
> > Xtt = 14/3
> > Xth = 8/3
> > Xht = 10/3
> > Xhh = 6/3
> >
> > So the overall expectation = 2 + (14/3 + 8/3 + 10/3 + 6/3)/4 = 31/6
> you're working along the right lines, but since the four cases aren't
> equiprobable
> (and if the game hasn't finished after n>2 tosses then the last two tosses
> *can't*
> have been hh) you can't just add all the figures up and divide by 4.
OK, please run the simulation, and let us know what you get.
> >
> > David
> Martin
David
[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to , and ]
[ ask your news administrator to fix the problems with your system. ]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
