计数

(nk)=nk(n−1k−1)\tbinom{n}{k}=\frac{n}{k}\tbinom{n-1}{k-1}

∑k=0nk(nk)=n2n−1\sum\limits_{k=0}^n k\tbinom{n}{k}=n2^{n-1}

∑k=0m(n+kn)=(n+m+1n+1)\sum\limits_{k=0}^m \tbinom{n+k}{n}=\tbinom{n+m+1}{n+1}

卡特兰数 Cn=(2nn)−(2nn−1)C_n=\tbinom{2n}{n}-\tbinom{2n}{n-1} 若干实际意义，不必多说

容斥原理：不必多说

若序列长度 >st>st ，则要么存在长为 s+1s+1 的上升子序列，要么存在长为 t+1t+1 的下降子序列

生成函数

对于数列 {an}\{a_n\} 可以定义其生成函数为 A(x)=∑n=0∞anxnA(x)=\sum\limits_{n=0}^{\infty}a_nx^n 。

性质：任意 P(x)Q(x)\frac{P(x)}{Q(x)} 都能写成 ∑ci(1−αix)ki+R(x)\sum \frac{c_i}{(1-\alpha_ix)^{k_i}}+R(x) ，其中 P(x),Q(x),R(x)P(x),Q(x),R(x) 都是项数有限的多项式。

我们考察斐波那契数列的生成函数。因为 F(x)=1+xF(x)+x2F(x)F(x)=1+xF(x)+x^2F(x) ，所以可以解出 F(x)=11−x−x2F(x)=\frac{1}{1-x-x^2} 。

令 1−x−x2=(1−α)(1−β)1-x-x^2=(1-\alpha)(1-\beta) ，其中 α,β=(1±5)/2\alpha,\beta=(1\pm\sqrt{5})/2 ，我们可以解出 F(x)=15(α1−αx−β1−βx)F(x)=\frac{1}{\sqrt{5}}(\frac{\alpha}{1-\alpha x}-\frac{\beta}{1-\beta x}) ，于是 fn=15(αn+1−βn+1)f_n=\frac{1}{\sqrt{5}}(\alpha^{n+1}-\beta^{n+1}) 。

我们考察划分数的生成函数。发现 A(x)=∏k=1∞11−xkA(x)=\prod\limits_{k=1}^{\infty}\frac{1}{1-x^k} 。（OIer：我记得有个东西叫五边形数）

两个重要的生成函数：exe^x 是数列 10!,11!,12!…\frac{1}{0!},\frac{1}{1!},\frac{1}{2!}\dots 的生成函数。ln⁡(11−x)\ln (\frac{1}{1-x}) 是 0,1,12,13,…0,1,\frac{1}{2},\frac{1}{3},\dots 的生成函数。

指数生成函数

A~(x)=∑n=0∞1n!anxn\tilde{A}(x)=\sum\limits_{n=0}^{\infty}\frac{1}{n!}a_nx^n 。

例：考察长度为 nn 的排列的 EGF，有 S(x)=11−xS(x)=\frac{1}{1-x} 。考察长度为 nn 的轮换的 EGF，有 C(x)=ln⁡(11−x)C(x)=\ln (\frac{1}{1-x}) 。

发现 S(x)=eC(x)S(x)=e^{C(x)} ，它的组合意义是枚举排列的轮换个数。（OIer：求 nn 个点的无向连通图个数）

一些例子

考察卡特兰数的生成函数。有 C(x)=xC2(x)+1C(x)=xC^2(x)+1 。

可以解出 C(x)=1−1−4x2xC(x)=\frac{1-\sqrt{1-4x}}{2x} 。

广义的二项式定理：(1+x)α=∑n=0∞αn‾n!xn(1+x)^{\alpha}=\sum\limits_{n=0}^{\infty}\frac{\alpha^{\underline{n}}}{n!}x^n 。

我们可以计算 (1−4x)1/2=∑n=0∞(1/2)n‾n!(−4x)n=−∑n=0∞1∗3∗⋯∗(2n−3)n!(2x)n=−2∑n=0∞(2n−2)!(n−1)!n!xn(1-4x)^{1/2}=\sum\limits_{n=0}^{\infty}\frac{(1/2)^{\underline{n}}}{n!}(-4x)^n=-\sum\limits_{n=0}^{\infty}\frac{1* 3*\dots*(2n-3) }{n!}(2x)^n=-2\sum\limits_{n=0}^{\infty}\frac{(2n-2)!}{(n-1)!n!}x^n 。所以进一步能算出 [xn]C(x)=(2n)!(n+1)!n!=1n+1(2nn)[x^n]C(x)=\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}\tbinom{2n}{n} 。

