Poisson-Binomial Laws for Unequal Bernoulli Trials

Why Unequal Success Probabilities Matter

A count of successes in independent trials is binomial when every trial has the same success probability. In applications, however, trials may be independent while their success probabilities differ: patients can have different response probabilities, or components can have different failure risks. The total is still a count, but it need not follow a binomial law. Its distribution is called a Poisson-binomial distribution.

The key calculation is to multiply the probability-generating functions of the individual trials. The coefficients of the resulting polynomial give the exact probabilities for every possible total. This tutorial derives that polynomial and its coefficients, develops a convenient recurrence for computing them, and establishes when the resulting law is genuinely binomial.

Definition and Probability-Generating Function

Definition: Let \(X_1,\ldots,X_n\) be independent Bernoulli random variables with \(P(X_i=1)=p_i\) and \(P(X_i=0)=1-p_i\), where each \(p_i\in[0,1]\). The sum \(S=\sum_{i=1}^n X_i\) has a Poisson-binomial distribution. Its probability-generating function is \(G_S(z)=E[z^S]\), for values of \(z\) where the expectation is defined; here it is a polynomial defined for every real or complex \(z\).

For one Bernoulli variable, the generating function is \(E[z^{X_i}]=(1-p_i)+p_i z\), since \(X_i\) takes only the values zero and one. Independence then gives the generating function for the total.

Theorem: For independent Bernoulli variables with success probabilities \(p_1,\ldots,p_n\),

G_S(z)=\prod_{i=1}^n(1-p_i+p_i z).

To justify the product, \(z^S=z^{X_1+\cdots+X_n}=\prod_{i=1}^n z^{X_i}\). Independence implies that the expectation of this product is the product of the expectations. Each factor is \((1-p_i)+p_i z\), giving the stated expression. This is the same product principle used for transforms of independent sums, here in its probability-generating-function form.

Extracting the Probability Mass Function

Expanding the product means choosing either \(1-p_i\) or \(p_i z\) from each factor. A term contributes to the coefficient of \(z^k\) exactly when the \(p_i z\) term is chosen for \(k\) indices. Therefore the mass at \(k\) is a sum over all possible sets of \(k\) successful trials.

Probability mass function: For \(k=0,1,\ldots,n\),

P(S=k)=\sum_{\substack{A\subseteq\{1,\ldots,n\}\\ |A|=k}} \left(\prod_{i\in A}p_i\right) \left(\prod_{j\notin A}(1-p_j)\right).

The empty product is defined to be 1, so the formula also covers \(k=0\) and \(k=n\). For \(k\) outside \(\{0,\ldots,n\}\), \(P(S=k)=0\). Each summand is the probability of one particular pattern: precisely the indices in \(A\) succeed and all other trials fail. The patterns are disjoint, so adding their probabilities gives the event \(S=k\).

Worked Example: Three Unequal Trials

Let \(X_1,X_2,X_3\) be independent Bernoulli variables with success probabilities \(0.1,0.4,0.7\), respectively. Find the generating function and the full probability mass function of \(S=X_1+X_2+X_3\).

The generating function is

$$ G_S(z)=(0.9+0.1z)(0.6+0.4z)(0.3+0.7z). $$

The probability of no successes is the constant coefficient, and the probability of three successes is the coefficient of \(z^3\):

P(S=0)=0.9(0.6)(0.3)=0.162,\qquad P(S=3)=0.1(0.4)(0.7)=0.028.

For exactly one success, add the three possibilities for which trial succeeds:

$$ P(S=1)=0.1(0.6)(0.3)+0.9(0.4)(0.3)+0.9(0.6)(0.7) =0.018+0.108+0.378=0.504. $$

For exactly two successes, add the possibilities for which trial fails:

$$ P(S=2)=0.1(0.4)(0.3)+0.1(0.6)(0.7)+0.9(0.4)(0.7) =0.012+0.042+0.252=0.306. $$

The probabilities sum to \(0.162+0.504+0.306+0.028=1\), as required. Thus the mass function, listed for \(k=0,1,2,3\), is \(0.162,0.504,0.306,0.028\).

A Recurrence for Computing the Coefficients

The subset formula can involve many terms: for \(k\) successes there are \(\binom{n}{k}\) possible subsets. A recurrence builds the distribution one trial at a time and avoids listing every subset separately. Let \(S_m=\sum_{i=1}^m X_i\), and define \(c_{m,k}=P(S_m=k)\). Use \(c_{0,0}=1\) and \(c_{0,k}=0\) for \(k\ne0\).

Theorem: For \(m=1,\ldots,n\),

c_{m,k}=(1-p_m)c_{m-1,k}+p_m c_{m-1,k-1}.

The convention is that \(c_{m-1,k}=0\) when \(k<0\) or \(k>m-1\). In particular, the recurrence gives \(c_{m,k}=0\) outside \(0\le k\le m\).

Proof. The event \(S_m=k\) occurs either when the \(m\)th trial fails and the first \(m-1\) trials have \(k\) successes, or when it succeeds and the first \(m-1\) trials have \(k-1\) successes. These cases are disjoint. The \(m\)th trial is independent of the earlier trials, so their probabilities are \((1-p_m)c_{m-1,k}\) and \(p_m c_{m-1,k-1}\). Adding them proves the recurrence. \(\square\)

Worked Example: Applying the Coefficient Recurrence

