All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Many Heads part 2 (Posted on 2021-08-02) Difficulty: 3 of 5
A coin is biased with P(heads)=p.

What is the expected number of flips to get n consecutive heads?

For a fair coin, here is the original Many Heads.

No Solution Yet Submitted by Jer    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution trial and error with the computer | Comment 1 of 2
p=1/3;
cHad=zeros(1,7);
for trial=1:1000000
   had=zeros(1,7); 
   toss=0; noHad=0;
   while had(7)==0
      r=rand;
      toss=toss+1;
      if r<p
         noHad=noHad+1;
         if had(noHad) == 0
            had(noHad) = toss; 
            cHad(noHad)=cHad(noHad)+toss;
         end
      else
          noHad=0;
      end
   end
end
cHad=cHad/trial;
for i=1:7
   disp([i cHad(i)]) 
end

finds after a million trials, the average number of tosses to get n in a row when p = 1/3 are:


 n             number of tosses
 
 1                  3.001766
 2                 12.000364
 3                 39.002595
 4                119.839147
 5                362.422748
 6               1089.524599
 7               3279.016219
 
Looking up 3, 12, 39, 120 in the OEIS we find  A029858,  a(n) = (3^n - 3)/2, leading to conjecture that E(n) = (1/p^n - 1/p) / 2.

For a fair coin (p = 1/2) we'd predict (2^n - 2) / 2 = 2^(n-1) - 1. But

 n               number of tosses                (2^n - 2) / 2

 1                   2.00201                         0
 2                    6.0366                         1
 3                  13.92041                         3
 4                  29.87251                         7
 5                  61.89579                        15
 6                 125.83007                        31
 7                 255.76048                        63
 
Perhaps the 2 in the denominator is actually 3-1. Then it would be 2-1 for the case of p = 1/2:

 n               number of tosses                 formula
 1                    2.0012                        -1
 2                   6.02266                         0
 3                  14.04181                         2
 4                  30.03818                         6
 5                  62.24075                        14
 6                 126.41717                        30
 7                 253.84761                        62

 
Looks like we're getting the expected value for n-2.  So instead of (1/p^(n-1) - 1/p) / (1/p - 1), try (1/p^(n+1) - 1/p) / (1/p - 1)

 1                   2.00426                         2
 2                   5.98119                         6
 3                  13.98262                        14
 4                  29.94804                        30
 5                  61.61188                        62
 6                 125.33954                       126
 7                 252.61914                       254

OK, that works for p=1/2, what about back at p=1/3?:

 1                   3.01046                         3
 2                  12.02261                        12
 3                  39.25753                        39
 4                 120.55419                       120
 5                 365.10167                       363
 6                1092.11087                      1092
 7                3283.99898                      3279
 
It still fits. For good measure, p=1/4: 

  1                   3.99144                         4
  2                   19.9314                        20
  3                  83.80132                        84
  4                 340.25499                       340
  5                1361.95732                      1364
  6                5473.16279                      5460
  7               21882.14931                     21844
  
  Well another, p = 1/5 (this time we'll leave out n=7; that'd take too long):
  
 1                   5.00394                         5
 2                  30.04088                        30
 3                 154.90385                       155
 4                 779.05481                       780
 5                 3897.8722                      3905
 6               19593.49331                     19530  
  
It looks like (1/p^(n+1) - 1/p) / (1/p - 1) is it.  

Waiting for 7 would be expected to take 97655 trials, and we were trying 100,000 trials (down from a million for the smaller probabilities) each of these test runs. If we had been waiting to get 7, we'd have been waiting 9,765,500,000 tosses (expected).



  Posted by Charlie on 2021-08-02 13:36:56
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information