#include
#include
#include
using namespace std;
//
// This program prints out some of the probabilities
// of seeing k consecutive heads in n tosses at for probabilities
// of 90%, 99%, 99.9%, and so on.
//
// Author: Mark Nelson
//
// See http://marknelson.us/2011/02/13/a-big-problem-that-doesnt-need-a-bignum
//
int main() {
const int k = 20;
//
// Before the loop is entered, the deque is set
// to the correct values for n=0 - that is, it
// contains F(2) divided by 2^0. Each time
// through the loop n is incremented by 1.
//
deque q(k, 0);
q[0] = 1.0;
q[1] = 1.0;
double seeking = 0.1;
for ( int i = 1 ; ; i++ ) {
q.push_front( 0.0 );
for ( int j = 1 ; j <= k ; j++ ) {
q[ j ] /= 2.0;
q[0] += q[j];
}
q.pop_back();
if ( q[0] < seeking ) {
cout << "There is a " << 100*(1-seeking)
<< "% probability of seeing " << k
<< " consecutive heads in " << i
<< " tosses of a fair coin"<< endl;
seeking /= 10;
if ( seeking < .00001 )
return 0;
}
}
return 0;
}