aiwiki.page
中文
数学 / 概率与统计 / probability-generating-function

概率生成函数

概率生成函数以幂级数编码非负整数值随机变量的分布,可用于计算概率、矩及随机变量之和的分布。

25 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
生成函数随机变量概率分布概率质量函数期望值复数幂级数解析函数概率生成函…

概率生成函数(PGF)是一种生成函数,其系数为非负整数值随机变量取各个值的概率。它用一个函数表示整个概率分布。其代数性质和解析性质使其特别适合研究计数、独立随机变量之和、随机项数的和以及种群模型。

定义与定义域

设 XX 的取值范围为 {0,1,2,…}\{0,1,2,\ldots\},其概率质量函数为

pn=Pr⁡(X=n).p_n=\Pr(X=n).

XX 的概率生成函数定义为

GX(s)=E[sX]=∑n=0∞pnsn,G_X(s)=\mathbb E[s^X] =\sum_{n=0}^{\infty}p_n s^n,

其中,E\mathbb E 表示期望值。当 s=0s=0 时,规定 X=0X=0 对应的项为 11,因此 GX(0)=p0G_X(0)=p_0。

尽管在许多概率论应用中,只需考虑实数自变量 0≤s≤10\le s\le1,但也可以将概率生成函数视为以复数为自变量的函数。定义它的幂级数对所有 ∣s∣≤1|s|\le1 都绝对收敛,因为

∑n=0∞∣pnsn∣≤∑n=0∞pn=1.\sum_{n=0}^{\infty}|p_ns^n| \le \sum_{n=0}^{\infty}p_n=1.

因此,它的收敛半径至少为 11。它在开单位圆盘内是解析函数,并且在闭单位圆盘上连续。

收敛半径可能大于 11,但并不一定如此。有限支撑分布的概率生成函数是多项式,而尾部足够重的分布,其概率生成函数的收敛半径可能恰好为 11。

幂级数

G(s)=∑n=0∞ansnG(s)=\sum_{n=0}^{\infty}a_ns^n

是概率生成函数,当且仅当其各项系数非负且总和为 11。

还原概率

概率生成函数的系数恰好就是它所编码的概率。具体而言,

Pr⁡(X=n)=GX(n)(0)n!,n=0,1,2,…,\Pr(X=n)=\frac{G_X^{(n)}(0)}{n!}, \qquad n=0,1,2,\ldots,

其中 GX(0)=GXG_X^{(0)}=G_X。因此,概率生成函数唯一确定其对应的分布。

采用系数提取记号,可写为

[sn]GX(s)=Pr⁡(X=n).[s^n]G_X(s)=\Pr(X=n).

例如,若

GX(s)=14+12s+14s2,G_X(s)=\frac14+\frac12s+\frac14s^2,

则 XX 分别以概率 1/4,1/2,1/41/4,1/2,1/4 取值 0,1,20,1,2。

累积概率也可以从生成函数中提取。对于 ∣s∣<1|s|<1,有

GX(s)1−s=∑n=0∞Pr⁡(X≤n)sn.\frac{G_X(s)}{1-s} = \sum_{n=0}^{\infty}\Pr(X\le n)s^n.

类似地,

1−GX(s)1−s=∑n=0∞Pr⁡(X>n)sn.\frac{1-G_X(s)}{1-s} = \sum_{n=0}^{\infty}\Pr(X>n)s^n.

第二个恒等式给出尾和公式

E[X]=∑n=0∞Pr⁡(X>n),\mathbb E[X]=\sum_{n=0}^{\infty}\Pr(X>n),

其中两边都允许为无穷大。

基本性质

每个概率生成函数都满足

GX(0)=Pr⁡(X=0),GX(1)=1.G_X(0)=\Pr(X=0), \qquad G_X(1)=1.

在区间 [0,1][0,1] 上,概率生成函数单调不减且为凸函数。在 0<s<10<s<1 内,其各阶导数均非负,因为逐项求导可得

