南京大学：《概率与计算 Probability and Computing》课程教学资源（课件讲稿）random5

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 n￾ln ln n) ln n/ ln ln n ￾ ne￾2 ln n = 1 n ￾ ne￾3 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:

Chernoff Bounds Life in Los Angeles ORBAN STRES RATE LOW MED Herman Chernoff

Chernoff Bounds Herman Chernoff

Concentration Flip a coin for many times: flips -1 flips-5 flips-50 flips -500 fips=500000 0.8 0.8 0.8 0.8 0.8 0.6 0.6 0.6 0.6 0.6 0.4 0.4 04 0.4 0.4 0.2 0.2 0.2 0.2 02 0 1 1 1 0 0

Concentration Flip a coin for many times:

Chernoff bound: For independent trials X1,X2,...,XnE(0,1} Let X=>2 Xi,and u=E[X]. For any 6 >0, Pr[X≥(1+6)W≤ PrX≤I-oW a

Chernof bound: Pr[X ⇥ (1+￾)µ] ￾ ⇥ e￾ (1+￾)(1+￾) ￾µ Pr[X ⇥ (1￾￾)µ] ⇥ ⇥ e￾￾ (1￾￾)(1￾￾) ￾µ For any ￾ > 0, For independent trials X1,X2,...,Xn 2 {0, 1}. Let X = Pn i=1 Xi , and µ = E[X]

Chernoff Bounds 0.8 0.6 Pr[X≥1+6川≤ 0.4 0.2 0 0.5 1 1.5 6

Chernoff Bounds Pr[ X ⇥ (1 + ￾ ) µ ] ￾ ⇥ e ￾ (1 + ￾ )(1 + ￾ ) ￾ µ

Chernoff Bound independent X1,X2,...,XnE {0,1} X=∑X,EX]=u i=1 0<6≤1： Px之+<ae(-"肾） r≤1-洲<即(-） t≥2eu: Pr[X≥t≤2-t

X = X n i=1 Xi E[X] = µ independent X1, X2,...,Xn 2 {0, 1} Chernoff Bound Pr[X ￾ (1 + ￾)µ] < exp ✓ ￾µ￾2 3 ◆ Pr[X  (1 ￾ ￾)µ] < exp ✓ ￾µ￾2 2 ◆ Pr[X ￾ t]  2￾t 0 < ￾  1 : t ￾ 2eµ :