一个微分不等式，概率方法的威力

摘要: 概率方法证明微分不等式一例

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

---

我们大学以及考研的时候都学过微分中值定理。书上给出的形式是 $f(b) - f(a) = f’(\xi)(b - a)$，其中 $\xi$ 只知道与 $a, b, f$ 有关，但不知道具体值。

但其实要表达微分中值定理的意思不一定需要具体的 $\xi$，只需要知道 $f’$ 的下确界 $m = \inf \{f’(x) : x\in(a, b)\}$ 和上确界 $M = \sup \{f’(x) : x\in (a, b)\}$。即可得到：

$$m(b - a) \leq f(b) - f(a) \leq M(b - a)$$

也就是说，微分中值定理的实质是由以上不等式揭示出来的，其中 $m$，$M$ 是关于 $f’(x)$ 的上下确界。像这种关于 $f’$ 的不等式称其为微分不等式。

前面我们介绍了概率方法，并且解决了一些代数不等式，本文我们通过概率方法，解决一个微分不等式。从中我们可以看到通过巧妙构造随机变量，把不等式的项凑成期望方差等数字特征，然后再根据期望方差等数字特征本身满足的不等式，自然证明原不等式的思路。难点依然是构造随机变量。

本题在使用上述概率方法的过程中用到了数学期望满足的 Cauchy-Schwarz 不等式，这个不等式不是那么显然，我们首先看一下该不等式。

数学期望的 Holder 不等式

设 $E[|\xi|^{p}] < \infty$，$E[|\eta|^{q}] < \infty$，$1 < p < \infty$，$\frac{1}{p} + \frac{1}{q} = 1$，则：

$$E[|\xi\eta|] \leq (E[|\xi|^{p}])^{\frac{1}{p}}(E[|\eta|^{q}])^{\frac{1}{q}}$$

证明

Young 不等式

设 $p, q > 1$, $\frac{1}{p} + \frac{1}{q} = 1$，则有：

$$|ab| \leq \frac{1}{p}|a|^{p} + \frac{1}{q}|b|^{q}$$

当且仅当 $|a|^{p} = |b|^{q}$ 时等号成立。

在 Young 不等式 $|ab| \leq \frac{1}{p}|a|^{p} + \frac{1}{q}|b|^{q}$ 中，将 $a, b$ 视为两个随机变量：令 $a = \xi(E[|\xi|^{p}])^{-\frac{1}{p}}$，$b = \eta(E[|\eta|^{q}])^{-\frac{1}{q}}$。然后在 Young 不等式两边取期望，有：

$$\begin{align} E[|ab|] \leq E[\frac{1}{p}|a|^{p} + \frac{1}{q}|b|^{q}] &= E[\frac{1}{p}|\xi(E[|\xi|^{p}])^{-\frac{1}{p}}|^{p} + \frac{1}{q}|\eta(E[|\eta|^{q}])^{-\frac{1}{q}}|^{q}] \\ &= E[\frac{1}{p}|\xi|^{p}(E[|\xi|^{p}])^{-1} + \frac{1}{q}|\eta|^{q}(E[|\eta|^{q}]])^{-1} \\ &= \frac{1}{p} + \frac{1}{q} \\ &= 1 \end{align}$$

将 $a = \xi(E[|\xi|^{p}])^{-\frac{1}{p}}$，$b = \eta(E[|\eta|^{q}])^{-\frac{1}{q}}$ 代入 $E[|ab|] \leq 1$，有：

$$E[|\xi(E[|\xi|^{p}])^{-\frac{1}{p}}\eta(E[|\eta|^{q}])^{-\frac{1}{q}}|] \leq 1$$

移项后得：

$$E[|\xi\eta|] \leq (E[|\xi|^{p}])^{\frac{1}{p}}(E[|\eta|^{q}])^{\frac{1}{q}}$$

$\Box$

Cauchy-Schwarz 不等式

在数学期望的 Holder 不等式中，取 $p = q = 2$，得到Cauchy-Schwarz 不等式：

$$E[\xi\eta] \leq |E[\xi\eta]| \leq E[|\xi\eta|] \leq (E[|\xi|^{2}])^{\frac{1}{2}}(E[|\eta|^{2}])^{\frac{1}{2}} = (E[\xi^{2}])^{\frac{1}{2}}(E[\eta^{2}])^{\frac{1}{2}}$$

在上面的 $E[\xi\eta] \leq (E[\xi^{2}])^{\frac{1}{2}}(E[\eta^{2}])^{\frac{1}{2}}$ 中对 $\xi, \eta$ 没有要求，那么令 $\xi = \xi - E[\xi]$，$\eta = \eta - E[\eta]$，上式自然也成立，于是有：

$$E[(\xi - E[\xi])(\eta - E[\eta])] \leq (E[(\xi - E[\xi])^{2}])^{\frac{1}{2}}(E[(\eta - E[\eta])^{2}])^{\frac{1}{2}}$$

上式左边涉及到协方差 $cov(\xi, \eta)$ 的定义，右边涉及到方差 $D[\xi], D[\eta]$ 的定义，代入后得到柯西不等式的以下变形：

$$cov(\xi, \eta) \leq (D[\xi])^{\frac{1}{2}}(D[\eta])^{\frac{1}{2}}$$

下面的问题用概率方法解决的过程中，要用到以上不等式。

问题

设 $f(x) = \sum\limits_{k=0}\limits^{\infty}\binom{n}{k}a_{k}x^{k}(1 - x)^{n-k}$，其中 $0 \leq a_{k} \leq 1, 0 < x < 1$，则：

