在闭区间[0, 1]内,我们随机取出两点(服从均匀分布)A和B,形成一个新的闭区间[min{A,B}, max{A,B}]。如此反复n次,我们就有了n个随机闭区间。那么这n个闭区间不出现重叠的概率是多大呢?
2个回答
答案是
$$\frac{2^n n!}{(2n)!}.$$
思路大致如下:
我们是随机按照均匀分布抽取$n$个闭区间的上下界。我们把$n$个区间的下界从小到大排序,也就是$(x_{1,1},x_{1,2}),(x_{2,1},x_{2,2}),\cdots,(x_{n,1},x_{n,2})$,满足$x_{1,1}<x_{2,1}<x_{3,1}<\cdots < x_{n,1}$。
在这种情况下,唯一能够达到所有闭区间不重叠的情况是
$$x_{1,1} < x_{1,2} < x_{2,1} < x_{2,2} < x_{3,1} < x_{3,2} < \cdots < x_{n,1} < x_{n,2}.$$
因为我们只在乎其排序,而且均匀随机抽样。这个问题就等价于从集合$\{1,2,3,\cdots,2n\}$中无放回的抽样。
符合不重叠的唯一可能性是
$$x_{1,1}=1,x_{1,2}=2,x_{2,1}=3,\cdots,x_{n,1}=2n-1,x_{n,2}=2n,$$
而所有的可能性一共有
$$\frac{(2n)!}{2^n n!}.$$
然后就可以得到概率。
我用python验证了下高代兄的答案
import math
import pandas as pd
import numpy as np
n = 3
rounds = 10000
p = 0
for m in range(rounds):
bounds = pd.DataFrame(columns=['lower_bound', 'upper_bound'])
for i in range(n):
bounds.loc[i] = np.sort(np.random.uniform(0, 1, 2))
bounds.sort_values('lower_bound', inplace=True)
diff = np.diff(bounds['upper_bound'].values)
p += np.all(diff <= 0) / float(rounds)
print('simulation', p)
print('true:', ((2 ** n) * math.factorial(n)) / math.factorial(2*n))
得到的结果:
simulation: 0.0675
true: 0.06666666666666667
SofaSofa数据科学社区DS面试题库 DS面经 相关主题
关于三门问题的疑问
2回答
轮流射击先中枪的概率题
2回答
柯西分布没有数学期望
1回答
今天明天都下雨的概率
1回答
什么函数族满足关于最值函数封闭?
0回答
用一个骰子生成1到7的随机数?
5回答
证明马尔可夫不等式
1回答
我们谢绝在回答前讲“生动”的故事。
我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。
我们谢绝答非所问。
我们谢绝自己不会、硬要回答。
我们感激每一个用户在编写答案时的努力与付出!