首页 > 分享 > 概率论：邮票收集问题的期望与方差求解

概率论：邮票收集问题的期望与方差求解

花匠小妙招
2025-12-15 23:39

概率论——赠券收集问题

题意

有nnn中不同的邮票。现在想购买所有种类的邮票，第iii次购买一张邮票需要花费iii元，并且购买到的这张邮票的种类的概率均等即均为1nfrac{1}{n}n1，求花费的期望。

题解

根据等差数列求和公式，购买次数为xxx的花费为x(x+1)2frac{x(x+1)}{2}2x(x+1)，我们所求的就是E(x(x+1)2)E(frac{x(x+1)}{2})E(2x(x+1))，即：

E(x(x+1)2)=E(x2+x2)=E(x2)+E(x)2 E(frac{x(x+1)}{2}) = E(frac{x^2+x}{2}) = frac{E(x^2) + E(x)}{2} E(2x(x+1))=E(2x2+x)=2E(x2)+E(x)

根据方差与期望之间的关系E(x2)=D(x)+E2(x)E(x^2) = D(x) + E^2(x)E(x2)=D(x)+E2(x)，我们有：

E(x(x+1)2)=D(x)+E2(x)+E(x)2 E(frac{x(x+1)}{2}) = frac{D(x) + E^2(x) + E(x)}{2} E(2x(x+1))=2D(x)+E2(x)+E(x)

此问题就变成了：

有nnn中不同的邮票。现在想购买所有种类的邮票，一次只能购买一张邮票，并且购买到的这张邮票的种类的概率均等即均为1nfrac{1}{n}n1，求购买的次数的期望和方差。

我们定义xix_ixi为从已经买到了i−1i-1i−1张不同种类的邮票开始，到购买到iii张不同种类的邮票结束所购买的次数，根据期望的线性性，有：

E(x)=E(∑i=1nxi)=∑i=1nE(xi) E(x) = E(sum_{i=1}^nx_i) = sum_{i=1}^n E(x_i) E(x)=E(i=1∑nxi)=i=1∑nE(xi)

其中xi∼G(n−i+1n)x_i sim G(frac{n-i+1}{n})xi∼G(nn−i+1)，GGG为几何分布。

几何分布x∼G(p)x sim G(p)x∼G(p)，期望E(x)=1pE(x) = frac{1}{p}E(x)=p1，方差D(x)=1−pp2D(x) = frac{1-p}{p^2}D(x)=p21−p

E(xi)=nn−i+1 E(x_i) = frac{n}{n-i+1} E(xi)=n−i+1n

则带入上式：

E(x)=∑i=1nnn−i+1=n∑i=1n1i=nHn E(x) = sum_{i = 1}^n frac{n}{n-i+1} = n sum_{i = 1}^n frac{1}{i} = nH_n E(x)=i=1∑nn−i+1n=ni=1∑ni1=nHn

下一步，求D(x)D(x)D(x)，因为xix_ixi之间相互独立，协方差等于000，故：

D(x)=D(∑i=1nxi)=∑i=1nD(xi)=∑i=1nn(i−1)(n−i+1)2=n∑i=1nn−(n−i+1)(n−i+1)2=n2∑i=1n1i2−n∑i=1n1i=n2Hn(2)−nHn D(x) = D(sum_{i=1}^nx_i) = sum_{i=1}^n D(x_i) \ = sum_{i=1}^n frac{n(i-1)}{(n-i+1)^2} = n sum_{i=1}^n frac{n-(n-i+1)}{(n-i+1)^2}\ = n^2 sum_{i=1}^n frac{1}{i^2} - n sum_{i=1}^n frac{1}{i} \ = n^2H^{(2)}_n-nH_n D(x)=D(i=1∑nxi)=i=1∑nD(xi)=i=1∑n(n−i+1)2n(i−1)=ni=1∑n(n−i+1)2n−(n−i+1)=n2i=1∑ni21−ni=1∑ni1=n2Hn(2)−nHn

带入上式：

E(x(x+1)2)=D(x)+E2(x)+E(x)2=n2(Hn(2)+Hn2)2 E(frac{x(x+1)}{2}) = frac{D(x) + E^2(x) + E(x)}{2} \ = frac{n^2(H^{(2)}_n + H^2_n)}{2} E(2x(x+1))=2D(x)+E2(x)+E(x)=2n2(Hn(2)+Hn2)

代码

我们只需要循环计算一下调和数列的值即可，时间复杂度O(n)O(n)O(n)，空间复杂度O(1)O(1)O(1)。

int main() { int n; scanf("%d", &n); double h = 0; double h2 = 0; for (int i = 1; i <= n; i++) { h += 1.0 / i; h2 += (1.0 / i) * (1.0 / i); } double ans = (h2 + h * h) * n * n / 2; printf("%.2lf", ans); return 0; }

cpp

运行

123456789101112131415