# “At least” approximation calculation

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$$
• 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$? – Ivan Mishalkin May 31 at 13:15
• 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 – Henry May 31 at 13:59