7 1.Preliminaries mnt r amru可oatsaacoaamihwaeifeoaie Here is an elementary fact which is used all the time: 1.1.3 Lemma.For any collection of events A,....A P[UA≤∑PA, Li=1 =1 Proof.For i=1,...,n,we define B:=A;\(A:U A2 U...UAi-1). P[UA=P[UB=PB刷≤EPA 1.1.4 Definition.Events A,B are independento if P[AOB]=P[A]P[B]. More events A,A2,....An are independent if for any subset of P04:=IIP[Ad. We use the convenient notation [n]for the set {1,2.....n. The independence of A,A2,. An is not equivalent to all the pairs A,A, being independent.Exercise:find three events A,A2 and As that are pairwise independent but not mutually independent. Intuitively,the property of independence means that the knowledge of whe- ther some of the events A. ...An occurred does not provide any information regarding the remaining events. h比，（e h P(B]=PIAOB PB] toss a fair coin=hodit spravedlivou minci eads=lic (hlava) conditional probability podminena pravdepodobnost 7 1. Preliminaries This corresponds to generating the random graph by including every po￾tential edge independently with probability p. For p = 1 2 , we toss a fair coin7 for each pair {u, v} of vertices and connect them by an edge if the outcome is heads.8 9 Here is an elementary fact which is used all the time: 1.1.3 Lemma. For any collection of events A1, . . . , An, P  [n i=1 Ai  ≤ Xn i=1 P[Ai ]. Proof. For i = 1, . . . , n, we define Bi = Ai \ (A1 ∪ A2 ∪ . . . ∪ Ai−1). Then S Bi = S Ai , P[Bi ] ≤ P[Ai ], and the events B1, . . . , Bn are disjoint. By additivity of the probability measure, P  [n i=1 Ai  = P [n i=1 Bi  = Xn i=1 P[Bi ] ≤ Xn i=1 P[Ai ]. ✷ 1.1.4 Definition. Events A, B are independent10 if P[A ∩ B] = P[A] P[B] . More generally, events A1, A2, . . . , An are independent if for any subset of indices I ⊆ [n] P  \ i∈I Ai  = Y i∈I P[Ai ]. We use the convenient notation [n] for the set {1, 2, . . . , n}. The independence of A1, A2, . . . , An is not equivalent to all the pairs Ai , Aj being independent. Exercise: find three events A1, A2 and A3 that are pairwise independent but not mutually independent. Intuitively, the property of independence means that the knowledge of whe￾ther some of the events A1, . . . , An occurred does not provide any information regarding the remaining events. 1.1.5 Definition (Conditional probability). For events A and B with P[B] > 0, we define the conditional probability11 of A, given that B occurs, as P[A|B] = P[A ∩ B] P[B] . 7 toss a fair coin = hodit spravedlivou mincí 8 heads = líc (hlava) 9 tails = rub (orel) 10independent events = nezávislé jevy 11conditional probability = podmíněná pravděpodobnost