Normal Limits for Poisson-Binomial Sums

Why Unequal Bernoulli Probabilities Matter

A count need not come from identical trials to have a useful normal approximation. In a clinical study, for example, independent patients may have different probabilities of experiencing an event because their risk profiles differ. The resulting count is a sum of Bernoulli variables with unequal success probabilities. Its mean and variance are straightforward to calculate, but a normal limit requires checking that the total variability grows and is not concentrated in one summand.

The central object is the Poisson-binomial sum. The name distinguishes a sum of independent Bernoulli variables with potentially different success probabilities from the special case with a common probability. This tutorial focuses on its centered and standardized limit; it does not require the summands to be identically distributed.

Definition: For each $n$, let $B_{n1},\ldots,B_{nk_n}$ be independent Bernoulli random variables, with $P(B_{ni}=1)=p_{ni}$ and $P(B_{ni}=0)=1-p_{ni}$, where $0\le p_{ni}\le1$. Their sum $S_n=\sum_{i=1}^{k_n}B_{ni}$ is a Poisson-binomial sum. Its mean and variance are denoted by $\mu_n=E[S_n]$ and $s_n^2=\operatorname{Var}(S_n)$.

Independence gives the formulas

\mu_n=\sum_{i=1}^{k_n}p_{ni}, \qquad s_n^2=\sum_{i=1}^{k_n}p_{ni}(1-p_{ni}).

Each summand has variance $p_{ni}(1-p_{ni})$, since $B_{ni}^2=B_{ni}$. The variances add because the summands are independent. The probabilities need not be equal, and in general the variance is not determined by the mean alone.

A Normal-Limit Theorem for Bernoulli Sums

The useful feature specific to Bernoulli variables is that their centered values are uniformly bounded: $|B_{ni}-p_{ni}|\le1$. As the total standard deviation grows, no individual bounded summand can remain large on the standardized scale. The following theorem makes this argument precise.

Theorem: Suppose that, for every $n$, $B_{n1},\ldots,B_{nk_n}$ are independent Bernoulli random variables with success probabilities $p_{ni}$. If $s_n^2=\sum_{i=1}^{k_n}p_{ni}(1-p_{ni})\to\infty$, then $$ \frac{S_n-\mu_n}{s_n}\xrightarrow{d}N(0,1). $$

Proof. Write $Y_{ni}=B_{ni}-p_{ni}$. A centered Bernoulli variable takes the values $1-p_{ni}$ and $-p_{ni}$, so

E[|Y_{ni}|^3] =p_{ni}(1-p_{ni})^3+(1-p_{ni})p_{ni}^3 =p_{ni}(1-p_{ni})\bigl((1-p_{ni})^2+p_{ni}^2\bigr) \le p_{ni}(1-p_{ni}).

The last inequality follows from $p^2+(1-p)^2=1-2p(1-p)\le1$. Summing over a row and dividing by $s_n^3$ therefore gives

\frac{\sum_{i=1}^{k_n}E[|Y_{ni}|^3]}{s_n^3} \le \frac{\sum_{i=1}^{k_n}p_{ni}(1-p_{ni})}{s_n^3} =\frac{1}{s_n}\longrightarrow0.

Thus the Lyapunov condition with exponent $3$ holds for this independent triangular array. The Lyapunov central limit theorem yields $\sum_iY_{ni}/s_n\xrightarrow{d}N(0,1)$. Since $\sum_iY_{ni}=S_n-\mu_n$, this is the asserted limit. $\square$

The theorem needs no separate restriction that the number of summands grow: $s_n^2\to\infty$ itself forces enough total variability. Nor must every success probability stay away from zero and one. Probabilities may approach either endpoint, provided their combined variance diverges.

Why a Dominant Summand Is Ruled Out

For general triangular arrays, a normal-limit argument must guard against one term accounting for a substantial share of the total variance. In the Bernoulli setting, growing total variance automatically prevents that.

Proposition: Under the assumptions of the theorem, if $v_{ni}=p_{ni}(1-p_{ni})$, then $$ \frac{\max_{1\le i\le k_n}v_{ni}}{s_n^2}\longrightarrow0 \quad\text{and}\quad \frac{\max_{1\le i\le k_n}|B_{ni}-p_{ni}|}{s_n}\le\frac{1}{s_n}\longrightarrow0. $$

Proof. For every $p\in[0,1]$, $p(1-p)\le1/4$, because $(p-\tfrac12)^2\ge0$. Hence

0\le \frac{\max_i v_{ni}}{s_n^2}\le\frac{1}{4s_n^2}\longrightarrow0.

Also, $|B_{ni}-p_{ni}|\le1$ for every possible value of $B_{ni}$. Dividing by $s_n\to\infty$ proves the second assertion. Thus neither a single variance contribution nor a single centered increment can dominate after standardization. $\square$

The variance-ratio statement is often called Feller’s condition for this array. It is a useful diagnostic, but here it is automatic once $s_n^2\to\infty$. For Bernoulli sums, the moment bound in the theorem gives the stronger and direct Lyapunov verification.

Worked Example: Alternating Success Probabilities

For each $n$, suppose there are $n$ independent Bernoulli variables, with probabilities alternating between $0.2$ and $0.7$. Take $n=100$, with 50 variables of each type. Find the mean and variance, and identify the corresponding standardized normal approximation.