考察 nn 个点的有标号有根树个数。考虑其 EGF,有 T~(x)=xeT~(x)\tilde{T}(x)=xe^{\tilde{T}(x)} 。

Burnside & Polya

我们先回顾一下群作用 G×X→XG×X\to X 的一些记号：

orbit(x)=Gx={g∘x∣g∈G}orbit(x)=Gx=\{g\circ x|g\in G\} 。

StabG(x)={g∣g∘x=x}Stab_G(x)=\{g|g\circ x=x\}

xg={x∣g∘x=x}x^{g}=\{x|g\circ x=x\}

X/G={Gx∣x∈X}X/G=\{Gx|x\in X\} （也就是轨道个数）

burnside 引理：∣X/G∣=1∣G∣∑g∈G∣xg∣|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|x^g| 。

怎么证明呢？有 ∣X/G∣=∑x∈X1∣Gx∣=∑x∈XStab(x)∣G∣=1∣G∣∑x,g[g∘x=x]=1∣G∣∑g∈G∣xg∣|X/G|=\sum\limits_{x\in X}\frac{1}{|Gx|}=\sum\limits_{x\in X}\frac{Stab(x)}{|G|}=\frac{1}{|G|}\sum\limits_{x,g}[g\circ x=x]=\frac{1}{|G|}\sum\limits_{g\in G}|x^g| 。

polya 计数：在 burnside 的基础上做进一步拓展。设 F={f:X→C}F=\{f:X\to C\} ，如果已经有群作用 G×X→XG×X\to X ，然后定义 G×F→FG×F\to F 满足 g×f=f∘gg×f=f\circ g ，其中我们把 gg 看做 X→XX\to X 的置换。那么 ∣F/G∣=1∣G∣∑g∣Fg∣=1∣G∣∑g∣C∣c(g)|F/G|=\frac{1}{|G|}\sum\limits_{g}|F^g|=\frac{1}{|G|}\sum\limits_{g}|C|^{c(g)} ，其中 c(g)c(g) 表示 gg 的轮换个数。

例：考虑 nn 个点的项链，每个点能染成 CC 种颜色之一，求染色方案数，其中认为旋转后相同的方案是相同的。

不难算出就是 1n∑g∈ZnCgcd⁡(g,n)\frac{1}{n}\sum\limits_{g\in Z_n}C^{\gcd(g,n)} 。可以进一步化成 1n∑d∣nφ(nd)Cd\frac{1}{n}\sum\limits_{d|n}\varphi(\frac{n}{d})C^d 。

进一步的我们可以做以下拓展：我们之前用 ∣C∣|C| 个颜色对小球染色。现在比方说我们用了 33 种颜色，假设我想对所有 i+j+k=ni+j+k=n 算出第一种颜色用 ii 次，第二种用 jj 次，第三种用 kk 次的方案数，怎么求？

我们设 ci(g)c_i(g) 是 gg 长度为 ii 的轮换个数。

那么只需提取 1∣G∣∑gZ1c1(g)Z2c2(g)…\frac{1}{|G|}\sum\limits_{g}Z_1^{c_1(g)}Z_2^{c_2(g)}\dots 的相应系数即可，其中 Zi=xi+yi+ziZ_i=x^i+y^i+z^i 。

然后我们再看一些例子。求 GG 的共轭类个数？考虑群作用 G×G→GG×G\to G 满足 g∘x=gxg−1g\circ x=gxg^{-1} ，那么共轭类个数就是这个作用的轨道个数，由 burnside，有 1∣G∣∑gCG(g)\frac{1}{|G|}\sum\limits_{g}C_G(g) 。

概率

我们研究概率空间 (Ω,P)(\Omega,P) 。其中 Ω\Omega 是样本空间，PP 是 Ω→R\Omega\to \R 的函数满足：

∀w∈Ω,P(w)≥0\forall w\in \Omega,P(w)\geq 0 以及 ∑w∈ΩP(w)=1\sum\limits_{w\in \Omega}P(w)=1 。

我们称一个 事件 是 Ω\Omega 的子集，即 A⊆ΩA\subseteq \Omega 。令 P(A)=∑w∈AP(w)P(A)=\sum\limits_{w\in A}P(w) 。也记作 Pr[A]Pr[A] 。

