Probability distribution
In probability theory and statistics, the Poisson binomial distribution is the discrete probability distribution of a sum of independent Bernoulli trials that are not necessarily identically distributed. The concept is named after Siméon Denis Poisson.
In other words, it is the probability distribution of the
number of successes in a collection of "n" independent yes/no experiments with success probabilities formula_1. The ordinary binomial distribution is a special case of the Poisson binomial distribution, when all success probabilities are the same, that is formula_2.
Definitions.
Probability Mass Function.
The probability of having "k" successful trials out of a total of "n" can be written as the sum
formula_3
where formula_4 is the set of all subsets of "k" integers that can be selected from formula_5. For example, if "n" = 3, then formula_6. formula_7 is the complement of formula_8, i.e. formula_9.
formula_4 will contain formula_11 elements, the sum over which is infeasible to compute in practice unless the number of trials "n" is small (e.g. if "n" = 30, formula_12 contains over 1020 elements). However, there are other, more efficient ways to calculate formula_13.
As long as none of the success probabilities are equal to one, one can calculate the probability of "k" successes using the recursive formula 
formula_14
where
 formula_15
The recursive formula is not numerically stable, and should be avoided if formula_16 is greater than approximately 20. 
An alternative is to use a divide-and-conquer algorithm: if we assume formula_17 is a power of two, denoting by formula_18 the Poisson binomial of formula_19 and formula_20 the convolution operator, we have formula_21. 
More generally, the probability mass function of a Poisson binomial can be expressed as the convolution of the vectors formula_22 where formula_23. This observation leads to the Direct Convolution (DC) algorithm for computing formula_24 through formula_25:
formula_26will be found in PMF[k]. DC is numerically stable, exact, and, when implemented as a software routine, exceptionally fast for formula_27. It can also be quite fast for larger formula_28, depending on the distribution of the formula_29.
Another possibility is using the discrete Fourier transform.
formula_30
where formula_31 and formula_32.
Still other methods are described in "Statistical Applications of the Poisson-Binomial and conditional Bernoulli distributions" by Chen and Liu and in "A simple and fast method for computing the Poisson binomial distribution function" by Biscarri et al.
Cumulative distribution function.
The cumulative distribution function (CDF) can be expressed as:
formula_33 ,
where formula_34 is the set of all subsets of size formula_35 that can be selected from formula_5.
It can be computed by invoking the DC function above, and then adding elements formula_37 through formula_38 of the returned PMF array. 
Properties.
Mean and Variance.
Since a Poisson binomial distributed variable is a sum of "n" independent Bernoulli distributed variables, its mean and variance will simply be sums of the mean and variance of the "n" Bernoulli distributions:
 formula_39
 formula_40
Entropy.
There is no simple formula for the entropy of a Poisson binomial distribution, but the entropy is bounded above by the entropy of a binomial distribution with the same number parameter and the same mean. Therefore, the entropy is also bounded above by the entropy of a Poisson distribution with the same mean.
The Shepp–Olkin concavity conjecture, due to Lawrence Shepp and Ingram Olkin in 1981, states that the entropy of a Poisson binomial distribution is a concave function of the success probabilities formula_1. This conjecture was proved by Erwan Hillion and Oliver Johnson in 2015. The Shepp–Olkin monotonicity conjecture, also from the same 1981 paper, is that the entropy is monotone increasing in formula_42, if all formula_43. This conjecture was also proved by Hillion and Johnson, in 2019.
Chernoff bound.
The probability that a Poisson binomial distribution gets large, can be bounded using its moment generating function as follows (valid when formula_44 and for any formula_45):
 formula_46
where we took formula_47. This is similar to the tail bounds of a binomial distribution.
Related distribution.
Approximation by Binomial Distribution.
A Poisson binomial distribution formula_48 can be approximated by a binomial distribution formula_49 where formula_50, the mean of the formula_42, is the success probability of formula_49. The variances of formula_48 and formula_49 are related by the formula
formula_55
As can be seen, the closer the formula_42 are to formula_50, that is, the more the formula_42 tend to homogeneity, the larger formula_48's variance. When all the formula_42are equal to formula_50", formula_48 becomes formula_49", formula_64, and the variance is at its maximum.
Ehm has determined bounds for the total variation distance of "formula_48" and "formula_49", in effect providing bounds on the error introduced when approximating "formula_48" with "formula_49". Let formula_69 and formula_70 be the total variation distance of "formula_48" and "formula_49". Then
formula_73
formula_74
where formula_75.
formula_70 tends to 0 if and only if formula_77 tends to 1.
Approximation by Poisson Distribution.
A Poisson binomial distribution formula_48 can also be approximated by a Poisson distribution formula_79 with mean formula_80. Barbour and Hall have shown that
formula_81
where formula_70 is the total variation distance of "formula_48" and formula_79. It can be seen that the smaller the formula_42, the better formula_79 approximates "formula_48". 
As formula_88 and formula_89, formula_90; so a Poisson binomial distribution's variance is bounded above by a Poisson distribution with formula_80, and the smaller the formula_42, the closer formula_93 will be to formula_94.
Computational methods.
The reference discusses techniques of evaluating the probability mass function of the Poisson binomial distribution. The following software implementations are based on it: