概率方法证明不等式：构造随机变量，将不等式中的项解释为事件的概率

摘要: 构造随机变量，然后组装事件，凑出不等式的项中的概率

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们看一个不等式的证明，涉及到构造随机变量通过概率方法证明的思路，还是很巧妙的。

其过程大致是先根据条件恰当地构造随机变量，使得不等式中的各项都可以解释为由此前构造的随机变量组装出的某个事件的概率，最终将不等式的关系转化为事件的包含关系。

问题1 (伯努利随机变量)

令 $p, q > 0$ 满足 $p + q = 1$，证明对于任意正整数 $m, n$，有：

$$(1 - p^{n})^{m} + (1 - q^{m})^{n} \geq 1$$

证明 (概率方法)

由于 $p + q = 1$，可以考虑构造一个随机变量 $\xi$，其取值有两种，不妨设为 $0, 1$，概率分别为 $p, q$。

这样构造的话，$1 - p^{n}$ 是 $n$ 个独立随机变量中，至少有一个取 $1$ 的概率。将 $n$ 个独立随机变量的取值视为 1 组试验，$(1 - p^{n})^{m}$ 就是 $m$ 组试验的结果均为至少有 1 个取 $1$ 的概率。

类似地，$1 - q^{m}$ 是 $m$ 个独立随机变量中，至少有一个取 $0$ 的概率。将 $m$ 个独立随机变量的取值视为 1 组试验，$(1 - q^{m})^{n}$ 就是 $n$ 组试验的结果均为至少有 1 个取 $0$ 的概率。

$1 - (1 - q^{m})^{n}$ 就是 $n$ 组试验中，存在某一组试验的结果全都取 1 的概率。构造下面两个事件：

• A：m 组试验，每组试验有 n 个独立随机变量，每组试验结果均至少有一个随机变量取 1。
• B：n 组试验，每组试验有 m 个独立随机变量，存在某一组试验的结果是所有随机变量均取 1。

由于两个事件均涉及到 $mn$ 个独立随机变量，只是排列方式不一样。因此整体考虑 $mn$ 个独立随机变量，然后研究上述 A，B 两个事件的包含关系。

将 $mn$ 个独立随机变量排列成 $m$ 行 $n$ 列，如下图：

其中每一行可以视为事件 A 中的每一组试验，共 m 组，每组 n 个独立随机变量；每一列可以视为事件 B 中的每一组试验，共 n 组，每组 m 个独立随机变量。

事件 A 相当于每一行都至少有 1 个 1；事件 B 相当于存在某一列的结果都是 1。

若事件 B 成立，如上图，即有一列全是 1，那么每一行自然就至少有 1 个 1。

也就是只要事件 B 成立，则事件 A 一定成立。但是事件 A 中每一行至少有的 1 个 1 不一定在同一列，还可能有别的排列方式。

因此事件 A 包含事件 B，因此 $P(A) > P(B)$，将概率代入，得：

$$(1 - p^{n})^{m} > 1 - (1 - q^{m})^{n}$$

$\Box$

问题2 (广义伯努利随机变量)

求证：

$$\sum\limits_{n=1}\limits^{N}\frac{nk^{n-1}}{\Gamma(n + k + 1)} < \frac{1}{\Gamma(k+1)}$$

证明 (概率方法)

原不等式等价于：

$$\sum\limits_{n=1}\limits^{N}\frac{nk^{n-1}\Gamma(k+1)}{\Gamma(n + k + 1)} < 1$$

进而等价于：

$$\sum\limits_{n=1}\limits^{N}\frac{nk^{n-1}}{(n+k)(n+k-1)\cdots(k+1)} < 1$$

构造广义伯努利模型。设 $E$ 为随机试验，其结果只有两个基本事件 $A$ 和 $\bar{A}$，独立重复地进行试验 $E$，设第 $n$ 次试验中 $A$ 出现的概率为 $P_{n} = \frac{n}{n+k}$，不出现的概率即为 $1 - P_{n} = \frac{k}{n+k}$。

记 $f_{n}$ 表示在第 $n$ 次试验中 $A$ 首次出现的概率，则有：

$$f_{n} = (1 - P_{1})(1 - P_{2})\cdots(1 - P_{n-1})P_{n}$$

于是：

$$\begin{align} \sum\limits_{n=1}\limits^{N}f_{n} &= \sum\limits_{n=1}\limits^{N}(1 - P_{1})(1 - P_{2})\cdots(1 - P_{n-1})P_{n} \\ &= \sum\limits_{n=1}\limits^{N}\frac{k}{1+k}\frac{k}{2+k}\cdots\frac{k}{n-1+k}\frac{n}{n+k} \\ &= \sum\limits_{n=1}\limits^{N}\frac{nk^{n-1}}{(n+k)(n+k-1)\cdots(k+1)} \end{align}$$

