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