From: dnk@OMIT.cs.mu.oz.au   
      
   "Andrew Au Ying Hung"  wrote in message news:bmi1   
   5$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.   
      
   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   
      
   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)