Chen–Stein Poisson近似

把很多稀有事件的总次数近似成Poisson分布，需要检查两件事：单个事件不能占据太多质量，事件之间的依赖也不能被漏掉。Chen–Stein方法为这两部分提供有限样本预算，控制的不只是均值，而是任意计数事件的概率误差。

形式陈述

目标距离与本页常数

设 $W=\sum_{i=1}^nI_i$ ，其中 $I_i\in\{0,1\}$ ， $p_i=EI_i$ ， $\lambda=\sum_i p_i>0$ ；比较目标为 $Z\sim\mathrm{Poisson}(\lambda)$ 。本页使用本库的总变差距离约定

d_{\mathrm{TV}}(W,Z)=\sup_{A\subseteq\mathbb Z_{\ge0}} |P(W\in A)-P(Z\in A)|,

它在0与1之间。若文献用不带1/2的质量绝对差总和定义TV范数，其常数需要相应换算。

对每个i，选择含i的指标集合 $B_i\subseteq\{1,\ldots,n\}$ ，要求 $I_i$ 与邻域外整个向量 $(I_j:j\notin B_i)$ 独立。定义

b_1=\sum_i\sum_{j\in B_i}p_i p_j,\qquad b_2=\sum_i\sum_{\substack{j\in B_i\\j\ne i}}E[I_iI_j].\tag{1}

则本页证明

d_{\mathrm{TV}}(W,Z)\le\min\{1,b_1+b_2\}.\tag{2}

这是使用简单差分常数1的保守版本。经典理论还能给依赖λ的更好因子；本页不会将未证明的更强常数混进算例。当λ=0时所有指标恒为0，W与退化Poisson相同，可直接处理，不进入除以λ的公式。

另一个可选择的耦合接口

更一般地，设W为任意非负整数变量、EW=λ∈(0,∞)， $(W,W^s)$ 是它的大小偏置耦合。则

d_{\mathrm{TV}}(W,Z)\le \min\{1,\lambda E|W+1-W^s|\}.\tag{3}

期望可能为无穷，此时只剩平凡上界1。式(2)用依赖邻域，式(3)用一个联合构造；它们是两种估计同一方程缺口的工具，不要求读者同时找到两份证书。

直觉

Poisson分布具有一个加一平衡：对任意有界f，

E[Zf(Z)]=\lambda E[f(Z+1)].

左边按计数大小重新加权，右边则把原计数加一。如果另一个计数W也近似满足这个恒等式，而且这种近似对足够丰富的f统一成立，就能比较完整分布。

大小偏置把左侧精确改写成 $\lambda Ef(W^s)$ ，于是只需比较 $W^s$ 和W+1。局部依赖则先拿掉一个指标的整个邻域，让剩余计数与这个指标独立；拿掉的局部部分产生b1和b2两份预算。

每个事件对应一个离散方程

固定事件A，令h(k)=1{k∈A}。求解

\lambda f(k+1)-kf(k)=h(k)-Eh(Z),\qquad k=0,1,\ldots.\tag{4}

存在有界解，使

\|f\|_\infty\le1,\qquad \sup_{k\ge0}|f(k+1)-f(k)|\le1.\tag{5}

f(0)不影响式(4)，因为它只乘以零；本页取f(0)=f(1)，使第零个差分为零。这个边界约定与取f(0)=0的常见写法不同，但对方程及Wf(W)没有影响。

一旦式(5)成立，代入W便有

P(W\in A)-P(Z\in A)=E[\lambda f(W+1)-Wf(W)].\tag{6}

下面先用这条接口证明误差界，再完整构造具有式(5)的解。

例子与边界

四种独立稀有事件

若各指标相互独立，可取 $B_i=\{i\}$ ，所以b2=0，b1=Σp_i²。也可直接使用大小偏置构造：按 $p_i/\lambda$ 选I，将 $I_I$ 改为1，则 $W^s=W-I_I+1$ ，式(3)同样给出

d_{\mathrm{TV}}(W,Z)\le\sum_i p_i^2.\tag{7}

例如成功率为 $(.02,.05,.08,.15)$ ，λ=.30，右端为.0318。Poisson–二项递推算得精确零次概率 $364021/500000=.728042$ ；同均值Poisson给 $e^{-.3}\approx.74081822$ 。两者的这一个事件差约.01277622，没有超过.0318；完整TV约.02271653，也受同一个预算控制。