$$[f'(x)]^{2} \leq \frac{nf(x)[1-f(x)]}{x(1-x)}$$

证明 (概率方法)

由于这里 $0 < x < 1$，那么 $\binom{n}{k}x^{k}(1 - x)^{n-k}$ 就很像是二项分布随机变量 $\xi$ 的概率质量函数：

$$p_{k} = P(\xi = k) = \binom{n}{k}x^{k}(1 - x)^{n-k}, \quad\quad 0\leq k \leq n$$

即 $\xi \sim B(n, x)$，其均值、方差为 $E[\xi] = nx$，$D[\xi] = nx(1 - x)$。

原不等式中还有一个 $a_{k}$，将 $k$ 视为随机变量 $\xi$ 的取值，那么 $a_{k}$ 就可以视为关于 $\xi$ 的函数 $a(\xi)$ 当 $\xi = k$ 时的取值。

对于离散型随机变量 $\xi$，以及随机变量函数 $a(\xi)$，由期望的定义有：

$$E[a(\xi)] = \sum\limits_{k=0}\limits^{\infty}a(k)p_{k}$$

因此：

$$f(x) = \sum\limits_{k=0}\limits^{\infty}a_{k}\binom{n}{k}x^{k}(1 - x)^{n-k} = \sum\limits_{k=0}\limits^{\infty}a(k)p_{k} = E[a(\xi)]$$

$f(x)$ 的导数如下：

$$\begin{align} f'(x) &= \sum\limits_{k=0}\limits^{\infty}\binom{n}{k}a_{k}[kx^{k-1}(1-x)^{n-k} - x^{k}(n-k)(1 - x)^{n-k-1}] \\ &= \sum\limits_{k=0}\limits^{\infty}\binom{n}{k}a_{k}x^{k-1}(1-x)^{n-k-1}[k(1-x) - (n-k)x] \\ &= \sum\limits_{k=0}\limits^{\infty}\binom{n}{k}a_{k}x^{k-1}(1-x)^{n-k-1}(k-nx) \\ &= \sum\limits_{k=0}\limits^{\infty}\binom{n}{k}a_{k}x^{k}(1-x)^{n-k}\frac{k-nx}{x(1-x)} \\ \end{align}$$

这样上式中 $p_{k} = \binom{n}{k}a_{k}(1-x)^{n-k}$ 这一项没变，只是多了 $k-nx$ 这一与 $k$ 有关的项，相当于 $f(x)$ 中的 $a_{k}$ 变成了 $a_{k}(k - nx)$。因此 $a_{k}(k-nx)$ 整体可以视为一个新的随机变量 $b(\xi) = a(\xi)(\xi - nx)$ 当 $\xi = k$ 时的取值。

这样 $f’(x)$ 即可凑成新的随机变量 $b(\xi)$ 的期望的形式：

$$f'(x) = \frac{\sum\limits_{k=0}\limits^{\infty}b(k)p_{k}}{x(1-x)} = \frac{E[(\xi - nx)a(\xi)]}{x(1-x)}$$

由于 $E[\xi] = nx$，因此 $E[\xi - nx] = 0$，因此对于任意实数 $t$，有：

$$E[(\xi - nx)a(\xi)] = E[(\xi - nx)(a(\xi) - t)]$$

令 $t = f(x) = E[a(\xi)]$，上式自然也成立。于是：

$$E[(\xi - nx)a(\xi)] = E[(\xi - E[\xi])(a(\xi) - E[a(\xi)])] \\$$

上式正是 $\xi$ 与 $a(\xi)$ 的协方差的定义 $cov(\xi, a(\xi))$，因此：

$$E[(\xi - nx)a(\xi)] = cov(\xi, a(\xi)) \\$$

下面要用到概率论中数学期望满足的柯西不等式，也就是前面介绍过的以下不等式：

$$cov(\xi, \eta) \leq (D[\xi])^{\frac{1}{2}}(D[\eta])^{\frac{1}{2}}$$

令 $\eta = a(\xi)$ 代入以上不等式，得：

$$E[(\xi - nx)a(\xi)] = cov(\xi, a(\xi)) \leq (D[\xi])^{\frac{1}{2}}(D[a(\xi)])^{\frac{1}{2}}$$

将 $D[\xi] = nx(1-x)$ 代入，两边平方，得：

$$(E[(\xi - nx)a(\xi)])^{2} \leq nx(1-x)D[a(\xi)]$$

上式左边为 $[f’(x)]^{2}x^{2}(1-x)^{2}$，因此有：

$$[f'(x)]^{2} \leq \frac{n}{x(1-x)}D[a(\xi)]$$

因此要证明原不等式，还剩下最后一步，即证 $D[a(\xi)] \leq f(x)[1 - f(x)]$，这就要用到 $0 \leq a_{k} \leq 1$ 的条件了。

由于 $0 \leq a_{k} \leq 1$，于是有 $a(\xi)^{2} \leq a(\xi)$，于是：

$$D[a(\xi)] = E[a(\xi)^{2}] - (E[a(\xi)])^{2} \leq E[a(\xi)] - (E[a(\xi)])^{2}$$

将 $f(x) = E[a(\xi)]$ 代入，得到：

$$D[a(\xi)] \leq f(x)[1 - f(x)]$$

$\Box$

总结

对于关于函数 $f$ 的微分不等式，如果 $f$ 可以与离散型随机变量的概率质量函数或连续型随机变量的概率密度函数找到关系，就可以考虑概率方法。

构造随机变量之后，可能还需要凑更复杂的随机变量，使得原不等式的项可以凑成某个随机变量的期望、方差等数字特征。然后用期望、方差等数字特征本身满足的不等式，来证明原不等式。

本题中我们将原不等式左边凑成了某两个随机变量的协方差，右边凑成了这两个随机变量的方差，然后用协方差与方差本身满足的不等式，自然证明了原不等式。

之前我们用概率方法解决的问题中，在构造随机变量后，都是把项解释为概率，然后通过事件的包含关系证明原不等式；这里是把项解释为期望方差等数字特征，然后通过期望方差本身满足的不等式证明原不等式，这也是概率方法的一个常见套路，尤其是涉及和式或积分的不等式。

---