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) = eA 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)k1 X S2( [n] k ) Pr \ i2S Ai ! X 2` k=1 (1)k1 X S2( [n] k ) Pr \ i2S Ai ! Pr 0 @ [ i2[n] Ai 1 A 2 X `+1 k=1 (1)k1 X S2( [n] k ) Pr \ i2S Ai ! Works for arbitrary dependency!