于是 $\sum\limits_{n=1}\limits^{N}f_{n}$ 正是原不等式的左边，其含义是 $N$ 次试验中，$A$ 在第 $n$ 次试验时首次出现时的概率之和，其中 $n$ 可以取 $1, 2, \cdots, N$。但这并不是所有的可能性，因为还有可能 $N$ 次试验中 $A$ 始终没出现过，这个概率为 $\prod\limits_{n=1}\limits^{N}(1 - P_{n})$。

因此：

$$\sum\limits_{n=1}\limits^{N}f_{n} = 1 - \prod\limits_{n=1}\limits^{N}(1 - P_{n}) < 1 \\$$

$\Box$

问题3 (将 $\sin x, x\in [0, \frac{\pi}{2}]$ 视为概率)

若 $x \in [0, \frac{\pi}{2}]$，求证：

$$\frac{\sqrt{2}\cos(x - \frac{\pi}{4})}{1 + \sin x\cos x} \leq 1$$

证明 (概率方法)

由于：

$$\begin{align} \sqrt{2}\cos(x - \frac{\pi}{4}) &= \sqrt{2}(\cos x\cos \frac{\pi}{4} + \sin x\sin \frac{\pi}{4}) \\ &= \sqrt{2}(\frac{\sqrt{2}}{2}\cos x + \frac{\sqrt{2}}{2}\sin x) \\ &= \sin x + \cos x \end{align}$$

于是我们要证的是 $\sin x + \cos x \leq 1 + \sin x\cos x$。

由于 $x \in [0, \frac{\pi}{2}]$，$\sin x, \cos x$ 均在 $[0, 1]$ 范围内，这样我们可以将 $\sin x$ 和 $\cos x$ 视为某个事件的概率。

设 A, B 为两个独立事件，事件 A 的概率为 $P(A) = \sin x$，事件 B 的概率为 $P(B) = \cos x$。

由于 A，B 相互独立，于是有 $P(AB) = P(A)P(B) = \sin x\cos x$。

另一方面，$P(A\cup B) = P(A) + P(B) - P(AB) = \sin x + \cos x - \sin x\cos x$。

于是 $\sin x + \cos x - \sin x\cos x$ 为事件 $A \cup B$ 的概率，其值当然在 $[0, 1]$ 范围内，因此 $\sin x + \cos x - \sin x\cos x \leq 1$ 自然成立。

$\Box$

问题4 (球盒模型)

设自然数 $m_{j} < n_{j}$，其中 $j = 1, 2, \cdots, k$，记 $A = \sum\limits_{j=1}\limits^{k}n_{j}, B = \sum\limits_{j=1}\limits^{k}m_{j}$，证明：

$$0 < \prod\limits_{j=1}\limits^{k}\binom{n_{j}}{m_{j}} \leq \binom{A}{B}$$

证明 (概率方法)

设一个盒子中有 $A = \sum\limits_{j=1}\limits^{k}n_{j}$ 个球，其中有 $n_{j}$ 个球标有号码 $j$，其中 $j=1,2,\cdots,k$。现在从中任取 $B = \sum\limits_{j=1}\limits^{k}m_{j}$ 个球。

则恰好取 $m_{1}$ 个 1 号球，$m_{2}$ 个 2 号球，$m_{k}$ 个 $k$ 号球的概率为 $\frac{\prod\limits_{j=1}\limits^{k}\binom{n_{j}}{m_{j}}}{\binom{A}{B}}$，其取值范围自然是在 $[0, 1]$ 内，于是原不等式成立。

$\Box$

问题5 (多个事件的交并补)

设 $0 \leq a, b, c, d \leq 1$，求证：

$$(a + b - ab)(c + d - cd) \geq ac + bd - abcd$$

证明 (概率方法)

由于 $a, b, c, d$ 的范围均为 $[0, 1]$，于是可以考虑视其为概率。

设事件 A, B, C, D 独立，概率分别为 a, b, c, d。

由于 $(A + B)(C + D) = AC + AD + BC + BD \supset AC + BD$，于是有：

$$P((A+B)(C+D)) \geq P(AC + BD)$$

又由 A, B, C, D 的独立性，有 $P((A+B)(C+D)) = P(A+B)P(C+D)$，于是有：

$$P(A+B)P(C+D) \geq P(AC + BD)$$

另一方面，由概率的加法公式：

$$P(A + B) = P(A) + P(B) - P(AB) = a + b - ab$$ $$P(C + D) = P(C) + P(D) - P(CD) = c + d - cd$$ $$P(AC + BD) = ac + bd - abcd$$

将以上三式代入，前面的不等式，得到：

$$(a + b - ab)(c + d - cd) \geq ac + bd - abcd$$

$\Box$

---