Take four independent Bernoulli trials with success probabilities \(0.2,0.3,0.6,0.8\). Compute the distribution by adding one trial at a time. Entries below are the probabilities of \(0,1,\ldots,m\) successes after \(m\) trials.

Initially, with no trials, the entries are \((1)\). After the first trial they are \((0.8,0.2)\). After the second trial, the recurrence gives

(c_{2,0},c_{2,1},c_{2,2}) =(0.8\cdot0.7,\ 0.2\cdot0.7+0.8\cdot0.3,\ 0.2\cdot0.3) =(0.56,0.38,0.06).

After the third trial, with \(p_3=0.6\), the entries are

(c_{3,0},c_{3,1},c_{3,2},c_{3,3}) =(0.56\cdot0.4,\ 0.38\cdot0.4+0.56\cdot0.6,\ 0.06\cdot0.4+0.38\cdot0.6,\ 0.06\cdot0.6) =(0.224,0.488,0.252,0.036).

For the fourth trial, \(p_4=0.8\), so

(c_{4,0},c_{4,1},c_{4,2},c_{4,3},c_{4,4}) =(0.224\cdot0.2,\ 0.488\cdot0.2+0.224\cdot0.8,\ 0.252\cdot0.2+0.488\cdot0.8,\ 0.036\cdot0.2+0.252\cdot0.8,\ 0.036\cdot0.8)

$$ =(0.0448,0.2768,0.4408,0.2088,0.0288). $$

These entries sum to 1. For example, the probability of exactly two successes is \(0.4408\). The recurrence also makes clear that the order in which the trial probabilities are processed does not change the final distribution: the generating function is a product whose factors can be reordered.

How the Poisson-Binomial Law Differs From the Binomial

If all the probabilities are equal to a common value \(p\), the generating function becomes \((1-p+pz)^n\), which is the generating function of a \(\operatorname{Binomial}(n,p)\) random variable. When probabilities differ, the factors generally differ, and the sum is not binomial. Its first two moments provide a quick diagnostic.

Because \(E[X_i]=p_i\), independence gives

E[S]=\sum_{i=1}^n p_i,\qquad \operatorname{Var}(S)=\sum_{i=1}^n p_i(1-p_i).

For the variance, expand \(\operatorname{Var}(\sum_i X_i)\): it is the sum of the individual variances plus twice the sum of pairwise covariances. Independence makes every such covariance zero, and a Bernoulli variable has variance \(p_i(1-p_i)\).

Worked Example: Checking Against a Binomial Model

For the three trials with probabilities \(0.1,0.4,0.7\), the mean is \(0.1+0.4+0.7=1.2\), and the variance is

$$ 0.1(0.9)+0.4(0.6)+0.7(0.3)=0.09+0.24+0.21=0.54. $$

A binomial distribution on three trials with the same mean would have success probability \(p=1.2/3=0.4\). Its variance would be \(3(0.4)(0.6)=0.72\), not \(0.54\). Thus the Poisson-binomial law calculated above is not \(\operatorname{Binomial}(3,0.4)\). The mean alone does not identify the distribution; the variance already rules out this particular binomial candidate.

In fact, for a sum of \(n\) independent Bernoulli variables, the binomial case occurs exactly when all their success probabilities are equal. To see why, suppose first that the sum has a \(\operatorname{Binomial}(n,r)\) distribution. Its generating function is then both \(\prod_i(1-p_i+p_i z)\) and \((1-r+rz)^n\). If \(0<r<1\), the latter polynomial has degree \(n\) and nonzero constant term. Equality forces every \(p_i\) to be strictly between zero and one: a zero probability would reduce the degree, and a probability of one would make the constant term zero. Each factor then has one root, \(-(1-p_i)/p_i\). Equality of the polynomials implies the same roots, counted with multiplicity, as \((1-r+rz)^n\). Hence every \(p_i\) equals \(r\). If \(r=0\), the sum is zero with probability one, which forces every \(p_i=0\); if \(r=1\), the sum is \(n\) with probability one, which forces every \(p_i=1\). Conversely, equal probabilities give the binomial generating function directly.

Common Pitfall and Why the Distinction Matters

Common mistake: “There are \(n\) independent yes-or-no trials, so their total is binomial.” Independence is necessary for the product formula, but it does not make the success probabilities equal. A binomial law requires both independence and a common success probability. With unequal probabilities, the exact subset probabilities differ, and the coefficient calculation must retain each \(p_i\).

This distinction matters when probabilities vary across individuals or items. Treating the total as binomial can give incorrect probabilities for rare or extreme counts, even if a binomial model is chosen to match the mean. The product generating function gives the appropriate law, while the recurrence provides a direct calculation method. As a final check on a calculation, its coefficients should be nonnegative and sum to \(G_S(1)=1\).

Check Your Understanding

Use the definitions and formulas above to answer the following.

Write the probability-generating function for the sum of three independent Bernoulli variables with probabilities \(0.2,0.2,0.8\).
For probabilities \(p_1,\ldots,p_n\), explain why the probability of exactly one success is a sum of \(n\) terms.
Apply the recurrence to one additional Bernoulli trial with success probability \(p\), starting from any distribution \((c_{m,0},\ldots,c_{m,m})\).
Can a sum of independent Bernoulli variables with probabilities \(0.2,0.5,0.8\) have a binomial distribution? Explain using the criterion proved above.
Why does matching the mean of a Poisson-binomial sum to a binomial mean not, by itself, establish that the distributions agree?