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 mn 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