随机排序的复杂度下界：Yao's principle 介绍

基于比较的确定性排序算法在最坏输入下的比较次数下界是 $\Omega(n\lg n)$，但随机算法在最坏输入下的期望比较次数又如何呢？本文介绍 Yao’s principle，并用它分析随机排序算法的比较次数下界。

作者：silverxz
审核：phy东西

Introduction

  基于比较的确定性排序算法在最坏输入下的比较次数下界是 $\Omega(n\lg n)$，这个结果很著名，《算法导论》等教材和大部分算法课程都有讲述，读者应该清楚（本文默认读者初步学习过算法和概率论，但要求不高。本文遵循算法领域的惯例，lg 以 $2$ 为底）。

  但是，对于随机算法来说，它在最坏输入下的期望比较次数又如何呢？

  倘若读者完全没有了解过随机算法相关的知识，可能会觉得允许随机性也不会让算法神奇地变好。不过世界上的确存在一些神奇的随机算法。

  排序算法中的快速排序本身就是一个例子。普通的快速排序若按固定规则选择主元，其在最坏输入下的复杂度可以达到 $\Theta(n^2)$；随机选择主元则能在最坏输入下保持期望 $O(n\lg n)$ 的复杂度。当然，这个例子可能不够神奇，毕竟我们还有一堆其他的 $\Theta(n\lg n)$ 排序算法。一个更神奇的例子是 Freivalds 算法。它虽然与排序问题无关，但非常简洁巧妙，我们简单介绍一下。这一算法意在解决以下问题。

问题：给定三个 $n\times n$ 矩阵 $A,B,C$，判断 $AB$ 是否等于 $C$. 换言之，检验矩阵乘法的结果是否正确.

  最直接的做法当然就是直接把 $A$ 和 $B$ 乘起来，再去判断 $AB$ 是否等于 $C$. 这一方法的计算代价就是矩阵乘法的代价，朴素的做法是 $O(n^3)$. 实际上我们也很难想到比矩阵乘法更好的方法了，然而 Freivalds 给出了一个随机化方法，每个人第一次看到都会拍案叫绝。

引理（Freivalds 算法）

设 $r\in \{0, 1\}^n$ 是长度 $n$ 的 $01$ 随机向量，那么

• 若 $AB=C$，则 $ABr=Cr$ 恒成立；
• 若 $AB\neq C$，则 $\mathrm{Pr}_{r\in \{0, 1\}^n}[ABr=Cr]\leq 1/2$.

  为了缩短正文篇幅，我们把引理的证明放在附注(注1)。当然它也很简单啦。

  基于上述引理，只需独立随机选取 $k$ 个向量 $r_1, r_2, \dots, r_k \in \{0, 1\}^n$，由于矩阵与向量的乘法是平方级的，我们能够以 $O(kn^2)$ 的代价计算并比较每个 $ABr_i$ 是否等于 $Cr_i$（其中 $i=1,\dots,k$）。若有一个不相等，就说明 $AB\neq C$；若全都相等，算法直接断言 $AB=C$，发生误判（真实情形为 $AB\neq C$ 但所有 $ABr_i=Cr_i$ 使算法误判）的概率由引理可知不超过 $2^{-k}$. 当我们固定 $k$ 为常数时，这就是一个 $O(n^2)$ 的算法。

  要知道，目前最快的矩阵乘法算法离 $O(n^2)$ 的复杂度也还很远，而 Freivalds 用如此简单的算法就绕过了矩阵乘法……虽然付出了一点小小的错误率作为代价，但那完全可接受：大不了你就多重复几次嘛，指数降低的错误率很快就会降到比硬件错误、系统错误、或者机房爆炸发生的概率更低(注2)。

  这个例子会让你对随机算法的能力更有信心吗？事实上，有许多随机算法能以很简明的方式做到确定性算法不那么容易做到的事。与 Freivalds 算法类似的还有各种 Hash 算法及其扩展，比如你可能听说过的 Bloom filter (布隆过滤器)。它们本质上都是在用尽可能低的成本构造某种随机“指纹”，来尽可能可靠地完成识别、对比的任务。

  但注意，这里不是说随机算法真的比确定性算法有更好的复杂度。以 Freivalds 算法的例子而言，我们并不知道是否存在 $O(n^2)$ 的确定性矩阵乘法算法。理论上它确实可能存在，此时我们就能获得 $O(n^2)$ 的确定性算法来判定 $AB$ 是否等于 $C$，使随机算法和确定性算法打个平手。可即便这种算法真的存在，也一定极其复杂；而我们刚才看到的随机算法却非常简单，这才是它们神奇且厉害的地方。

  那么我们回过头来看排序问题。随机算法有可能神奇地突破确定性算法的下界，在最坏输入下的期望比较次数低于 $\Omega(n\lg n)$ 吗？好吧，这里就不卖关子了，答案仍然是：不能。为了解决这个问题，我们需要一些能够刻画随机算法性能下界的工具，告诉我们“即便是随机算法，也不可能创造比这更多的奇迹”。

Yao’s principle

  我们要介绍的工具叫做 Yao’s minimax principle，或简称为 Yao’s principle。它来自姚期智先生 1977 年的工作，是随机算法下界分析中最经典、最基本的工具，其中的核心思想是以博弈的观点看待算法与输入之间的关系。

  读者可能不知道什么是“博弈”。我们举一个你一定很熟悉的例子：石头剪刀布。设有集合 $\mathcal{A},\mathcal{X}$ 和它们上面的二元函数 $l$ 如下：

