[笔记] 收集邮票

有 $n$ 种邮票,第 $i$ 轮会花费 $i$ 的代价随机得到一种,问收集完全部邮票的期望代价。

$1\le n\le 10000$

题目链接


思路

弱鸡概率蓝题我都要推好一会儿,干

首先你考虑你已经有 $i$ 种邮票,收集到一种新的邮票花费的代价:

$$ w_i=\frac{(g_i+1+g_i+s)s}2 $$

$g_i$ 是指你在此之前买了多少邮票,这个很好算;$s$ 是你收集到这种新邮票买了多少次。然后我们有:

$$ \begin{aligned} E(w_i)&=E\left(\frac{(2g_i+s+1)s}2\right)\\ &=\frac{2E(g_i)+1}2E(s)+\frac{E(s^2)}2 \end{aligned} $$

注意期望的平方不等于平方的期望。注意到这个 $s$ 遵从 $p=\frac{n-i}n$ 的几何分布,于是我们现在就是要求几何分布的期望和平方的期望。期望众所周知是 $\frac1p$,那平方的期望是?

我们写出几何分布的概率生成函数:

$$ \begin{aligned} F(x)&=\sum_{i=1}^\infty(1-p)^{i-1}px^i\\ &=\frac{px}{px-x+1} \end{aligned} $$

然后验算一下是对的,因为 $F(1)=1$。然后我们知道平方的期望就等于:

$$ \begin{aligned} &\left((F'(x)\cdot x)'\cdot x\right)(1)\\ =&\left(\left(\frac{px}{(px-x+1)^2}\right)'\cdot x\right)(1)\\ =&\left(\frac{px(px-2x(p-1)-x+1)}{(px-x+1)^3}\right)(1)\\ =&\frac{2-p}{p^2} \end{aligned} $$

(草)

然后直接爆算,完事。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Mivik 2020.12.23
#include <mivik.h>

#include <iomanip>

MI cin;

int n;
int main() {
cin > n;
double f = 0, g = 0;
for (int i = 0; i < n; ++i) {
const double p((double)(n - i) / n);
f += ((g * 2 + 1) / p + (2 - p) / (p * p)) / 2;
g += 1. / p;
}
cout < std::fixed < std::setprecision(2) < f < endl;
}
作者

Mivik

发布于

2020-12-23

更新于

2021-05-31

许可协议

评论