如果我有 2^(-n) 概率获得 2^n 元

题目见 https://www.zhihu.com/question/570330301

设随机变量 $X$，定义 $f(w): (0, 1) \rightarrow \R, Pr(X \in (a, b)) = \int_0^1 [f(i) \in (a, b)]$，要求 $f$ 单调，不妨设 $f$ 单调减。

这样构造的函数有两个性质：

• $E(X) = \int_0^1 f(x) \mathrm{d} x$

• 若 $Y \sim U(0, 1)$，则 $f(Y)$ 与 $X$ 同分布

现在令 $X$ 服从题设分布，则 $\frac{k}{2x} \leq f(x) \leq \frac{k}{x}$（这里 $k = 2$，不过 $k$ 不重要），可以求出 $\int_a^{b} f(x) = \ln b - \ln a$

假设重复 $n$ 次，那么可以期望所有概率小于 $1/n$ 的事件均不会发生，一个自然的想法当然是令 $g_c(x) = f(\argmin\limits_{|x' - x| < c}|f(x')|)$。

由单调性，近似地，作积分：

$$\int_{n^{-1}}^{1-n^{-1}} f(x) = \ln(1 - n^{-1}) - \ln(n^{-1}) \sim \ln n$$

可以得到重复 $n$ 次的期望收益是 $\Theta(n \ln n)$ 量级。