Chapter 1

Introduction to distributional approximation

Distributional approximation replaces a complicated probability law by a simpler one. Sums of Bernoulli variables provide examples in which binomial, Poisson and normal approximations can be compared directly.

Sums of Bernoulli variablesContents

Let X1,…,XnX_1,\ldots,X_n be independent Bernoulli variables with success probabilities p1,…,pnp_1,\ldots,p_n. Their sum has the Poisson–binomial distribution:

S=∑i=1nXi,λ=E[S]=∑ipi,σ2=Var⁡(S)=∑ipi(1−pi).S=\sum_{i=1}^n X_i,\qquad \lambda=\mathbb E[S]=\sum_i p_i,\qquad \sigma^2=\operatorname{Var}(S)=\sum_i p_i(1-p_i).

When all pip_i equal pp, S∼Bin⁡(n,p)S\sim\operatorname{Bin}(n,p). Two further extensions are a random number of trials, S=∑i=1NXiS=\sum_{i=1}^N X_i, and dependent indicators, such as overlapping runs of consecutive successes.

Comparing approximationsContents

The three approximations below match the theoretical conditional mean: Poi⁡(λ)\operatorname{Poi}(\lambda), Bin⁡(n,λ/n)\operatorname{Bin}(n,\lambda/n), and a normal law with variance σ2\sigma^2. For the normal approximation, mass at each integer is defined by a continuity correction:

qk=Φ ⁣(k+12−λσ)−Φ ⁣(k−12−λσ).q_k=\Phi\!\left(\frac{k+\tfrac12-\lambda}{\sigma}\right)-\Phi\!\left(\frac{k-\tfrac12-\lambda}{\sigma}\right).

The probabilities pip_i are drawn once using a fixed seed. The exact distribution is computed by repeated convolution.

ExactPoissonBinomialDiscrete normal
ApproximationTotal variationKolmogorov distance

Distances include mass outside {0,…,n}\{0,\ldots,n\}; the plot shows the central range. These curves use theoretical moments, whereas the simulations below fit parameters from the observations.

npˉ(1−pˉ)−Var⁡(S)=∑i(pi−pˉ)2,pˉ=λn.n\bar p(1-\bar p)-\operatorname{Var}(S)=\sum_i(p_i-\bar p)^2,\qquad \bar p=\frac\lambda n.

The binomial variance excess is exactly the heterogeneity of the success probabilities.

Refinements

A skewness correction uses κ3=∑ipi(1−pi)(1−2pi)\kappa_3=\sum_i p_i(1-p_i)(1-2p_i), γ1=κ3/σ3\gamma_1=\kappa_3/\sigma^3, and G(x)=Φ(x)+(γ1/6)(1−x2)φ(x)G(x)=\Phi(x)+(\gamma_1/6)(1-x^2)\varphi(x) in place of Φ\Phi. A saddlepoint approximation uses the cumulant generating function K(t)=∑ilog⁡(1−pi+piet)K(t)=\sum_i\log(1-p_i+p_ie^t):

P(S=k)≈exp⁡ ⁣(K(tk)−ktk)2πK′′(tk),K′(tk)=k.\mathbb P(S=k)\approx\frac{\exp\!\bigl(K(t_k)-kt_k\bigr)}{\sqrt{2\pi K''(t_k)}},\qquad K'(t_k)=k.

For Bin⁡(20,0.2)\operatorname{Bin}(20,0.2) at k=8k=8, the exact mass is 0.02216; the discrete normal gives 0.01926, the skewness correction 0.02354, and the saddlepoint approximation 0.02246. The two refinements approximate individual masses and need not form normalised probability distributions.

Monte Carlo goodness of fitContents

The original simulations use 100 observations per repetition, 100 repetitions at each nn, and 9,999 parametric bootstrap samples per test, with parameter re-estimation. A fresh probability vector is drawn for each repetition and held fixed across its observations. Shaded bands are approximate pointwise 95% confidence intervals for the mean pp-values.

Mean bootstrap p-values versus n for Rare events: pᵢ = (3 + δᵢ)/n. δᵢ ∼ U[−0.5, 0.5]. As n grows, the Poisson and binomial mean p-values become nearly identical and lie around 0.5; the discrete normal remains systematically lower.
Rare events. Poisson and binomial mean pp-values become nearly identical as nn increases; the discrete normal remains lower.
Mean bootstrap p-values versus n for Near one half: pᵢ = 0.5 + δᵢ. δᵢ ∼ U[−0.1, 0.1]. Binomial and discrete normal mean p-values fluctuate around 0.5. The Poisson mean p-values remain approximately 0.009–0.028.
Probabilities near one half. Binomial and normal mean pp-values are near 0.5. Poisson remains approximately 0.009–0.028.
Mean bootstrap p-values versus n for Strong heterogeneity: pᵢ ∼ U(0,1). The discrete normal gives mean p-values around 0.441–0.558, compared with 0.123–0.210 for binomial and 0.00014–0.00138 for Poisson.
Uniformly heterogeneous probabilities. The normal approximation gives the highest mean pp-values; the binomial and Poisson models are too dispersed.

