A.4 The Proof of Theorem 4 Proof.First we view the two sequences D={di1 and H =(h1 as constant values.By Eqn.(5)we have: 1-(-)+sa-g-9a+ Then we take the expectation on (h conditional on {d leading to Ea1-(-)p≤a[-0-8a:+lo =(1-c）-EH[h:+1D] Note that under our assumption,each of the adjacent edges is chosen to be hashed by v with probability Prd≥d)=l-Pr(d≤d)=.Thus,by the assumption:≤d-l,we have EH[d:-hD]=1+(d:-1)× di-a which means +回-4-a-若-君+器 Then we further take the expectation on D={d21: a-1 a-11 =dmin X &-2-dmm×2a-3+2 Finally,we obtain the result: w--》-容w-- ≤pl-c-m×&-号-dm×云+ Here e=（L-）°-l-）”in(l-)and0=(1-）”n(1-）.The expectation above is aken w.r.t.both (hi1 and (di)1 Similar to Theorem 3,we take derivative w.r.t.and get the global minimizer=(dmin -dmin x a二+)，Thus weget the tightest bound: m2(--】s--] where=(dmin×g号-dnm×会+) Note that our assumption suggestsdmin≥2.And for a∈(2,3)，-dmin 2-+交<0.Thus we have 8昌dnx会二+)<m×二号 (dmin x a-1 Thus we have: --)]<--) 0 12A.4 The Proof of Theorem 4 Proof. First we view the two sequences D = {di} n i=1 and H = {hi} n i=1 as constant values. By Eqn. (5) we have: 1 −  1 − 1 p hi+1 ≤ (1 − c) − θ(hi + 1). Then we take the expectation on {hi} n i=1 conditional on {di} n i=1, leading to EH  1 −  1 − 1 p hi+1 D  ≤ EH (1 − c) − θ(hi + 1)  D = (1 − c) − θEH (hi + 1)  D . Note that under our assumption, each of the adjacent edges is chosen to be hashed by vi with probability Pr(d ≥ di) = 1 − Pr(d ≤ di) = d 1−α i d 1−α min . Thus, by the assumption hi ≤ di − 1, we have EH di − hi  D = 1 + (di − 1) × d 1−α i d 1−α min , which means EH hi + 1  D = di − (di − 1) × d 1−α i d 1−α min = di − d 2−α i d 1−α min + d 1−α i d 1−α min . Then we further take the expectation on D = {di} n i=1: ED  di − d 2−α i d 1−α min + d 1−α i d 1−α min  = Z +∞ dmin  di − d 2−α i d 1−α min + d 1−α i d 1−α min  (α − 1)d α−1 min d −αddi = dmin × α − 1 α − 2 − dmin × α − 1 2α − 3 + 1 2 . Finally, we obtain the result: EH,D " p n Xn i=1  1 −  1 − 1 p hi+1# = p n Xn i=1 EH,D  1 −  1 − 1 p hi+1 ≤ p  1 − c − θ  dmin × α − 1 α − 2 − dmin × α − 1 2α − 3 + 1 2  . Here c =  1 − 1 p Ω − Ω  1 − 1 p Ω ln(1 − 1 p ) and θ =  1 − 1 p Ω ln  1 − 1 p  . The expectation above is taken w.r.t. both {hi} n i=1 and {di} n i=1. Similar to Theorem 3, we take derivative w.r.t. Ω and get the global minimizer Ωˆ0 =  dmin × α−1 α−2 − dmin × α−1 2α−3 + 1 2  . Thus we get the tightest bound: EH,D " p n Xn i=1  1 −  1 − 1 p hi+1# ≤ p  1 −  1 − 1 p Ωˆ0  , where Ωˆ0 =  dmin × α−1 α−2 − dmin × α−1 2α−3 + 1 2  . Note that our assumption suggests dmin ≥ 2. And for α ∈ (2, 3), −dmin α−1 2α−3 + 1 2 < 0. Thus we have  dmin × α − 1 α − 2 − dmin × α − 1 2α − 3 + 1 2  < dmin × α − 1 α − 2 . Thus we have: p  1 −  1 − 1 p Ωˆ0  < p  1 −  1 − 1 p Ωˆ  . 12