南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Balls and Bins

Randomized Algorithms 南京大学 尹一通

Randomized Algorithms 南京大学 尹一通

Probability Space Sample space: Probability measure: Pr:2→[0,1] s.t.Pr(e)=1 e∈2 event AC probability Pr(A)=>Pr(e) e∈A

Probability Space ￾ Sample space: Ω Probability measure: Pr : ￾ ￾ [0, 1] ￾ e￾￾ s.t. Pr(e)=1 event A ￾ ￾ Pr(A) = ￾ e￾A probability Pr(e)

Probability Space Kolmogorov (1933) Sample space set of all elementary events (samples) Set of events∑： each event is a subset of K1)0,2∈∑.impossible event,certain event (K2)∑is closed under U,∩，\. o-algebra Probability measure Pr:∑→[0，l (K3)Pr(2)=1 (K4)A∩B=0→Pr(AUB)=Pr(A)+Pr(B) (K5*)forA1·pAnD·with∩mAn=0 lim Pr(An)=0 m→oo

Probability Space Kolmogorov (1933) Sample space Ω: set of all elementary events (samples) Set of events Σ: each event is a subset of Ω ￾ is closed under ￾, ￾, \. ￾, ￾ ￾ ￾. Probability measure Pr(￾)=1 A ￾ B = ￾ ￾ Pr(A ￾ B) = Pr(A) + Pr(B) lim n￾￾ Pr(An)=0 for A1 ￾ ··· ￾ An ￾ ··· with ￾ n An = ￾ impossible event, certain event σ-algebra (K1) (K2) (K3) (K4) (K5*) Pr : ￾ ￾ [0, 1]

K1)0,2∈∑. (K2)∑is closed under U,∩，\. (K3)Pr(2)=1 (K4)A∩B=0→Pr(AUB)=Pr(A)+Pr(B) Pr(2\A)=1-Pr(A) If A C B,then Pr(A)<Pr(B). Pr(AUB)-Pr(A)+Pr(B)-Pr(A0B)

￾ is closed under ￾, ￾, \. ￾, ￾ ￾ ￾. Pr(￾)=1 A ￾ B = ￾ ￾ Pr(A ￾ B) = Pr(A) + Pr(B) (K1) (K2) (K3) (K4) Pr(￾ \ A)=1 ￾ Pr(A) If A ￾ B, then Pr(A) ￾ Pr(B). Pr(A ￾ B) = Pr(A) + Pr(B) ￾ Pr(A ￾ B)

The Union bound Works for arbitrary dependency! Union bound (Boole's inequality): (U4=2mia Inclusion-Exclusion: -2品 k=1 e() Boole-Bonferroni; 会(0)（这 2e+1 k=1 SE( =1 s∈( i∈S

The Union bound Union bound (Boole’s inequality): Pr [ i Ai !  X i Pr(Ai) Boole-Bonferroni: Inclusion-Exclusion: Pr 0 @ [ i2[n] Ai 1 A = X n k=1 (￾1)k￾1 X S2( [n] k ) Pr \ i2S Ai ! X 2` k=1 (￾1)k￾1 X S2( [n] k ) Pr \ i2S Ai !  Pr 0 @ [ i2[n] Ai 1 A  2 X `+1 k=1 (￾1)k￾1 X S2( [n] k ) Pr \ i2S Ai ! Works for arbitrary dependency!

Conditional Probability Definition: The conditional probability that event E occurs given that event &2 occurs is Pr8|E2]= Pr[E1AE2] Pr(E2] For independent E1,E2, Pr[E1|e2]= Pr[E1∧E2] Pr[E1 E2] Pr(E2] Pr[e]·Pr[e2] 2 Pr[E2] =Pr[E1]

Conditional Probability ￾ E1 E2 Pr[E1 | E2] Definition: The conditional probability that event E1 occurs given that event E2 occurs is Pr[E1 | E2] = Pr[E1⇥E2] Pr[E2] . For independent E1, E2, Pr[E1 | E2] = Pr[E1 ⇤ E2] Pr[E2] = Pr[E1] · Pr[E2] Pr[E2] = Pr[ E1]

Law of Total Probability Law of total probability: m For disjoint E1,82,...,n that 8=2, m m 2 Pr[E]=Pr[eAE=>Pr[EE]Pr[Ei. i=1 i=1 Analyze the probability by cases!

Law of Total Probability Law of total probability: Pr[E] = ￾ n i=1 Pr[E ⇤ Ei] = ￾ n i=1 Pr[E|Ei] · Pr[Ei]. For disjoint E1, E2,..., En that ￾ n i Ei = ￾, Analyze the probability by cases!

Law of Successive Conditioning (chain rule) Theorem For any E1,E2,...,n, 区- i<飞 Proof: m Pr E m-1 Pr Li=1 m-1 51 Pr recursion! 2=1

Law of Successive Conditioning For any E1, E2,..., En, Pr ￾ ⌅ n i=1 Ei ⇥ = ⇤ n k=1 Pr ￾ Ek | ⌅ i<k Ei ⇥ . Theorem Proof: recursion! Pr ￾ En ￾ ￾ ￾ n ￾￾1 i=1 Ei ￾ Pr ￾ ￾ n i=1 Ei ￾ Pr ￾n ￾￾1 i=1 Ei = ￾ (chain rule)

Random Variables probability space: X is the outcome (2,∑，Pr) 1 2 random variable X 3 4 5 6

Random Variables random variable X X is the outcome 1 2 3 4 5 6 (￾, ￾,Pr) probability space:

Random Variables probability space: X indicates the evenness (2,∑，Pr) random variable X a function defined over the sample space X:2→R

Random Variables random variable X a function defined over the sample space X : ￾ ￾ R (￾, ￾,Pr) probability space: X indicates the evenness 0 1