令 Pr[B∣A]=Pr[A∩B]Pr[A]Pr[B|A]=\frac{Pr[A\cap B]}{Pr[A]} 表示条件概率。

有贝叶斯定理：Pr[B∣A]=Pr[B]Pr[A]Pr[A∣B]Pr[B|A]=\frac{Pr[B]}{Pr[A]}Pr[A|B] 。

定义 事件 A,BA,B 独立：Pr[A∩B]=Pr[A]Pr[B]Pr[A\cap B]=Pr[A]Pr[B] 。

定义随机变量：X:Ω→SX:\Omega\to S ，设 P(x)=Pr[X=x]=∑X(w)=xP(w)P(x)=Pr[X=x]=\sum\limits_{X(w)=x}P(w) ，这被称为概率函数。

一些常见分布

定义 分布：对随机变量 XX ，设 PX(x)=Pr[X=x]P_X(x)=Pr[X=x] 。

联合分布：对随机变量 X,YX,Y ，设 PXY(x,y)=Pr[X=x∧Y=y]P_{XY}(x,y)=Pr[X=x\land Y=y] 。

条件分布 ：PY∣X(y∣x)=Pr[Y=y∣X=x]P_{Y|X}(y|x)=Pr[Y=y|X=x] 。

显然 PY∣X(y∣x)=PXY(x,y)PX(x)P_{Y|X}(y|x)=\frac{P_{XY}(x,y)}{P_X(x)} 。

现在我们定义一些常见的分布。

