Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


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


JohnF <john@please.see.sig.for.email.com> wrote:
=== 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); } /*  endofmain()  */
/**************************************************************************** * Function: bweight ( n, k ) * Purpose: Calculate C(n,k)/2**n = [n!/(k!(nk)!)]/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!(nk)!) and * recursion relation C(n,k) = n/k*C(n1,k1) until C(nk,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<nk?k:nk); /* (n,k)=(n,nk) 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 */ } /*  endofwhile(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*/ } /*  endoffunction bweight()  */
 John Forkosh ( mailto: j@f.com where j=john and f=forkosh )