$\mathcal{A}=\mathcal{X}=\{\text{石头, 剪刀, 布}\}, l(a,x)=\{\text{win, lose, tie}\}$

  那么“石头剪刀布”的博弈，就是由对局双方——不妨设分别为 Alice 和 Bob——分别在集合 $\mathcal{A}$ 和 $\mathcal{X}$ 中选出一个元素，决一胜负。用博弈的语言说，$\mathcal{A}$ 中的元素是 Alice 的策略(注3)，而 $\mathcal{X}$ 中的元素是 Bob 的策略。双方选定策略后，函数 $l$ 就给出这一对策略下双方的收益或代价。

  那么这和算法问题有什么关系呢？就以我们考虑的排序问题为例，我们可以这样定义：令 $\mathcal{A}$ 为所有基于比较的确定性排序算法集合，令 $\mathcal{X}_n$ 为所有规模为 $n$ 的输入集合，令 $l(a,x)$ 表示算法 $a\in \mathcal{A}$ 对输入 $x\in \mathcal{X}_n$ 进行排序所需要的比较次数。此时还是 Alice 和 Bob 两个人博弈，你可以想象 Alice 是算法设计师，而 Bob 是算法攻击者：Alice 想挑选尽可能好的算法 $a$ 让比较次数 $l(a,\cdot)$ 尽可能小，而 Bob 想要挑选尽可能坏的输入 $x$ 让比较次数 $l(\cdot, x)$ 尽可能大。

  此时，针对某一算法 $a\in \mathcal{A}$ 的最坏情况分析，比如排序算法 $a\in \mathcal{A}$ 最坏情况下所需的比较次数，就是让 Bob 针对 $a$ 选一个最坏的输入 $x$ 进行攻击。这一最大比较次数可以表达为

$\max_{x\in \mathcal{X}_n} l(a, x)$

  而我们熟悉的下界 $\Omega(n\lg n)$ 在这种博弈的观点下就可以解释成不管 Alice 挑选怎样的算法 $a$，Bob 都能根据这一算法 $a$ 找出一个很坏的输入 $x$ 来攻击 Alice，使算法 $a$ 需要的比较次数 $l(a,x)>cn\lg n$. 请注意，这里有一个先后顺序：Alice 先选算法，而 Bob 可以在知道 Alice 的选择之后做出针对性的攻击。如果写成数学公式，就是存在常数 $c>0$ 使对于充分大的 $n$ 有

$\min_{a\in \mathcal{A}}\max_{x\in \mathcal{X}_n} l(a,x) > cn\lg n$

  上式左侧就是最优算法（在规模为 $n$ 的输入下）在最坏输入下所需的比较次数，请读者观察这个式子是如何表达了我们刚才说的“先后顺序”的。如果我们加上括号，写成

$\min_{a\in \mathcal{A}} \Big( \max_{x\in \mathcal{X}_n} \big(l(a,x)\big) \Big)$

  那么你会发现，对于 $\max_{x\in\mathcal{X}_n}$ 来说，它使用了外层下标中的 $a\in \mathcal{A}$，并且按照这个 $a$ 来最大化函数 $l(a, x)$. 这意味着 Bob 是在知道 $a$ 的前提下来最大化 $l(a, x)$ 的，也就体现了先后顺序。理解这一点很重要，因为后面会反复用到这种 $\min$ 和 $\max$ 交错的形式。

  以上都是在复述确定性算法的结果，其实只是把我们熟悉的事实换了种方式表述，相信读者花一点时间就可以看懂。

  我们刚才用博弈的观点看待确定性算法和输入之间的关系，接下来的关键是：随机算法呢？

  先想一想，什么是随机算法？它与确定性算法的区别是，我们可以生成一些随机数，再按照随机数的值决定算法的行为。

  如果我们把生成的随机数都固定住，那么这个随机算法就变成了一个确定性算法。比如说，如果程序用 C 语言中的 rand 来获得随机数，那么固定 srand 函数中的随机数种子就会让 rand 生成的随机数序列固定下来。这意味着，我们可以把随机算法视为一个在确定性算法上取值的随机变量。

  ——以防万一，如果读者觉得上面那句话有点难懂，我再解释一下：随机变量的取值不一定非得是一个数。如果我们在一副扑克牌里均匀随机地抽一张扑克牌，那这就是一个在这副扑克牌上取值的随机变量，服从扑克牌上的均匀分布。类似地，随机算法也只是在所有确定性算法构成的集合中抽了一个算法，因此它是一个在所有确定性算法上取值的随机变量。我们的确可以用更朴实的大白话说“随机算法就是在一堆确定性算法里随机选择了一个”，但由于之后不可避免地要用到一些概率论，包括这个随机变量，所以请读者理解它。

  用数学的语言重述：记 $\Delta(\mathcal{A})$ 为 $\mathcal{A}$ 上的所有概率分布构成的集合，因此其中的元素 $R\in \Delta(\mathcal{A})$ 就是一个概率分布，而随机算法就是服从某个分布 $R\in \Delta(\mathcal{A})$ 的随机变量 $A\sim R$ (注4)。

  回到 Alice 与 Bob 之间的算法攻防战，现在我们允许 Alice 选择一个随机算法。也就是说，Alice 可以不再只是傻傻地选一个固定的算法 $a\in \mathcal{A}$，让 Bob 针对 $a$ 的弱点进行攻击；Alice 可以选择 $\mathcal{A}$ 上的一个随机变量 $A$，代表一个随机算法，这样 Bob 想要攻击就会变得更困难。

  单单这么说，读者可能意识不到这有什么用。我们再回看石头剪刀布的例子。如果 Alice 只能选择确定性策略，那么 Bob 必胜。正如之前说过的，这里有一个先后顺序，相当于 Bob 可以看着 Alice 出完拳再决定他出什么，自然一定能赢。但如果 Alice 可以采用随机策略，以各 $1/3$ 的概率决定出石头剪刀还是布，那么 Bob 就无法针对了。

  这个例子想必可以让读者领会为什么随机算法可能具有优势。请注意，这里的先后顺序没有变，Bob 也仍然可以预先知道 Alice 的策略。但由于策略本身是随机的，哪怕 Bob 知道“Alice 会在石头剪刀布中等概率选择一个”这件事，他也没有任何办法。

  我们已经知道排序问题中最优确定性算法在最坏情况下的比较次数可以表达为

