From: dnk@OMIT.cs.mu.oz.au   
      
   In  JXStern  writes:   
      
   >On Thu, 16 Oct 2003 06:12:07 GMT, dnk@OMIT.cs.mu.oz.au (David) wrote:   
   >>So the overall expectation = 2 + (14/3 + 8/3 + 10/3 + 6/3)/4 = 31/6   
      
   >In other words, four tosses, where three was the min possible.   
      
   5 and a bit, actually.   
      
   >I agree.  Seat of the pants reasoning:   
   >Either the first three tosses give you the condition and you're done   
   >right there, or the last two had a 50% odds of being either HT or TH,   
   >and you have a 50-50 change of getting the third H on the next, so   
   >you're over 50% odds on the whole deal at that point, plus other more   
   >complicated scenarios.   
      
   >Now, if you change the question to 99% certainty of the result, ...   
      
   That seems like a much harder question, but rather amazingly there's   
   a very simple sequence that gives the probability of non-termination   
   after n>2 tosses:   
      
   3, 4, 5, 7, 10, 14, 20, 29, 42, 61, 89, 130, 190, 278, 407, 596, ...   
      
   (The recurrence relation is given by Sn = Sn-1 + Sn-3 - 1  for N > 3,   
   I suppose you could call it a Pythagorean Triple Fibonacci sequence :)   
      
   It tells you after 3 tosses the probability of non-termination is 5/8,   
   after 4 tosses it's 7/16, after 5 tosses it's 10/32, and so on.   
      
   To get it under 1% takes 16 tosses (596/65536)   
      
   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)