A Bernoulli variable with probability $0.2$ has mean $0.2$ and variance $0.2(0.8)=0.16$. One with probability $0.7$ has mean $0.7$ and variance $0.7(0.3)=0.21$. Therefore

\mu_{100}=50(0.2)+50(0.7)=10+35=45, \qquad s_{100}^2=50(0.16)+50(0.21)=8+10.5=18.5.

The standard deviation is $s_{100}=\sqrt{18.5}\approx4.301$. In a sequence formed by extending this alternating pattern, each pair contributes $0.9$ to the mean and $0.37$ to the variance. The variance therefore grows without bound, so the theorem applies. For $n=100$, the standardized sum is approximated by $N(0,1)$; equivalently, the sum is described by the normal approximation with mean $45$ and variance $18.5$. The theorem gives an asymptotic approximation, not an exact distribution at this finite sample size.

Worked Example: Probabilities Spread Across the Unit Interval

For row $n$, let $B_{ni}$ be independent with $p_{ni}=i/(n+1)$, for $i=1,\ldots,n$. Calculate the mean and variance and verify the condition for a normal limit.

For the mean,

\mu_n=\sum_{i=1}^n\frac{i}{n+1} =\frac{1}{n+1}\frac{n(n+1)}{2} =\frac n2.

For the variance, use $\sum_{i=1}^n i=n(n+1)/2$ and $\sum_{i=1}^n i^2=n(n+1)(2n+1)/6$:

\begin{aligned} s_n^2 &=\sum_{i=1}^n\frac{i}{n+1}\left(1-\frac{i}{n+1}\right)\\ &=\frac{(n+1)\sum_i i-\sum_i i^2}{(n+1)^2}\\ &=\frac{n(n+1)(n+2)}{6(n+1)^2} =\frac{n(n+2)}{6(n+1)}. \end{aligned}

Since $s_n^2/n\to1/6$, the variance diverges. Consequently,

\frac{S_n-n/2}{\sqrt{n(n+2)/(6(n+1))}}\xrightarrow{d}N(0,1).

The probabilities range from values near zero to values near one, yet no probability needs to be bounded away from either endpoint. What matters for this theorem is the growing sum of the individual variances.

Worked Example: A Normal Limit with Slowly Growing Variance

Let $B_i$, $i=2,\ldots,n$, be independent, with $P(B_i=1)=1-1/i$. Find the mean and variance of their sum $S_n$, and explain why the normal limit holds even though many probabilities are close to one.

Define $H_n=\sum_{i=1}^n1/i$ and $H_n^{(2)}=\sum_{i=1}^n1/i^2$. Then

\mu_n=\sum_{i=2}^n\left(1-\frac1i\right) =(n-1)-(H_n-1)=n-H_n.

The variance contribution for $B_i$ is $(1-1/i)(1/i)=1/i-1/i^2$, so

s_n^2=\sum_{i=2}^n\left(\frac1i-\frac1{i^2}\right) =H_n-H_n^{(2)}.

The harmonic sums satisfy $H_n\to\infty$, while $H_n^{(2)}$ converges to a finite limit. Thus $s_n^2\to\infty$, and $(S_n-\mu_n)/s_n\xrightarrow{d}N(0,1)$. The variance grows only on the order of $\log n$, so convergence can be slow. But the theorem requires divergence, not growth at a particular rate.

When the Condition Fails

A growing number of summands by itself does not guarantee a normal limit. If one summand retains a fixed share of total variance and the remaining terms contribute negligibly, the standardized sum can preserve the shape of that single summand instead of becoming normal.

For example, in row $n$, take one Bernoulli variable with success probability $1/2$ and $n$ independent Bernoulli variables with success probability $1/n^2$, all mutually independent. The total variance tends to $1/4$, not infinity. The probability that any of the $n$ rare-event variables equals one is at most $n(1/n^2)=1/n$, by the union bound. Their sum therefore tends to zero in probability. After centering and standardizing, the first Bernoulli variable remains the dominant contribution, so the limit is a two-point distribution, not $N(0,1)$.

Common pitfall: “There are many independent Bernoulli variables, so their sum must be approximately normal.” Independence and a large number of terms are not enough. Check the total variance and whether an individual summand can dominate. For Bernoulli arrays, $s_n^2\to\infty$ both establishes the theorem’s condition and ensures that no single summand dominates on the standardized scale.

In applications, the practical sequence is to calculate $\mu_n$ and $s_n^2$ from the individual probabilities, check whether $s_n^2$ diverges, and then standardize by the actual $s_n$. Replacing the unequal probabilities by a common probability, or using the mean as though it alone determined the variance, can give an incorrect scale. When the variance does diverge, the Bernoulli-specific Lyapunov bound provides a concise justification for the normal limit.

Check Your Understanding

Use the definitions and theorem to answer the following questions.

For independent Bernoulli variables with probabilities $0.1$, $0.4$, and $0.8$, calculate the sum’s mean and variance.
Why does $s_n^2\to\infty$ imply that the largest individual variance divided by the total variance tends to zero?
In the Lyapunov proof, which inequality bounds the sum of third absolute centered moments?
Can a sequence of probabilities approach zero or one and still satisfy the normal-limit theorem? Explain what condition must hold.
Why does a growing number of summands alone fail to guarantee a normal limit?

Normal Limits for Poisson-Binomial Sums

What You'll Learn