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