GX(k)(s)=∑n=k∞n(n−1)⋯(n−k+1)pnsn−k.G_X^{(k)}(s) = \sum_{n=k}^{\infty} n(n-1)\cdots(n-k+1)p_ns^{n-k}.

概率生成函数在某些特定复数处的取值可以揭示分布的算术特征。例如,

GX(−1)=Pr⁡(X is even)−Pr⁡(X is odd),G_X(-1) = \Pr(X\text{ is even})-\Pr(X\text{ is odd}),

因此

Pr⁡(X is even)=1+GX(−1)2.\Pr(X\text{ is even})=\frac{1+G_X(-1)}2.

更一般地,概率生成函数在单位根处的取值可以确定各剩余类的概率。若 ω=e2πi/m\omega=e^{2\pi i/m},则

Pr⁡(X≡r(modm))=1m∑j=0m−1ω−jrGX(ωj).\Pr(X\equiv r\pmod m) = \frac1m\sum_{j=0}^{m-1} \omega^{-jr}G_X(\omega^j).

这是一个有限的离散傅里叶变换反演恒等式。

阶乘矩、均值与方差

在 s=1s=1 处求导可得到阶乘矩。将下降阶乘定义为

(X)k=X(X−1)⋯(X−k+1).(X)_k=X(X-1)\cdots(X-k+1).

则

GX(k)(1−)=E[(X)k].G_X^{(k)}(1-)=\mathbb E[(X)_k].

记号 1−1- 表示 ss 从下方递增趋于 11 时的极限。即使相关的矩不有限,这些恒等式仍然成立,此时取值为 +∞+\infty。

特别地,

E[X]=GX′(1−)\mathbb E[X]=G_X'(1-)

且

E[X(X−1)]=GX′′(1−).\mathbb E[X(X-1)]=G_X''(1-).

当二阶矩有限时,方差为

Var⁡(X)=GX′′(1−)+GX′(1−)−(GX′(1−))2.\operatorname{Var}(X) = G_X''(1-)+G_X'(1-) -\bigl(G_X'(1-)\bigr)^2.

这可由 X2=X(X−1)+XX^2=X(X-1)+X 得出。

普通矩也可以通过微分算子

D=sddsD=s\frac{d}{ds}

求得。由于 D(sn)=nsnD(s^n)=ns^n,有

E[Xk]=lim⁡s↑1DkGX(s).\mathbb E[X^k] = \lim_{s\uparrow1}D^kG_X(s).

因此,即使随机变量的均值或更高阶矩为无穷大,其概率生成函数也总是在 [0,1][0,1] 上存在。

典型示例

伯努利分布

对于成功概率为 pp 的伯努利分布随机变量,

Pr⁡(X=0)=1−p,Pr⁡(X=1)=p,\Pr(X=0)=1-p,\qquad \Pr(X=1)=p,

且

GX(s)=1−p+ps.G_X(s)=1-p+ps.

二项分布

若 XX 服从参数为 nn 和 pp 的二项分布,则

GX(s)=(1−p+ps)n.G_X(s)=(1-p+ps)^n.

各项系数可由二项式定理求出。求导可得

E[X]=np,Var⁡(X)=np(1−p).\mathbb E[X]=np, \qquad \operatorname{Var}(X)=np(1-p).

泊松分布

对于参数为 λ≥0\lambda\ge0 的泊松分布,

GX(s)=∑n=0∞e−λλnn!sn=eλ(s−1).G_X(s) = \sum_{n=0}^{\infty} e^{-\lambda}\frac{\lambda^n}{n!}s^n = e^{\lambda(s-1)}.

因此,

E[X]=Var⁡(X)=λ.\mathbb E[X]=\operatorname{Var}(X)=\lambda.

几何分布

假设每次独立试验的成功概率为 pp,其中 0<p≤10<p\le1,而 XX 表示首次成功之前的失败次数。则

