Occupancy Problem m balls n bins 4444444 Theorem: If m=n,the max load is() Inn with high probability
Theorem: If m = n, the max load is O ln n ln ln n ⇥ with high probability. Occupancy Problem n bins m balls
n balls into n bins: Pr[bin-1has≥t balls Pr a set S of t balls s.t.all balls in S are in bin-1 1 t n union bound ∑ Prall balls in S are in bin-1 set s of t balls (g）=-山<日≤ t!nt Stirling approximation
n balls into n bins: union bound Stirling approximation Pr[ bin-1 has t balls ] n t Pr [ a set S of t balls s.t. all balls in S are in bin-1 ] set S of t balls Pr[all balls in S are in bin-1] 1 nt 1 nt n t = n(n 1)(n 2)···(n t + 1) t!nt 1 t! e t t
n balls into n bins: Pr[bin-lhas≥t balls]≤ () Pr[max load≥t=Pr闩bin-ihas≥t balls] ≤mPr[bin-1has≥t balls] union bound ≤ () 31nn choose t= InIn n (） 31nn/InInn Inn/Inlnn =ne3(In InIn n-InInn)inn/Ininn ne-3Inn+3(InInIn n)(In n)/InInn ≤ne-2lnn 1 m
n balls into n bins: Pr[ bin-1 has t balls ] e t t Pr[ max load t] = Pr[ bin-i has t balls] nPr[ bin-1 has t balls ] union bound n e t t = n e ln ln n 3 ln n 3 ln n/ ln ln n < n ln ln n ln n 3 ln n/ ln ln n = ne3(ln ln ln nln ln n) ln n/ ln ln n ne2 ln n = 1 n ne3 ln n+3(ln ln ln n)(ln n)/ ln ln n t = 3 ln n ln ln n choose
Occupancy Problem Theorem: m balls into n bins: If m-n,the max load is ( with high probability
Theorem: If m = n, the max load is O ln n ln ln n ⇥ with high probability. Occupancy Problem m balls into n bins:
Occupancy Problem Theorem: m balls into n bins: If m=n,the max load is O( In In n/ with high probability When m (n logn),the max load is O() with high probability balls =100,bins =100 balls =2000,bins =100 6 20 dhher iwbyw 0 20 40 60 80 100 20 40 60 80 100 balls =600,bins =100 balls =5000,bins =100 20 100 10 bar bbb solthruw 0 20 40 60 80 100 20 40 60 80 100
Theorem: If m = n, the max load is O ln n ln ln n ⇥ with high probability. When m = (n log n), the max load is O( m n ) with high probability Occupancy Problem m balls into n bins: