动机
当独立的任务被均匀地分配到各个服务器时,平均负载可能很小,而最繁忙的服务器却接收到很多任务。决定最坏响应时间或内存需求的,往往是最大负载,而不是平均负载。
我们研究将 n n n 个独立的球均匀地放入 n n n 个箱子的情形。并集界(union bound)可以证明极大的负载出现的概率很小。要说明适度大的负载也很可能出现,则需要统计过载箱子的个数并控制其方差。这两种论证在 log n / log log n \log n/\log\log n log n / log log n 这一数量级上会合。
定义
设 n ≥ 2 n\ge2 n ≥ 2 。n n n 个带标号的球各自独立地均匀选择 n n n 个箱子之一。设 X i X_i X i 为第 i i i 个箱子中的球数,M n = max i X i M_n=\max\limits_iX_i M n = i max X i 。所有对数均为自然对数。这里“以高概率”的意思是:所述的失败概率在 n → ∞ n\to\infty n → ∞ 时趋于零。
定理
对每个整数 k ≥ 1 k\ge1 k ≥ 1 ,
Pr ( M n ≥ k ) ≤ n ( e k ) k . \Pr(M_n\ge k)\le n\left(\frac e k\right)^k. Pr ( M n ≥ k ) ≤ n ( k e ) k . 因此,当 k = ⌈ 6 log n / log log n ⌉ k=\lceil6\log n/\log\log n\rceil k = ⌈ 6 log n / log log n ⌉ 且 n n n 充分大时,该概率至多为 n − 2 n^{-2} n − 2 。
当 k = ⌊ log n / ( 4 log log n ) ⌋ k=\lfloor\log n/(4\log\log n)\rfloor k = ⌊ log n / ( 4 log log n )⌋ 且 n n n 充分大时,
Pr ( M n ≥ k ) ≥ 1 − 4 n − 3 / 4 . \Pr(M_n\ge k)\ge1-4n^{-3/4}. Pr ( M n ≥ k ) ≥ 1 − 4 n − 3/4 . 两个估计合起来,得到 M n = Θ ( log n / log log n ) M_n=\Theta(\log n/\log\log n) M n = Θ ( log n / log log n ) 以高概率成立;所列出的常数只是便于计算的界,并非最优常数。
k k k 的渐近取法仅在 log log n > 0 \log\log n>0 log log n > 0 且 k ≥ 1 k\ge1 k ≥ 1 时使用,这对充分大的 n n n 成立。第一个定理中的有限不等式对每个 n ≥ 2 n\ge2 n ≥ 2 和 k ≥ 1 k\ge1 k ≥ 1 都成立,不过右端可能超过 1 1 1 ,此时该界是平凡的。
证明
由见证子集得到上界
固定一个箱子。若它至少接收 k k k 个球,则存在由 k k k 个带标号的球组成的集合,其中的球全都选择了这个箱子。一个给定的集合全部选择该箱子的概率为 n − k n^{-k} n − k 。由并集界,
Pr ( X i ≥ k ) ≤ ( n k ) n − k ≤ ( e / k ) k . \Pr(X_i\ge k)\le\binom nk n^{-k}\le(e/k)^k. Pr ( X i ≥ k ) ≤ ( k n ) n − k ≤ ( e / k ) k . 当 k > n k>n k > n 时,左端和二项式系数均为零,故不等式仍成立。当 k ≤ n k\le n k ≤ n 时,标准估计 ( n k ) ≤ ( e n / k ) k \binom nk\le(en/k)^k ( k n ) ≤ ( e n / k ) k 给出第二个不等式。再对全部 n n n 个箱子作一次并集界,就得到有限形式的上界。独立性只用于所指定的那组球;不同箱子的负载事件之间是否独立并不需要。
令 L = log n L=\log n L = log n ,取 k = ⌈ 6 L / log L ⌉ k=\lceil6L/\log L\rceil k = ⌈ 6 L / log L ⌉ 。当 L L L 充分大时,log k − 1 ≥ 1 2 log L \log k-1\ge\tfrac12\log L log k − 1 ≥ 2 1 log L 。因此
k ( log k − 1 ) ≥ 3 L , n ( e / k ) k ≤ e L − 3 L = n − 2 . k(\log k-1)\ge3L,\qquad n(e/k)^k\le e^{L-3L}=n^{-2}. k ( log k − 1 ) ≥ 3 L , n ( e / k ) k ≤ e L − 3 L = n − 2 . 选取常数 6 6 6 是为了让计算简单。更精细的分析可以改进它,但要确定这一数量级并不需要。
证明透视
过载的箱子有一个小的见证 各假设用在哪里:独立性只用来说明固定的 k k k 个球全部选中同一个箱子的概率为 n − k n^{-k} n − k ;不同箱子之间的独立性从不需要。关键一步是把事件“这个箱子的负载至少为 k k k ”放大为可以计数的事件“某个 k k k 元球子集全部选中这个箱子”。估计 ( n k ) ≤ ( e n / k ) k \binom nk\le(en/k)^k ( k n ) ≤ ( e n / k ) k 吸收了计数因子,对箱子的并集界再贡献一个因子 n n n 。论证之所以闭合,是因为在所取的尺度上 k ( log k − 1 ) k(\log k-1) k ( log k − 1 ) 比 log n \log n log n 大出一个常数倍,使 n ( e / k ) k n(e/k)^k n ( e / k ) k 成为 n n n 的负幂。若把见证概率相加后当作精确的尾概率,就会重复计算含有多个见证的放法。
对上界的解读
组合因子数的是带标号的子集,而不是球的有序列表。若某个箱子恰好接收 k k k 个球,则恰有一个见证子集;若接收更多,则可能有许多个。在并集界中,这种重复计数是无害的。但若把各见证的概率相加并称之为精确的负载概率,则是错误的,因为在同一种放置方式中可能同时出现多个见证。
不等式 ( n k ) ≤ ( e n / k ) k \binom nk\le(en/k)^k ( k n ) ≤ ( e n / k ) k 可由 ( n k ) ≤ n k / k ! \binom nk\le n^k/k! ( k n ) ≤ n k / k ! 与 k ! ≥ ( k / e ) k k!\ge(k/e)^k k ! ≥ ( k / e ) k 得到。对后者,可比较 log ( k ! ) = ∑ j = 1 k log j \log(k!)=\sum\limits_{j=1}^{k}\log j log ( k !) = j = 1 ∑ k log j 与 ∫ 1 k log x d x = k log k − k + 1 \int_1^k\log x\,dx=k\log k-k+1 ∫ 1 k log x d x = k log k − k + 1 。和不小于积分,由此得到阶乘的所述下界。这些估计是有意取得初等的,不使用任何正态近似。
为什么阈值要取成含 log n / log log n \log n/\log\log n log n / log log n 的形式?上界取对数后为 log n − k ( log k − 1 ) \log n-k(\log k-1) log n − k ( log k − 1 ) 。若 k k k 是 log n / log log n \log n/\log\log n log n / log log n 的一个足够大的常数倍,则 log k \log k log k 与 log log n \log\log n log log n 同阶,负项压过 log n \log n log n 。上述证明把这一启发式想法写成对充分大的 n n n 成立的明确不等式。对较小的输入,可以改用有限形式的界或直接计算,而不用渐近阈值。
上尾界即使大于 1 1 1 也仍然正确,但在那种范围内不提供信息。把右端换成它与 1 1 1 的较小者总是允许的。当 k k k 很小时,“某个箱子的负载至少为 k k k ”这一事件可能几乎必然发生,不应期望这种计数论证给出小于 1 1 1 的有用上界。
统计大负载的箱子
对于下界,令 Z = ∑ i = 1 n 1 { X i ≥ k } Z=\sum\limits_{i=1}^n\mathbf 1_{\{X_i\ge k\}} Z = i = 1 ∑ n 1 { X i ≥ k } 。则 M n ≥ k M_n\ge k M n ≥ k 当且仅当 Z > 0 Z>0 Z > 0 。对固定的一个箱子,X i ∼ Bin ( n , 1 / n ) X_i\sim\operatorname{Bin}(n,1/n) X i ∼ Bin ( n , 1/ n ) 。当 k ≤ n / 2 k\le n/2 k ≤ n /2 时,
Pr ( X i ≥ k ) ≥ Pr ( X i = k ) = ( n k ) n − k ( 1 − 1 / n ) n − k ≥ 1 4 ( 2 k ) k . \Pr(X_i\ge k)\ge\Pr(X_i=k)=\binom nk n^{-k}(1-1/n)^{n-k}
\ge\frac1{4(2k)^k}. Pr ( X i ≥ k ) ≥ Pr ( X i = k ) = ( k n ) n − k ( 1 − 1/ n ) n − k ≥ 4 ( 2 k ) k 1 . 事实上,( n k ) ≥ ( n / 2 ) k / k ! \binom nk\ge(n/2)^k/k! ( k n ) ≥ ( n /2 ) k / k ! ,k ! ≤ k k k!\le k^k k ! ≤ k k ,且当 n ≥ 2 n\ge2 n ≥ 2 时 ( 1 − 1 / n ) n ≥ 1 / 4 (1-1/n)^n\ge1/4 ( 1 − 1/ n ) n ≥ 1/4 。因此 E [ Z ] ≥ n / [ 4 ( 2 k ) k ] \mathbb E[Z]\ge n/[4(2k)^k] E [ Z ] ≥ n / [ 4 ( 2 k ) k ] 。
取 k = ⌊ L / ( 4 log L ) ⌋ k=\lfloor L/(4\log L)\rfloor k = ⌊ L / ( 4 log L )⌋ ,当 n n n 充分大时,有 1 ≤ k ≤ n / 2 1\le k\le n/2 1 ≤ k ≤ n /2 且 2 k ≤ L 2k\le L 2 k ≤ L 。于是 k log ( 2 k ) ≤ L / 4 k\log(2k)\le L/4 k log ( 2 k ) ≤ L /4 ,从而
E [ Z ] ≥ 1 4 n 3 / 4 . \mathbb E[Z]\ge\tfrac14 n^{3/4}. E [ Z ] ≥ 4 1 n 3/4 . 仅有较大的均值,并不能证明 Z > 0 Z>0 Z > 0 以高概率成立。接下来我们证明各过载指示变量的两两协方差非正,从而得到足够小的方差。
两两协方差为负
证明
(两两协方差为负与切比雪夫(Chebyshev)不等式)
对不同的箱子 i , j i,j i , j ,以 X i = a X_i=a X i = a 为条件。其余 n − a n-a n − a 个球独立地、均匀地落入其他 n − 1 n-1 n − 1 个箱子,故
X j ∣ X i = a ∼ Bin ( n − a , 1 / ( n − 1 ) ) . X_j\mid X_i=a\sim\operatorname{Bin}(n-a,1/(n-1)). X j ∣ X i = a ∼ Bin ( n − a , 1/ ( n − 1 )) . 条件概率 g ( a ) = Pr ( X j ≥ k ∣ X i = a ) g(a)=\Pr(X_j\ge k\mid X_i=a) g ( a ) = Pr ( X j ≥ k ∣ X i = a ) 关于 a a a 是不增的:试验次数越少,二项计数可以耦合为试验次数较多时成功次数的一个子集。指示函数 f ( a ) = 1 { a ≥ k } f(a)=\mathbf 1_{\{a\ge k\}} f ( a ) = 1 { a ≥ k } 是不减的。
若 A , A ′ A,A' A , A ′ 是某个随机变量的两个独立副本,则
2 Cov ( f ( A ) , g ( A ) ) = E [ ( f ( A ) − f ( A ′ ) ) ( g ( A ) − g ( A ′ ) ) ] ≤ 0. 2\operatorname{Cov}(f(A),g(A))=\mathbb E[(f(A)-f(A'))(g(A)-g(A'))]\le0. 2 Cov ( f ( A ) , g ( A )) = E [( f ( A ) − f ( A ′ )) ( g ( A ) − g ( A ′ ))] ≤ 0. 取 A = X i A=X_i A = X i 应用这一恒等式,可知 X i ≥ k X_i\ge k X i ≥ k 与 X j ≥ k X_j\ge k X j ≥ k 的指示变量的协方差非正。每个指示变量的方差至多等于其均值,所以
Var ( Z ) ≤ E [ Z ] . \operatorname{Var}(Z)\le\mathbb E[Z]. Var ( Z ) ≤ E [ Z ] . 切比雪夫不等式给出
Pr ( Z = 0 ) ≤ Var ( Z ) ( E Z ) 2 ≤ 1 E Z ≤ 4 n − 3 / 4 . \Pr(Z=0)\le\frac{\operatorname{Var}(Z)}{(\mathbb E Z)^2}\le\frac1{\mathbb E Z}\le4n^{-3/4}. Pr ( Z = 0 ) ≤ ( E Z ) 2 Var ( Z ) ≤ E Z 1 ≤ 4 n − 3/4 . 这就证明了下界。我们并没有假设各箱子的负载或过载指示变量相互独立;协方差的符号是由条件分布证明出来的。
反例模式
各箱子的负载并不独立 在两个球、两个箱子的情形,总有 X 1 + X 2 = 2 X_1+X_2=2 X 1 + X 2 = 2 。若 X 1 = 2 X_1=2 X 1 = 2 ,则 X 2 = 0 X_2=0 X 2 = 0 。把两个负载当作相互独立,就会忽略这一约束。下界的证明改用条件单调性的论证。
理解下界的估计
二项分布的计算把“某箱子恰好 有 k k k 个球”这一事件当作“至少有 k k k 个球”的子事件。其概率包含一个因子,表示其余 n − k n-k n − k 个球都避开该箱子。在所选的阈值处,k k k 的增长比 n n n 慢得多,所以要求恰好 k k k 个球,仍然留下足够大的见证数的期望。
证明透视
为什么下界需要二阶矩 目标只是让某个箱子的负载达到 k k k 。一阶矩给出 E Z ≥ 1 4 n 3 / 4 \mathbb E Z\ge\tfrac14n^{3/4} E Z ≥ 4 1 n 3/4 ,但大的均值可能来自 Z Z Z 偶尔出现的极大值,所以真正的想法是切比雪夫不等式,它需要 Var ( Z ) ≤ E Z \operatorname{Var}(Z)\le\mathbb E Z Var ( Z ) ≤ E Z 。协方差的符号正是起作用的假设:Var ( Z ) \operatorname{Var}(Z) Var ( Z ) 的交叉项都不是正的,只剩下对角项。条件 k ≤ n / 2 k\le n/2 k ≤ n /2 只用于二项式系数的估计。论证因 Pr ( Z = 0 ) ≤ 1 / E Z → 0 \Pr(Z=0)\le1/\mathbb E Z\to0 Pr ( Z = 0 ) ≤ 1/ E Z → 0 而完结。
当 k ≤ n / 2 k\le n/2 k ≤ n /2 时,n ( n − 1 ) ⋯ ( n − k + 1 ) n(n-1)\cdots(n-k+1) n ( n − 1 ) ⋯ ( n − k + 1 ) 中每个因子都至少为 n / 2 n/2 n /2 。再除以 k ! k! k ! ,就得到二项式系数所述的下界。估计 k ! ≤ k k k!\le k^k k ! ≤ k k 和 ( 1 − 1 / n ) n ≥ 1 / 4 (1-1/n)^n\ge1/4 ( 1 − 1/ n ) n ≥ 1/4 则是用精确的常数换取一个紧凑的表达式。下界的证明需要该表达式在乘以 n n n 之后增长;并不需要 Z Z Z 的精确分布。
协方差的计算有一个直观的耦合解释。一旦已知有 a a a 个球在箱子 i i i 中,其余 n − a n-a n − a 个球就在剩下的箱子中独立地选择。把它与较小的 a a a 相比,多出来的试验可能落入箱子 j j j ,但不会减少已有的成功。因此,箱子 j j j 达到阈值的机会随箱子 i i i 的负载增大而减小。独立副本恒等式把这一单调性转化为方差界所需的精确的两两协方差不等式。
切比雪夫不等式是应用于非负整数计数 Z Z Z ,而不是某一个箱子。在没有箱子过载的事件上,Z Z Z 等于零,与其较大的均值相差整个均值。方差界使这一事件不太可能发生。结论是“至少存在一个负载很重的箱子”这一存在性陈述;它并不事先指出是哪个箱子。
两个阈值的常数不同:上界的证明排除了超过该数量级足够大倍数的负载,而下界的证明找到超过足够小倍数的负载。两者的失败概率都趋于零,所以再取一次并集界,两个结论便以高概率同时成立。这正是这里 Θ \Theta Θ 陈述的含义;它并不断言收敛到某个特定的常数。
改变球数或箱数
见证论证有一个有用的一般形式。若 m m m 个独立的球均匀地放入 w w w 个箱子,则
Pr ( max i X i ≥ k ) ≤ w ( m k ) w − k . \Pr(\max_iX_i\ge k)\le w\binom mk w^{-k}. Pr ( i max X i ≥ k ) ≤ w ( k m ) w − k .
箱子有 w w w 种选法,带标号的见证集有 ( m k ) \binom mk ( k m ) 种选法。当 m m m 与 w w w 不同时,此公式仍然有效。然而,它最佳的渐近解释取决于两者的关系;上面证明的下界阈值专属于 m = w = n m=w=n m = w = n ,未经新的计算不应推广到所有负载范围。
例如,若球远少于箱子,则大多数箱子是空的,最繁忙的负载可能远小于 n n n 个球入 n n n 个箱子的数量级。若球远多于箱子,则平均负载本身就大于 1 1 1 。此时固定箱子的分布是 Bin ( m , 1 / w ) \operatorname{Bin}(m,1/w) Bin ( m , 1/ w ) ,过载箱子数的期望和有用的阈值都必须重新计算。说明输入所处的范围,是陈述概率定理的一部分,有助于避免把一个本来正确的估计用到错误的系统上。
例题详解
共有四种等可能的有序放置。其中两种是两个球选择同一个箱子,最大负载为二;另外两种是两球分开,最大负载为一。因此 Pr ( M 2 ≥ 2 ) = 1 / 2 \Pr(M_2\ge2)=1/2 Pr ( M 2 ≥ 2 ) = 1/2 。有限形式的并集界是成立的,但在这个很小的例子中宽松得多。
当 n = 10 n=10 n = 10 时,指定的三个球全都选择指定的某个箱子的概率为 10 − 3 10^{-3} 1 0 − 3 。这个集合有 ( 10 3 ) \binom{10}{3} ( 3 10 ) 种选法,所以由并集界,该箱子的负载至少为三的概率至多为 120 / 1000 120/1000 120/1000 。这些见证事件是相互重叠的;把它们的概率相加得到的是一个上界,而不是精确的计数。
在 n n n 个球、n n n 个箱子的情形,每种放置的平均负载都恰好为一。然而,把所有球放入同一个箱子,最大负载为 n n n ;而每个箱子放一个球,最大负载为一。随机模型的定理描述的是不同最大负载出现的可能性;仅凭平均值无法确定它们。
当某个箱子接收很多球时,留给其他箱子的球就变少了。上面的条件分布把这一点说得精确。但这并不是说涉及两个箱子的每个事件都是独立的,也不是说所有可能的负载事件都有简单的乘积概率。
常见错误
固定某个箱子过载的概率,不等于某个箱子过载的概率。后者是对 n n n 个箱子取并集。漏掉这个因子,会得到过于乐观的界。
反过来,把不同箱子的概率当作负载相互独立而相乘,是没有根据的。球的总数固定会产生相依性。对于下界,我们证明了所需的特定协方差不等式,然后使用切比雪夫不等式。
最后,一个正的计数的期望,本身并不蕴含该计数以高概率为正。随机变量的均值可能很大,而这是由稀少的极大值造成的。这里的方差估计防止了这种可能性破坏下界的论证。
总结
大负载有一个由球组成的见证集,所以两次并集界给出上尾界。在较小的阈值处,过载箱子的个数有很大的期望,而两两协方差为负使其方差受到控制。合起来,这些结果表明:在独立均匀放置下,最大负载以高概率位于 log n / log log n \log n/\log\log n log n / log log n 的数量级。
练习
快速检查
(对两个球、两个箱子,计算 Pr ( M 2 = 1 ) \Pr(M_2=1) Pr ( M 2 = 1 ) 。)
解答 · 答案 两个球必须选择不同的箱子。四种等可能的放置中有两种满足,故概率为 1 / 2 1/2 1/2 。
快速检查
(对 n = 10 n=10 n = 10 ,利用三球见证,给出指定的某个箱子至少接收三个球的概率的上界。)
先数三球组的个数,再乘以某个三球组全部选中指定箱子的概率。
解答 · 答案 可能的见证三元组共有 ( 10 3 ) = 120 \binom{10}{3}=120 ( 3 10 ) = 120 个,每个的概率为 10 − 3 10^{-3} 1 0 − 3 。并集界为 120 / 1000 = 0.12 120/1000=0.12 120/1000 = 0.12 。
快速检查
(解释为什么在两个球、两个箱子的情形,事件 X 1 = 2 X_1=2 X 1 = 2 与 X 2 = 2 X_2=2 X 2 = 2 不可能同时发生。)
解答 · 答案 两个负载之和等于球的总数,即二。若两者都等于二,则和至少为四。
快速检查
(若取非负整数值的 Z Z Z 的均值为正,且 Var ( Z ) ≤ E Z \operatorname{Var}(Z)\le\mathbb E Z Var ( Z ) ≤ E Z ,利用切比雪夫不等式给出 Pr ( Z = 0 ) \Pr(Z=0) Pr ( Z = 0 ) 的上界。)
事件 Z = 0 Z=0 Z = 0 即 Z Z Z 比均值低了 E Z \mathbb E Z E Z 。
解答 · 答案 在 Z = 0 Z=0 Z = 0 上,与均值的偏差至少为 E Z \mathbb E Z E Z 。切比雪夫不等式给出 Pr ( Z = 0 ) ≤ Var ( Z ) / ( E Z ) 2 ≤ 1 / E Z \Pr(Z=0)\le\operatorname{Var}(Z)/(\mathbb E Z)^2\le1/\mathbb E Z Pr ( Z = 0 ) ≤ Var ( Z ) / ( E Z ) 2 ≤ 1/ E Z 。