返回题库

随机数累加超过 1

Sum To One

专题
Probability / 概率
难度
L6

题目详情

每按一次按钮，会生成一个在 (0,1)(0,1) 上均匀随机数。不断生成并累加，直到总和首次超过 1。

  1. 需要按按钮次数大于 nn 的概率是多少？
  2. 期望需要按多少次？

提示：条件化 / 几何体体积。

On pressing a button, a random number is generated uniformly between 0 & 1. You keep on generating these numbers until their sum exceeds 1. What is the probability that you need to press the button more than n times? What is the expected number of times you need to press the button?

Hint

Probability by conditioning

解析
  1. P(T>n)=1n!P(T>n)=\frac{1}{n!}。

因为 T>nT>n 等价于 X1+⋯+Xn≤1X_1+\cdots+X_n\le 1，这对应 nn 维单纯形体积，恰为 1/n!1/n!。

  1. 期望次数为 ee。

用尾和公式：

E[T]=∑n≥0P(T>n)=∑n≥01n!=e.E[T]=\sum_{n\ge 0} P(T>n)=\sum_{n\ge 0}\frac{1}{n!}=e.

Original Explanation

Probability: 1/n! ; Expected times: e

Solution

Probability of more than n throws is equivalent to saying X1+..+Xn <=1, this is the volume of n dimensional symplex from origin, its volume is 1/n! and can be proved by induction. This can be used to calculate expected number of button presses, sum( 1/n! * n ) = sum( 1/(n-1)!) = e^1

Otherwise, set up a (lag)differential equation for f(x), the expected number of draws needed for the sum to exceed x. For x=0,f(x)=1. For x>0, suppose a draw gave number t, then f(x)= 1 + integral (t=0 to x)f(x-t)dt, which is same as f(x) = 1 + integral(t=0 to x) f(t)dt, differentiate wrt x, we get f'(x) = 0 + f'(x). This has the solution f(x)=e^x and x=1 gives e. To take derivative, we used leibniz integral rule: d/dx ( integral( a(x) to b(x) ) f(t) dt = f(b(x)) * b'(x) - f(a(x)) * a'(x) = f(x) * 1 - f(x) * 0 = f(x)