These averages summarise repeated tests. They are not pp-values for a combined test, and changing the controls above does not change these saved figures.

Quantitative guaranteesContents

For independent Bernoulli sums, Le Cam’s inequality gives

dTV ⁣(L(S),Poi⁡(λ))≤∑ipi2.d_{\mathrm{TV}}\!\left(\mathcal L(S),\operatorname{Poi}(\lambda)\right)\leq\sum_i p_i^2.

For pi=λ/np_i=\lambda/n with fixed λ\lambda, the right-hand side is λ2/n\lambda^2/n. The Chen–Stein bound improves this by the factor (1−e−λ)/λ(1-e^{-\lambda})/\lambda.

The Berry–Esseen inequality gives, when σ>0\sigma>0,

sup⁡x∣P ⁣(S−λσ≤x)−Φ(x)∣≤1σ.\sup_x\left|\mathbb P\!\left(\frac{S-\lambda}{\sigma}\leq x\right)-\Phi(x)\right|\leq\frac1\sigma.

This compares SS with a continuous normal in Kolmogorov distance. Total variation between a discrete law and a continuous law is 1.

Random sums and dependence

For an independent random number NN of ii.ii.d. Bernoulli⁡(p)\operatorname{Bernoulli}(p) trials,

Var⁡(S)=p(1−p)E[N]+p2Var⁡(N).\operatorname{Var}(S)=p(1-p)\mathbb E[N]+p^2\operatorname{Var}(N).

Replacing nn by E[N]\mathbb E[N] misses the second term. If N∼Poi⁡(a)N\sim\operatorname{Poi}(a), then S∼Poi⁡(ap)S\sim\operatorname{Poi}(ap); if N∼Bin⁡(M,q)N\sim\operatorname{Bin}(M,q), then S∼Bin⁡(M,pq)S\sim\operatorname{Bin}(M,pq).

For nn overlapping blocks of rr consecutive successes in ii.ii.d. Bernoulli⁡(p)\operatorname{Bernoulli}(p) trials, the mean is nprnp^r and

Var⁡(S)=npr(1−pr)+2∑h=1min⁡(r−1,n−1)(n−h)(pr+h−p2r).\operatorname{Var}(S)=np^r(1-p^r)+2\sum_{h=1}^{\min(r-1,n-1)}(n-h)(p^{r+h}-p^{2r}).

The additional covariance terms require approximation methods that account for dependence.

Probability metricsContents

An integral probability metric compares expectations over a class H\mathcal H of integrable test functions:

dH(μ,ν)=sup⁡h∈H∣∫h dμ−∫h dν∣.d_{\mathcal H}(\mu,\nu)=\sup_{h\in\mathcal H}\left|\int h\,d\mu-\int h\,d\nu\right|.
DistanceTest functionsProperty
Total variationIndicators of measurable setsLargest difference in event probabilities
KolmogorovIndicators of half-linesLargest CDF gap; dK≤dTVd_{\mathrm K}\leq d_{\mathrm{TV}}
Wasserstein–11-Lipschitz functionsTransport cost; finite first moments
Bounded–Lipschitz∣h∣≤1,  Lip⁡(h)≤1\lvert h\rvert\leq1,\;\operatorname{Lip}(h)\leq1Metrizes weak convergence on Rd\mathbb R^d
Zolotarev ζs\zeta_smm derivatives, with α\alpha-Hölder mth derivative; s=m+αs=m+\alphaUnder finite absolute sth moments, finiteness requires matching moments through order mm

For integer-valued laws, dTV=12∑k∣pk−qk∣d_{\mathrm{TV}}=\tfrac12\sum_k|p_k-q_k|. On R\mathbb R, W1=∫∣F−G∣W_1=\int|F-G|. A general test class gives an extended pseudo-metric and may fail to distinguish different laws.

Weak convergence and counterexamples

Weak convergence means convergence of expectations for every bounded continuous function. It does not imply convergence in every metric.

If one law has a density bounded by CC and both have finite first moments, a useful comparison is dK≤2CW1d_{\mathrm K}\leq\sqrt{2CW_1}.

Back to contents