$\min_{a\in \mathcal{A}}\max_{x\in \mathcal{X}_n} l(a,x)$

  那么最优随机算法在最坏输入下的期望比较次数是什么呢？由于 Alice 可以随机选择算法，因此 $\min$ 下面就不再是 $a\in \mathcal{A}$ 了，而是

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}_n} \mathbb{E}_{A\sim R}[l(A, x)]$

  意思是，Alice 可以给出一个随机策略 $A$ 服从分布 $R\in \Delta(\mathcal{A})$，然后 Bob 针对这个随机策略选择一个 $x\in \mathcal{X}_n$ 来攻击，计算其期望代价 $\mathbb{E}_{A\sim R}[l(A, x)]$.

  可以看出，这个式子很难计算分析。我们根本不知道有哪些确定性算法，更别提上面的分布 $R$ 了。然而，Yao’s principle 可以把随机性从 Alice 一侧转换到 Bob 一侧，那会让问题变得简单很多，因为 $\mathcal{X}_n$ 是什么我们非常清楚，无非就是 $1$ 到 $n$ 的所有排列。接下来我们就给出定理的陈述。

定理（Yao’s minimax principle）

设有两个有限集合 $\mathcal{A}, \mathcal{X}$ 和函数 $l:\mathcal{A}\times \mathcal{X}\to \mathbb{R}$，则对于任意 $\mathcal{A}$ 上随机变量 $A$ 和任意 $\mathcal{X}$ 上随机变量 $X$，都有

$\max_{x\in\mathcal{X}} \mathbb{E}_{A}[l(A,x)] \geq \min_{a\in \mathcal{A}} \mathbb{E}_{X}[l(a,X)]$

证明

证明很简单，所以我们证完再去讲这个定理到底是什么意思。

$\begin{aligned} \max_{x\in\mathcal{X}} \mathbb{E}_{A}[l(A,x)] &\geq \mathbb{E}_X \mathbb{E}_A[l(A,X)]\\ &=\mathbb{E}_A\mathbb{E}_X[l(A,X)]\\ &\geq \min_{a\in \mathcal{A}} \mathbb{E}_{X}[l(a,X)] \end{aligned}$

证明的第一行和最后一行是用了一个很平凡的不等式：

$\max_{z\in \mathcal{Z}} f(z) \geq \mathbb{E}_{Z} [f(Z)] \geq \min_{z\in \mathcal{Z}} f(z)$

这很好理解，最大值大于等于平均值大于等于最小值，对吧？通常来说，这么平凡的不等式难以推出什么有用的结果，而这里的灵魂就在于第二步交换了期望的顺序。之所以能交换期望的顺序，是因为定理的陈述中说了 $\mathcal{A},\mathcal{X}$ 是有限集合，因此这里的期望其实是两重有限求和，可以换序。这样也就证完了。

还要提到的是，上述命题其实并不要求 $\mathcal{A}, \mathcal{X}$ 两个集合都有限。我们只是在第二步期望交换那里用了有限性，但这个交换其实只需要其中一个集合有限就可以了（有限求和和积分是可以交换顺序的）。我们在后面证明排序问题下界的时候用到的其实是这个“一个集合无限，另一个有限”的版本，但单独写一个定理比较繁琐，我们就不另写了(注5)。

对于两个集合都无限的情形，只需要加上 $l\geq 0$ 等条件，利用 Tonelli 定理也可以让积分交换。总之，Yao’s principle 是可以扩展的，但我们不会用到这种扩展版本，没有数学背景的读者可以不必关注。

  证明相当简单，但关键不在于证明本身，而在于这个定理究竟表达了什么意思。虽然定理陈述中 $\mathcal{A},\mathcal{X}$ 只是两个抽象的集合，没有具体意义，$l$ 也是没有具体意义的抽象函数，但为了理解它，我们还是先赋予它典型的意义：这仍然是算法设计师 Alice 和算法攻击者 Bob 两人之间的博弈。$\mathcal{A}$ 是 Alice 可以选择的所有确定性算法，$\mathcal{X}$ 是 Bob 可以选择的所有具体输入，而 $l(a,x)$ 是算法 $a$ 在输入 $x$ 下所需要付出的代价（如总运行时间、比较次数等等）。Alice 想要选择尽可能好的算法来对抗 Bob 给出的输入，使得代价 $l$ 尽量低；Bob 则想要选择尽可能坏的输入来攻击 Alice 给出的算法，使代价 $l$ 尽量高。

  那么，如前所述，$\mathcal{A}$ 上的随机变量 $A$ 就是 Alice 的一个随机算法，而式子左侧的 $\max_{x\in\mathcal{X}} \mathbb{E}_{A}[l(A,x)]$ 就是 Bob 针对随机算法 $A$ 能达成的最好的攻击效果：他会选择让期望代价 $\mathbb{E}_{A}[l(A,x)]$ 尽可能大的 $x$. 与之相对，$\mathcal{X}$ 上的随机变量 $X$ 则是一个随机输入，Bob 的输入是随机的，然后让 Alice 针对这一随机输入寻找一个最优的确定性算法，这一算法需要付出的期望代价就是式子右侧的 $\min_{a\in \mathcal{A}} \mathbb{E}_{X}[l(a,X)]$。

  明白了不等式两侧各自的意思，我们就知道了不等式本身的意思：如果你想分析一个随机算法 $A$ 在最坏输入下的期望代价（式子左侧）下界，你可以改成去分析一个随机输入 $X$ 下的最好确定性算法的期望代价（式子右侧），后者就构成了你想要的那个下界。或者举一个更具体的例子，如果你想证明 $\max_{x\in\mathcal{X}} \mathbb{E}_{A}[l(A,x)] > n\lg n$，那么这个不等式告诉你，你可以证明 $\min_{a\in \mathcal{A}} \mathbb{E}_{X}[l(a,X)] > n\lg n$，然后根据不等式自然就有