单凭λ=.3并不能说明任意模型都同样接近。例如将全部均值集中成一个Bernoulli(.3)，式(7)变成.09；分散到更多小概率独立事件，平方和才会缩小。

20个位中出现多少次相邻11

这里m始终表示原始位数。设 $Y_1,\ldots,Y_m$ 独立、均为Bernoulli(p)，m≥3，令

I_i=Y_iY_{i+1},\quad i=1,\ldots,m-1,\qquad W=\sum_{i=1}^{m-1}I_i.

因此共有m−1个计数指标，λ=(m−1)p²。指标 $I_i$ 只使用两个相邻位，可以取 $B_i=\{i-1,i,i+1\}\cap\{1,\ldots,m-1\}$ 。邻域外所有指标只使用其余位，故整个外部向量与 $I_i$ 独立。

两个端点邻域各有2个指标，其余m−3个邻域各有3个，所以

b_1=(3m-5)p^4.

相邻指标的共同成功要求三个连续位全为1，概率为p³；有m−2个相邻无序对，而式(1)按两个方向计数，故

b_2=2(m-2)p^3.

取m=20、p=.1，得到

\lambda=.19,\qquad b_1=.0055,\qquad b_2=.036,\qquad b_1+b_2=.0415.

若误把19个指标当独立Bernoulli(.01)，只会留下.0019，遗漏了重叠造成的预算。

精确分布也能计算，但状态必须记住末位。令 $a_j(k,b)$ 为处理j个位后已出现k次11、末位为b的概率；从空前缀取 $a_0(0,0)=1$ ，附加下一位z时做

a_{j+1}(k+bz,z)\mathrel{+}=a_j(k,b)p^z(1-p)^{1-z}.

最终对末位求和。对本例，精确 $P(W=0)=.83882575688449447359$ ，而 $e^{-.19}\approx.8269591339433623$ ，完整TV约.02085346。状态数量为O(m²)、每个状态只作两次转移，滚动空间O(m)。这里新增的末位记忆正是依赖模型与独立计数DP的区别。

异质独立计数与重叠11计数分别和同均值Poisson比较，图下保留真实概率差和合法TV预算 — 独立与重叠计数的近似预算

两两独立不够，小界失败也不等于近似失败

取两个独立公平位B、C，令 $I_1=B,I_2=C,I_3=B\mathbin{\mathrm{xor}}C$ 。三个指标两两独立，但 $I_1$ 由 $(I_2,I_3)$ 完全确定。若V=I2+I3，则 $I_1=1$ 恰好对应V=1，所以

E[I_1\mathbf1\{V=1\}]=1/2 \ne (EI_1)P(V=1)=1/4.

因此不能取 $B_1=\{1\}$ 来使用邻域证明。要求“与邻域外每一个指标分别独立”比本页条件弱。

邻域选得过大仍可能合法，却给出很差的b1、b2。式(2)大于或接近1，只说明这份充分证书没能提供有用精度；不证明W必然远离Poisson。若依赖不满足严格局部独立性，可研究带额外依赖项的版本，但不能删掉该项后沿用本页公式。

推论与应用

两种误差界的证明

先用大小偏置定义，将式(6)改写为

\lambda E[f(W+1)-f(W^s)].

整数位置间逐项相减，式(5)给 $|f(a)-f(b)|\le|a-b|$ ，即得式(3)。对A取上确界不会改变常数。

对邻域证明，记 $V_i=\sum_{j\notin B_i}I_j$ ，它与 $I_i$ 独立。在式(6)中逐项加减 $p_iEf(V_i+1)$ ，得到

\begin{aligned} E[\lambda f(W+1)-Wf(W)] ={}&\sum_i p_i E[f(W+1)-f(V_i+1)]\\ &-\sum_iE[I_i\{f(W)-f(V_i+1)\}]. \end{aligned}

第一行的绝对值由差分界控制为 $\sum_i p_iE(W-V_i)=b_1$ 。第二行只在 $I_i=1$ 时有贡献，此时 $W-V_i-1=\sum_{j\in B_i,j\ne i}I_j$ ，所以其绝对值至多为b2。这就证明式(2)，包括邻域内任意强度的依赖。

解的构造：保留旧点，再补入新点

为证明式(5)，对t≥0令q=e^−t，并定义

P_t h(k)=E[h(Y_{k,t})],\qquad Y_{k,t}\stackrel d=\mathrm{Binomial}(k,q)+\mathrm{Poisson}(\lambda(1-q)),

