I have a vector of different probabilities to get 1, for example probs = [0.1, 0.5, 0.2, 0.9, 0.25, 0.55] I have to calculate the probability of having at least four ones.

Straightforward way to calculate this is to calculte the prob of having zero ones, one ones, two ones, three ones, sum these probabilities and then subtract this sum from one. The problem is that calculation of exactly n ones is very consuming(because of available combinations), especially, when the length of the vector is about 35 and I have to calculate at least 18 ones.

Are there any ways to calculate approximate probability for such cases?


Assuming independence, an approximation might be to look at a normal distribution with mean $\sum p_i$ and variance $\sum p_i(1-p_i)$

and then find the probability of exceeding $17.5$

A precise calculation is not actually that difficult: suppose $X_i$ represents the number of ones from the first $i$ cases, then you can say $\mathbb P(X_i=n) = p_i\mathbb P(X_{i-1}=n-1) +(1-p_i)\mathbb P(X_{i-1}=n)$ starting from $\mathbb P(X_0=0) =1$

  • $\begingroup$ Thanks, could you be so kind to give me the link to the details(why this is correct) or what phrase should I google to find? $\endgroup$ – Ivan Mishalkin May 31 at 12:47
  • $\begingroup$ @IvanMishalkin Which part are you finding difficult to understand? $\endgroup$ – Henry May 31 at 12:49
  • $\begingroup$ I do not understand why normal distribution has such variance and why we use exactly normal distribution as an approximation. Are there any proofs that it is ok? I also do not quite understand the second part formula. It is recursive as I understand but what is $p_i$? $\endgroup$ – Ivan Mishalkin May 31 at 13:15
  • $\begingroup$ The variance comes from the sum of independent Bernouilli random variables. The normal approximation comes from a Central Limit Theorem type argument. Using $17.5$ rather than $18$ comes from a continuity correction. $p_i$ is the $i$th term in your list of Bernouilli probabilities $\endgroup$ – Henry May 31 at 13:59

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.