$\max_{x\in\mathcal{X}} \mathbb{E}_{A}[l(A,x)] \geq \min_{a\in \mathcal{A}} \mathbb{E}_{X}[l(a,X)] > n\lg n$

  跟上的读者可能会有一个问题：这种方法不是只分析了一个随机算法 $A$ 吗？可是我们一开始想要做的是分析所有随机算法的下界，给出所有随机排序算法比较次数的下界，而不是只针对某个随机算法。看起来两者差别很大。但是请注意，定理中的 $A$ 和 $X$ 是任取的，因此我们立刻得到以下推论

推论

设有两个有限集合 $\mathcal{A}, \mathcal{X}$ 和函数 $l:\mathcal{A}\times \mathcal{X}\to \mathbb{R}$，则

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \max_{D\in \Delta(\mathcal{X})}\min_{a\in\mathcal{A}} \mathbb{E}_{X\sim D}[l(a,X)]$

特别地，对于某个随机输入，即 $\mathcal{X}$ 上随机变量 $X$，有

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \min_{a\in\mathcal{A}} \mathbb{E}_{X}[l(a,X)]$

证明

我们已经说过，定理中的 $A, X$ 任取，因此

$\forall R\in \Delta(\mathcal{A}),\quad \max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \min_{a\in\mathcal{A}} \mathbb{E}_{X}[l(a,X)]$

既然对于每一个 $R$ 这个不等式都成立，那么哪怕是使不等式左侧最小的 $R$ 也仍然使不等式成立，因此

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \min_{a\in\mathcal{A}} \mathbb{E}_{X}[l(a,X)]$

对 $X\sim D$ 做一次同样的论证即可得到

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \max_{D\in \Delta(\mathcal{X})}\min_{a\in\mathcal{A}} \mathbb{E}_{X\sim D}[l(a,X)]$

  这样，我们立刻就把针对某一具体随机算法 $A$ 的结果提升成了对全体随机算法的结果了。这一结果提供了分析随机算法下界的一个范式：如果我们想证明所有随机算法都很难做（$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)]$ 大于某个值），只需要证明对于某个随机输入 $X$，所有确定性算法也都很难做（$\min_{a\in\mathcal{A}} \mathbb{E}_{X}[l(a,X)]$大于某个值）即可。这也就是我们说过的，把随机性从算法上转移到输入上。

  有的读者可能会问：这是一个不等式，而且它的证明非常简单，那么这样给出的下界真的有用吗？会不会给出的界非常松、非常平凡？

  如果读者的确有这个疑惑，那我不得不夸赞一下，这是个好问题。而这也正是这一结果的强大之处，在$\mathcal{A},\mathcal{X}$有限的条件下，我们其实可以证明

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] = \max_{D\in \Delta(\mathcal{X})}\min_{a\in\mathcal{A}} \mathbb{E}_{X\sim D}[l(a,X)]$

  这里其实可以取等号。这意味着，如果你确实能构造出使右侧取到 $\max$ 的那个随机变量 $X$，或者说构造出对应的分布 $D$，那么你通过这种方式给出的下界就是紧的，不会因为随机性的转移有任何损失！事实上，如何构造出一个足够难的 $X$ 也正是 Yao’s principle 在应用时的难点，构造的越难，得到的下界也就越紧。Yao’s principle 并不是一个可以无脑套用的定理，它常常作为整个证明的最后一步出现。

  这一等式的证明直接来自于博弈论中的 von Neumann minimax theorem，由于其证明与我们要讲的内容无关，所以我们就不证明这件事了；在无限情形下它不一定成立。读者也可以从这里看出 Yao’s minimax principle 名字的来源。

基于比较的随机排序算法的比较次数下界

  现在我们可以解决最开始的问题了。先复习一下最基本的结果，因为我们要用到相同的决策树模型。但我们不会讲的很细，只是为了唤起读者可能淡忘了的记忆。

定理

基于比较的确定性排序算法的比较次数下界是 $\Omega(n\lg n)$.

证明

所谓“基于比较”，是指算法不能直接利用元素的具体数值，只能通过询问形如 $x_i < x_j\ ?$ 的问题来获得元素之间的大小关系。注意，在排序问题中我们通常假定元素之间不相等。

现在考虑一个确定性排序算法。由于算法是确定性的，所以它的比较策略也完全固定，下一次比较哪两个元素完全取决于之前得到的所有比较结果。

于是，我们可以把算法的整个运行过程展开成一棵二叉树，称为决策树。树的结点代表算法运行到这里会做哪个比较。比如说，树的根节点可能是 $x_i < x_j \ ?$，代表算法最开始会比较 $x_i, x_j$. 如果根节点的左儿子是 $x_k < x_l\ ?$，就代表若算法得到 $x_i < x_j$ 的结果，那么它下一步会比较 $x_k, x_l$; 而如果根节点的右儿子是 $x_m < x_n\ ?$，就代表若算法得到 $x_i > x_j$ 的结果，那么它下一步会比较 $x_m, x_n$. 由于算法是确定性的，整棵树也就因算法的行为唯一确定。

