这个问题很有意思,我们来一步一步把它拆解开,看看怎么求出从自然数 1 到 n 中随机抽取 m 个数,其中最大数的数学期望。
理解问题
首先,我们要明确几个概念:
自然数 1 ~ n: 就是集合 {1, 2, 3, ..., n}。
随机抽取 m 个: 这意味着我们从这 n 个数中选出 m 个,并且每一种组合被选中的概率是相等的。比如,从 {1, 2, 3} 中选 2 个数,可能的组合有 {1, 2}, {1, 3}, {2, 3},每种组合被抽到的概率都是 1/3。
最大数: 就是我们抽到的 m 个数里最大的那个。
数学期望: 简单来说,就是所有可能结果的平均值。在概率论里,它是随机变量的期望值,计算方法是“每个结果出现的概率乘以该结果的值,然后将所有这些乘积相加”。
举个小例子
在开始正式推导之前,我们先用一个简单的例子来感受一下。
假设 n=4,我们要从中随机抽取 m=2 个数。
可能的组合有哪些?
{1, 2},最大数是 2
{1, 3},最大数是 3
{1, 4},最大数是 4
{2, 3},最大数是 3
{2, 4},最大数是 4
{3, 4},最大数是 4
总共有 C(4, 2) = 6 种组合。
每种组合被抽到的概率是 1/6。
现在我们来看看最大数可能的值以及它们出现的次数:
最大数是 2:只有 {1, 2} 一种组合,出现 1 次。
最大数是 3:有 {1, 3}, {2, 3} 两种组合,出现 2 次。
最大数是 4:有 {1, 4}, {2, 4}, {3, 4} 三种组合,出现 3 次。
最大数的数学期望就是:
E = (2 1/6) + (3 2/6) + (4 3/6)
E = 2/6 + 6/6 + 12/6
E = 20/6 = 10/3
这个例子帮助我们理解了“数学期望”的计算方式。
如何计算?
现在我们回到一般情况:从自然数 1 ~ n 中随机抽取 m 个数,求最大数的数学期望。
我们直接去计算每一种最大值(比如 3 能够成为最大值,4 能够成为最大值等等)的概率,然后乘以这个值再相加,会比较繁琐。有没有更巧妙的方法?
换个角度思考:最大数是 k 的概率
一个常见的策略是先确定“最大数是某个特定值 k”的概率。
假设我们抽取的 m 个数中,最大数是 k。这意味着什么?
1. 抽到的 m 个数都必须小于或等于 k。
2. 抽到的 m 个数中,至少有一个数是 k。
换句话说,我们是从 {1, 2, ..., k} 这 k 个数里抽取 m 个数,并且这 m 个数必须包含 k。
那么,从 {1, 2, ..., k} 中抽取 m 个数,这 m 个数都小于等于 k 的情况有多少种呢?就是从这 k 个数里任选 m 个,总共有 C(k, m) 种组合。
如果这 m 个数中最大的是 k,那么这 m 个数就必须从 {1, 2, ..., k} 中选出来,并且其中必须包含 k。这意味着,除了 k 本身之外,我们还需要从 {1, 2, ..., k1} 这 k1 个数中再选出 m1 个数。
所以,使得最大数是 k 的组合数量是 C(k1, m1)。
注意这里的限制:
k 必须至少是 m,因为你得从 m 个数里选出最大的,最大的那个数至少得是 m。比如你想选 3 个数,最大的那个数不可能小于 3。
k 最多是 n。
总的组合数
我们从 n 个数里随机抽取 m 个数,总共有多少种组合?这是组合数 C(n, m)。
计算概率 P(最大数 = k)
因此,最大数是 k 的概率 P(最大数 = k) 就是:
P(最大数 = k) = (最大数是 k 的组合数) / (总的组合数)
P(最大数 = k) = C(k1, m1) / C(n, m)
数学期望的计算
现在,最大数的数学期望 E 就是所有可能的 k 值乘以它们对应的概率再求和:
E = Σ [k P(最大数 = k)] (k 从 m 到 n)
E = Σ [k C(k1, m1) / C(n, m)] (k 从 m 到 n)
我们可以把 C(n, m) 提出来:
E = (1 / C(n, m)) Σ [k C(k1, m1)] (k 从 m 到 n)
利用组合数性质简化求和
接下来是关键的简化步骤。我们需要计算这个求和:Σ [k C(k1, m1)] (k 从 m 到 n)。
这里有一个非常重要的组合数恒等式:
k C(k1, m1) = m C(k, m)
这个恒等式是怎么来的呢?
考虑从 k 个人里选出 m 个人,其中指定一个人(比如“领导”)的方案数。
方法一:先选出 m 个人,再从这 m 个人里指定一个领导。即 C(k, m) m。
方法二:先选出领导,再从剩下 k1 个人里选出 m1 个人组成团队。即 m C(k1, m1)。
所以 k C(k1, m1) = m C(k, m)。
利用这个恒等式,我们的求和变成:
Σ [k C(k1, m1)] = Σ [m C(k, m)] (k 从 m 到 n)
= m Σ [C(k, m)] (k 从 m 到 n)
现在我们又遇到了一个新的求和:Σ [C(k, m)] (k 从 m 到 n)。
这个求和可以用另一个组合数恒等式来简化:
Σ [C(i, r)] (i 从 r 到 N) = C(N+1, r+1)
在这个例子里,r = m,N = n。
所以,Σ [C(k, m)] (k 从 m 到 n) = C(n+1, m+1)。
将这一切代回去:
求和部分 = m C(n+1, m+1)
最终的数学期望
现在我们把这个结果代回期望的公式:
E = (1 / C(n, m)) [m C(n+1, m+1)]
我们知道 C(n, m) = n! / (m! (nm)!)
而 C(n+1, m+1) = (n+1)! / ((m+1)! (nm)!)
代入计算:
E = (m! (nm)!) / n! m [(n+1)! / ((m+1)! (nm)!)]
E = (m! (nm)!) / n! m [(n+1) n! / ((m+1) m! (nm)!)]
化简一下:
E = (m! (nm)!) / n! m [(n+1) / (m+1)] [n! / (m! (nm)!)]
可以看到,n!, m!, (nm)! 都可以约掉。
E = 1 m (n+1) / (m+1)
E = m (n+1) / (m+1)
结论
从自然数 1 到 n 中随机抽取 m 个数,其中最大数的数学期望是:
E = (m (n + 1)) / (m + 1)
回顾与验证
让我们用之前的小例子来验证一下这个公式。
n=4, m=2
E = (2 (4 + 1)) / (2 + 1)
E = (2 5) / 3
E = 10/3
这个结果和我们之前手动计算的结果是一致的!
这个推导过程利用了组合数的性质,将直接求和的问题转化为了利用已知公式进行化简,这是解决这类统计问题的常用技巧。整个过程环环相扣,从理解问题到分解思路,再到利用数学工具进行推导,最终得到简洁而优美的结果。