Re: Stupid question in probability that amazed me

David <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> "Andrew Au Ying Hung" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> > 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.

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. 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.

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.
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.

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.


>
> 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.



>
> David

Martin

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <[EMAIL PROTECTED]>, and ]
[ ask your news administrator to fix the problems with your system. ]