動機
在碰撞變得很可能發生之前,可以獨立生成多少個識別碼?一個很自然的猜測是,這個數目必須接近識別碼空間的大小。事實上,碰撞在該大小的平方根附近就已相當可觀,因為可能發生碰撞的配對數目是二次增長的。
我們先在均勻模型中推導精確概率,再給出一個簡單的聯集界和一個二階矩論證。隨後,我們考察非均勻概率,以及一個兩兩獨立的構造,說明為甚麼完全獨立的假設不能被隨意放棄。
定義
設 w≥1 為整數。從含 w 個標籤的集合中獨立均勻地抽取 n≥0 個值 X1,…,Xn。若對某兩個不同的下標有 Xi=Xj,就稱發生了碰撞。令
C=1≤i<j≤n∑1{Xi=Xj}
為發生碰撞的配對個數。三個相等的值貢獻三個配對,而不是一個。記 μ=(2n)/w,並約定當 n<2 時 (2n)=0。
概念視角組合
按標籤計數,而非按配對計數
設 Na 為等於標籤 a 的抽取次數。則 C=a∑(2Na),而沒有碰撞,恰好表示每個 Na≤1。每個標籤貢獻 E(2Na)=(2n)/w2,所以 EC=μ 再次成立。一個標籤被抽到三次,就貢獻三對。
定理
當 0≤n≤w 時,無碰撞的概率為
Pr(C=0)=i=0∏n−1(1−wi).當 n>w 時該概率為零。空積等於一。
對每個 n≥0,碰撞概率滿足
1−e−μ≤Pr(C>0)≤min{1,μ}.特別地,對固定的 c>0 及 n=⌊cw⌋,當 w 增大時,該概率保持在一個非平凡的常數尺度上。
證明
按順序展開抽取過程
假設 n≤w。在前 i 次抽取互不相同的條件下,它們恰好佔用 i 個標籤。下一次抽取避開這些標籤的概率為 (w−i)/w。把 i=0,1,…,n−1 的這些條件概率相乘,即得乘積公式。若 n>w,由鴿巢原理必有碰撞。對於 n=0 或 n=1,公式給出無碰撞的概率為一。
對每一對 i<j,兩者相等的概率為 1/w。對所有配對使用聯集界,得 Pr(C>0)≤(2n)/w=μ,再以一為上限。對於下界,在無碰撞的乘積中使用 1−x≤e−x:
Pr(C=0)≤exp(−i=0∑n−1wi)=e−μ.當 n>w 時無碰撞概率為零,所以同一不等式顯然成立。取補事件即得所述下界。
當 n=⌊cw⌋ 時,均值 μ 趨於 c2/2。對足夠大的 w,有 n≤w 且 (n−1)/w<1。對 0≤x<1 成立的不等式 log(1−x)≥−x/(1−x) 給出乘積的另一側界:
exp(−1−(n−1)/wμ)≤Pr(C=0)≤e−μ.兩個界都趨於 e−c2/2,因此碰撞概率趨於 1−e−c2/2,對固定的 c>0,它嚴格介乎零與一之間。具體地說,c 較小時這個極限較小,而固定的較大 c 會使它接近一。固定的有限 c 並不意味著極限概率恰好為一。
證明透視
數的是可能的配對,而不僅是被佔用的標籤
各假設用在哪裏:乘積公式只需要每次新抽取獨立於先前各次且為均勻,透過避開已佔用的 i 個標籤的條件概率 (w−i)/w 體現。聯集界只需要每一對以概率 1/w 碰撞。指數型下界對每個因子使用 1−x≤e−x,並用到 i<n∑i/w=μ。關鍵一步是數 (2n) 個配對而不是數抽取次數:決定尺度的是配對數,所以 μ 恰在 n 為 w 量級時達到常數量級。極限論證需要 n≤w 與 (n−1)/w<1,以便使用較精細的對數估計;它之所以閉合,是因為兩側都趨於 e−c2/2。
二階矩證明
記 Iij=1{Xi=Xj}。在完全獨立的均勻模型下,不同配對的指示變量是兩兩獨立的。對於不相交的配對,這是顯然的。若兩個配對共享一個下標,例如 I12 與 I13,則兩者同時為一恰好當 X1=X2=X3,其概率為 1/w2,等於它們邊緣概率之積。這些指示變量兩兩獨立,並不意味著它們全體是聯合獨立的。
由線性性得 E[C]=μ。由於 Var(Iij)=(1/w)(1−1/w) 且不同配對的協方差為零,
Var(C)=μ(1−1/w)≤μ.當 μ>0 時,對 C1{C>0} 應用柯西–施瓦茨(Cauchy–Schwarz)不等式,得
Pr(C>0)≥E[C2](EC)2≥1+μμ.事實上,E[C2]=Var(C)+μ2≤μ+μ2。若 μ=0,則碰撞概率為零,下界按零理解。這個二階矩界在此處比基於乘積的指數界弱,但這一方法可以推廣到無法得到精確乘積的情形。它的證明既用到方差,也用到期望。
證明透視
方差這一步真正的假設
界 Pr(C>0)≥(EC)2/E[C2] 只是 Cauchy–Schwarz 不等式,不需要任何獨立性。獨立性只在 Var(C)=μ(1−1/w) 中出現,它要求指示變量 Iij 與 Iik 不相關。這是關於三次抽取的陳述,即 Pr(Xi=Xj=Xk)=1/w2,而兩兩獨立的抽取推不出它。在仿射例子中 Pr(I12I13=1)=1/3=1/9,且 Var(C)=2,而不是 2/3。
非均勻的標籤概率
現在假設各次抽取仍然獨立同分佈,但標籤 a 的概率為 pa,其中 a=1∑wpa=1。定義 s2=a∑pa2 與 s3=a∑pa3。指定的一對發生碰撞的概率為 s2,所以 E[C]=(2n)s2,並且聯集界給出 Pr(C>0)≤(2n)s2,再以一為上限。
不相交配對的指示變量仍然相互獨立。對於共享一個下標的兩個配對,二者同時碰撞的概率為 s3,所以它們的協方差為 s3−s22。每三個下標對應三個無序的相互重疊的配對組合。因此,
Var(C)=(2n)s2(1−s2)+6(3n)(s3−s22).
第二項不一定為零。事實上,由柯西–施瓦茨不等式有 s3≥s22,因為 (a∑pa2)2≤(a∑pa3)(a∑pa)。集中的標籤概率會增加出現重複值的機會,並可能使均勻情形的估計產生誤導。僅憑期望仍能得到上界,但要得到準確的下界,通常還需要額外的相依性資訊。
從界到抽樣預算
設目標是把碰撞概率控制在至多 δ,其中 0<δ<1。一個充分條件是 n(n−1)≤2wδ,因為此時聯集界給出 Pr(C>0)≤δ。這是一個保守的保證:它不成立並不證明實際概率超過 δ。反過來,若 μ≥log(1/δ),則乘積界給出 Pr(C=0)≤δ,所以碰撞以至少 1−δ 的概率發生。
在選擇識別碼大小時,必要條件與充分條件的區別十分重要。例如,按聯集界準則設計的系統,在獨立均勻生成下擁有一個站得住腳的上界。但若不對精確乘積在另一方向上加以計算或估計,就不能聲稱每一個更小的空間都必然違反目標。此外,該模型計入的是所生成的全部識別碼,包括重複嘗試;在發生碰撞後悄悄把計數重置,就改變了實驗本身。
對於近似 Pr(C=0)≈e−μ,有一種定量的評估方式。對 0≤x<1,透過積分或 −log(1−x) 的冪級數可得
−x−1−xx2≤log(1−x)≤−x.
若 1≤n≤w 且 r=(n−1)/w<1,把該不等式對乘積的各個因子求和,得
e−μ−E≤Pr(C=0)≤e−μ,E=6w2(1−r)n(n−1)(2n−1).
這裏 E 是對數額外幅度的一個顯式界。當 n 與 w 成比例時,E 趨於零,從而說明了極限近似的合理性。當 n 大得多,或分母很小時,該界可能過於鬆弛而失去資訊;精確的有限乘積仍然成立。
解讀非均勻情形的方差
考慮從兩個標籤中獨立抽取 n=3 次,標籤的概率分別為 0.9 與 0.1。此時 s2=0.82,s3=0.73。碰撞配對個數的均值為 3(0.82)=2.46,而方差公式給出 3(0.82)(0.18)+6(0.73−0.822)=0.7884。第二項為正,來自共享同一次抽取的碰撞檢驗配對。
這個值不用一般公式也能驗證。三次抽取全部相同的概率為 0.93+0.13=0.73,此時 C=3;否則恰有兩個相同,此時 C=1。於是 E[C2]=9(0.73)+1(0.27)=6.84,減去 2.462 得 0.7884。由於只有兩個標籤,碰撞必然發生,儘管計數是變化的。這個例子把事件的概率與相等配對的個數區分開來。
例題詳解
對於兩次獨立的均勻抽取,只有一個配對。碰撞概率恰為 1/w,精確乘積與聯集界都給出這一答案。當只有一個標籤,即 w=1 時,兩次抽取必然碰撞。
當 w=3 且 n=3 時,無碰撞的概率為 1⋅(2/3)⋅(1/3)=2/9。碰撞概率為 7/9。碰撞配對的期望個數為 μ=3/3=1,它並不等於碰撞概率:當三次抽取全部相同時,它們同時貢獻三個配對。
對於概率分別為 3/4 與 1/4 的兩個標籤,兩次獨立抽取碰撞的概率為 (3/4)2+(1/4)2=5/8。均勻的兩標籤概率為 1/2。較重的標籤使匹配更容易發生。
若 w=10,000 且 n=100,則 μ=100⋅99/(2⋅10,000)=0.495。這些界給出 1−e−0.495≤Pr(C>0)≤0.495。下界約為 0.390。如需更精確的答案,可使用精確乘積;不應把任何一個界當作精確概率。
解讀一個具體的概率
對於含 365 個標籤的均勻空間和 23 次獨立抽取,精確乘積給出的碰撞概率約為 0.5073。此處 μ=253/365≈0.69315,指數下界約為 0.5000。上界 0.69315 有效,但不夠緊。這些數字指的是各次抽取中任意一對相等的情形;它們並不描述某個指定抽取與另一個指定抽取相匹配的機會,後者僅為 1/365。
該模型也不同於不放回抽樣。如果我們不放回地均勻選取 n≤w 個標籤,則所選標籤不可能重合,所以碰撞概率為零。兩種方案都可以使每一次抽取具有均勻的邊緣分佈,但它們的聯合分佈不同。獨立性是關於聯合實驗的陳述,而不只是關於單次抽取的分佈。
在真實的識別碼系統中,均勻性可能只是一種近似,不同的用戶或機器也可能共享隨機性。因此,精確公式是在所述生成過程條件下的一個預測。如果某個確定性規則防止重複,或者生成器重複使用同一個種子,則應改為分析該規則。僅憑名義上很大的識別碼空間,不足以證明獨立均勻的計算是合理的。
「碰撞」一詞還取決於所計數的對象。本章檢驗的是標籤的精確相等。雜湊表可能把映射到同一個桶的兩個不同鍵稱為碰撞;只有當所得的桶值滿足模型假設時,同樣的數學才適用。兩個原始鍵是否相等是另一個獨立的問題。
獨立性不能被悄悄削弱
各次抽取兩兩獨立,並不蘊含精確的乘積公式。在 F3 中取獨立均勻的 A,B。令 X1=A,X2=A+B,X3=A+2B。這些變量中的每一對在 F32 上都是聯合均勻的:從 (A,B) 出發的相應線性映射的行列式非零。因此這些抽取兩兩獨立,並且各自均勻。
若 B=0,三個值全部相同。若 B=0,它們兩兩不同。因此它們的碰撞概率為 1/3。而在從三個標籤中進行三次完全獨立的均勻抽取時,該概率為 7/9。兩個模型對每個指定的配對給出相同的碰撞概率 1/3,但它們的聯合行為不同。聯集界僅憑兩兩邊緣分佈即仍然有效;上文的乘積公式與方差計算則使用了更強的假設。
反例模式
兩兩獨立的抽取不一定相互獨立
仿射構造中只有九個等可能的 (A,B) 對,而三次完全獨立的三元抽取有 27 個等可能的三元組。知道其中兩個仿射抽取就能確定第三個。因此,相同的兩兩分佈並不能決定涉及全部三個配對的聯集的概率。
常見錯誤
碰撞配對的期望個數一般並不等於至少發生一次碰撞的概率。兩者只在特殊情形下一致,因為一個結果可能包含多個碰撞配對。聯集界是把期望用作上界,而不是等式。
不應把單個碰撞概率反覆相乘,彷彿所有配對碰撞事件都是獨立的。即使各次抽取獨立,三個事件 X1=X2、X1=X3 與 X2=X3 之間也存在聯合的邏輯約束。順序的無碰撞乘積則是以此前的全部歷史為條件的。
最後,對嚴重偏斜的識別碼使用均勻公式會低估風險。相關的配對概率是 ∑pa2,並且碰撞過程還可能具有超出獨立抽取範圍的相關性。在應用數值保證之前,應先說明隨機生成模型。
總結
均勻獨立的抽取給出精確的無碰撞乘積,以及由 (2n)/w 控制的簡單界。配對數目的二次增長解釋了平方根尺度。在此模型中配對指示變量是兩兩獨立的,由此得到二階矩界;並不需要它們完全聯合獨立,而且這一點可能不成立;當 n≥3 且 w≥2 時它不成立。非均勻的或僅兩兩獨立的抽取需要另行分析。
練習
快速檢查
(計算從 w=5 個標籤中均勻抽取 n=2 次的碰撞概率。)
解答 · 答案
只有一個配對,其相同的概率為 1/5。
快速檢查
(對 w=4,n=3,計算精確的無碰撞概率和碰撞配對的期望個數。)
解答 · 答案
乘積為 1⋅(3/4)⋅(2/4)=3/8。碰撞配對的期望個數為 (23)/4=3/4。其補事件的概率 5/8 才是碰撞概率,這說明期望與概率不同。
快速檢查
(兩個標籤的概率分別為 0.9 與 0.1。計算兩次獨立抽取相同的概率。)
解答 · 答案
兩種相同方式的概率分別為 0.92 與 0.12,所以答案為 0.82。
快速檢查
(在仿射三元構造中,解釋為甚麼 B=0 使三個值互不相同,並求出碰撞概率。)
解答 · 答案
在 F3 中,乘以非零的 B 會置換三個值 0,B,2B,所以再加上 A 就得到三個互不相同的標籤。碰撞恰好在 B=0 時發生,其概率為 1/3。