随机数累加达到上界问题
问题
不断地生成 [0, 1] 的随机数并累加，直到总和超过 1，求生成的随机数数量 \xi 的概率分布？平均生成多少个随机数？
解答
考虑 n 个独立同均匀分布数 X_1, \dots, X_n 相加小于等于 1 的概率，有
P(X_1 + \cdots + X_n \le 1) \int\limits_{x_1 + \cdots + x_n \le 1} \mathrm{d} x_1 \cdots \mathrm{d} x_n = \frac{1}{n!}.
最后一个等号是因为 x_1 + \cdots + x_n \le 1, x_1 \ge 0, \dots, x_n \ge 0 形成了一个单纯形，而 n 维标准单纯形的体积是其对应平行六面体的 1 / n!。
关键步骤：若随机数数量 \xi > k，则说明前 k 个随机数相加 X_1 + \cdots + X_{k - 1} \le 1（事件的等价转化），于是得到
P(\xi > k) = P(X_1 + \cdots + X_k \le 1) = \frac{1}{k!}.
所以有
P(\xi = k) = P(\xi > k - 1) - P(\xi > k) = \frac{1}{(k - 1)!} - \frac{1}{k!}.
此为 \xi 的概率质量函数。
接下来计算平均生成多少个随机数：
\begin{aligned}
E(\xi) = \sum_{k = 1}^n k P(\xi = k) &= \frac{1}{0!} - \frac{1}{1!} + 2 \left(\frac{1}{1!} - \frac{1}{2!}\right) + 3 \left(\frac{1}{2!} - \frac{1}{3!}\right) + \cdots \\
&= \frac{1}{0!} - \frac{1}{1!} + 2 \cdot \frac{1}{2!} - 2 \cdot \frac{1}{2!} + 3 \cdot \frac{1}{2!} - 3 \cdot \frac{1}{3!} + \cdots \\
&= \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots \\
&= \mathrm{e}
\end{aligned}
所以，平均会生成 \mathrm{e} 个随机数。
BEYOND THE ARTICLE
读完了，有什么想法？
阅读已保存的问答示例，并循着引用回到原文。
— 本文完 — 返回文章列表