2020 STEP II Q12 —— 巧用概率证明代数不等式
本篇的问题来自于 2020 STEP II 数学考试中的第12题，这个问题提供了一种巧用概率来证明一个复杂的代数不等式的思路。
STEP (Sixth Term Examination Paper) 是英国剑桥考试中心为本科申请者提供的数学专项考试，通常会是剑桥、帝国理工、伦敦大学、华威等名校的数学、计算机、工程等专业的录取要求之一。每年都会有一些非常精彩的考题，我在此挑选一些个人喜欢的考题作分享。
问题梗概
我们将证明如下结论：对于任意 \(n\) 个正数 \(x_i (i=1,2,\cdots,n)\)，有
\[\sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \leq \frac{n-1}{2n}\left( \sum_{i=1}^n x_i \right)^2\]原题及解答
设有一颗 \(n\) 面的不公正骰子，其掷出的点数可表示为随机变量 \(X\)。对于 \(i=1,2,\cdots,n\)，随机变量 \(X\) 遵从概率分布 \(P(X=i)=\frac{1}{n} + \epsilon_i\)，其中 \(\epsilon_i\) 不全都为零。
(1) 求将这颗骰子连续投掷两次得到相同点数的概率，并判断使用公正骰子还是不公正骰子更有可能在连续两次投掷中得到相同的点数。
(2) 利用前面的结论，证明对于任意 \(n\) 个正数 \(x_i (i=1,2,\cdots,n)\)，有
\[\sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \leq \frac{n-1}{2n}\left( \sum_{i=1}^n x_i \right)^2\](1)
对于不公正骰子，每次投掷得到任何点数的概率总和必须为一
\[\sum_i P(X=i) = \sum_i \left( \frac{1}{n} + \epsilon_i \right) = 1 \\ n\times\frac{1}{n} + \sum_i\epsilon_i=1 \\ \Rightarrow \sum_i \epsilon_i = 0\]连续投掷两次，得到相同点数的概率为：
\[\begin{aligned} P_\text{unfair}(X_1=X_2) &= \sum_i \left[P(X=i)\right]^2 \\ &=\sum_i \left( \frac{1}{n} + \epsilon_i \right)^2 \\ &= \sum_i \left( \frac{1}{n^2} + \frac{2\epsilon_i}{n} + \epsilon_i^2 \right) \\ &= n\times\frac{1}{n^2} + \frac{2}{n} \cancelto{0}{\sum_i \epsilon_i} + \sum_i \epsilon_i^2 \\ &= \frac{1}{n} + \sum_i \epsilon_i^2 \end{aligned}\]若使用公正骰子，则掷出任何点数的概率都是 \(P(X=i)=\frac{1}{n}\)，即每一项 \(\epsilon_i=0\)。因此用公正骰子相应连续投掷两次得到相同点数的概率为：
\[P_\text{fair}(X_1=X_2) = \frac{1}{n}\]不公正骰子有 \(\sum_i \epsilon_i^2 > 0\)，因此 \(P_\text{unfair}(X_1=X_2)> P_\text{fair}(X_1=X_2)\)，即使用不公正骰子更可能连续两次投出相同点数。
(2)
对于系列正数 \(x_i (i=1,2,\cdots,n)\)，记它们的总和为
\[A = \sum_i x_i\]引入归一化后的系列正数
\[p_i = \frac{x_i}{A} \quad(i=1,2,\cdots,n)\]显然每一项 \(p_i>0\)，并且 \(\sum_i p_i=1\)，因此我们可以将 \(p_i\) 视作一个 \(n\) 面的骰子掷出点数为 \(i\) 的相应概率。由于 \(x_i\) 为任意正数，因此 \(p_i\) 的取值尽可以不全相等，这枚骰子可以被当作不公正的骰子来对待。
现在考察 \(\displaystyle \sum_{i=2}^{n}\sum_{j=1}^{i-1}p_ip_j\)，这可以理解为连续作两次投掷，第一次投出的点数大于第二次投出的点数的概率。由于对称性质，第一次点数大于第二次点数的概率，应该等于第一次点数小于第二次点数的概率。而我们又可以利用两次投出点数相同的概率的结论，来估计两次投出点数不相同的概率。于是
\[\begin{aligned} \sum_{i=2}^{n}\sum_{j=1}^{i-1}p_ip_j &= \frac{1}{2}\left[1 - P(X_1=X_2)\right] \\ &= \frac{1}{2} \left[ 1- \left( \frac{1}{n} + \sum_i \epsilon_i^2 \right) \right] \\ &= \frac{n-1}{2n} - \frac{1}{2}\sum_i \epsilon_i^2 \\ &\leq \frac{n-1}{2n} \end{aligned}\]注意到 \(\sum_i p_i=1\)，上式可以写成
\[\sum_{i=2}^{n}\sum_{j=1}^{i-1}p_ip_j \leq \frac{n-1}{2n} \left( \sum_{i=1}^n p_i \right)^2\]上述不等式当且仅当所有 \(\epsilon_i=0\) 时取得等号，这对应于一枚公平骰子，即掷出任意点数的概率 \(p_i\) 都相等。
再把 \(x_i\) 的总和的平方乘到不等式的两边，由于 \(x_i=Ap_i\)，这样我们就得到
\[\sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \leq \frac{n-1}{2n}\left( \sum_{i=1}^n x_i \right)^2\]其中等号当且仅当所有 \(x_i\) 都相等成立。
一些讨论
其实，这个不等式完全可以通过常规的方式来证明。
我们不妨先看最简单的情形：取 \(n=2\)，从所需求证的不等式出发，我们有
\[\begin{aligned} & x_2x_1 \leq \frac{1}{4}(x_1+x_2)^2 \\ \Leftrightarrow \quad & 4x_1x_2 \leq x_1^2 + x_2^2+2x_1x_2\\ \Leftrightarrow \quad & x_1^2 + x_2^2 - 2x_1x_2 \geq 0\\ \Leftrightarrow \quad & (x_2-x_1)^2 \geq 0 \end{aligned}\]显然结论成立。原不等式看来完全也可以用常规的代数方法来证明。
对于更一般的情况，从原不等式出发，我们也可以最终凑出一堆完全平方项来：
\[\begin{aligned} & \sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \leq \frac{n-1}{2n}\left( \sum_{i=1}^n x_i \right)^2 \\ \Leftrightarrow \quad & 2n \sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \leq (n-1)\left( \sum_{i=1}^n x_i^2 + 2 \sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j\right) \\ \Leftrightarrow \quad & (n-1)\sum_{i=1}^n x_i^2 - 2\sum_{i=2}^{n}\sum_{j=1}^{i-1}x_ix_j \geq 0 \\ \Leftrightarrow \quad & \sum_{i=2}^{n}\sum_{j=1}^{i-1} (x_i-x_j)^2 \geq 0 \\ \end{aligned}\]以上最后一步可以通过将 \(\displaystyle \sum_{i=2}^{n}\sum_{j=1}^{i-1} (x_i-x_j)^2\) 中的每一项都打开，然后收集所有的平方项 \(x_i^2\) 和交叉项 \(x_ix_j\)，就可以倒推回倒数第二步。
很显然最后一步得到的不等式对于任意正数 \(x_i\) 成立，因此原不等式也成立。并且我们也能够很容易看出，等号必须在所有 \((x_i-x_j)^2=0\) 时，即所有 \(x_i\) 都相等时成立。