伯努利分布 Bern(p)Bern(p) 形如 {1−px=0px=1\begin{cases}1-p&x=0\\p&x=1\end{cases}

二项式分布 Binom(n,p)Binom(n,p) 形如 (nx)px(1−p)n−x\tbinom{n}{x}p^x(1-p)^{n-x}

几何分布 Geom(p)Geom(p) 形如 p(1−p)x−1p(1-p)^{x-1}

负二项分布 NB(r,p)NB(r,p) 形如 (x+r−1x)pr(1−p)x\tbinom{x+r-1}{x}p^r(1-p)^x

（组合意义是以 pp 概率抽 11 ，若干次后抽出 rr 个 11）

泊松分布 Poisson(λ)Poisson(\lambda) 形如 e−λλxx!\frac{e^{-\lambda}\lambda^x}{x!} 。

（可以看做 n→∞n\to\infty 时的 Binom(n,λn)Binom(n,\frac{\lambda}{n})）

期望，方差

我们定义 E[X]=∑xPX(x)x=∑wP(w)X(w)E[X]=\sum\limits_{x}P_X(x)x=\sum\limits_{w}P(w)X(w)

例题：设 X∼Geom(p)X\sim Geom(p) ，求 E[X]E[X] 。根据实际意义，我们有 E[X]=E[X−1∣X>1]E[X]=E[X-1|X>1] 。而 E[X−1∣X>1]=∑x=2∞(x−1)Pr[X=x∣X>1]=∑x=2∞(x−1)Pr[X=x]1−p=∑x=0∞(x−1)Px(x)1−p=E[X]−11−pE[X-1|X>1]=\sum\limits_{x=2}^{\infty}(x-1)Pr[X=x|X>1]=\sum\limits_{x=2}^{\infty}(x-1)\frac{Pr[X=x]}{1-p}=\sum\limits_{x=0}^{\infty}\frac{(x-1)P_x(x)}{1-p}=\frac{E[X]-1}{1-p} ，于是 E[X]=1pE[X]=\frac{1}{p} 。

定义 Var[X]=E[X2]−E[X]2=E[(X−E[X])2]Var[X]=E[X^2]-E[X]^2=E[(X-E[X])^2] 。定义 Cov[X,Y]=E[XY]−E[X]E[Y]=E[(X−E[X])(Y−E[Y])]Cov[X,Y]=E[XY]-E[X]E[Y]=E[(X-E[X])(Y-E[Y])] 。

对于两个独立随机变量 X,YX,Y ，我们有 E[XY]=E[X]E[Y]E[XY]=E[X]E[Y] 。

有 Var[X+Y]=E[(X−E[X]+Y−E[Y])2]=Var[X]+Var[Y]+2Cov[X,Y]=Var[x]+Var[y]Var[X+Y]=E[(X-E[X]+Y-E[Y])^2]=Var[X]+Var[Y]+2Cov[X,Y]=Var[x]+Var[y] 。

概率生成函数(PGF)

GX(z)=∑xPX(x)zx=E[zX]G_X(z)=\sum\limits_{x}P_X(x)z^x=E[z^X] 。

若 X,YX,Y 是独立分布，那么 GX+Y(z)=GX(z)GY(z)G_{X+Y}(z)=G_X(z)G_Y(z)

你发现 GXG_X 有一些良好性质，比如 G′X(1)=E[x],G′′X(1)+GX′(1)=E[X2]G'X(1)=E[x],G''X(1)+G'_X(1)=E[X^2] 。

例：考察掷硬币，第一次连续两次正面朝上的概率。考虑其 PGF，有 G(z)=p2z2+(1−p)zG(z)+(1−p)pz2G(z)G(z)=p^2z^2+(1-p)zG(z)+(1-p)pz^2G(z) 。

我们考察 GX(ez)=E[ezX]G_X(e^z)=E[e^{zX}] 。其 nn 阶导代入 z=0z=0 可得 E[Xn]E[X^n] 。

熵

考虑随机变量 XX 遵从概率分布 PxP_x ，我们设 H[X]=∑xPX(x)log⁡1Px(x)H[X]=\sum\limits_{x}P_X(x)\log \frac{1}{P_x(x)} 。也可以看做是 E[log⁡1PX(X)]E[\log \frac{1}{P_X(X)}]

比如说设 X∼Bern(12)X\sim Bern(\frac{1}{2}) ，我们有 H(X)=1log⁡2H(X)=1\log 2 。

令 ∣X∣={x∣PX(x)>0}|X|=\{x|P_X(x)>0\} ，不难证明 0≤H(X)≤log⁡∣X∣0\le H(X)\le \log |X|

联合熵 对随机变量 X,YX,Y ，设 H[X,Y]=∑x,yPXY(x,y)log⁡1PXY(x,y)H[X,Y]=\sum\limits_{x,y}P_{XY}(x,y)\log \frac{1}{P_{XY}(x,y)}

条件熵 对随机变量 X,YX,Y ，H[Y∣X]=∑xH[Y∣X=x]⋅Pr[X=x]H[Y|X]=\sum\limits_{x}H[Y|X=x]\cdot Pr[X=x] 。

我们推一下式子：H[Y∣X]=∑x∑yPY∣X(y∣x)log⁡1PY∣X(y∣x)Px(X)=∑x,yPxy(x,y)log⁡1PY∣X(y,x)=E[log⁡1PY∣X(Y∣X)]H[Y|X]=\sum\limits_{x}\sum\limits_{y}P_{Y|X}(y|x)\log \frac{1}{P_{Y|X}(y|x)}P_x(X)=\sum\limits_{x,y}P_{xy}(x,y)\log\frac{1}{P_{Y|X}(y,x)}=E[\log\frac{1}{P_{Y|X}(Y|X)}]

我们有 H[X,Y]=H[X]+H[Y∣X]H[X,Y]=H[X]+H[Y|X] ，因为 E[log⁡1PXY(X,Y)]=E[log⁡1PX(X)]+E[log⁡1PY∣X(Y∣X)]E[\log\frac{1}{P_{XY}(X,Y)}]=E[\log\frac{1}{P_X(X)}]+E[\log\frac{1}{P_{Y|X}(Y|X)}]

互信息

我们有 H[X∣Y]≤H[X]H[X|Y]\le H[X] 。

证明：

因为 H[X]−H[X∣Y]=∑xPx(x)log⁡1Px(x)−∑x,yPX∣Y(x∣y)log⁡1PX∣Y(x∣y)=∑x,yPXY(x,y)log⁡PXY(x∣y)PX(x)=∑x,yPXY(x,y)log⁡PXY(x,y)PX(x)PY(y)H[X]-H[X|Y]=\sum\limits_{x}P_x(x)\log\frac{1}{P_x(x)}-\sum\limits_{x,y}P_{X|Y}(x|y)\log\frac{1}{P_{X|Y}(x|y)}=\sum\limits_{x,y}P_{XY}(x,y)\log \frac{P_{XY}(x|y)}{P_X(x)}=\sum\limits_{x,y}P_{XY}(x,y)\log\frac{P_{XY}(x,y)}{P_X(x)P_Y(y)}

到这里，可以看成有两个长为 ∣X∣⋅∣Y∣|X|\cdot |Y| 的序列 a,ba,b ，上述和式为 ∑iailog⁡aibi\sum\limits_{i}a_i\log\frac{a_i}{b_i} ，∑a\sum a 和 ∑b\sum b 都是固定的，求这个式子下界。经过系列数学推导，可以得到它大于等于 (∑a)log⁡∑a∑b(\sum a)\log\frac{\sum a}{\sum b} ，回到之前问题，即有 H[X]≥H[X∣Y]H[X]\geq H[X|Y] 了。

定义互信息为 I(X;Y)=H[X]−H[X∣Y]=H[Y]−H[Y∣X]I(X;Y)=H[X]-H[X|Y]=H[Y]-H[Y|X] 。

data-processing 不等式 ：I(X;Y)≥I(X;Z)I(X;Y)\geq I(X;Z) ，其中 PY=PXPY∣X,PZ=PYPZ∣YP_Y=P_XP_{Y|X},P_Z=P_YP_{Z|Y}

KL散度

D(P∣∣Q)=∑xP(x)log⁡P(x)Q(x)D(P||Q)=\sum\limits_{x}P(x)\log \frac{P(x)}{Q(x)} 可以看做 PP 偏离 QQ 的程度

(注意 P,QP,Q 是两个概率分布)

我们有 D(P∣∣Q)≥0D(P||Q)\geq 0 ，因为设 D(P∣∣Q)=Ex∼Q[P(x)Q(x)log⁡P(x)Q(x)]=Ex∼Q[f(P(x)Q(x))]≥f(Ex∼Q[P(x)Q(x)])=f(1)=0D(P||Q)=E_{x\sim Q}[\frac{P(x)}{Q(x)}\log \frac{P(x)}{Q(x)}]=E_{x\sim Q}[f(\frac{P(x)}{Q(x)})]\geq f(E_{x\sim Q}[\frac{P(x)}{Q(x)}])=f(1)=0 ，其中 f(x)=xlog⁡xf(x)=x\log x

我们有 D(P∣∣Unif(Ω))=log⁡∣Ω∣−H(P)D(P||Unif(\Omega))=\log |\Omega|-H(P) 这很好证明

现在考虑 PXY,QXYP_{XY},Q_{XY} 。

我们证明 D(PXY∣∣QXY)=D(PX∣∣QX)+D(PY∣X∣∣QY∣X∣PX)D(P_{XY}||Q_{XY})=D(P_X||Q_X)+D(P_{Y|X}||Q_{Y|X}|P_X)

因为 EX,Y∼PXY[log⁡PXY(X,Y)QXY(X,Y)]=EX,Y∼PXY[log⁡PX(X)QX(X)+log⁡PY∣X(Y∣X)QY∣X(Y∣X)]E_{X,Y\sim P_{XY}}[\log \frac{P_{XY}(X,Y)}{Q_{XY}(X,Y)}]=E_{X,Y\sim P_{XY}}[\log \frac{P_X(X)}{Q_X(X)}+\log \frac{P_{Y|X}(Y|X)}{Q_{Y|X}(Y|X)}]

同理我们有 D(PX1X2…Xn∣∣QX1X2…Xn)=∑i=1nD(PXi∣X1…Xi−1∣∣QXi∣X1…Xi−1∣PX1X2…Xi−1)D(P_{X_1X_2\dots X_n}||Q_{X_1X_2\dots X_n})=\sum\limits_{i=1}^n D(P_{X_i|X_1\dots X_{i-1}}||Q_{X_i|X_1\dots X_{i-1}}|P_{X_1X_2\dots X_{i-1}})

集中不等式

马尔科夫不等式 (Markov Bound)

对于在 [0,+∞)[0,+\infty) 上的随机变量 XX

P[X≥αE[X]]≤1αP[X\geq \alpha E[X]]\le \frac{1}{\alpha}

证明：首先有 ∫0∞P1[X≥x] dx=E[X]\int_0^{\infty}P_1[X\geq x]\,dx=E[X] 。

这是因为 ∫0∞P1[X≥x] dx=∫0∞∑wP(w)[X(w)≥x] dx=∑wP(w)∫0∞[X(w)≥x] dx=∑wP(w)X(w)=E[X]\int_0^{\infty}P_1[X\geq x]\,dx=\int_0^{\infty}\sum\limits_{w}P(w)[X(w)\geq x]\,dx=\sum\limits_{w}P(w)\int_0^{\infty}[X(w)\geq x]\,dx=\sum\limits_{w}P(w)X(w)=E[X] 。

切比雪夫不等式 (Chebyshev’s Bound/Inequality)

对随机变量 XX ，设 Var(X)=Δ2Var(X)=\Delta^2 。

Pr[∣X−E[X]∣≥αΔ]≤1α2Pr[|X-E[X]|\geq \alpha\Delta]\le \frac{1}{\alpha^2} 。

我们可以由马尔科夫不等式推出来：Pr[∣X−E[X]∣≥αΔ]=Pr[(X−E[X])2≥α2Δ2]Pr[|X-E[X]|\geq \alpha\Delta]=Pr[(X-E[X])^2\geq \alpha^2\Delta^2] 。而 Δ2=E[(X−E[X])2]\Delta^2=E[(X-E[X])^2] ，那就有 Pr[(X−E[X])2≥α2Δ2]≤1α2Pr[(X-E[X])^2\geq \alpha^2\Delta^2]\le \frac{1}{\alpha^2}

切尔诺夫不等式 (Chernoff Bound)

对随机变量 XX ，Pr(X≥a)=Pr(etX≥eta)≤E[etX]etαPr(X\geq a)=Pr(e^{tX}\geq e^{ta})\le \frac{E[e^{tX}]}{e^{t\alpha}} ，其中 tt 是任意一个 >0>0 的实数。

例子：设 X1,…,Xn∼Bern(p)X_1,\dots,X_n\sim Bern(p) 且互相独立，估计 Pr[∑iXi≥qn]Pr[\sum\limits_{i}X_i\geq qn] ，其中 q>pq>p 。

利用 chernoff bound ，它小于等于 E[et∑Xi]etqn=(pet+(1−p)etq)n\frac{E[e^{t\sum X_i}]}{e^{tqn}}=(\frac{pe^t+(1-p)}{e^{tq}})^n

现在我们希望寻找 pet+(1−p)etq\frac{pe^t+(1-p)}{e^{tq}} 的最小值，把它对 tt 求导并找零点，发现零点满足 et=q(1−p)p(1−q)e^t=\frac{q(1-p)}{p(1-q)} ，代入上面式子即可得到一个很好的界：(1−p1−q)1−q(pq)q(\frac{1-p}{1-q})^{1-q}(\frac{p}{q})^q 的 nn 次方。

但同时我们发现 (1−p1−q)1−q(pq)q(\frac{1-p}{1-q})^{1-q}(\frac{p}{q})^q 有些眼熟，它等于 exp⁡(qlog⁡pq+(1−q)log⁡1−p1−q)=exp(−d(q∣∣p))\exp(q\log \frac{p}{q}+(1-q)\log \frac{1-p}{1-q})=exp(-d(q||p)) 。于是最后的结果是 exp(−d(q∣∣p)n)exp(-d(q||p)n) 。

更进一步，之前的作业我们证明过 d(q∣∣p)≤2(p−q)2d(q||p)\le 2(p-q)^2 ，于是它小于等于 exp(−2(p−q)2n)exp(-2(p-q)^2n) 。

斯特林公式

对 n!n! 的估计。我们有 n!n! 约为 2πn(ne)n\sqrt{2\pi n}(\frac{n}{e})^n 。还有另一个更严谨的式子：ln⁡n!=nln⁡n−n+ln⁡n2+112n+O(1n3)\ln n!=n\ln n-n+\frac{\ln n}{2}+\frac{1}{12n}+O(\frac{1}{n^3})

Sanov Bound

对于 X1,X2,…,Xn∼Bern(p)X_1,X_2,\dots,X_n\sim Bern(p) ，有 Pr[∑Xi=qn]∈[1n+1exp(−nd(q∣∣p)),exp(−nd(q∣∣p))]Pr[\sum\limits X_i=qn]\in [\frac{1}{n+1}exp(-nd(q||p)),exp(-nd(q||p))] 。

1(n+1)L+1exp(nH(Q))≤(ns1,s2,…sL)≤exp(nH(Q))\frac{1}{(n+1)^{L+1}}exp(nH(Q))\le \binom{n}{s_1,s_2,\dots s_L}\le exp(nH(Q)) ，其中 QQ 满足 Pr[Q=i]=sinPr[Q=i]=\frac{s_i}{n} 。