CZ.1.07/2.2.00/28.0041 Centrum interaktivn´ıch a multimedi´aln´ıch studijn´ıch opor pro inovaci v´yuky a efektivn´ı uˇcen´ı Prologue You should spent most of your time thinking about what you should think about most of your time. IV054 0. 2/62 RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 Prof. Jozef Gruska, DrSc Wednesday, 10.00-11.40, B410 WEB PAGE of the LECTURE http://www.fi.muni.cz/usr/gruska/random20 FINAL EXAM: You need to answer four questions out of five given to you. CREDIT (ZAPOˇCET): You need to answer three questions out of five given to you. EXERCISES/TUTORIALS EXERCISES/TUTORIALS: Thursdays 14.00-15.40, C525 TEACHER: RNDr. Matej Pivoluˇska PhD Language English NOTE: Exercises/tutorials are not obligatory IV054 0. 5/62 CONTENTS - preliminary 1 Basic concepts and examples of randomized algorithms 2 Types and basic design methods for randomized algorithms 3 Basics of probability theory 4 Simple methods for design of randomized algorithms 5 Games theory and analysis of randomized algorithms 6 Basic techniques I: moments and deviations 7 Basic techniques II: tail probabilities inequalities 8 Probabilistic method I: 9 Markov chains - random walks 10 Algebraic techniques - fingerprinting 11 Fooling the adversary - examples 12 Randomized cryptographic protocols 13 Randomized proofs 14 Probabilistic method II: 15 Quantum algorithms IV054 0. 6/62 LITERATURE R. Motwami, P. Raghavan: Randomized algorithms, Cambridge University Press, UK, 1995 J. Gruska: Foundations of computing, International Thompson Computer Press, USA. 715 pages, 1997 J. Hromkoviˇc: Design and analysis of randomized algorithms, Springer, 275 pages, 2005 N. Alon, J. H. Spencer: The probabilistic method, Willey-Interscience, 2008 Part I Basics of Probability Theory Chapter 3. PROBABILITY THEORY BASICS CHAPTER 3: BASICS of PROBABILITY THEORY IV054 1. Basics of Probability Theory 9/62 PROBABILITY INTUITIVELY Intuitively, probability of an event E is the ratio between the number of favorable elementary events involved in E to the number of all possible elementary events involved in E. Pr(E) = number of favorable elementary events involved in E number of all possible elementary events involved in E Example: Probability that when tossing a perfect 6-sided dice we get a number divided by 3 is 2/6 = 1/3 . Key fact: Any probabilistic statement must refer to a specific underlying probability space - a space of elements to which a probability is assigned. IV054 1. Basics of Probability Theory 10/62 PROBABILITY SPACES A probability space is defined in terms of a sample space Ω (often with an algebraic structure – for example outcomes of some cube tossing) and a probability measure (probability distribution) defined on Ω. Subsets of a sample space Ω are called events. Elements of Ω are referred to as elementary events. Intuitively, the sample space represents the set of all possible outcomes of a probabilistic experiment – for example of a cube tossing. An event represents a collection (a subset) of possible outcomes. Intuitively - again, probability of an event E is the ratio between the number of favorable elementary events involved in E and the number of all possible elementary events. IV054 1. Basics of Probability Theory 11/62 PROBABILITY THEORY Probability theory took almost 300 years to develop from intuitive ideas of Pascal, Fermat and Huygens, around 1650, to the currently acceptable axiomatic definition of probability (due to A. N. Kolmogorov in 1933). IV054 1. Basics of Probability Theory 12/62 AXIOMATIC APPROACH - I. Axiomatic approach: Probability distribution on a set Ω is every function Pr : 2Ω → [0, 1], satisfying the following axioms (of Kolmogorov): 1 Pr({x}) ≥ 0 for any element (elementary event) x ∈ Ω; 2 Pr(Ω) = 1 3 Pr(A ∪ B) = Pr(A) + Pr(B) if A, B ⊆ Ω, A ∩ B = ∅. Example: Probabilistic experiment – cube tossing; elementary events – outcomes of cube tossing; probability distribution – {p1, p2, p3, p4, p5, p6}, 6 i=1 pi = 1, where pi is probability that i is the outcome of a particular cube tossing. In general, a sample space is an arbitrary set. However, often we need (wish) to consider only some (family) of all possible events of 2Ω . The fact that not all collections of events lead to well-defined probability spaces leads to the concepts presented on the next slide. IV054 1. Basics of Probability Theory 13/62 AXIOMATIC APPROACH - II. Definition: A σ-field (Ω, F) consists of a sample space Ω and a collection F of subsets of Ω satisfying the following conditions: 1 ∅ ∈ F 2 ε ∈ F ⇒ ε ∈ F 3 ε1, ε2, . . . ∈ F ⇒ (ε1 ∪ ε2 ∪ . . .) ∈ F Consequence A σ-field is closed under countable unions and intersections. Definition: A probability measure (distribution) Pr : F → R≥0 on a σ-field (Ω,F) is a function satisfying conditions: 1 If ε ∈ F, then 0 ≤ Pr(ε) ≤ 1. 2 Pr[Ω] = 1. 3 For mutually disjoint events ε1, ε2, . . . Pr i εi = i Pr(εi ) Definition: A probability space (Ω,F,Pr) consists of a σ-field (Ω,F) with a probability measure Pr defined on (Ω, F). IV054 1. Basics of Probability Theory 14/62 PROBABILITIES and their PROPERTIES - I. Properties (for arbitrary events εi ): Pr (ε) = 1 − Pr (ε); Pr (ε1 ∪ ε2) = Pr (ε1) + Pr (ε2) − Pr (ε1 ∩ ε2); Pr( i≥1 εi ) ≤ i≥1 Pr(εi ). Definition: Conditional probability of an event ε1 given an event ε2 is defined by Pr [ε1|ε2] = Pr [ε1 ∩ ε2] Pr [ε2] if Pr [ε2] > 0. Theorem: Law of the total probability Let ε1, ε2, . . . , εk be a partition of a sample space Ω. Then for any event ε Pr [ε] = k i=1 Pr [ε|εi ] · Pr [εi ] IV054 1. Basics of Probability Theory 15/62 EXAMPLE: Let us consider tossing of two perfect dices with sides labelled by 1, 2, 3, 4, 5, 6. Let ε1 be the event that the reminder at the division of the sum of the outcomes of both dices when divided by 4 is 3, and ε2 be the event that the outcome of the first cube is 4. In such a case Pr [ε1|ε2] = Pr [ε1 ∩ ε2] Pr [ε2] = 1 36 1 6 = 1 6 IV054 1. Basics of Probability Theory 16/62 PROBABILITIES and their PROPERTIES - II. Theorem: (Bayes’ Rule/Law) (a) Pr (ε1) · Pr (ε2|ε1) = Pr (ε2) · Pr (ε1|ε2) basic equality (b) Pr(ε2|ε1) = Pr(ε2) Pr(ε1|ε2) Pr(ε1) simple version (c) Pr [ε0|ε] = Pr[ε0∩ε] Pr[ε] = Pr[ε|ε0]·Pr[ε0] k i=1 Pr[ε|εi ]·Pr[εi ] . extended version Definition: Independence 1 Two events ε1, ε2 are called independent if Pr (ε1 ∩ ε2) = Pr (ε1) · Pr (ε2) . 2 A collection of events {εi |i ∈ I} is independent if for all subsets S ⊆ I Pr i∈S εi = i∈S Pr [εi ]. IV054 1. Basics of Probability Theory 17/62 MODERN (BAYESIAN) INTERPRETATION of BAYES RULE for the entire process of learning from evidence has the form Pr [ε1|ε] = Pr [ε1 ∩ ε] Pr [ε] = Pr [ε|ε1] · Pr [ε1] k i=1 Pr [ε|εi ] · Pr [εi ] . In modern terms the last equation says that Pr [ε1|ε], the probability of a hypothesis ε1 (given information ε), equals Pr (ε1), our initial estimate of its probability, times Pr [ε|ε1], the probability of each new piece of information (under the hypothesis ε1), divided by the sum of the probabilities of data in all possible hypothesis (εi ). IV054 1. Basics of Probability Theory 18/62 TWO BASIC INTERPRETATIONS of PROBABILITY In Frequentist interpretation, probability is defined with respect to a large number of trials, each producing one outcome from a set of possible outcomes - the probability of an event A , Pr(A), is a proportion of trials producing an outcome in A. In Bayesian interpretation, probability measures a degree of belief. Bayes’ theorem then links the degree of belief in a proposition before and after receiving an additional evidence that the proposition holds. IV054 1. Basics of Probability Theory 19/62 EXAMPLE 1 Let us toss a two regular cubes, one after another and let ε1 be the event that the sum of both tosses is ≥ 10 ε2 be the event that the first toss provides 5 How much are: Pr(ε1), Pr(ε2), Pr(ε1|ε2), Pr(ε1 ∩ ε2)? Pr(ε1) = 6 36 Pr(ε2) = 1 6 Pr(ε1|ε2) = 2 6 Pr(ε1 ∩ ε2) = 2 36 IV054 1. Basics of Probability Theory 20/62 EXAMPLE 2 Three coins are given - two fair ones and in the third one heads land with probability 2/3, but we do not know which one is not fair one. When making an experiment and flipping all coins let the first two come up heads and the third one comes up tails. What is probability that the first coin is the biased one? Let εi be the event that the ith coin is biased and B be the event that three coins flips came up heads, heads, tails. Before flipping coins we have Pr(εi ) = 1 3 for all i. After flipping coins we have Pr(B|ε1) = Pr(B|ε2) = 2 3 1 2 1 2 = 1 6 Pr(B|ε3) = 1 2 1 2 1 3 = 1 12 and using Bayes’ law we have Pr(ε1|B) = Pr(B|ε1)Pr(ε1) 3 i=1 Pr(B|εi )Pr (εi ) = 1 6 · 1 3 1 6 · 1 3 + 1 6 · 1 3 + 1 12 · 1 3 = 2 5 Therefore, the above outcome of the three coin flips increased the likelihood that the first coin is biased from 1/3 to 2/5 IV054 1. Basics of Probability Theory 21/62 THEOREM Let A and B be two events and let Pr(B) = 0. Events A and B are independent if and only if Pr(A|B) = Pr(A). Proof Assume that A and B are independent and Pr(B) = 0. By definition we have Pr(A ∩ B) = Pr(A) · Pr(B) and therefore Pr(A|B) = Pr(A ∩ B) Pr(B) = Pr(A) · Pr(B) Pr(B) = Pr(A). Assume that Pr(A|B) = Pr(A) and Pr(B) = 0. Then Pr(A) = Pr(A|B) = Pr(A ∩ B) Pr(B) and multiplying by Pr(B) we get Pr(A ∩ B) = Pr(A) · Pr(B) and so A and B are independent. IV054 1. Basics of Probability Theory 22/62 SUMMARY The notion of conditional probability, of A given B, was introduced in order to get an instrument for analyzing an experiment A when one has partial information B about the outcome of the experiment A before experiment has finished. We say that two events A and B are independent if the probability of A is equal to the probability of A given B, Other fundamental instruments for analysis of probabilistic experiments are random variables as functions from the sample space to R, and expectation of random variables as the weighted averages of the values of random variables. IV054 1. Basics of Probability Theory 23/62 MONTY HALL PARADOX Let us assume that you see three doors D1, D2 and D3 and you know that behind one door is a car and behind other two are goats. Let us assume that you get a chance to choose one door and if you choose the door with car behind the car will be yours, and if you choose the door with a goat behind you will have to milk that goat for years. Which door you will choose to open? IV054 1. Basics of Probability Theory 24/62 Let us now assume that you have chosen the door D1. and let afterwords a moderator comes who knows where car is and opens one of the doors D2 or D3, say D2, and you see that the goat is in. Let us assume that at that point you get a chance to change your choice of the door. Should you do that? IV054 1. Basics of Probability Theory 25/62 Let C1 denote the event that the car is behind the door D1. Let C3 denote the event that the car is behind the door D3. Let M2 denote the event that moderator opens the door D2. Let us assume that the moderator chosen a door at random if goats were behind both doors he could open. In such a case we have Pr[C1] = 1 3 = Pr[C3], Pr[M2|C1] = 1 2 , Pr[M2|C3] = 1 Then it holds Pr[C1|M2] = Pr[M2|C1]Pr[C1] Pr[M2] = Pr[M2|C1]Pr[C1] Pr[M2|C1]Pr[C1] + Pr[M2|C3]Pr[C3] = 1/6 1/6 + 1/3 = 1 3 Similarly Pr[C3|M2] = Pr[M2|C3]Pr[C3] Pr[M2] = Pr[M2|C3]Pr[C3] Pr[M2|C1]Pr[C1] + Pr[M2|C3]Pr[C3] = 1/3 1/6 + 1/3 = 2 3 IV054 1. Basics of Probability Theory 26/62 RANDOM VARIABLES - INFORMAL APPROACH A random variable is a function defined on the elementary events of a probability space and having as values real numbers. Example: In case of two tosses of a fair six-sided dice, the value of a random variable V can be the sum of the numbers on te two top spots on the dice rolls. The value of V can therefore be an integer from the interval [2, 12]. A random variable V with n potential values v1, v2, . . . , vn is characterized by a probability distribution p = (p1, p2, . . . , pn), where pi is probability that V takes the value vi . The concept of random variable is one of the most important of modern science and technology. IV054 1. Basics of Probability Theory 27/62 INDEPENDENCE of RANDOM VARIABLES Definition Two random variables X, Y are called independent random variables if x, y ∈ R ⇒ PrX,Y (x, y) = Pr[X = x] · Pr[Y = y] IV054 1. Basics of Probability Theory 28/62 EXPECTATION – MEAN of RANDOM VARIABLES Definition: The expectation (mean or expected value) E[X] of a random variable X is defined as E[X] = ω∈Ω X(ω)PrX (ω). Properties of he mean for random variabkes X and Y and a constant c: E[X + Y ] = E[X] + E[Y ]. E[c · X] = c · E[X]. E[X · Y ] = E[X] · E[Y ], if X, Y are independent The first of the above equalities is known as linearity of expectations. It can be extended to a finite number of random variables X1, . . . , Xn to hold E[ n i=1 Xi ] = n i=1 E[Xi ] and also to any countable set of random variables X1, X2, . . . to hold: If ∞ i=1 E[|Xi |] < ∞, then ∞ i=1 |Xi | < ∞ and E[ ∞ i=1 Xi ] = ∞ i=1 E[Xi ]. IV054 1. Basics of Probability Theory 29/62 EXPECTATION VALUES For any random variable X let RX be the set of values of X. Using RX one can show that E[X] = x∈RX x · Pr(X = x). Using that one can show that for any real a, b it holds E[aX + b] = x∈RX (ax + b)Pr(X = x) = a x∈RX x · Pr(X = x) + b x∈RX Pr(X = x) = a · E[X] + b The above relation is called weak linearity of expectation. IV054 1. Basics of Probability Theory 30/62 INDICATOR VARIABLES A random variable X is said to be an indicator variable if X takes on only values 1 and 0. For any set A ⊂ S, one can define an indicator variable XA that takes value 1 on A and 0 on S − A, if (S, Pr) is the underlying probability space. It holds: EPr[XA] = s∈S XA(s) · Pr({s}) = s∈A XA(s) · Pr({s}) + s∈S−A XA(s) · Pr({s}) = s∈A 1 · Pr({s}) + s∈S−A 0 · Pr({s}) = s∈A Pr({s}) = Pr(A) IV054 1. Basics of Probability Theory 31/62 VARIANCE and STANDARD DEVIATION Definition For a random variable X variance VX and standard deviation σX are defined by VX = E((X − EX)2 ) σX = √ VX Since E((X − EX)2 ) = E(X2 − 2XEX + (EX)2 ) = = E(X2 ) − 2(EX)2 + (EX)2 = = E(X2 ) − (EX)2 , it holds VX = E(X2 ) − (EX)2 Example: Let Ω = {1, 2, . . . , 10}, Pr(i) = 1 10 , X(i) = i; Y (i) = i − 1 if i ≤ 5 and Y (i) = i + 1 otherwise. EX = EY = 5.5, E(X2 ) = 1 10 10 i=1 i2 = 38.5, E(Y 2 ) = 44.5; VX = 8.25, VY = 14.25 IV054 1. Basics of Probability Theory 32/62 TWO RULES For independent random variables X and Y and a real number c it holds V(cX) = c2 V(X); σ(cX) = cσ(X) V(X + Y ) = V(X) + V(Y ). σ(X + Y ) = V (X) + V (Y ). IV054 1. Basics of Probability Theory 33/62 MOMENTS Definition For k ∈ N the k-th moment mk X and the k-th central moment µk X of a random variable X are defined as follows mk X = EXk µk X = E((X − EX)k ) The mean of a random variable X is sometimes denoted by µX = m1 X and its variance by µ2 X . IV054 1. Basics of Probability Theory 34/62 EXAMPLE I Each week there is a lottery that always sells 100 tickets. One of the tickets wins 100 millions, all other tickets win nothing. What is better: to buy in one week two tickets (Strategy I) or two tickets in two different weeks (Strategy II)? Or none of these two strategies is better than the second one? IV054 1. Basics of Probability Theory 35/62 EXAMPLE II With Strategy I we win (in millions) 0 with probability 0.98 100 with probability 0.02 With Strategy II we win (in millions) 0 with probability 0.9801 = 0.99 · 0.99 100 with probability 0.0198 = 2 · 0.01 · 0.99 200 with probability 0.0001 = 0.01 · 0.01 Variance at Strategy I is 196 Variance at Strategy II is 198 IV054 1. Basics of Probability Theory 36/62 PROBABILITY GENERATING FUNCTION The probability density function of a random variable X whose values are natural numbers can be represented by the following probability generating function (PGF): GX (z) = k≥0 Pr(X = k) · zk . Main properties GX (1) = 1 EX = k≥0 k · Pr(X = k) = k≥0 Pr(X = k) · (k · 1k−1 ) = GX(1). Since it holds E(X2 ) = k≥0 k2 · Pr(X = k) = k≥0 Pr(X = k) · (k · (k − 1) · 1k−2 + k · 1k−1 ) = GX(1) + GX(1) we have VX = GX (1) + GX (1) − (GX (1))2 . IV054 1. Basics of Probability Theory 37/62 AN INTERPRETATION Sometimes one can think of the expectation E[Y ] of a random variable Y as the ”best guess” or the ”best prediction” of the value of Y . It is the ”best guess” in the sense that among all constants m the expectation E[(Y − m)2 ] is minimal when m = E[Y]. IV054 1. Basics of Probability Theory 38/62 WHY ARE PGF USEFUL? Main reason: For many important probability distributions their PGF are very simple and easy to work with. For example, for the uniform distribution on the set {0, 1, . . . , n − 1} the PGF has form Un(z) = 1 n (1 + z + . . . + zn−1 ) = 1 n · 1 − zn 1 − z . Problem is with the case z = 1. IV054 1. Basics of Probability Theory 39/62 PROPERTIES of GENERATING FUNCTIONS Property 1 If X1, . . . , Xk are independent random variables with PGFs G1(z), . . . , Gk (z), then the random variable Y = k i=1 Xi has as its PGF the function G(z) = k i=1 Gi (z). Property 2 Let X1, . . . , Xk be a sequence of independent random variables with the same PGF GX (z). If Y is a random variable with PGF GY (z) and Y is independent of all Xi , then the random variable S = X1 + . . . + XY has as PGF the function GS (z) = GY (GX (z)). IV054 1. Basics of Probability Theory 40/62 IMPORTANT DISTRIBUTIONS Two important distributions are connected with experiments, called Bernoulli trials, that have two possible outcomes: success with probability p failure with probability q = 1 − p Coin tossing is an example of a Bernoulli trial. 1. Let values of a random variable X be the number of trials needed to obtain a success. Then Pr(X = k) = qk−1 p Such a probability distribution is called the geometric distribution and such a variable geometric random variable. It holds EX = 1 p VX = q p2 G(z) = pz 1 − qz 2. Let values of a random variable Y be the number of successes in n trials. Then Pr(Y = k) = n k pk qn−k Such a probability distribution is called the binomial distribution and it holds EY = np VY = npq G(z) = (q + pz)n IV054 1. Basics of Probability Theory 41/62 and also EY 2 = n(n − 1)p2 + np IV054 1. Basics of Probability Theory 42/62 BERNOULLI DISTRIBUTION Let X be a binary random variable (called usually Bernoulli or indicator random variable) that takes value 1 with probability p and 0 with probability q = 1 − p, then it holds E[X] = p VX = pq G[z] = q + pz. IV054 1. Basics of Probability Theory 43/62 BINOMIAL DISTRIBUTION revisited Let X1, . . . , Xn be random variables having Bernoulli distribution with the common parameter p. The random variable X = X1 + X2 + . . . + Xn has so called binomial distribution denoted B(n, p) with the density function denoted B(k, n, p) = Pr(X = k) = n k pk q(n−k) IV054 1. Basics of Probability Theory 44/62 POISSON DISTRIBUTION Poisson distribution Let λ ∈ R>0 . The Poisson distribution with the parameter λ is the probability distribution with the density function p(x) = λx e−λ x! , for x = 0, 1, 2, ... 0, otherwise For large n the Poisson distribution is a good approximation to the Binomial distribution B(n, λ n ) Property of a Poisson random variable X: E[X] = λ VX = λ G[z] = eλ(z−1) IV054 1. Basics of Probability Theory 45/62 EXPECTATION+VARIANCE OF SUMS OF RANDOM VARIABLES Let Sn = n i=1 Xi where each Xi is a random variable which takes on value 1 (0) with probability p (1 − p = q). It clearly holds E(Xi ) = p E(X2 i ) = p E(Sn) = E( n i=1 Xi ) = n i=1 E(Xi ) = np E(S2 n ) = E(( n i=1 Xi )2 ) = E( n i=1 X2 i + i=j Xi Xj ) = = n i=1 E(X2 i ) + i=j E(Xi Xj ) IV054 1. Basics of Probability Theory 46/62 Hence E(S2 n ) = E(( n i=1 Xi )2 ) = E( n i=1 X2 i + i=j Xi Xj ) = = n i=1 E(X2 i ) + i=j E(Xi Xj ) and therefore, if Xi , Xj are pairwise independent, as in this case, E(Xi Xj ) = = E(Xi )E(Xj ) Hence E(S2 n ) = np + 2 n 2 p2 = np + n(n − 1)p2 = np(1 − p) + n2 p2 = n2 p2 + npq VAR[Sn] = E(S2 n ) − (E(Sn))2 = n2 p2 + npq − n2 p2 = npq IV054 1. Basics of Probability Theory 47/62 MOMENT INEQUALITIES The following inequality, and several of its special cases, play very important role in the analysis of randomized computations: Let X be a random variable that takes on values x with probability p(x). Theorem For any λ > 0 the so called kth moment inequality holds: Pr [|X| > λ] ≤ E(|X|k ) λk Proof of the above inequality; E(|X|k ) = x∈X |x|k p(x) ≥ |x|>λ |x|k p(x) ≥ ≥ λk |x|>λ p(x) = λk Pr [|X| > λ] IV054 1. Basics of Probability Theory 48/62 Two important special cases - I.1 of the moment inequality; Pr [|X| > λ] ≤ E(|X|k ) λk Case 1 k → 1 λ → λE(|X|) Pr [|X| ≥ λE(|X|)] ≤ 1 λ Markov s inequality Case 2 k → 2 X → X − E(X), λ → λ V (X) Pr |X − E(X)| ≥ λ V (X) ≤ E((X − E(X))2 ) λ2V (X) = = V (X) λ2V (X) = 1 λ2 Chebyshev s inequality Another variant of Chebyshev’s inequality: Pr[|X − E(X)| ≥ λ] ≤ V (X) λ2 and this is one of the main reasons why variance is used. IV054 1. Basics of Probability Theory 49/62 Two important special cases - I.2 The following generalization of the moment inequality is also of importance: Theorem If g(x) is non-decreasing on [0, ∞), then Pr [|X| > λ] ≤ E(g(X)) g(λ) As a special case, namely if g(x) = etx , we get: Pr [|X| > λ] ≤ E(etX ) etλ basic Chernoff s inequality Chebyshev’s inequalities are used to show that values of a random variable lie close to its average with high probability. The bounds they provide are called also concentration bounds. Better bounds can usually be obtained using Chernoff bounds discussed in Chapter 5. IV054 1. Basics of Probability Theory 50/62 FLIPPING COINS EXAMPLES on CHEBYSHEV INEQUALITIES Let X be a sum of n independent fair coins and let Xi be an indicator variable for the event that the i-th coin comes up heads. Then E(Xi ) = 1 2 , E(X) = n 2 , Var[Xi ] = 1 4 and Var[X] = Var[Xi ] = n 4 . Chebyshev’s inequality Pr[|X − E(X)| ≥ λ] ≤ V (X) λ2 for λ = n 2 gives Pr[X = n] ≤ Pr[|X − n/2| ≥ n/2] ≤ n/4 (n/2)2 = 1 n IV054 1. Basics of Probability Theory 51/62 THE INCLUSION-EXCLUSION PRINCIPLE Let A1, A2, . . . , An be events – not necessarily disjoint. The Inclusion-Exclusion principle, that has also a variety of applications, states that Pr n i=1 Ai = n i=1 Pr (Ai) − i