binomial coefficient (by hand)
Author Message
binomial coefficient (by hand)

Does anybody have or know where to get the code for computing the
binomial coefficient as you'd do it on a piece of paper/manually?

The problem I having are due to approximations made my the factorial
routine as described by Numerical Recipes.  The error increases when
further approximations are made when I try to compute the binomial
coefficient and then the hypergeometric distribution.

If sumeone is familiar with hypergeometric distribution, to obtain the
p-value, you take the -ln of the sum of probabilities and subtract
them from 1.  Well, the problem is that due to the approximations
described above, when I sum all probabilities the total is greater
than one by 1.0e-6; and probability cannot be defined as negative. In
reality the correct answer should be something very close to 1.0.

How does one encounter these numerical errors when trying to prodict
probabilities of such a low chance?

Mon, 30 May 2005 01:30:49 GMT
binomial coefficient (by hand)

Quote:

> Does anybody have or know where to get the code for computing the
> binomial coefficient as you'd do it on a piece of paper/manually?

> The problem I having are due to approximations made my the factorial
> routine as described by Numerical Recipes.  The error increases when
> further approximations are made when I try to compute the binomial
> coefficient and then the hypergeometric distribution.

> If sumeone is familiar with hypergeometric distribution, to obtain the
> p-value, you take the -ln of the sum of probabilities and subtract
> them from 1.  Well, the problem is that due to the approximations
> described above, when I sum all probabilities the total is greater
> than one by 1.0e-6; and probability cannot be defined as negative. In
> reality the correct answer should be something very close to 1.0.

> How does one encounter these numerical errors when trying to prodict
> probabilities of such a low chance?

i'd suggest doing the calcs in log space and then transforming back into real space (if required) -- this is a common technique for dealing with very large/small numbers.

Mon, 30 May 2005 08:10:45 GMT
binomial coefficient (by hand)

Quote:

> Does anybody have or know where to get the code for computing the
> binomial coefficient as you'd do it on a piece of paper/manually?

> The problem I having are due to approximations made my the factorial
> routine as described by Numerical Recipes.  The error increases when
> further approximations are made when I try to compute the binomial
> coefficient and then the hypergeometric distribution.

> If sumeone is familiar with hypergeometric distribution, to obtain the
> p-value, you take the -ln of the sum of probabilities and subtract
> them from 1.  Well, the problem is that due to the approximations
> described above, when I sum all probabilities the total is greater
> than one by 1.0e-6; and probability cannot be defined as negative. In
> reality the correct answer should be something very close to 1.0.

> How does one encounter these numerical errors when trying to prodict
> probabilities of such a low chance?

Note: I assume you calculate n! etc. directly or via the Sterling
formula.

You could try to avoid the calculation of n! etc:

Compute ( n )
( k ) by:

result = 1
do i = 1,k
result = result * (n-k+1) / k
enddo

The intermediate products are always integer, so no loss of precision

Regards,

Arjen

Mon, 30 May 2005 16:07:55 GMT
binomial coefficient (by hand)
You could divide by your sum to force unity.

If you are doing

n! (n - a)! / a! then you may be better off recasting this as the form

prod1 = 1; prod2 = 1
DO i = 2, n - a; prod1 = prod1 * i; END DO
DO i = a + 1, n; prod2 = prod2 * i; END DO
final_result = prod1 * prod2

(You may want to check that my handling of the result is correct - done on the fly)

Quote:

> > Does anybody have or know where to get the code for computing the
> > binomial coefficient as you'd do it on a piece of paper/manually?

> > The problem I having are due to approximations made my the factorial
> > routine as described by Numerical Recipes.  The error increases when
> > further approximations are made when I try to compute the binomial
> > coefficient and then the hypergeometric distribution.

> > If sumeone is familiar with hypergeometric distribution, to obtain the
> > p-value, you take the -ln of the sum of probabilities and subtract
> > them from 1.  Well, the problem is that due to the approximations
> > described above, when I sum all probabilities the total is greater
> > than one by 1.0e-6; and probability cannot be defined as negative. In
> > reality the correct answer should be something very close to 1.0.

> > How does one encounter these numerical errors when trying to prodict
> > probabilities of such a low chance?

> i'd suggest doing the calcs in log space and then transforming back into real space (if required) -- this is a common technique for dealing with very large/small numbers.

Mon, 30 May 2005 22:20:43 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages