从[0,1]区间不断取小数，平均取多少个才能使取出数的和大于1

数学 算法

---

给出一种直接算的暴力解法，首先分析一下这个问题，从$[0,1]$区间不断取小数，取每一个数的概率相同，则我们设取出的数的序列为$A,B,C,D,E,\cdots$，然后要求平均取多少个才能使取出的解的和大于$1$，这里需要注意两个关键词，一是“平均”，表明这个地方需要求期望，第二个是“才”，表明这是个反命题，需要求和大于1时的解的反，故综合来说我们只需要求，取$n$个小数，这$n$个数的和小于等于$1$的概率为$p(n)$，要求$E_{p(n)}[n]$，则最后有平均取$E_{p(n)}[n]$个才能使取出数的和大于$1$

这时问题就集中在$p(n)$怎么求，先来看$p(n)$如何表示

$$p(n) = P(X_1 + X_2 + \cdots + X_n \le 1)$$

为了方便理解，先从二维来看，$p(2) = P(X+Y\le 1)$，这时$X\sim \mathrm{Uniform}(0,1), Y\sim\mathrm{Uniform}(0,1)$，故其可以转换为求解面积的形式

相当于求解阴影部分的面积，则$p(2) = \frac{1}{2}$，同样扩展到三维$p(3) = P(X+Y+Z \le 1)$

由此看到$p(3)$就等于该直角棱锥的体积，则$p(3) = \frac{1}{6}$，综上可以看出来，$p(n)$就是一个区域条件为$x_1 + x_2 + \cdots + x_n \le 1$的1的$n$重积分，可以得到此时的“体积”公式为$p(n) = \frac{1}{n!}$，这个式子如何推出来的，下次再说

那么期望为

$$\begin{split} E[n] & = \sum_{n=1}^{+\infty} \frac{1}{n!}\cdot n \\ & = \frac{1}{1!} \cdot 1 + \frac{1}{2!} \cdot 2 + \frac{1}{3!} \cdot 3 + \cdots + \frac{1}{n!}\cdot n \\ & = 1 + 1 + \frac{1}{2!} + \cdots + \frac{1}{(n-1)!} \end{split}$$

由于指数函数的泰勒展开为

$$e^x = 1 + \frac{1}{1!}x + \frac{1}{2!}x^2 + \frac{1}{3!}x^3 + \cdots + \frac{1}{n!}x^n + o(x^n) \\ e^1 = 1 + 1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{n!}$$

故$E[n] = e$

---

$S(n) = \frac{1}{n!}$的推导首先我们列出多重积分的公式

$$\begin{split} S(1) & = \int_0^1 1 \mathrm{d}x \\ S(2) & = \int_0^1 \mathrm{d}y \int_0^{1-y}(1-y-x)\mathrm{d}x \\ S(3) & = \int_0^1 \mathrm{d}z \int_0^{1-z} \mathrm{d}z + \int_0^{1-z-y-x} (1-z-y-x)\mathrm{d}x \\ & \vdots \end{split}$$

由此可以的得出一个递归的模式公式

$$S_n(k) = \int_0^k S_{n-1}(k') \mathrm{d}k'$$

就是递归的对$k$求积分，很容易可以得出来$S_n(1) = \frac{1}{n!}$