如此下去，算法根据每一次的比较结果选择进入当前结点的左儿子还是右儿子，不断向下移动。当算法停止时，它也就不会再比较，到达了决策树的叶子，此时它会输出一个确定的排列。这意味着，决策树的叶子对应一个排列。只要算法是正确的，那么不同顺序的输入就一定不会落到同一个叶子，否则算法对它们的输出一定有一个是错的。总共有 $n!$ 种顺序，因此决策树至少有 $n!$ 个叶子。

设决策树高度为 $h$. 高度为 $h$ 的二叉树至多有 $2^h$ 个叶子，因此

$2^h \geq n!$

根据 Stirling 公式，

$h \geq \lg (n!) = n\lg n- O(n) = \Omega(n\lg n)$

因此对于最深的叶子，其对应的排列至少需要该算法进行 $\Omega(n\lg n)$ 次比较才能完成排序。

  复习到此结束。我们现在要处理的是随机算法，看起来无法再套用决策树模型。决策树模型成立的一个重要原因是，算法的比较策略是固定的，只要之前得到的所有比较结果都相同，那么下一步会比较哪两个元素就完全确定，因此才能展开出一棵二叉树作为决策树。但是随机算法完全打破了这一点，它的下一步比较策略完全可以是随机的。

  而这正是 Yao’s principle 起作用的地方，它把随机性从算法移到输入上去，这样算法就又变成确定性的了，我们又可以使用决策树模型了。已经铺垫了太多，我们直接开始证明。

定理

基于比较的随机排序算法在最坏输入下的期望比较次数下界是 $\Omega(n\lg n)$.

证明

回顾 Yao’s principle，我们要找一个随机输入分布 $D$，让每个确定性算法在它上面都很难做。我们曾提到，许多时候构造 $D$ 才是困难的地方。但是在这个问题下，我们恰好有一个最自然的选择，相信读者也能想到：均匀分布。因为，在排序问题中，不同的元素、不同的排列完全是平权的，我们没有理由厚此薄彼，所以以均匀分布作为构造的尝试是最自然的。

设 $\mathcal{A}=${ 所有基于比较的确定性排序算法 }, $\mathcal{X}=${ 1 到 n 的所有排列 }, $l(a,x)=$算法 a 排序输入 x 需要的比较次数，令 $D$ 为 $\mathcal{X}$ 上的均匀分布。为了应用 Yao’s principle，我们要给出 $\min_{a\in A}\mathbb{E}_{X\sim D}[l(a, X)]$ 的下界，也就是均匀分布下确定性算法期望要比较多少次。这正是决策树的领域。

对于一个确定性算法 $a\in\mathcal{A}$，我们仍然考虑它的决策树。$n!$ 种不同的输入会落到决策树的 $n!$ 个不同叶子上，设这 $n!$ 个叶子的深度分别为 $d_1,d_2,\dots,d_{n!}$，那么算法 $a$ 在这一随机输入下的期望比较次数就是所有深度的平均值，即

$\mathbb{E}_{X\sim D}[l(a, X)]=\frac{1}{n!}\sum_{k=1}^{n!} d_k$

为了估计式子的右端，我们只需要一点点数学技巧。首先，我们有以下的 Kraft 不等式

$\sum_{k=1}^{n!} 2^{-d_k} \leq 1$

别被它吓到，它的直观证明很简单。首先想象一棵满二叉树（每个结点要么有两个儿子，要么没有儿子），我们给所有叶子按它的深度 $d$ 分配一个值 $2^{-d}$，接着就像合成大西瓜一样不断合并两个互为兄弟的叶子，把两个值为 $2^{-d}$ 的兄弟叶子删掉，并给它的父亲（变成了新的叶子）分配一个值 $2^{-d+1}$. 重复这个过程不断合并，最后只剩下一个光秃秃的值为 $1$ 的根节点。这就说明对于满二叉树而言，所有叶子的深度满足 $\sum 2^{-d_i} = 1$. 而对于那些不一定满的二叉树，某些结点只有一个儿子，你可以把这样的边缩掉（合并它和它唯一的儿子）让它变成满二叉树，而这条边只是让叶子的深度增加了，所以式子左端只会更小，因此 $\sum_{k=1}^{n!} 2^{-d_k} \leq 1$.

接下来是最后的一点点数学技巧。Jensen 不等式说，若 $\mathbb{R}$ 上函数 $f(x)$ 是凸函数，正实数 $a_1,\dots,a_m>0$满足 $\sum_{i=1}^m a_i = 1$，那么对于 $x_1,\dots,x_m\in \mathbb{R}$ 有

$f\left(\sum_{i=1}^m a_i x_i\right) \leq \sum_{i=1}^m a_if(x_i)$

我们知道 $f(x)=2^{-x}$ 是凸函数。因此有

$2^{-\frac{1}{n!}\sum_{k=1}^{n!} d_k}\leq \frac{1}{n!}\sum_{k=1}^{n!}2^{-d_k} \leq \frac{1}{n!} \Longrightarrow \mathbb{E}_{X\sim D}[l(a, X)]=\frac{1}{n!}\sum_{k=1}^{n!} d_k \geq \lg n!$

这里 $1/n!$ 就是不等式中的 $a_i$，而 $d_k$ 就是不等式中的 $x_i$. 由于上述结果对任意的算法 $a$ 都成立，因此

$\min_{a\in \mathcal{A}}\mathbb{E}_{X\sim D}[l(a, X)]\geq \lg n! = \Omega(n\lg n)$

根据 Yao’s principle，也就得到

$\min_{R\in \Delta(\mathcal{A})}\max_{x\in \mathcal{X}} \mathbb{E}_{A\sim R}[l(A, x)] \geq \min_{a\in\mathcal{A}} \mathbb{E}_{X\sim D}[l(a,X)] =\Omega(n\lg n)$

