0
$\begingroup$

I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$). I am trying to figure out the following:

  1. I need to know, if it shoud work for large numbers: i.e. K=501000, N=10^6, P=0.5

  2. Is there a way to calculate how long the computation takes?

Maybe it is possible to perform a computer routine that calculates an approximation? Like Poisson Probability

$\endgroup$
  • $\begingroup$ Whether it should work for large numbers is up to you. $\endgroup$ – Yuval Filmus Apr 12 '18 at 7:43
  • $\begingroup$ Programming is offtopic here. I expect that part of your question might be better served on Computational Science or Stack Overflow. $\endgroup$ – Raphael Apr 12 '18 at 7:44
  • 1
    $\begingroup$ Instead of writing your own routine, I suggest looking for a library in which such a routine is already implemented. $\endgroup$ – Yuval Filmus Apr 12 '18 at 7:45
2
$\begingroup$

If you can avoid it, you don't want to compute sums like that at all.

  1. If you compute terms like $p^k$ directly, you'll get big errors due to floating-point precision (because your result will be almost zero).

    If you haven't seen it, one common way to handle small probabilities is to apply the logarithm trick:

    $\qquad \displaystyle p^k(1-p)^{n-k}\ \leadsto\ k \cdot \log p + (n-k) \cdot \log(1-p)$.

  2. If possible, apply well-known closed forms for sums to eliminate them entirely. Computing that is less problematic, both in terms of numerical issues and running time.

  3. Failing that, find an approximation that you can tune to the required precision.

And also:

  • Computing running times with an algorithm is not computable in general. You will have to apply algorithm analysis yourself. After implementing an actual algorithm, that is. See a good textbook or our reference questions for starters.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a closed form for that sum? I wasn't aware of one (only bounds on it and approximations). $\endgroup$ – D.W. Apr 12 '18 at 17:12
  • $\begingroup$ @D.W. If memory serves, the sum starting from $k=0$ is $1$. It may be possible to find a nice closed form for the sum from $k=1$ to $i-1$, but I haven't checked. $\endgroup$ – Raphael Apr 12 '18 at 21:26
  • $\begingroup$ Yes, for the special case of summing over $k=0..n$, of course the answer is 1 (probabilities sum to 1). However for the general case of summing over $i..n$, I don't believe there are any closed forms -- at least, none known to me. So, I'm confused by your suggestion to use well-known closed forms, and I'm wondering if you can either elaborate on that -- or if perhaps you might want to delete that suggestion. $\endgroup$ – D.W. Apr 12 '18 at 21:44
  • $\begingroup$ @D.W. Better now? (I really don't know if/how this specific sum can be simplified; it looked attackable.) $\endgroup$ – Raphael Apr 14 '18 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.