Pr⁡(X=n)=p(1−p)n,n≥0,\Pr(X=n)=p(1-p)^n,\qquad n\ge0,

利用等比级数可得

GX(s)=p1−(1−p)s.G_X(s)=\frac{p}{1-(1-p)s}.

如果随机变量表示直到首次成功为止的试验次数,且包括首次成功的那次试验,那么其概率生成函数为

ps1−(1−p)s.\frac{ps}{1-(1-p)s}.

这一区别对应于几何分布的两种常见约定。

独立随机变量之和与卷积

若 XX 与 YY 满足统计独立性,则

GX+Y(s)=E[sX+Y]=E[sX]E[sY]=GX(s)GY(s).G_{X+Y}(s) = \mathbb E[s^{X+Y}] = \mathbb E[s^X]\mathbb E[s^Y] = G_X(s)G_Y(s).

概率生成函数的乘法对应于概率质量函数的卷积:

Pr⁡(X+Y=n)=∑k=0nPr⁡(X=k)Pr⁡(Y=n−k).\Pr(X+Y=n) = \sum_{k=0}^{n}\Pr(X=k)\Pr(Y=n-k).

对于相互独立的 X1,…,XmX_1,\ldots,X_m,有

GX1+⋯+Xm(s)=∏j=1mGXj(s).G_{X_1+\cdots+X_m}(s) = \prod_{j=1}^{m}G_{X_j}(s).

如果它们同分布,且概率生成函数均为 GG,则上式变为 G(s)mG(s)^m。

例如,参数分别为 λ1,…,λm\lambda_1,\ldots,\lambda_m 的独立泊松随机变量,其和的概率生成函数为

∏j=1meλj(s−1)=e(λ1+⋯+λm)(s−1),\prod_{j=1}^{m}e^{\lambda_j(s-1)} = e^{(\lambda_1+\cdots+\lambda_m)(s-1)},

由此可知,该和服从参数为 λ1+⋯+λm\lambda_1+\cdots+\lambda_m 的泊松分布。

若不具备独立性,上述乘法法则一般不成立。

随机和与稀疏化

随机和

设 NN 为非负整数值随机变量,X1,X2,…X_1,X_2,\ldots 为独立同分布的非负整数值随机变量,且整个序列与 NN 独立。定义

S=∑j=1NXj,S=\sum_{j=1}^{N}X_j,

并约定当 N=0N=0 时,S=0S=0。

以 NN 为条件计算可得

GS(s)=E[GX(s)N]=GN(GX(s)).G_S(s) = \mathbb E[G_X(s)^N] = G_N(G_X(s)).

因此,随机和对应于概率生成函数的函数复合。

当相关的矩有限时,

E[S]=E[N]E[X1]\mathbb E[S]=\mathbb E[N]\mathbb E[X_1]

且

Var⁡(S)=E[N]Var⁡(X1)+Var⁡(N)(E[X1])2.\operatorname{Var}(S) = \mathbb E[N]\operatorname{Var}(X_1) + \operatorname{Var}(N)\bigl(\mathbb E[X_1]\bigr)^2.

若 NN 服从参数为 λ\lambda 的泊松分布,则所得的复合泊松分布具有概率生成函数

GS(s)=exp⁡ ⁣(λ(GX(s)−1)).G_S(s)=\exp\!\left(\lambda(G_X(s)-1)\right).

独立稀疏化

假设有 XX 个对象,每个对象都以概率 pp 独立地被保留。若 YY 为保留下来的对象数,则给定 X=nX=n 时,YY 的条件分布为二项分布:

Y∣X=n∼Binomial⁡(n,p).Y\mid X=n\sim\operatorname{Binomial}(n,p).

因此,

GY(s)=GX(1−p+ps).G_Y(s)=G_X(1-p+ps).

特别地,对均值为 λ\lambda 的泊松计数进行稀疏化,所得计数仍服从泊松分布,均值为 pλp\lambda。

