【理论学习】minmax——从冯诺依曼到姚期智

发表于 2023-04-07 更新于 2023-08-07 分类于理论学习

本文目前仅对几个定理做记录，不详细解释，以后有机会再填坑。

Max-min Inequality

Minmax Theorem —— John von Neumann

令及为紧凸集。如果是一个连续的凹凸函数，即：

对于固定的是凹的，且

对于固定的是凸的。

则

这个二元函数的图像可以视为一个马鞍面，在鞍点处取得等号。

Yao’s Principle —— 姚期智

令为一个实值的资源消耗的度量的期望，为输入的分布，为输入的集合，为随机算法，为确定性算法，

则

也即：最好的随机算法在它最差的输入上的开销等于最差的输入分布在最好的确定性算法上的开销。

可以看到，Yao’s Principle大概是（事实上也是）Minmax Theorem的一个特例。

这个定理有一个直接的推论，

这也是Yao’s Principle较常用到的形式。

这个推论的直接证明如下（用更清楚的期望的形式写出）：

令，，我们有：

在经典的排序问题中，我们首先考虑确定算法的部分。

“最差的输入分布”是什么？比方说，所有的输入都是1234……这样子的递增输入（非递增输入的概率为0），那这显然是一个特别好的输入分布，因为它自己已经排好序了，在这种分布下的最佳算法就是什么也不做，开销为0。那么，直觉上，最差的输入分布应该是随机的均匀的输入之类的东西，防止先前这种非常容易利用的性质出现，此时性能最好的确定性算法的开销期望就是”最差的输入分布在最好的确定性算法上的开销“。（注意，cost是期望，那么这里的期望就是因为输入分布带来的期望）

再考虑随机算法的部分。

“最好的随机算法”是什么？比方说，完全确定也是一种随机（给某种行为分配100%的概率），那么就可以构造出一个特定的输入（注意，cost是期望，那么这里的期望就是因为随机算法的inner coin flip带来的期望，而不是输入带来的，这里的输入类似competitive ratio分析法，是特化以得到最差表现的输入），使得它表现得特别差。那么，直觉上，最好的随机算法应该需要一些”变幻莫测“的行为，使得competitive的对手构造不出什么一定特别差的输入。