返回题库

递减抽样：次数与最小值的期望

Chosen numbers

专题
General / 综合
难度
L4

题目详情

Independent random numbers with uniform distribution on [0,1][0,1] are generated as long as they keep decreasing. The procedure stops when the obtained number is greater than the previous one. What is the average number of numbers that were picked? What is the average value of the smallest of the chosen numbers?

解析

设 X1,X2,…∼iidUnif[0,1]X_1,X_2,\ldots\overset{iid}{\sim}\mathrm{Unif}[0,1]，当出现 Xk>Xk−1X_{k}>X_{k-1} 时停止，令总次数为 NN。

对 k≥2k\ge 2，有

P(N>k)=P(X1>⋯>Xk)=1k!.\mathbb{P}(N>k)=\mathbb{P}(X_1>\cdots>X_k)=\frac{1}{k!}.

因此

E[N]=∑k≥0P(N>k)=1+1+∑k=2∞1k!=e.\mathbb{E}[N]=\sum_{k\ge 0}\mathbb{P}(N>k)=1+1+\sum_{k=2}^{\infty}\frac{1}{k!}=\boxed{e}.

设 MM 为已选数中的最小值，可计算得到

E[M]=3−e.\boxed{\mathbb{E}[M]=3-e}.