返回题库

均匀数累加

Uniform(0,1) draws until sum > 1

专题
Probability / 概率
难度
L6

题目详情

独立生成随机数 U1,U2,⋯∼Unif[0,1]U_1,U_2,\dots\sim \mathrm{Unif}[0,1]，并不断累加，直到部分和首次超过 1 为止。

  1. 求 P(需要超过 n 次抽取)P(\text{需要超过 }n\text{ 次抽取})。

  2. 求期望抽取次数。

英文原题

You generate random numbers U1,U2,…∼Uniform[0,1]U_1, U_2, \ldots \sim \text{Uniform}[0,1] and keep drawing until their partial sum exceeds 1.

  1. What is P(need more than n draws)P(\text{need more than }n\text{ draws})?
  2. What is the expected number of draws?
解析

设 Sn=U1+⋯+UnS_n=U_1+\cdots+U_n。

  1. “需要超过 nn 次” 等价于 Sn≤1S_n\le 1。

Sn≤1S_n\le 1 对应于单位超立方体 [0,1]n[0,1]^n 中的单纯形体积：

P(Sn≤1)=1n!.P(S_n\le 1)=\frac{1}{n!}.

因此

P(N>n)=1n!.P(N>n)=\frac{1}{n!}.
  1. 用尾和公式：
E[N]=∑n=0∞P(N>n)=∑n=0∞1n!=e.\mathbb{E}[N]=\sum_{n=0}^{\infty}P(N>n)=\sum_{n=0}^{\infty}\frac{1}{n!}=e.

英文解析

Set Sn=U1+⋯+UnS_n=U_1+\cdots+U_n.

  1. “Requires more than nn times” is equivalent to Sn≤1S_n\le 1.

Sn≤1S_n\le 1 corresponds to the simplex volume in the unit hypercube[0,1]n[0,1]^n:

P(Sn≤1)=1n!.P(S_n\le 1)=\frac{1}{n!}.

Therefore,

P(N>n)=1n!.P(N>n)=\frac{1}{n!}.
  1. Tail sum formula:
E[N]=∑n=0∞P(N>n)=∑n=0∞1n!=e.\mathbb{E}[N]=\sum_{n=0}^{\infty}P(N>n)=\sum_{n=0}^{\infty}\frac{1}{n!}=e.