probability of sum of a given set of whole numbers being greater than a certain number There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a box or none. How can we find the probability that sum of balls picked from the boxes will be greater than or equal to ceil(n/2) . I want to know the general procedure for approaching such questions, answer would be nice but I want to generalize this question and find the probability of numbers being greater than some number. I think there will be some recursive relation like finding the sum of heads or tails in unfair coins but I am not able to think of such a relation. EDIT: Think of it as balls kept in n bags.We move sequentially from bag 1 to n. We pick certain number of bags from them. We have to find the probability that sum of balls obtained from the chosen bags is greater than ceil(n/2).

The most straightforward method is probably just to recursively marginalize the distribution, each time reducing the number of boxes and (in one branch) reducing the sum threshold. That is, $P(sum_{1..i}>n_{thresh}) = P(sum_{1..i}>n_{thresh} | picked_i)p_i + P(sum_{1..i}>n_{thresh}|\
eg picked_i)(1-p_i) = P(sum_{1..i-1}>(n_{thresh}-n_i))p_i + P(sum_{1..i-1}>n_{thresh})(1-p_i)$. Obviously, at a certain point you're looking at thresholds less than zero or greater than all the remaining boxes, which are your termination cases.

This takes exponential time in the general case, but the problem is NP-complete so that's not really negotiable.