Subject: Re: CCL:Calc Binomial Dist. Function.

From: "Elizabeth A. Abbott" <[email-masked]>
Date: Sun, 28 Nov 1999 15:06:18 -0500

Hi Iraj,

You might want to check out _Introduction to Algorithms_ by Cormen,
Leiserson, and Rivest (Chapter 6: counting and probability) and/or Knuth's
_Art of Computer Programming_ Vol 2: Seminumerical Algorithms.

CL&R give upper and lower bounds for (N,k).

Lower bound:
(n,k) = n(n-1)...(n-k+1)
           --------------------
           k(k-1)...1

        = (n/k) ( (n-1)/(k-1) ) ... ( (n-k+1)/1 )

        >= (n/k) ^k

Upper bound:
(n,k) = n(n-1)...(n-k+1)
           ----------------------
           k(k-1)...1

        <= n^k / k!

         <= (en / k ) ^k 

since we know k! >= (k/e)^k from Stirling's apx.

CL&R also give an upper bound for the binomial prob. dist.

b(k;n,p) <= (np/k) ^k  *  (nq/(n-k) ^ (n-k)

(q is just 1 -p)

Sorry to switch notation from N,n to n,k on you, but I have a hard enough
time getting it onto the screen without translating, too.  :)  Hope this is
of some help.  Check out Knuth.

-Liz
(can you tell I wandered into comp chem from cs and applied math?? :-)

At 28-11-99 13:49 -0500, you wrote:
>
>Hello.
>
>The binomial prob. density function is ubiquitous in stat mech:
>
>P(x) = (N,n) * p^n * (1-p)^(N-n)
>
>The question is how does one-- practically -- compute
>the above formula for very large N and n. 
>
>I have been playing around with the numerical recipes BICO function for N
>around 206 and n around 106---it returns
>
>inf or nan()--- thus P(x) is inf or nan...
>
>We understand that bico uses something akin to stirling's approx... using
>the relation: n! = Gamma(n+1) where Gamma is the gamma function...
>
>Is there a trick to calculation this density function...Maybe calculating
>first the product of the p's then dividing then multiplying by e(ln(N))...
>
>Thanks. Iraj.
>
>
>
>Iraj Daizadeh, Ph.D.
>Harvard University
>Department of Cellular and Molecular Biology
>The Biological Laboratories
>16 Divinity Avenue
>Cambridge, MA 02138
>Phone:   (617) 495-0783
>         (617) 495-0560
>Fax:     (617) 496-4313
>Email:   [email-masked]
>WebPage: http://mcb.harvard.edu/gilbert/daizadeh
>
>
>
>-= This is automatically added to each message by mailing script =-
>[email-masked] -- To Everybody    |   [email-masked] -- To
Admins
>[email-masked] -- HELP CHEMISTRY or HELP SEARCH
>[email-masked] -- archive search    |    Gopher: gopher.ccl.net 70
>Ftp: ftp.ccl.net  |  WWW: http://www.ccl.net/chemistry/   | Jan: [email-masked]
>