動機
當獨立的工作被均勻地分配到各個伺服器時,平均負載可能很小,而最繁忙的伺服器卻接收到很多工作。決定最壞回應時間或記憶體需求的,往往是最大負載,而不是平均負載。
我們研究將 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 。