为何证明特例?
现有随机复杂度笔记使用 Hoeffding 不等式,但没有在该处证明。这里用对数矩估计及 Markov 不等式证明其多数表决论证所需的 Bernoulli 指示变量特例;我们不证明任意 值随机变量的一般定理。
固定一个输入。令 为独立 Bernoulli 随机变量,其中 且 。 可以不同,也可等于零或一。令 、。在应用中, 是“随机算法第 次独立运行出错”的指示变量,所以 是出错运行的次数。我们要对每个 证明 。
控制单个中心化矩
证明建立在单个 Bernoulli 变量的一个函数之上。
定义 6.1.1
(Bernoulli 变量的中心化对数矩)
设 为 Bernoulli 变量,。其矩母函数为
对每个实数 都为正。中心化对数矩定义为
右边的等式成立,是因为 是常数,可以提到期望之外。下一个命题说明 至多二次增长,而且与 无关。
引理 6.1.2
(Bernoulli 矩界)
对每个 及每个 ,
证明
(对有界二阶导数积分两次)
令 。对 求导得 ;再求导并利用 ,得
又 ,。由 得 ,所以处处有 。从 积分到 得 ,再积分一次得 。
过程中没有除以 或 ,所以 和 也包括在内。
从矩到尾概率
定理 6.1.3
(独立 Bernoulli 和的指数尾界)
设 为独立 Bernoulli 变量,,并令 、。对每个 ,
证明
(Markov、分解、最优化)
对任意 ,把 Markov 不等式用于非负随机变量 ,得到
独立性使期望分解成各中心化矩的乘积,再对每个因子使用矩界:
因此对每个 都有 。指数是 的凸二次式,在 时最小;因 且 ,此值为正。代入得 。
证明透视
每个假设在哪里发挥作用
证明有三步,每步恰好用到一个假设。Markov 不等式需要非负变量,所以我们先取指数,而不直接处理 ; 使事件 变成事件 。乘积步骤是唯一用到独立性的地方。其后矩界逐个因子使用,所以 不必相等,而 的变量只贡献因子 。最后取 ,是在线性收益 与二次代价 之间取舍;它是唯一的自由参数,而之所以可以这样取,是因为引理对所有 成立。若没有独立性,单项的矩界无法说明乘积的期望。
乘积这一步并非技术细节。下面的例子放弃独立性,说明所述的界随即失效。
反例模式
完全相关的运行使上界失效
断言:无论是否独立,任意 Bernoulli 变量都满足 。取 及 ,其中 是同一个公平比特。每个 都是 的 Bernoulli 变量,故 ,但 以各 的概率取 或 。取 ,事件 恰是 ,概率为 。断言所给的界为 ,所以断言不成立。独立性使 成为乘积;这里 ,比各边缘矩的乘积 更大。
多数表决放大与精确核对
推论 6.1.4
(独立运行的多数表决)
设 为奇数。假设在固定输入上的 次运行相互独立,且各自出错的概率至多为 。则多数答案错误的概率至多为 。
证明
(把门槛平移 )
令 指示第 次运行出错,则 。多数错误要求 ,所以 。取 用尾界,,所以多数错误的概率至多为 。
这是上界,一般不是精确错误概率。下面的例题分开不等式的两种用途:先在小得可以精确计算的情形核对,再用它决定重复次数。
例题 6.1.5
(三个公平比特的精确核对)
令 为独立公平比特,所以 、,取 。事件 恰是 ,概率为 。上界为 。确实 :界有效但不紧。这个例子核对的是尾界本身,并不是满足“错误率至多 ”的多数表决例子。
例题 6.1.6
(要运行多少次才能使错误至多 ?)
由多数表决推论, 次( 为奇数)独立运行、各自错误率至多 ,则多数错误的概率至多为 。要使 ,即 ,所以 。满足此式的最小奇数是 。核对: 时 ,保证不适用; 时 。另外, 时上界为 。这个界给出的是充分的次数,不一定是最少的次数。
例题 6.1.7
(退化与不等的概率)
令 、, 为公平比特,三者独立,所以 、、。则 。取 :事件 即 ,概率为 ;上界为 ,有效。各中心化矩为 、、,所以两个确定性变量没有贡献。定理仍除以完整的 ,因此这里远非尖锐。证明并不要求 。
常见错误
(把指数式当成错误概率)
是在“每次运行出错概率至多 ”这个较弱假设下得到的上界,并不是多数错误的概率。在三个公平比特的核对中,精确概率是 ,而界是 。这类量应当作为保证来报告,不能当作实际错误的估计。
常见错误
(把单边界用于双边事件)
定理只界定 。对事件 ,要再对 用定理(它们是独立 Bernoulli 变量,以 取代 ),然后用并集界,所得为 。同样, 是绝对偏差:偏差 即 ,得 。
习题与解答
快速检查
(若 , 是多少?)
先计算 。
解答 · 答案
时 ,所以 ,且 。因此对所有 都有 ,显然满足 。所以退化情形无须另行处理。
快速检查
(为何证明中可取 ?)
检查对 的正负要求。
解答 · 答案
假设 和 使 为正,这正是 Markov 步骤及矩界所需的条件。它也使二次指数 最小,因为导数 在此点为零。
快速检查
(独立性在证明的哪一步使用?)
找出把一个期望变成多个期望的步骤。
解答 · 答案
只在把 分解为各 的乘积时使用。Markov 不等式、单个变量的矩界以及对 的最优化都没有用到它。
快速检查
(在三个公平比特的核对中,界 等于精确概率吗?)
与 比较。
解答 · 答案
不等于。精确概率为 ,而 。指数式只是有效的上界,并非等式。