即，对任何随机算法 $A$ 都存在一个足够坏的输入 $x$，让期望比较次数也达到 $n\lg n$ 级别。

允许犯错的随机排序算法

  好了，到此为止似乎我们已经圆满解决了问题，虽然得到的是一个略有遗憾的结果——没有奇迹发生，随机算法也无法突破 $\Omega(n\lg n)$ 的极限。

  但是细心的读者很可能一直有一个疑惑。我们最开始举的例子，那个 Freivalds 算法，它不是可以允许有一个小的错误率吗？很大程度上，这也是它能有优异表现的原因。然而我们刚才的证明表面上涵盖了所有随机算法，实则不然：我们只涵盖了所有那些不会犯错的随机算法！因为，随机算法 $A$ 是 $\mathcal{A}$ 上的随机变量，而$\mathcal{A}$ 是由那些不会犯错的正确确定性算法组成的，所以无论怎样随机，$A$ 都不会犯错。有没有一种可能，如果我们允许一定的错误率，随机算法其实是可以神奇地变好的？这一节就作为 encore，把这个问题也一并解决。这会比之前的内容稍微复杂一些，但难度其实也没什么实质提升。

  刚才的分析表明，我们之所以没有涵盖到允许犯错的随机算法，是因为集合 $\mathcal{A}$ 就不包含那些错误的确定性算法。所以首先我们应该扩大集合 $\mathcal{A}$，让它包含那些错误的确定性算法。

  但问题在于，这样的确定性算法很有可能错的离谱。举一个很简单且很蠢的例子，考虑这样一个随机算法：以 $\varepsilon$ 的概率原样输出，以 $1-\varepsilon$ 的概率调用一个正确的确定性排序算法，比如归并排序。这当然就是一个允许犯错的随机排序算法，以不超过 $\varepsilon$ 的概率犯错。为了涵盖这样的随机算法，我们就得把“按原样输出”这种几乎总是犯错的算法纳入 $\mathcal{A}$ 当中。可这是一个根本不需要比较的算法，如果允许这样的算法存在于 $\mathcal{A}$ 中，那么我们就会得到

$\min_{a\in \mathcal{A}}\mathbb{E}_{X\sim D}[l(a, X)]=0$

  这样的无意义的结果。

  这背后的原因是，我们希望随机算法的错误率是可控的，并且排序次数也应该和错误率相关。然而，一个错误率可控的随机算法，其对应的确定性算法也可以是错的离谱的东西，但我们计算代价的函数 $l$ 却只能反映比较次数，无法反映错误率。

  Yao’s principle 的框架只允许一个函数 $l$，我们好像没法搞出两个函数分别考虑比较次数和错误率，这怎么办？熟悉优化方法的同学可能已经想到了一个经典套路：拉格朗日松弛。这种技术、技巧允许我们把想要约束优化的两个东西塞到一块。

  我们令 $\mathcal{A}$ 为所有确定性算法的集合，无论它是不是正确的排序算法；$\mathcal{X}$ 不变，仍然是所有规模为 $n$ 的输入，也就是 $n!$ 种排列；然后重新定义 $l$ 为一个带有超参数 $\lambda > 0$ 的函数

$l(a, x) = c(a, x) + \lambda e(a, x)$

  其中 $c(a, x)$ 是我们原本的 $l(a,x)$，也就是算法 $a$ 在输入 $x$ 运行需要的比较次数，而 $e(a, x)$ 定义为

$e(a, x)= \begin{cases} 1, & \text{排序结果错误}, \\ 0, & \text{排序结果正确}. \end{cases}$

  也就是说我们把比较次数 $c$ 和犯错 $e$ 用一个系数 $\lambda$ 组合起来塞到函数 $l$ 里去了。我们所谓的至多 $\varepsilon$ 错误率的随机算法 $A$，指的就是满足以下条件的算法

$\forall x\in\mathcal{X}, \ \mathrm{Pr}_{A}[e(A,x)=1]\leq \varepsilon$

  针对这样定义的 $\mathcal{A},\mathcal{X}, l$，我们重新应用 Yao’s principle 的分析方式，看看会发生什么。

  仍然选择 $\mathcal{X}$ 上的均匀分布 $D$，考虑某个确定性算法 $a \in\mathcal{A}$ 在该随机输入上的表现如何。设算法 $a$ 在全部 $N=n!$ 种输入中，可以正确排序的比例为 $q$，即可以正确排序其中 $qN$ 种。

  允许 $q=0$ 会带来一些麻烦，所以我们先想办法把这种完全错误的算法剔除掉。幸运的是，我们有“永远固定输出一种排列”这种不需要任何比较但仍然能恰好蒙对一种情况的算法作为更优的选择，所以 $q=0$ 的情形确实可以剔除，不妨设 $q>0$.

  仿照之前的决策树论证，为了正确排序这 $qN$ 种不同输入，这 $qN$ 种输入必须落到决策树不同的叶子上，因此决策树至少要有 $qN$ 个不同的叶子。设这 $qN$ 个不同叶子的深度为 $d_1,\dots,d_{qN}$，由于 Kraft 不等式仍然成立，可以仿照之前的证明，利用 Jensen 不等式给出其平均深度

$\frac 1 {qN}\sum_{k=1}^{qN} d_k \geq \lg (qN)$

  细节留给读者验证。由此可以得到