分枝过程

概率生成函数在分枝过程中起着核心作用。在 Galton–Watson 过程中,每个个体独立地产生随机数量的子代,且子代数量具有相同的概率生成函数 ff。设 ZnZ_n 为第 nn 代的种群数量,初始数量为 Z0=1Z_0=1。

给定 ZnZ_n 后,下一代的种群数量是 ZnZ_n 个独立子代数量之和。因此,

GZn+1(s)=GZn(f(s)),G_{Z_{n+1}}(s)=G_{Z_n}(f(s)),

且

GZn(s)=f∘n(s),G_{Z_n}(s)=f^{\circ n}(s),

其中,f∘nf^{\circ n} 表示 nn 次复合,而非普通乘方。

截至第 nn 代已经灭绝的概率为

Pr⁡(Zn=0)=f∘n(0).\Pr(Z_n=0)=f^{\circ n}(0).

最终灭绝概率 qq 是不动点方程

q=f(q).q=f(q).

在 [0,1][0,1] 内的最小解。

记平均子代数为 m=f′(1−)m=f'(1-),则:

  • 若 m<1m<1,灭绝概率为 11。
  • 若 m=1m=1,灭绝概率为 11,但每个个体都恰好产生一个子代的情形除外。
  • 若 m>1m>1,灭绝概率小于 11。

多元概率生成函数

对于非负整数值随机变量 X1,…,XdX_1,\ldots,X_d,联合概率生成函数为

G(s1,…,sd)=E ⁣[∏j=1dsjXj].G(s_1,\ldots,s_d) = \mathbb E\!\left[\prod_{j=1}^{d}s_j^{X_j}\right].

其系数编码了这些变量的联合概率分布。

将除 sis_i 之外的所有自变量设为 11,即可得到 XiX_i 的边缘概率生成函数。将所有自变量都设为 ss,即可得到 X1+⋯+XdX_1+\cdots+X_d 的概率生成函数,无论这些随机变量是否独立。

混合偏导数给出混合阶乘矩。对于不同的 ii 和 jj,若二阶矩有限,则

Cov⁡(Xi,Xj)=∂2G∂si∂sj(1)−∂G∂si(1)∂G∂sj(1),\operatorname{Cov}(X_i,X_j) = \frac{\partial^2G}{\partial s_i\partial s_j}(\mathbf1) - \frac{\partial G}{\partial s_i}(\mathbf1) \frac{\partial G}{\partial s_j}(\mathbf1),

其中,边界处的导数理解为从定义域内部趋近边界时的极限。

这些随机变量相互独立,当且仅当联合概率生成函数可分解为各边缘概率生成函数的乘积。

相关变换与局限性

矩生成函数

MX(t)=E[etX]M_X(t)=\mathbb E[e^{tX}]

与概率生成函数的关系为

MX(t)=GX(et)M_X(t)=G_X(e^t)

其中要求相应的期望值有限。概率生成函数在 [0,1][0,1] 上总是有限的,而 MX(t)M_X(t) 对任何正的 tt 都可能不有限。

特征函数(概率论)满足

φX(t)=GX(eit),\varphi_X(t)=G_X(e^{it}),

而拉普拉斯变换满足

E[e−tX]=GX(e−t),t≥0.\mathbb E[e^{-tX}]=G_X(e^{-t}), \qquad t\ge0.

普通概率生成函数专门适用于非负整数值随机变量。对于可以取负整数值的随机变量,通常需要使用含负幂的级数;对于非整数值随机变量,则使用其他变换更为自然。

虽然概率生成函数能够确定每个取值的概率,但提取高阶系数在计算上可能很困难。反复进行数值微分可能不稳定;根据函数的表示形式,采用系数递推、符号展开或基于傅里叶变换的方法可能更合适。将函数解析延拓到原收敛圆盘之外时也须谨慎:延拓后的函数值未必等于有限的期望值 E[sX]\mathbb E[s^X]。