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

Balls and Bins m balls ○○○○○○ uniformly independently L444↓I n bins birthday problem,coupon collector problem, occupancy problem

Balls and Bins m balls n bins uniformly & independently birthday problem, coupon collector problem, occupancy problem,

Random function balls-into-bins: [m] [n] Prlassignment)..1 nn m nm m random function: Prassigumeut)=m→n 1 1 m 1-1 birthday problem uniformly random function on-to coupon collector pre-images occupancy problem

Random function [m] [n] uniformly random function Pr[assignment] = 1 |[m] ￾ [n]| = 1 nm random function: balls-into-bins: Pr[assignment] = 1 n · 1 n ··· 1 n ⇤ ⇥￾ ⌅ = 1 nm m 1-1 birthday problem on-to coupon collector pre-images occupancy problem

Birthday Paradox Paradox: (i)a statement that leads to a contradiction; (ii)a situation which defies intuition. birthday paradox: Assumption:birthdays are uniformly independently distributed. In a class of m>57 students,with >99%probability, there are two students with the same birthday. m-balls-into-n-bins: &there is no bin with 1 balls

Birthday Paradox Paradox: (i) a statement that leads to a contradiction; (ii) a situation which defies intuition. birthday paradox: In a class of m>57 students, with >99% probability, there are two students with the same birthday. Assumption: birthdays are uniformly & independently distributed. m-balls-into-n-bins: E: there is no bin with > 1 balls. (ii) a situation which defies intuition

Birthday Paradox m-balls-into-n-bins: &there is no bin with >1 balls. uniformly random f [m)[nj, E:f is one-one. m马m_ n·(n-1)…(n-m+1) Im→m 亿m 0 =0

m-balls-into-n-bins: E: there is no bin with > 1 balls. uniformly random f : [m] ￾ [n], E: f is one-one. = m ⇤￾1 k=0 ￾ 1 ￾ k n ⇥ = |[m] 1-1 ￾⇥ [n]| |[m] ⇥ [n]| Pr[E] Birthday Paradox = n · (n ￾ 1)···(n ￾ m + 1) nm

Birthday Paradox m-balls-into-n-bins: m-】 E:there is no bin with >1 balls. ecleI(1-) suppose balls are thrown one-by-one: PrE=Prno collision for all m balls] m-1 Prno collision for the (+1)th ball no collision for the first k balls k=0 chain rule

= m ⇤￾1 k=0 ￾ 1 ￾ k n ⇥ Pr[E] Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox = m ￾￾1 k=0 Pr[no collision for the (k + 1)th ball | no collision for the first k balls] = Pr[no collision for all m balls] chain rule suppose balls are thrown one-by-one:

Birthday Paradox m-balls-into-n-bins: m- E:there is no bin with >1 balls. 胸=i〔-》 Taylor's expansion:e-k/1-/n (-) m-l m-1 e k=1 ( k=1 =e-m(m-1)/2n ≈e-m2/2n

Taylor's expansion: e￾k/n ⇥ 1 ￾ k/n ⇥ m ⌅￾1 k=1 e￾ k n = exp ￾ ￾ m ⇤￾1 k=1 k n ⇥ = e￾m(m￾1)/2n ￾ e￾m2/2n m ⇤￾1 k=1 ￾ 1 ￾ k n ⇥ = m ⇤￾1 k=0 ￾ 1 ￾ k n ⇥ Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox

Birthday Paradox m-balls-into-n-bins: E:there is no bin with >1 balls. PHe]-(1-) (-）≈6rea m-1 exact 08 ---approx k=三1 0.6 n=365 1 0.4 for m= 02 10 20 30 40 50 60 0.02 Pr[E]≈e 0 0.02 20 30 40 50 60 m=f(√m)for constant e m

￾ e￾m2/2n m ⇤￾1 k=1 ￾ 1 ￾ k n ⇥ Pr[E] ￾ ￾ for m = ￾ 2n ln 1 ￾ , m = ⇥( ￾n) for constant ￾ = m ⇤￾1 k=0 ￾ 1 ￾ k n ⇥ Pr[E] m-balls-into-n-bins: E: there is no bin with > 1 balls. Birthday Paradox

Perfect Hashing S={a,b,c,d,e,f uniform random h [N→[M Pr[perfect]1/2 M =O(n2) Table T: ca birthday！ UHA:Uniform Hash Assumption search(x):retrieve h; check whether T[h(x)]=x;

Perfect Hashing e b d f c a h Table T: M S = { a, b, c, d, e, f } search(x): retrieve h; check whether T[h(x)] = x; [N] ￾ [M] UHA: Uniform Hash Assumption uniform random Pr[perfect] > 1/2 birthday! = O(n2)

Coupon Collector (cover time) coupons in cookie box number of boxes bought to collect all n coupons number of balls thrown to cover all n bins each box comes with a uniformly random coupon

Coupon Collector number of boxes bought to collect all n coupons each box comes with a uniformly random coupon number of balls thrown to cover all n bins coupons in cookie box (cover time)

Coupon Collector X: number of balls thrown to make all the n bins nonempty 2=1 Xi is geometric! X:=4 with p:=1-i-1 m bins E[X;]= 1 m i-1 n-i+1

Coupon Collector bins i-1 Xi = 4 X = ￾ n i=1 Xi Xi is geometric! pi = 1 ￾ i ￾ 1 n with E[Xi] = 1 pi = n n ￾ i + 1 X : Xi : number of balls thrown to make all the n bins nonempty number of balls thrown while there are exactly (i-1) nonempty bins