blog

已知：事件 A1, …, An 发生的概率分别为 p1, …, pn。记 p = p1 + · · · + pn

求证：至少有 k 个事件发生的概率不大于 pk/k!

一道习题

已知：

事件$A_1,...,A_n$发生的概率分别为$p_1,...,p_n$。 记$p=p_1+\dots+p_n$

求证：至少有$k$个事件发生的概率不大于$p^k/k!$

想法

看到题目的第一感觉，就是类似于二项分布。但仔细考虑一下会发现困难有不少。 如果严格按照题目的要求来，大致是这样的结构：

先算刚好有$k$个事件发生的概率，是一个有$C_n^k$项的求和，求和的每一项具有 $p_{i_1}\cdots p_{i_k}(1-p_{i_{k+1}})\cdots(1-p_{i_n})$的形式，其中 $i_1,\dots,i_k$是$1$到$n$中选出$k$个数，$i_{k+1},\dots i_n$是剩余的数。

然后要算刚好有$k+1,\dots,n$个事件发生的概率。这又是一层求和。这样一个 式子，由于$p_1,\dots,p_n$都是未知的，因此几乎做不了什么化简工作。

好在此题的关键是要求的是一个不等式。因此我们再回过头来看看有什么地方可 以刨去一些使得运算变得复杂的细节。

对于求和的内部，看到最后的结果是只含有$p$的表达式，而上面的式子是连乘式。 想到了均值不等式，但是符号不对，得想其他办法。

再看外部的两层求和，若是能减少一层将会大大方便。这要从解题逻辑上考虑。 再来看看要求：至少发生$k$个事件。那么如果就直接选出$k$个事件让它发生， 剩下的就干脆不管，会怎样呢？

乍看起来好像没什么问题，但考虑一下就会发现存在重复的问题，即概率会变大。 不过本来就是要做概率的放大，因此可以尝试一下。这样，放大后的式子为

$$\sum{p_{i_1}\cdots p_{i_k}}$$

平均的思想

想一想上式的求和过程。既然最后结果是和每个具体事件的概率无关，那么肯定是求出这个式子的最大值，然后说明最大值不大于题目给的值。可以发现，这又是一个"和为定值，求表达式最值"的分配问题。看起来很棘手，但是我们可以猜当概率$p$被平均分配的时候表达式的值是最大的。

下一个问题是，到底是被$k$个事件平均分配，还是$n$个事件平均分配？并且应该怎么证明此时是最大值？我们来推演一下。

如果是被$k$个事件平均分配，虽然这不可能（因为不可能每个事件都有$p/k$的概率），但是证明是最大值比较方便。如果$p_{i_1}+\cdots+p_{i_k}$概率大小不足$p$，那么肯定不是最大值，因为有增大的空间；如果等于$p$，由均值不等式就可以明白平均分配时值最大。那么，这样放缩能不能证出原命题呢？

尝试一下。内部连乘式化为$p^k/k^k$，是一个与求和无关的常数。因此得到的答案为$C_n^kp^k/k^k$。和题目要求比较，要证明$n!\leq (n-k)!k^k$。代了几个具体的$k$后发现不对，说明放的太大了。

如果被$n$个事件平均分配，先看看能不能证出结论。类似地，此时得到的答案为$C_n^kp^k/n^k$。和题目要求比，要证明$n!\leq (n-k)!n^k$。注意到$n^k>n(n-1)\cdots(n-k+1)$，这个放缩刚刚好。

那么接下去试图证明被$n$个事件平均分配时是最大值，这个要难一些。但是这类问题，都可以考虑用调整法。

调整法证明最值

用调整法证明最大值，就是要说明在某个情况下，对参数进行任何满足约束的调整都会使得表达式的值变小。而各种调整又可以进行分解，即只需证明最小操作——对某两个参数进行满足约束的调整使得表达式的值变小即可。

在这里，约束是概率之和为$p$。我们假设在每个事件发生的概率都为$p/n$的情况下表达式值最大，为

$$ \frac{C_n^kp^k}{n^k}$$

接着为满足约束条件，对两个事件的概率引入小扰动，使其发生的概率分别变为$p/n-t$和$p/n+t$。此时表达式的值为

$$\frac{C_{n-2}^kp^k}{n^k}+\frac{C_{n-2}^{k-1}p^{k-1}}{n^{k-1}}(\frac{p}{n}-t)+\frac{C_{n-2}^{k-1}p^{k-1}}{n^{k-1}}(\frac{p}{n}+t)+\frac{C_{n-2}^{k-2}p^{k-2}}{n^{k-2}}(\frac{p}{n}-t)(\frac{p}{n}+t)$$

上式共有四项，从左至右依次是

• 从除去两个扰动事件中选$k$个；

• 从除去两个扰动事件中选$k-1$个并配上概率减小的事件；

• 从除去两个扰动事件中选$k-1$个并配上概率增大的事件；

• 从除去两个扰动事件中选$k-2$个并配上两个概率变化的事件；

简单化简后成为

$$ \frac{p^k}{n^k}(C_{n-2}^k+2C_{n-2}^{k-1}+C_{n-2}^{k-2})-t^2\frac{C_{n-2}^{k-2}p^{k-2}}{n^{k-2}}$$

对比一下前一个最大值表达式，容易猜到上式中左项应当就是最大值，而右式带平方的负项正是调整的损益。接下去只需要证明

$$C_{n-2}^k+2C_{n-2}^{k-1}+C_{n-2}^{k-2}=C_n^k$$

即可。事实上，这个直接通分即可验证。

最后，对于$n<2,k<2$的情况，直接单独验证即可。略（其实是懒）。

组合数的一个性质

从形式上看，可以猜到上式是下面这个式子的特殊情况。

$$C_n^k=\sum_{i=0}^m{C_{n-m}^{k-i}C_m^i},m=0,1,\dots,n-k$$

这个式子的代数证法试了一天无果，但是从实际意义上很好理解。

为从$n$个对象中选出$k$个，将其分为两堆。记$A$堆有$m$个，$B$堆有$n-m$个。 总共的种数是以下分配的种数之和：

• 从$A$堆中取出$0$个，$B$堆中取出$k$个。

• 从$A$堆中取出$1$个，$B$堆中取出$k-1$个。

• .......…

• 从$A$堆中取出$k$个，$B$堆中取出$0$个。

也就是

$$C_n^k=\sum_{i=0}^m{C_m^iC_{n-m}^{k-i}}$$

如果有读者知道该如何从代数角度证明，欢迎联系我。