1 Preliminaries 1.1 Probability Theory This section summarizes the fundamental notions of probability theory and some results which we will need in the following chapters.In no way is it inten ded to serve asa substitute for a course in probability theory. 1.1.1 Definition.A probability space is a triple (P),where is a set i gebra on of closed or untable w table inte tion vith P]=1.Th nts ofΣar nd the lled ele ementary events.For ar of A. where the set event ity mea ure i rds, y specifying a function p:9 0.1]with)=1.Then the probability meastire is 8 ven by P[A]=】 EAP(w). he basic example of a probability measure is the uniform distributiond on 9,where P[A)=4 for all A. Such a distribution represents the situation where any outcome of an experiment (such as rolling a die)5 is equally likely. 1.1.2 Definition (Random graphs).6 The probability space of random gra- phs G(n,p)is a finite probability space whose elementary events are all graphs on a fixed set of n vertices,and where the probability of a graph with m edges P(G)=p"(1-p)(3)-m probability space-pravdepodobnostni prostor event jev
1 Preliminaries 1.1 Probability Theory This section summarizes the fundamental notions of probability theory and some results which we will need in the following chapters. In no way is it intended to serve as a substitute for a course in probability theory. 1.1.1 Definition. A probability space1 is a triple (Ω, Σ,P), where Ω is a set, Σ ⊆ 2 Ω is a σ-algebra on Ω (a collection of subsets containing Ω and closed on complements, countable unions and countable intersections), and P is a countably additive measure2 on Σ with P[Ω] = 1. The elements of Σ are called events3 and the elements of Ω are called elementary events. For an event A, P[A] is called the probability of A. In this text, we will consider mostly finite probability spaces where the set of elementary events Ω is finite and Σ = 2Ω. Then the probability measure is determined by its values on elementary events; in other words, by specifying a function p : Ω → [0, 1] with P ω∈Ω p(ω) = 1. Then the probability measure is given by P[A] = P ω∈A p(ω). The basic example of a probability measure is the uniform distribution4 on Ω, where P[A] = |A| |Ω| for all A ⊆ Ω. Such a distribution represents the situation where any outcome of an experiment (such as rolling a die)5 is equally likely. 1.1.2 Definition (Random graphs). 6 The probability space of random graphs G(n, p) is a finite probability space whose elementary events are all graphs on a fixed set of n vertices, and where the probability of a graph with m edges is p(G) = p m(1 − p) ( n 2 )−m. 1probability space = pravděpodobnostní prostor 2measure = míra 3 event = jev 4 uniform distribution = rovnoměrné rozdělení 5 rolling a die = hod kostkou 6 random graph = náhodný graf
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 potential 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 whether 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
1.1 Probability Theory 8 Note that if A and B are independent,then P[AB]=P[A]. 1.1.6 Definition (Random variable).A real random variable2 on a pro bability (O s P)is a function x.O -R that is P.m easurable.(That is for any aR,{we:X(u)≤a}e) We can also consider random variables with other than real values:for riable In such c dom function om the bability into the P R"in onsider real ra 1.1.7 Definition.The expectation13 of a(real)random variable X is E[X]=x(w)dP(w). can be expressed as E[X]=p(w)X(w). 1.1.8 Definition (Independence of variables).Real random variables X,Y are independent if we have,for every two measurable sets A,B CR, PX∈A and Y∈B周=P[X∈APY∈B ents in the previous definition:For X and Y 塞 rm nce versa.I r al me e ts A and B:i P[K≤a and Y≤=P[K≤adPY≤ for all a.bE R.then X and Y are independent As we will check in Chapter 3.ElX+Yl=EIXI+EY]holds for anu two tandom variables (provided that the On the other hand. EXY]is generally different from E[X]E Y].But we have 1.1.9 Lemma.If X and Y are independent random variables,then EXY]=EXI·EY]
1.1 Probability Theory 8 Note that if A and B are independent, then P[A|B] = P[A]. 1.1.6 Definition (Random variable). A real random variable12 on a probability space (Ω, Σ,P) is a function X: Ω → R that is P-measurable. (That is, for any a ∈ R, {ω ∈ Ω: X(ω) ≤ a} ∈ Σ.) We can also consider random variables with other than real values; for example, a random variable can have complex numbers or n-component vectors of real numbers as values. In such cases, a random variable is a measurable function from the probability space into the appropriate space with measure (complex numbers or Rn in the examples mentioned above). In this text, we will mostly consider real random variables. 1.1.7 Definition. The expectation13 of a (real) random variable X is E [X] = Z Ω X(ω) dP(ω). Any real function on a finite probability space is a random variable. Its expectation can be expressed as E [X] = X ω∈Ω p(ω)X(ω). 1.1.8 Definition (Independence of variables). Real random variables X, Y are independent if we have, for every two measurable sets A, B ⊆ R, P[X ∈ A and Y ∈ B] = P[X ∈ A] · P[Y ∈ B] . Note the shorthand notation for the events in the previous definition: For example, P[X ∈ A] stands for P[{ω ∈ Ω: X(ω) ∈ A}]. Intuitively, the independence of X and Y means that the knowledge of the value attained by X gives us no information about Y , and vice versa. In order to check independence, one need not consider all measurable sets A and B; it is sufficient to look at A = (−∞, a] and B = (−∞, b]. That is, if P[X ≤ a and Y ≤ b] = P[X ≤ a] P[Y ≤ b] for all a, b ∈ R, then X and Y are independent. As we will check in Chapter 3, E [X + Y ] = E [X] +E [Y ] holds for any two random variables (provided that the expectations exist). On the other hand, E [XY ] is generally different from E [X] E [Y ]. But we have 1.1.9 Lemma. If X and Y are independent random variables, then E [XY ] = E [X] · E [Y ] . 12random variable = náhodná proměnná 13expectation = střední hodnota!!!
9 1.Preliminaries Proof(for finite probability spaces).If X and Y are random variables on a finite probability space,the proof is especially simple.Let Vx,Vy be the (finite)sets of values attained by X and by Y,respectively.By independence, we have P[X a and Y=]=P[X a]P[Y =b]for any a Vx and bVy. We calculate ∑ab.Px=a and y= = ab.P[X a]P[y =b = (∑aPX=al)(∑bPY=)=E[X]E [Y] aEVx but the idea is the same. 1.2 Useful Estimates th the probabilistic method,many problems are is belo 1,or even ten age of often nee e en rul here is to start ughest nd only i they don't can try ones. Here we describe the most often used estimates for basic co For the factorial function n!,we can often do with the obvious upper bound n!<n".More refined bounds are ()”s≤m()” =2.718281828 is the basis of natural ogarithms),which For the"o(月，the baic bound is(≤k,and sharper ones are ()≤（因s() For all k,we also have(2".Sometimes we need better estimates of the middle binomial coefficient ()we have 22m )需 (also see Section 5.2 for a derivation of a slightly weaker lower bound). Very often we nee d the inequality1+x≤e valid for all real In particula for bounding expressions of the form(1-p)from above,with p0small one uses (1-p)m≤e-mp
9 1. Preliminaries Proof (for finite probability spaces). If X and Y are random variables on a finite probability space, the proof is especially simple. Let VX, VY be the (finite) sets of values attained by X and by Y , respectively. By independence, we have P[X = a and Y = b] = P[X = a] P[Y = b] for any a ∈ VX and b ∈ VY . We calculate E [XY ] = X a∈VX ,b∈VY ab · P[X = a and Y = b] = X a∈VX ,b∈VY ab · P[X = a] P[Y = b] = X a∈VX a P[X = a] X b∈VY b P[Y = b] = E [X] E [Y ] . For infinite probability spaces, the proof is formally a little more complicated but the idea is the same. ✷ 1.2 Useful Estimates In the probabilistic method, many problems are reduced to showing that certain probability is below 1, or even tends to 0. In the final stage of such proofs, we often need to estimate some complicated-looking expressions. The golden rule here is to start with the roughest estimates, and only if they don’t work, one can try more refined ones. Here we describe the most often used estimates for basic combinatorial functions. For the factorial function n!, we can often do with the obvious upper bound n! ≤ n n . More refined bounds are n e n ≤ n! ≤ en n e n (where e = 2.718281828 . . . is the basis of natural logarithms), which can be proved by induction. The well-known Stirling formula is very seldom needed in its full strength. For the binomial coefficient n k , the basic bound is n k ≤ n k , and sharper ones are n k k ≤ n k ! ≤ en k k . For all k, we also have n k ≤ 2 n . Sometimes we need better estimates of the middle binomial coefficient 2m m ; we have 2 2m 2 √ m ≤ 2m m ! ≤ 2 2m √ 2m (also see Section 5.2 for a derivation of a slightly weaker lower bound). Very often we need the inequality 1+x ≤ e x , valid for all real x. In particular, for bounding expressions of the form (1 − p) m from above, with p > 0 small, one uses (1 − p) m ≤ e −mp
1.2 Useful Estimates 10 almost automatically.For estimating such expressions from below,which is usually more delicate,we can often use 1-p≥ep, which is valid for0≤p≤
1.2 Useful Estimates 10 almost automatically. For estimating such expressions from below, which is usually more delicate, we can often use 1 − p ≥ e −2p , which is valid for 0 ≤ p ≤ 1 2