[笔记] 收集邮票

有 $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} $$

（草）

然后直接爆算，完事。

代码

// 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;
}