22  Meeting 16: Stein’s Method and Poisson Approximation

Th Oct 22

Review

Meeting 14 started from an equation that characterizes the standard normal distribution, then used a coupling—the replace-one exchangeable pair—to measure how far a standardized sum is from satisfying that equation.

Meeting 15 showed why we need another target. The number of bad bottles in a small quality control sample is discrete, nonnegative, and skewed. A Poisson distribution respects that shape and closely matched the exact count probabilities.

Today we connect the two meetings. The Poisson distribution has its own characterizing equation. Once again, a coupling turns the difference between the two sides of that equation into an approximation bound.

Stein’s Characterization of the Poisson

Let \(Z\) have a Poisson distribution with mean \(\lambda\). For every bounded function \(f\) on the nonnegative integers, \[ \E[\lambda f(Z+1)-Zf(Z)]=0. \]

We can see why directly from the Poisson probabilities. Since \(k\Pr(Z=k)=\lambda\Pr(Z=k-1)\), \[ \begin{aligned} \E[Zf(Z)] &=\sum_{k=1}^\infty kf(k)\Pr(Z=k)\\ &=\lambda\sum_{k=1}^\infty f(k)\Pr(Z=k-1)\\ &=\lambda\E[f(Z+1)]. \end{aligned} \]

The converse is also true: a nonnegative integer-valued random variable that satisfies this identity for every bounded \(f\) is Poisson with mean \(\lambda\).

The parallel with the normal case is exact in purpose: \[ \begin{array}{rcl} \text{standard normal} &:& \E[f'(Z)-Zf(Z)]=0,\\ \text{Poisson}(\lambda) &:& \E[\lambda f(Z+1)-Zf(Z)]=0. \end{array} \] The derivative becomes a one-step difference because the Poisson distribution lives on integers.

The Poisson Approximation Theorem

First consider independent indicators \(X_1 \ldots X_n\), with \(\Pr(X_i=1)=p_i\). Let \[ W=\sum_{i=1}^n X_i \qquad\text{and}\qquad \lambda=\E[W]=\sum_{i=1}^n p_i. \]

If \(Z\) is Poisson with mean \(\lambda\), Stein’s method implies \[ d_{TV}(W,Z) \leq \min(1,\lambda^{-1})\sum_{i=1}^n p_i^2. \]

Total variation distance \(d_{TV}\) is the largest difference between the probabilities the two distributions assign to the same event. Thus the bound controls every count question at once, including a rejection event such as \(W\geq 3\).

For independent copies with the same probability \(p\), the bound becomes \[ d_{TV}(W,Z)\leq \min(1,(np)^{-1})np^2. \] When \(np\) stays fixed while \(n\) grows, this error goes to zero because \(p\) goes to zero. That is the law of small numbers.

ExerciseWhich Ingredient Makes the Error Small?

Suppose \(np=1\). Rewrite the bound in terms of \(n\) alone. What happens as \(n\) grows?

Applying to the Brewery Problem

The brewery sample is drawn without replacement, so its bottle indicators are not independent. We cannot apply the independent-indicator theorem and quietly ignore that hypothesis.

There is, however, a version built for this dependence. Suppose \(W=\sum_{i=1}^m X_i\) is a sum of indicators, \(p_i=\Pr(X_i=1)\), and \(\lambda=\sum_i p_i\). Select an index \(I\) independently with \(\Pr(I=i)=p_i/\lambda\). Conditional on \(I=i\), construct \((X_1^i \ldots X_m^i)\) with the conditional law of \((X_1 \ldots X_m)\) given \(X_i=1\), and write \(W^s=\sum_j X_j^I\). If this coupling satisfies \(W^s\leq W+1\)—forcing the selected success can only remove, never add, other successes—then Ross’s decreasing size-bias bound says \[ d_{TV}(W,Z) \leq \min(1,\lambda)\left(1-\frac{\Var(W)}{\lambda}\right), \] where \(Z\) is Poisson with mean \(\lambda\).

That coupling is concrete for sampling without replacement. Because every bad-bottle indicator has the same success probability, choose the forced bad bottle uniformly from all bad bottles. If it is already in the quality-control sample, do nothing. Otherwise add it and return one uniformly selected sampled bottle to the batch. The resulting sample has the conditional law of the original sample given that the selected bad bottle is included. No other bad bottle can be added by this operation, so \(W^s\leq W+1\).

For a population of size \(N\), a sample of size \(n\), and a bad-bottle proportion \(\theta\), the count \(W\) has \[ \lambda=n\theta, \qquad \Var(W)=n\theta(1-\theta)\frac{N-n}{N-1}. \]

At \(N=1{,}000{,}000\), \(n=100\), and \(\theta=.01\), we have \(\lambda=1\). The bound is \[ \begin{aligned} d_{TV}(W,Z) &\leq 1-(1-.01)\frac{1{,}000{,}000-100}{1{,}000{,}000-1}\\ &\approx .0101. \end{aligned} \]

Therefore the Poisson approximation can miss the probability of any event by at most about 1.01 percentage points. For the particular rejection event \(W\geq3\), the exact Hypergeometric probability is about 7.94% and the Poisson probability is about 8.03%, an error below one tenth of a percentage point.

When Poisson Beats Normal (and Vice Versa)

The two approximations answer different shape questions.

  • Poisson: useful when each success probability is small and the expected count \(\lambda\) is not too large. It preserves nonnegative integer support and skewness.
  • Normal: useful when the count is many standard deviations away from both zero and its upper boundary. For a Binomial count, that usually means both \(np\) and \(n(1-p)\) are large.
  • Both: when \(p\) is small but \(np\) is large, the Poisson distribution itself becomes approximately normal. The two routes can then agree.

There is no universal cutoff. The Stein bounds show what the slogans conceal: accuracy depends on the individual probabilities, the expected count, and the dependence structure.

ExerciseChoose the Shape

Which approximation would you try first for each count?

  1. bad bottles when \(n=100\) and \(p=.01\);
  2. heads when \(n=1{,}000\) and \(p=.5\);
  3. bad bottles when \(n=100{,}000\) and \(p=.01\).

Beyond Independent Summands

The brewery sample already showed why dependence matters: without-replacement indicators are negatively dependent, yet a coupling still produced a bound.

Stein’s method also handles local positive dependence. Counts of birthday collisions, runs of heads, and small patterns in networks are sums of indicators that overlap. The indicators are not independent, but each one interacts with only a structured neighborhood. A coupling can expose that neighborhood and charge the approximation error to those interactions.

This is where the method is more than a new proof of an old limit theorem. It gives a common language for deciding which parts of a dependent system prevent a Poisson approximation.

Takeaways

Stein’s method has the same architecture for two different target distributions.

  1. Write an equation that characterizes the target.
  2. Build a coupling that rewrites the corresponding expression for the random variable of interest.
  3. Bound the discrepancy.

For a normal target, the equation uses a derivative. For a Poisson target, it uses a one-step difference. In both cases the error depends on the structure of the problem, not merely on the raw sample size.

The brewery count is the full story in miniature. Normal approximation was geometrically awkward, Poisson matched the rare-event shape, and the decreasing coupling justified the approximation without pretending that without-replacement draws were independent.

Reference