动机
在碰撞变得很可能发生之前,可以独立生成多少个标识符?一个很自然的猜测是,这个数目必须接近标识符空间的大小。事实上,碰撞在该大小的平方根附近就已经相当可观,因为可能发生碰撞的配对数量是二次增长的。
我们先在均匀模型中推导精确概率,再给出一个简单的并集界和一个二阶矩论证。随后,我们考察非均匀概率,以及一个两两独立的构造,说明为什么完全独立的假设不能被随意放弃。
定义
设 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。