$\begin{aligned} \mathbb{E}_{X\sim D}[l(a, X)] &= \frac 1 N \sum_{x\in X} l(a, x)\\ &= \frac 1 N \left( \sum_{x\text{可以被正确排序}} l(a, x)+ \sum_{x\text{不能被正确排序}} l(a, x) \right)\\ &\geq \frac 1 N \left( \sum_{x\text{可以被正确排序}} c(a, x)+ \sum_{x\text{不能被正确排序}} \lambda e(a, x) \right)\\ &= \frac 1 N \left( \sum_{k=1}^{qN}d_k + \sum_{x\text{不能被正确排序}} \lambda \right)\\ &\geq \frac 1 N \big( qN\lg (qN) + \lambda(N-qN) \big)\\ &= q\lg(qN)+\lambda(1-q) \end{aligned}$

  注意，我们通过这种估计手段得到的界只和 $q$ 有关，完全不在乎算法的其他特征。这变相简化了算法集 $\mathcal{A}$，如果我们使用这个界，就不再需要真的枚举每个 $a\in\mathcal{A}$，而是只需要枚举算法的正确比例 $q=1/N,2/N,\dots,1$. 如此，应用 Yao’s principle，对于任意随机算法 $A$ 有

$\max_{x\in \mathcal{X}} \mathbb{E}_{A}[l(A, x)] \geq \min_{a\in\mathcal{A}} \mathbb{E}_{X\sim D}[l(a,X)] \geq \min_{q=\frac 1 N, \dots, 1} (q\lg(qN)+\lambda(1-q))$

  要注意式子左侧并不是我们想要的，因为这里的 $l$ 不再是比较次数，而是比较次数与错误代价的二合一。设 $A$ 是一个错误率至多为 $\varepsilon$ 的随机算法，即

$\forall x\in\mathcal{X},\ \mathrm{Pr}[e(A,x)=1] \leq \varepsilon$

  那么由 $l$ 的定义有

$\max_{x\in \mathcal{X}} \mathbb{E}_{A}[l(A, x)] \leq \max_{x\in \mathcal{X}} \mathbb{E}_{A}[c(A, x)] + \lambda\varepsilon$

  移项并代入 Yao’s principle 得到的不等式就得到

$\max_{x\in \mathcal{X}}\mathbb{E}_{A}[c(A, x)] \geq \min_{q=\frac 1 N, \dots, 1} \big(q\lg(qN)+\lambda(1-\varepsilon-q)\big)$

  这就是我们想要的形式了，它说明一个错误率至多 $\varepsilon$ 的随机算法 $A$ 在最坏情况下的期望比较次数至少为上式右侧的那个量。

  这当然还不是最终结果，因为这个式子还带着 $\lambda$。这个结果对所有 $\lambda > 0$ 都有效，因此我们要找到一个 $\lambda$ 使不等式右侧的值尽可能大，从而使不等式尽可能紧。在其他领域应用这一方法时，典型的方法自然是对 $\lambda$ 求导以找到右侧式子的最大值；但我们这里稍微有点麻烦，因为这个式子带个 $\min$，不好直接求导。那咋办呢？几何的观点可以把它看作是一个上凸壳，但也得费心说明细节。考虑到读者可能也不知道什么是凸壳，我们就最粗暴地，硬算。

  首先，$q$ 的取值是离散的 $1/N, 2/N, \dots, 1$，这太不方便了。由于对于给定的 $\lambda$ 显然有

$\min_{q=\frac 1 N, \dots, 1} \big(q\lg(qN)+\lambda(1-\varepsilon-q)\big) \geq \min_{0<q\leq 1} \big(q\lg(qN)+\lambda(1-\varepsilon-q)\big)$

  因此我们不妨处理连续的情形，得到的仍然是一个下界。设函数

$f(\lambda) = \min_{0<q\leq 1} \big( q\lg(qN)+\lambda (1-\varepsilon-q) \big)$

  我们分析内层的最小值，看它最小值到底是什么。对于固定的 $\lambda >0$，设函数

$g(q) = q\lg (qN) + \lambda(1-\varepsilon-q)$

  求导（请记得我们$\lg$的底数是$2$）得到

$g'(q)=\lg (qN) + \lg e -\lambda$

  因此最小值在导数零点 $q=\frac{1}{eN}2^\lambda$ 处取到。由于 $f(\lambda)$ 中 $\min$ 的 $q$ 有取值范围 $(0, 1]$，我们得做个小的分类讨论：当 $0 < \lambda \leq \lg (eN)$ 时，最小值点 $q=\frac{1}{eN}2^\lambda \leq 1$ 可以取到；当 $\lambda > \lg (eN)$ 时，$q<1$ 时导数 $g'(q)<0$，故最小值点在 $q=1$ 处取到。将两种情况回代到 $f(\lambda)$ 中，得到

$f(\lambda)= \begin{cases} -\frac{\lg e}{eN}2^\lambda + \lambda(1-\varepsilon), & 0 < \lambda \leq \lg (eN) , \\ \lg N - \lambda \varepsilon, & \lambda > \lg (eN). \end{cases}$

  这样就把外层的 $\min$ 消掉了。我们是想求 $f$ 的最大值。直接计算可验证分段处 $f(\lg (eN))=(1-\varepsilon)\lg N - \varepsilon \lg e$ 连续，由于 $\lambda > \lg(eN)$ 时 $f$ 单调递减，我们求最大值就可以直接把 $\lambda > \lg (eN)$ 的部分丢掉，只看 $0 < \lambda \leq \lg(eN)$ 就够了。

  对 $f$ 求导

$f'(\lambda) = -\frac{1}{eN}2^{\lambda} + (1-\varepsilon)$

  其最大值在导数零点 $\lambda = \lg(eN(1-\varepsilon)) \leq \lg(eN)$ 处取到。这里同样有个边界问题，若 $\lambda > 0$ 则好办，将它代入 $q=\frac{1}{eN}2^\lambda$ 得到 $q=1-\varepsilon$，并计算得到此时 $f(\lambda)=(1-\varepsilon)\lg((1-\varepsilon)N)$; 若 $\lambda < 0$，$(1-\varepsilon)\lg((1-\varepsilon)N)$ 此时小于 $0$，仍然可以作为一个平凡的比较次数下界（比较次数总是非负的），因此仍取这个界不影响正确性。

  回顾我们得到的结果，现在终于可以写出

