本文共 3590 字，大约阅读时间需要 11 分钟。
微信搜索：编程笔记本
获取更多校招干货知识
今天我们来看一个有趣的问题：
不断从[0,1]中随机选择一个数进行累加，直到其和超过1，需要选择几次？ 对于一次特定的实验，次数是一个确定的整数。我们要讨论的是，选择次数的数学期望。或者说，平均需要多少次。
现在，这已经变成了一个比较复杂的数学问题了。但是，好在问题描述并不复杂，我们可以用计算机进行数值模拟。
程序流程图：
step1: 设
step2: 从s=0;[0,1]中随机选择一个数x; step3:s=s+x; step4: 若s>1，停止；否则转到step2。
参考c++代码：
#include#include #include int main(){ // 设置随机数生成器 std::default_random_engine e(time(0)); std::uniform_real_distribution gen(0.0, 1.0); double sum = 0.0; int cnt = 0; // 总试验次数与总选择次数 int times = 100; long long all = 0; for (int i = 0; i < times; ++i) { sum = 0; cnt = 0; while (sum <= 1.0) { sum += gen(e); ++cnt; } all += cnt; } // 选择次数期望 = 总选择次数 / 总试验次数 double exp = double(all) / double(times); printf("exp = %.5lf\n", exp);}
下面我们运行程序：
jincheng@DESKTOP-42T69DJ:/mnt/e/LinuxSubSysFile$ g++ test.cppjincheng@DESKTOP-42T69DJ:/mnt/e/LinuxSubSysFile$ ./a.outexp = 2.74012
微信搜索：编程笔记本
获取更多校招干货知识
从实验结果可以看到，当我们进行100次这样的实验，得到的平均选择次数为2.74012。
100次还是太少了，下面我们修改times变量值，增加试验次数，再来观察实验结果。 times = 1000 exp = 2.72800times = 10000 exp = 2.71440times = 100000 exp = 2.71601times = 1000000 exp = 2.71939times = 10000000 exp = 2.71833times = 100000000 exp = 2.71824随着实验的进行，我们似乎看出来某种规律，选择次数的期望值怎么这么眼熟啊…是不是有点像**自然对数底数e**啊？
我们知道，自然对数底数e = 2.71828 18284 59……。当我们进行足够多次实验（100000000次）时，得到的选择次数期望值为2.71824，这与e的前四位小数惊人般地雷同！直觉告诉我，这一定不是巧合！此事必有蹊跷！
先说结论：
不断从
[0,1]中随机选择一个数进行累加，直到其和超过1，需要的选择次数的期望值为欧拉常数e。
今天的编程小知识主要是C++11新标准的随机数生成库的应用。在新标准下使用随机数，原则上我们不再使用rand()与srand()函数了，而是使用随机度更高、效率更快的随机数生成库，它内置了一系列常用的随机分布。感兴趣的小伙伴可以自行查阅学习。下面是上述结论的严格数学证明，请小伙伴们有选择性地阅读。
求数学期望，就是随机量的所有可能取值*随机量取该值的概率。
在我们讨论的问题中，选择次数（记为C）的可能取值为：2,3,4,...，则：
E ( C ) = Σ n = 2 ∞ [ n ∗ P ( C = n ) ] E(C) = \Sigma_{n=2}^{\infty} [n*P(C=n)] E(C)=Σn=2∞[n∗P(C=n)]
下面我们从简单的情况入手。
n = 2： 等价于，在边长为 1 的正方形中取一点，其落在箭头区域(x + y \> 1)的概率，即P = 1/2 = 1 - 1 / (2!)；n = 3： 等价于，在棱长为 1 的正方体中取一点，其落在箭头区域(x + y + z \> 1)的概率，即P = 5/6 = 1 - 1 / (3!)；为了不让证明过程过于复杂，我们直接给出一个数学定理：在n维单位空间中，其中任取一点，落在单位之外的概率为 P = 1 - 1 / (n!)。
在我们的问题中，考虑“第n次选择后，其和恰好大于 1 ”的事件。该事件成立的前提是，前 n-1 的和并未大于 1 ，而第 n 次选择之后，其和大于 1 。则有：
P ( C = n ) = [ 1 − 1 / ( n ! ) ] − [ 1 − 1 / ( ( n − 1 ) ! ) ] P(C=n) = [1 - 1 / (n!)] - [1 - 1 / ((n-1)!)] P(C=n)=[1−1/(n!)]−[1−1/((n−1)!)]
上式中后半部分减去的是“前n-1次选择后和大于 1 ”的概率。如此一来，我们的问题便能够求解了。
E ( C ) = Σ n = 2 ∞ [ n ∗ P ( C = n ) ] = Σ n = 2 ∞ n ∗ { [ 1 − 1 / ( n ! ) ] − [ 1 − 1 / ( ( n − 1 ) ! ) ] } = Σ n = 2 ∞ n ∗ { 1 / ( ( n − 1 ) ! ) − 1 / ( n ! ) } = Σ n = 2 ∞ n ∗ { ( n − 1 ) / ( n ! ) } = Σ n = 2 ∞ { 1 / ( ( n − 2 ) ! ) } = Σ n = 0 ∞ { 1 / ( n ! ) } E(C) = \Sigma_{n=2}^{\infty} [n*P(C=n)]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ =\Sigma_{n=2}^{\infty} n*\{[1 - 1 / (n!)] - [1 - 1 / ((n-1)!)]\}\\ =\Sigma_{n=2}^{\infty} n*\{1 / ((n-1)!) - 1 / (n!)\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ =\Sigma_{n=2}^{\infty} n*\{(n - 1) / (n!)\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ =\Sigma_{n=2}^{\infty} \{1 / ((n - 2)!)\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ =\Sigma_{n=0}^{\infty} \{1 / (n!)\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ E(C)=Σn=2∞[n∗P(C=n)] =Σn=2∞n∗{ [1−1/(n!)]−[1−1/((n−1)!)]}=Σn=2∞n∗{ 1/((n−1)!)−1/(n!)} =Σn=2∞n∗{ (n−1)/(n!)} =Σn=2∞{ 1/((n−2)!)} =Σn=0∞{ 1/(n!)}
由泰勒级数我们知道， Σ n = 0 ∞ { 1 / ( n ! ) } \Sigma_{n=0}^{\infty} \{1 / (n!)\} Σn=0∞{ 1/(n!)} = e。
证毕。微信搜索：编程笔记本
获取更多校招干货知识
转载地址：http://vhkgn.baihongyu.com/