免费概率中等

Uniforms Until the Sum Exceeds One

考察公司Five RingsJump Trading

Draw random numbers uniformly from $[0, 1]$ , one at a time, and keep a running total. Stop as soon as the total is greater than $1$ . Let $N$ be the number of draws. Find $E[N]$ .

解析

先自己试一试，卡住了再打开提示。

提示 1

$N > n$ means the first $n$ draws add up to at most $1$ . Find $P(U_1 + \dots + U_n \le 1)$ for $n = 1, 2$ by drawing a picture.

提示 2

For a count $N$ , $E[N] = P(N > 0) + P(N > 1) + P(N > 2) + \dots$

查看解析

Call the draws $U_1, U_2, \dots$

Step 1: When do we need more than $n$ draws? We are still going after $n$ draws exactly when the total so far has not passed $1$ :

N > n \iff U_1 + U_2 + \dots + U_n \le 1.

So we need $p_n = P(U_1 + \dots + U_n \le 1)$ .

Step 2: Why $p_n = \dfrac{1}{n!}$ .

Small cases first. $p_1 = P(U_1 \le 1) = 1$ . For $n = 2$ , the point $(U_1, U_2)$ is uniform in the unit square, and $U_1 + U_2 \le 1$ is the triangle below the diagonal: half the square, so $p_2 = \tfrac12$ .

The general case, by sorting. Look at the running totals

S_1 = U_1, \quad S_2 = U_1 + U_2, \quad \dots, \quad S_n = U_1 + \dots + U_n.

The event $S_n \le 1$ says these totals are $n$ points in $[0, 1]$ that come out in increasing order: $S_1 < S_2 < \dots < S_n \le 1$ .

Now compare with $n$ independent uniform points $V_1, \dots, V_n$ in $[0, 1]$ . Two facts:

Turning the draws $(U_1, \dots, U_n)$ into the totals $(S_1, \dots, S_n)$ is a one-to-one change of variables that keeps volume the same (each $S_i$ just adds the earlier draws, a shear). So "the totals land in increasing order inside $[0,1]$ " has the same probability as " $V_1 < V_2 < \dots < V_n$ ".
The $n$ points $V_1, \dots, V_n$ can come out in $n!$ different orders, all equally likely, so one particular order has probability $\frac{1}{n!}$ .

Therefore

P(N > n) = p_n = \frac{1}{n!}.

Check: $n = 2$ gives $\tfrac12$ , matching the triangle; $n = 3$ gives $\tfrac16$ , the corner pyramid of the cube.

Step 3: From these probabilities to $E[N]$ .

Why we can add the $P(N > n)$ instead of multiplying by $n$ . The definition is $E[N] = \sum_n n \, P(N = n)$ . The shortcut rewrites $n$ as a count:

N = \underbrace{1 + 1 + \dots + 1}_{N \text{ ones}} = \mathbf{1}(N > 0) + \mathbf{1}(N > 1) + \mathbf{1}(N > 2) + \cdots

because $N > k$ is true for exactly $N$ values of $k$ , namely $k = 0, 1, \dots, N - 1$ . Taking expectations of both sides,

E[N] = P(N > 0) + P(N > 1) + P(N > 2) + \cdots

Each draw count $n$ still gets weighted by $n$ ; it's just collected one layer at a time.

Shortcut:

E[N] = \sum_{n=0}^{\infty} \frac{1}{n!} = 1 + 1 + \frac12 + \frac16 + \frac1{24} + \cdots = e.

Same answer the long way. $P(N = n) = P(N > n - 1) - P(N > n) = \frac{1}{(n-1)!} - \frac{1}{n!} = \frac{n - 1}{n!}$ . Then

E[N] = \sum_{n=2}^{\infty} n \cdot \frac{n-1}{n!} = \sum_{n=2}^{\infty} \frac{1}{(n-2)!} = 1 + 1 + \frac12 + \frac16 + \cdots = e.

Answer: $E[N] = e \approx 2.71828$ .

Sanity check: each draw averages $\tfrac12$ , so you might guess $2$ draws. But you always need at least $2$ , and sometimes $3$ or more, so the average has to be above $2$ .

题目

解析