$\max_{x\in \mathcal{X}}\mathbb{E}_{A}[c(A, x)] \geq (1-\varepsilon)\lg((1-\varepsilon)N)$

  综上所述，我们证明了如下定理。

定理

若某个基于比较的随机排序算法 $A$ 的错误率至多为 $\varepsilon < 1$，则对于任意正整数 $n$，存在一组规模为 $n$ 的输入，使 $A$ 在这组输入下的期望比较次数至少为 $(1-\varepsilon)\lg ((1-\varepsilon)n!)$.

  对于常数错误率来说，这也是一个 $\Omega(n\lg n)$ 级别的量。这也就说明，允许犯错的随机排序算法也不能突破这一下界。

  此外有趣的是，想要达到这个 $1-\varepsilon$ 的因子其实非常简单。只需考虑我们之前提过的那个很蠢的算法：以 $\varepsilon$ 的概率胡乱排序，以 $1-\varepsilon$ 的概率调用确定性算法排序，你就获得了一个期望比较次数为 $(1-\varepsilon)\lg (n!)$ 级别的随机算法。这也说明，随机算法确实难以在排序方面有额外的斩获。到此，我们以排序问题为例，利用 Yao’s principle 对随机算法做出的分析就告一段落了。

结语

  这篇文章大致介绍了 Yao’s principle 这一工具，并用它分析了排序问题中的随机算法。读完的读者可能会觉得，我们好像完全没有用到什么高深的数学，也没有什么巧妙的算法设计，核心定理的证明更是极为简单甚至平凡。这可能会让一部分读者失望。

  然而，许多重要的结果之所以重要，本就不在于其高深晦涩、精巧玄妙，而在于其视角独到、醍醐灌顶。Yao’s principle 的核心不在于其仅有两行的证明，而在于早先将算法问题看作博弈问题的洞察。有了这样的洞察，搭建起相应的结构，得到这样的定理自然是水到渠成的事，整个理论也将简洁优美。

  如正文所述，这一结果归功于姚期智先生。姚期智先生 1946 年生，2000 年获图灵奖。作为本文选题的动机之一：今年的 12 月 24 日是姚期智先生的八十岁生日，愿他身体健康。

Remarks

  本节为附注，包括正文中省略的部分证明，以及对正文部分内容的补充。个别附注对读者的数学知识可能有比正文更高的要求，请按需阅读。

• 注 1. 我们证明正文中的引理。

证明

显然若 $AB=C$，则 $ABr=Cr$. 我们证明若 $AB\neq C$，则 $\mathrm{Pr}_{r\in \{0, 1\}^n}[ABr=Cr]\leq 1/2$.

若 $AB\neq C$，则 $D=AB-C$ 不是全$0$矩阵，必然存在某一元素非零。设这一元素$d_{i,j}$ 在 $i$ 行 $j$ 列。此时，若向量 $r$ 的第 $j$ 个元素从 $0$ 变成 $1$，那么 $ABr-Cr=Dr$ 的第 $i$ 个元素也将增加 $d_{i, j}\neq 0$ 的值；反之如果从 $1$ 变成 $0$，将减小 $d_{i,j}$. 因此，在固定 $r$ 其他位置不变时，第 $j$ 位为 $0$ 和为 $1$ 的两种情况至少有一种满足 $ABr\neq Cr$. 这就说明

$\mathrm{Pr}_{r\in \{0, 1\}^n}[ABr=Cr]\leq 1/2$

• 注 2. 这类运行时间有界但带有一个微小错误率的随机算法被称为 Monte Carlo 算法，它与 Monte Carlo 抽样法没有关系，只是都得名于拥有著名赌场的 Monte Carlo。如正文中所述，这一错误率可以通过重复算法来压低，并且错误率下降的速度是指数级的。
  与之相对，另一类不会犯错误但运行时间随机的随机算法称为 Las Vegas 算法，得名于赌城 Las Vegas。Las Vegas 算法给出的结果总是正确的。它的期望运行时间通常要求有界，但最坏运行时间则不一定，对于个别随机数序列可能运行很久很久：设想一个极蠢的排序算法，随机打乱数据，检查是否排好序，没有就再重复这一过程，打乱数据，检查……直到随机打乱后的数据恰好被排好序为止。这就是一个 Las Vegas 算法，如果它停机，那么数据肯定被排好序了；但是它也可以无限运行下去，永远不停机。

• 注 3. 严格来说，这里的策略在博弈中叫做纯策略，可以理解为是确定的策略；与之相对，后面那些随机的策略称为混合策略，如正文所述，混合策略是纯策略上的随机变量。

• 注 4. 随机算法可以被视为随机变量，但严格来说，一个随机变量未必是随机算法，因为其对应的分布可能是不可采样的。这里涉及到一些可计算性方面的小问题，类似的问题也会导致我们之后在讨论 Yao’s principle 给出的界是否足够紧时，那一讨论更多适用于那一博弈模型，离算法可能有一个小的 gap。这几乎不会真的导致什么问题，没有接触过的读者可以忽略，我们这里也不严加区分。

• 注 5. 严格来说，当集合变成无穷集合的时候，这里的最值不一定能取到，可能只能无限逼近。对于这种情况，数学早有妥善的处理方式，就是把表示最大最小值的 $\max,\min$ 换成表示上确界和下确界的 $\sup,\inf$. 但是考虑到这篇文章不预设数学背景，为了减轻理解新概念的负担，并且也考虑到这一差别在这里没有很大影响，正文中就牺牲一点严谨性，仍然使用 $\max,\min$（包括后面排序算法下界的证明中也是如此）。