右边两项独立。它表示原来的k个点各自以概率q保留，再独立补入Poisson新点。若原点数本来服从Poisson(λ)，其保留数为Poisson(λq)，相加后仍为Poisson(λ)。该稀疏化结论可直接在概率生成函数 $E[z^Z]=e^{\lambda(z-1)}$ 中代入 $1-q+qz$ 验证。

用共享的新点，并分别保留k个或Poisson(λ)个旧点，得到一份实际耦合：只要两侧没有旧点幸存，两个结果就相等。因此

|P_t h(k)-Eh(Z)|\le(k+\lambda)e^{-t}.

积分

g(k)=-\int_0^\infty[P_t h(k)-Eh(Z)]dt

绝对收敛。连续做两次“保留并补入”与一次总时长相同，因两次保留率相乘、Poisson均值相加，故 $P_sP_t=P_{s+t}$ 。对很小s，原k个点少一个的概率为ks+o(s)，多一个新点的概率为λs+o(s)，同时发生两次及以上改变的概率为o(s)。由此直接得到

\partial_tP_t h(k)=\lambda[P_t h(k+1)-P_t h(k)] +k[P_t h(k-1)-P_t h(k)].

k=0时省去第二项。把这个等式从0积分到无穷，便有

\lambda[g(k+1)-g(k)]+k[g(k-1)-g(k)]=h(k)-Eh(Z).

因此取 $f(k)=g(k)-g(k-1)$ 、k≥1，并令f(0)=f(1)，就解出了式(4)。整个构造只使用显式二项/Poisson变量，不需要先假设一个未定义的随机过程。

一阶差分常数为什么是1

多放一个原点，只会以概率q多保留一个。因此若 $\Delta h(j)=h(j+1)-h(j)$ ，

f(k+1)=-\int_0^\infty e^{-t}E[\Delta h(Y_{k,t})]dt,\qquad k\ge0.

指示函数满足 $|\Delta h|\le1$ ，所以 $|f(k+1)|\le\int_0^\infty e^{-t}dt=1$ 。再多比较一个原点，同理

f(k+2)-f(k+1)=-\int_0^\infty e^{-2t}E[\Delta^2h(Y_{k,t})]dt.

因 $|\Delta^2h|\le2$ ，其绝对值至多为 $2\int_0^\infty e^{-2t}dt=1$ 。第零个差分由边界约定为零，式(5)全部成立。没有在这一简单证明中得到更小的λ相关常数，故前面的预算也只使用1。

证书成本与概率量的范围

给定依赖邻域、边缘概率和相邻联合概率，形成b1、b2需O(Σ|B_i|)次算术；计算这些概率本身的成本需另计。邻域全部取全体指标时，操作数可到O(n²)，界也可能很松。一个成功的证书控制所有 $A\subseteq\mathbb Z_{\ge0}$ ，包括零次、超过阈值以及若干离散值的并，不只控制一个事先选择的尾部。

对一般无界损失，仅有TV界不够；若损失取值于[0,M]，期望差至多为M乘TV。标准化连续负载及Lipschitz但无界的损失，则可转向正态Stein与W1接口，不能直接把本页的全事件界当作所有无界函数的期望界。

参考资料

Richard Arratia, Larry Goldstein and Louis Gordon，Two Moments Suffice for Poisson Approximations: The Chen–Stein Method，Annals of Probability17(1),1989,pp.9–25；§2、Theorem1，§§4–5离散方程与邻域展开。原文更一般依赖项与TV范数不在本页无声省略。
Louis H. Y. Chen and Aihua Xia，Poisson Process Approximation: From Palm Theory to Stein’s Method，IMS Lecture Notes–Monograph Series52,2006,pp.236–244；§§1–2式(1)–(3)，保留/补入过程的方程积分表示。本页直接证明足够使用的差分常数1。
Nathan Ross，Fundamentals of Stein’s Method，§4、Theorem4.7与§4.3，独立稀有事件、局部依赖及大小偏置的比较。

形式陈述 ​

目标距离与本页常数 ​

另一个可选择的耦合接口 ​

每个事件对应一个离散方程 ​

四种独立稀有事件 ​

20个位中出现多少次相邻11 ​

两两独立不够，小界失败也不等于近似失败 ​

两种误差界的证明 ​

解的构造：保留旧点，再补入新点 ​

一阶差分常数为什么是1 ​

证书成本与概率量的范围 ​

反向链接