Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Prob of flipping coin n times, at no time with #h > #t?
Replies: 10   Last Post: Feb 14, 2013 2:25 AM

 Messages: [ Previous | Next ]
 JohnF Posts: 219 Registered: 5/27/08
Re: Prob of flipping coin n times, at no time with #h > #t?
Posted: Feb 8, 2013 6:23 AM

=== Please see preceding posts in this thread for detailed discussion ===

>>> Numerically, mine gives (haven't programmed yours yet, to check agreement)
>>> n | P_n
>>> ----+--------
>>> 0 | .5
>>> 1 | .375
>>> 2 | .3125
>>> . | ...
>>> 4999| .00798
>>> 9999| .00564
>>> 19999| .00399
>>>
>>> yours: p(2n+1) = C(2n+1,n+1)/2^(2n+1)
>>> mine: P_{2n+1} = 0.5 - sum(i=1...n) { 1/(2i) * 1/(2^(2i)) * C(2i,i+1) }

>
> Yours indeed matches mine for n=0,1,2, as per numerical table above.
> I'll have to do a little more work to check the large n cases.
> And I fooled around a little algebraically, but so far failed to prove
> them equal.

Large n cases also check. Use prog below, e.g., for n=19999
we have 2n+1=39999 and n+1=20000, so enter
./prog 39999 20000
and it prints
C(39999,20000)/2^39999 = 0.00398940
in exact agreement with above table.

# include <stdio.h>
# include <math.h>
int main ( int argc, char *argv[] ) {
int n = (argc>1? atoi(argv[1]) : 10 );
int k = (argc>2? atoi(argv[2]) : n/2 );
double bweight(), bw=bweight(n,k);
printf("C(%d,%d)/2^%d = %.8f\n", n,k,n,bw);
} /* --- end-of-main() --- */

/****************************************************************************
* Function: bweight ( n, k )
* Purpose: Calculate C(n,k)/2**n = [n!/(k!(n-k)!)]/2**n.
* --------------------------------------------------------------------------
* Arguments: n (I) n items...
* k (I) ...taken k at a time
* Returns: (double) as above, or 0 for any argument error
* --------------------------------------------------------------------------
* Notes: o Algorithm prevents dividing one (very) large number
* by another. Note that C(n,k) = n!/(k!(n-k)!) and
* recursion relation C(n,k) = n/k*C(n-1,k-1) until C(n-k,0)=1.
* To prevent the numerator from getting too large,
* we divide successive terms by powers of 2.
* At the end, we divide by any remaining powers of two
* for the total 2**n factor.
***************************************************************************/
/* --- entry point --- */
double bweight ( int n, int k )
{
/* --- allocations and declarations --- */
double weight=1.0; /* init weight */
int i = (k<n-k?k:n-k); /* (n,k)=(n,n-k) smaller #terms */
int n2 = n; /* #powers of 2 to divide by */
if ( n<0 || k<0 || n<k ) return(0.0); /* check args / return error */
/* --- accumulate weight --- */
while ( i > 0 ) { /* need another term */
weight *= ((double)n)/((double)i); /* recursion */
while (weight>1.0 && n2>0) { weight *= 0.5; n2--; } /*keep weight "slim"*/
n--; i--; /* next term */
} /* --- end-of-while(i>0) --- */
/* --- rescale weight with any remaining powers of two and return --- */
if ( n2 > 0 ) weight /= pow(2.0,(double)(n2)); /* remaining powers of 2 */
return ( weight ); /*return binomial weight to caller*/
} /* --- end-of-function bweight() --- */

--
John Forkosh ( mailto: j@f.com where j=john and f=forkosh )

Date Subject Author
2/6/13 JohnF
2/6/13 Robin Chapman
2/7/13 JohnF
2/14/13 James Waldby
2/14/13 JohnF
2/6/13 RGVickson@shaw.ca
2/6/13 RGVickson@shaw.ca
2/7/13 JohnF
2/7/13 RGVickson@shaw.ca
2/8/13 JohnF
2/8/13 JohnF