Prologue CZ.1.07/2.2.00/28.0041 Centrum interaktivních a multimediálních studijních opor pro inovaci výuky a efektivní učení evropský sociální soaaini ^h^h ministerstvo školství, opvzdsiavanr v*^^< fondVCR EVROPSKÁ UNIE MLÁDEŽE A TĚLOVÝCHOVY pro konkurenceschopnost ,*4JÍA'»*' INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ You should spent most of your time thinking about what you should think about most of your time. 2/72 RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 WEB PAGE of the LECTURE RANDOMIZED ALGORITHMS AND PROTOCOLS - 2020 Prof. Jozef Gruska, DrSc Wednesday, 10.00-11.40, B410 http://www.f i.muni.cz/usr/gruska/random20 FINAL EXAM: You need to answer four questions out of five given to you. CREDIT (ZAPOČET): 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ška PhD Language English NOTE: Exercises/tutorials are not obligatory 5/72 CONTENTS - preliminary 0 EE! Basic concepts and examples of randomized algorithms Types and basic design methods for randomized algorithms Basics of probability theory Simple methods for design of randomized algorithms Games theory and analysis of randomized algorithms Basic techniques I: moments and deviations Basic techniques II: tail probabilities inequalities Probabilistic method I: Markov chains - random walks Algebraic techniques - fingerprinting Fooling the adversary - examples Randomized cryptographic protocols Randomized proofs Probabilistic method II: Quantum algorithms 6/72 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. Hromkovic: Design and analysis of randomized algorithms, Springer, 275 pages, 2005 N. Alon, J. H. Spencer: The probabilistic method, Willey-lnterscience, 2008 Part I WHICH IS THE MOST BEAUTIFUL EQUATION? e,7r + 1 = 0 IV054 1. Probabilistic Method 9/72 How to prove that some object exists? HOW TO PROVE THAT SOME OBJECT EXISTS? To develop a constructive method (and to show its correctness) how to find or design such an object - a constructive approach To prove that probability that such an object exists is positive - a non constructive approach. IV054 1. Probabilistic Method 10/72 Chapter 8. PROBABILISTIC METHOD EXAMPLE The probabilistic method is a powerful tool to demonstrate the existence of some combinatorial objects. In some cases this method can be used also to derive an algorithm for finding such an object. Two basic approaches of the probabilistic method: □ The expectation approach: Any random variable V assumes at least one value that is not smaller than its expectation EV, and at least one value that is not greater than its expectation EV. B The sampling approach: If an object chosen randomly from a universe/set U satisfies a property P with a positive probability, then there must be an object in U that satisfies the property P. The above two simple ideas have a surprising power. Their power comes from our ability to reformulate, in various ways, so called counting arguments in the language of probability and then to apply various tools of the probability theory. Example: One can show that for every n x n 0-1-matrix A, and for any randomly chosen vector b £ { — 1, +1}", it holds \\Ab\\ < 4Vn In n with probability at least 1 — -n. From that we may conclude that for every such a matrix A, there always exists a vector b £ {-1, +1}" such that \\Ab\\ < Wnlnn. IV054 1. Probabilistic Method 11/72 IV054 1. Probabilistic Method 12/72 LIMITS of PROBABILISTIC METHODS Probabilistic method is especially useful in case we can show that the probability is quite large that the object we look for exists and we can quite easily verify whether the random process we will create indeed found such an object. If such a probability is indeed large then we can find such an object quite efficiently just by applying a random searching process - a sampling experiment. In some cases, however, no explicit construction of a combinatorial object is known yet, in spite of the fact that we can show that such object exists. IV054 1. Probabilistic Method 13/72 EXAMPLE Example Using the probabilistic method it can be shown that for any n there exists a sorting network that sorts n integers in parallel in O(log n) time. A method is known to construct for any n a sorting network that sorts n integers in parallel in O(log2 n) time. Mo method is known to construct for any n a sorting network that could sort n integers in parallel in O(logn) time. In spite of many efforts to do that during the last 25 years. IV054 1. Probabilistic Method 14/72 BASIC IDEA and an EXAMPLE EXAMPLE - MAX-CUT PROBLEM Probabilistic method consists of two stages. □ A so called "thought experiment" is designed in which a carefully chosen random process (called usually as an experiment - for example, a dice tossing) P plays a key role. H The random process P is then analyzed and some conclusions are made that are, or at least look as, independent of the experiment £. IV054 1. Probabilistic Method 15/72 Problem: Given is an undirected graph G — (V, E) with n — \ V\ vertices and m — \E\ edges. The task is to partition vertices of V into two sets A and B in such a way that maximizes the number of such edges (u, v), where u £ A, v £ B. Theorem: For any undirected graph G — (V, E) with n vertices and m edges, there is a partition of the vertex set V into two sets A and B such that \{(u, v)£E\u£A,v£B}\>^. Proof: Let us consider the following experiment: Each vertex of G is independently and equiprobably assigned to either A or B. For any edge (u, v), the probability that its end-vertices are in different sets is |. By linearity of expectations, the expected number of edges with end-vertices in different sets is thus t . , m E[cut-sizeJ = —. That implies that there must be a partition satisfying the theorem. IV054 1. Probabilistic Method 16/72 DERANDOMIZATIO N In some cases the proof of existence, of an object , obtained by the probabilistic method can be converted into an efficient randomized algorithm to find 0. In some other cases the existence proof obtained by the probabilistic method can be converted even to an efficient deterministic algorithm to find a desirable object 0- such a process is called derandomization. IV054 1. Probabilistic Method 17/72 FROM THE PROOF of EXISTENCE to LAS VEGAS ALGORITHM for MAX-CUT PROBLEM We show how to transform the argument from slide #4 about the existence of a partition with at least ^ of edges to a Las Vegas algorithm. Let us design a partition C(A, B) using randomization described above and denote p = Pr(C(A, B) < |) Then = E[C(A,B)] = J2 iPr{C{A,B) = i)+ £ iPr{C{A, B) = /) > (1 - p) - + 1 which implies that P> m/2+1 The expected number of samples before finding a cut with value at least ^ is therefore - + 1 2 -r x. Since we can test in polynomial time whether the value of the cut determined by a particular sample is at least m/2, by counting edges crossing the cut, we have a Las Vegas algorithm to find a cut. IV054 1. Probabilistic Method 18/72 ASSIGNMENT of HATS - I. ASSIGNMENT of HATS - II. There are n robots in a field and each of them can see only k other robots - n, k are fixed. Each robot wants to have a hat and a robot can be happy only if she has a hat and none of robots she sees has a hat. How many robots can be happy? There are n robots in a field and each of them can see only k other robots for fixed n, k. Each robot wants to have a hat and a robot can be happy only if she has a hat and none of robots she sees has a hat. How many robots can be happy? Experiment: Let us give to each robot a hat with a probability p. Then the probability that any particular robot is happy is p(l — p)k. If Xr is the indicator variable for the event that robot number r is happy, then E[Xr] = p(l — p)k and the expected number of happy robots is np(l — p)k and so there has to be a specific assignment of hats that so many robots are happy. Next task is to find such a p that maximizes the value np(l — p)k. From the equation d dp (np(l - p)k) = 0 we get p — l/(k + l).For this p and large k, the expected number of hats is np(l -p)k = n k + 1 k+1 < {k + l)ek IV054 1. Probabilistic Method 19/72 IV054 1. Probabilistic Method 20/72 HAMILTON IAN PATHS in TOURNAMENTS NUMBER of PATHS in TOURNAMENTS A tournament is a complete directed graph. A Hamiltonian path in a graph G — (V, E) is a path that visits each vertex (representing a player) of V exactly once. Theorem: For any n there exists a tournament of size n with the number of Hamiltonian paths equal to n!/2n_1. Proof: Generate a random tournament T — (V, E), V — {1,..., n}, by randomly choosing direction for all edges of Kn - of a complete graph of n vertices. Theorem: Every tournament has a Hamiltonian path. For each permutation a on V let Xa be a random variable defined as follows: Proof will be by the induction on the number n of vertices in a tournament. Induction step. Suppose that every tournament with at most n vertices has a Hamiltonian path and let a tournament T — (V, E) with n + 1 vertices be given. ^ ( 1, if a describes a Hamiltonian path on T a y 0 otherwise For all g, Pr(XCT = 1) = (i)"-1 = E[XCT]. Choose any vertex v and define two sets of vertices Let X be a random variable counting the number of Hamiltonian paths in T A = {u\(u,v) £ £} B — {u \ (v, u) £ E}. x= E Two subgraphs induced by these two sets of vertices form tournaments. By induction both of them have Hamiltonian paths. crePerm(n) Theorem now follows from the following calculations: By connecting these two paths through the node v we get a Hamiltonian path for the tournament T. a a IV054 1. Probabilistic Method 21/72 IV054 1. Probabilistic Method 22/72 TOURNAMENTS WITH a PROPERTY Sk EXPLANATION In a tournament, if there is an edge from a node A to a node B, then we say that the player A beats the player B. A tournament T is said to have property Sk, for an integer k, if for any set of k players there is one player that beats all of them. Theorem If (")(1 — 2~k)"~k < 1, then there is a tournament on n vertices with property K Sk- Proof Consider a random tournament with a set of n nodes. For any subset K of k vertices let Ak be the event that there is no player/node that beats all players/nodes in K. Clearly, Pr[AK} = (l-2-k)"-k. Therefore If AC is a set on k players, then the probability that a player P not in K beats all of them is 2~k and the probability is 1 — 2~k that he does not beat all of them. Since there are n — k players outside the group K, the probability that none of them beats all players in AC is (1 — 2~k)n~k. Pr[ V A"l< E Pr[AK] = (nk)(l-2-ky-k \ what implies that E[Z,] > \ for all /. If A achieves a performance ratio a, we say that A is an n-approximation algorithm. The expected number of clauses satisfied by a random assignment is If A is a randomized algorithm, then m/\(/) is a random variable and in such a case m/\(/) m m is replaced by E[m/\(/)] in the definition of the performance ratio. ErEz'] = EErz']>f Therefore, there exists at least one assignment for which ^' — T- IV054 1. Probabilistic Method 25/72 IV054 1. Probabilistic Method 26/72 FROM a PROOF of EXISTENCE to an ALGORITHM - II. BASIC IDEA We now show the existence of a randomized algorithm for MAXSAT with performance ratio |. The procedure in the proof of the last theorem actually yields a randomized algorithm is similar as in the case of the global wiring problem. whose guaranteed performance is 1 — 2~k, provided every clause contains at least k □ Reformulate the problem as a 0-1 linear programming problem. literals. El Solve the corresponding rational linear programming problem. As a consequence, we have a randomized ^-approximation algorithm for instances of □ Use the randomized rounding technique. MAX-SAT in which every clause contains at least 2 literals. Notation: With each clause Cj, in the given input formula, we associate We now show another algorithm that performs especially well when there are (many) clauses consisting of a single literal. an indicator variable Cj e {0,1}, that indicates whether or not the clause Q is satisfied at the algorithm being used. Finally, we show that on any input instance, one of the two designed algorithms yields a randomized |-approximation algorithm. IV054 1. Probabilistic Method 27/72 IV054 1. Probabilistic Method 28/72 INDICATOR VARIABLES 0-1 linear programming reformulation of the MAX-SAT problem. Find v,,CjG {0,1} (V/,j) (*) such that the sum Moreover, to each variable x, we assign an indicator variable v, defined by x, = true •<=>• v,■ — 1 Cj~ - set of indices of variables that appear uncomplemented in Q Cy - set of indices of variables that appear complemented in C, is maximized and £>+ £(1-„,)><:; (Vj). (1) ,ec; ,ecr Rational linear programming problem is then obtained by replacing the condition (*) by the condition Vi, q e [0, l] (v/,j). Let vi (c,) be the value of variable v, (c,) obtained by solving the rational linear programming problem. Clearly, Y^l-i CJ — Ylj-i IV054 1. Probabilistic Method 29/72 IV054 1. Probabilistic Method 30/72 CONTINUATION of THE PROOF 1/2 CONTINUATION of THE PROOF 2/2 Lemma: Let Q be a clause with k literals. The probability that it is satisfied by the randomized rounding is at least flkCj > (1 — Proof: Without loss of generality we can assume that We first show that using the randomized rounding method we obtain a truth assignment for which the expected number of satisfied clauses is at least (i-i)E^-j This will follow from the Lemma shown on the next slide for the case we use the following randomized rounding: each v, is set, independently, to 1 with the probability v,. Cj : xi V ■ ■ ■ V Xk By constrain (1) v\ + ■ ■ ■ + Qk > q. Observe that the clause Cj remains unsatisfied by randomized rounding method only if every variable v, is rounded to 0. Since each variable is rounded fully independently, this occurs with probability Notation: For an integer k denote (3k — 1 — (1 — j)k> 1 — ^- na-fc). It remains to show that k i - n (i - > pkq i=l C: left side is minimized if v;=-f-1 k IV054 1. Probabilistic Method 31/72 IV054 1. Probabilistic Method 32/72 Again: It remains to show that 1-TJ(1-P,-) > (3kq C: andtheleftsideisminimizedifv;= ' k k 1 - Tk This can be shown if one can show that 1 - (1 - j)k > /3kc for all 0 < z < 1. 1 0.5 1.0 2 0.75 0.75 Since function f(x) = 1 — (1 — j)k is concave, it suffices to verify the above inequality 3 0.875 0.704 for x — 0 and x — 1 what is easy. 4 0.938 0.684 5 0.969 0.672 IV054 1. Probabilistic Method 33/72 FINAL RESULT From the last Lemma, and from the linearity of expectations, it follows: Theorem: Given an instance of MAX-SAT, the expected number of clauses satisfied by linear programming and randomized rounding is at least (1 — j) time the maximum number of clauses that can be satisfied on that instance. Comparison of performances of our two algorithms for MAX-SAT We now show that on any instance one of the algorithms is a | - approximation algorithm for the MAX-SAT problem: IV054 1. Probabilistic Method 34/72 FINAL RESULT II Theorem: iax{ni,n2} > jJ2q. Let /7i denote the expected number of clauses that are satisfied when each variable is independently set to 1 with probability \ (what corresponds to the first algorithm). Let A72 denote the expected number of clauses that are satisfied when we use the linear programming followed by the randomized rounding (what corresponds to the second algorithm). Proof: It suffices to show that {^^) > f ]T. q. Let Sk denote the set of clauses that contain k literals. We know that "i = £ £ (X - 2-*)<5 >££(!- 2-*)*;, k Cj€Sk k Cj€Sk "2 > £ ^cj. k C:GSk Thus rti + n2 >££ (l-2-k) + f3k 2 - 2 k CjGSk Since (1 - 2~k) + /3k > § for all k, we get "1 + ^2 ^ 3 ~ 3 k qeSk 2 ^4££^=4£3- IV054 1. Probabilistic Method 35/72 IV054 1. Probabilistic Method 36/72 RAMSEY NUMBER PROBLEM The Ramsey number R(k, I) is the smallest integer n such that in any 2-coloring of the edges of a complete graph Kn, on n nodes, by red and blue, there either is a red subgraph (i.e. a complete subgraph on k vertices with edges coloured red), or there is a blue subgraph K\. Ramsey (1930) showed that R(k, I) is finite for any two integers k and /. We use the probabilistic method to show a lower bound on R(k, k). IV054 1. Probabilistic Method 37/72 A LOWER BOUND on RAMSEY NUMBERS Theorem: If (£) ■ 2^(2) < 1, then R(k, k) > n. Corollary Since (£) ■ 21 (2) < 1 for n — 2k/2 (that is if k — 2\gn), the above theorem implies that/?(/c, k) > 2k/2 for all k>3. Proof of Theorem: Let n, k satisfy the assumption of the theorem. Consider a random 2-coloring of the edges of Kn by red or blue. For any fixed set R of k vertices, let Ar be the event that the induced subgraph of Kn on R is monochromatic (i.e. that either all its edges are red or they are all blue). Clearly, P/-(/4r) = 2-rpr = 2^(2). Since there are possible choices for R, the probability that at least one of the events Ar occurs is at most (^)21—(2) < 1. Thus, with a 'positive probability, no event Ar occurs and therefore there is a 2-coloring of Kn without a monochromatic Kk, that is, R(k, k) > n. Note that if k > 3 and n — [2k/2\, then k) k\ 2fc2/2 < and hence R(k, k) > 2k/2 for all k>3. IV054 1. Probabilistic Method 38/72 ALGORITHMIC CONSEQUENCES A CONSEQUENCE Last theorem implies that there is an edge two-coloring of Kn without a monochromatic K2ig2n- It is therefore natural to ask whether we can find efficiently such a coloring. n (2) Since there are 2 possible colorings, an exhaustive search cannot be efficient. However, a closer look at the proof of the last theorem shows that the proof can be used to produce effectively a coloring that is very likely to be good. This is due to the fact for large k if n = [2k/2\, then n i-(0) 9i+| (n)2 2 isb- PROOF. BASIC IDEA: In points are chosen randomly in the unit square. All triangles created by these points are tested and those that are "too small" are eliminated - by deleting one vertex from each of them until only n of nodes are left. The idea is that this way we will be left with enough points, and with no too-small-area triangle. IV054 1. Probabilistic Method 43/72 IV054 1. Probabilistic Method 44/72 MIN-MAX TRIANGLE PROBLEM - II. PROOF Choose uniformly In points in the unit square. For points p, q, r let A(p, q, r) denote the area of the triangle these points create. For any real numbers 0 < b and Ab < 1 it holds Pr[b <\\p- q\ \ < b + Ab] < Tr(b + Abf -irb2 = 2-nbAb + Tr(Ab)2, where ||p — q\\ denote the Euclidean distance between p and q. (Observe that inequality follows from the fact that rings with radiuses b and b + Ab and centre in p may not be completely contained in the unit square.) Let (p, q) be the base of the triangle (p, q, r) and let ||p — q|| = b. IV054 1. Probabilistic Method 45/72 MIN-MAX TRIANGLE PROBLEM - III. We show now how to estimate Pr[/4(p, q, r) < e] for any e > 0 and p.q.r. Such an event happens when the height h of the triangle is < ^ and therefore r is not farther than ^ from the line of points p and q. The probability that this happens is less than because r has to be in a strip of width and length less than a/2- Hence, Pr[A(p, q, r) < e] C^2 2e / Pr[b < ||p - q|| < b + Ab] x Pr[triangle. h. < —] Jb=o " 2V2e < b=0 V2 -AirbAb — 167re. b=0 IV054 1. Probabilistic Method 46/72 MIN-MAX TRIANGLE PROBLEM - IV MIN-MAX TRIANGLE PROBLEM - V. Let us now compute the expected number of triangles with the area < e — jtj^. Let 5' be a set of In points uniformly distributed in the unit square. For each triple (pi, q,, r,) in 5' let XPhqhn be the indicator variable having value 1 if the area of the triangle determined by (p,, q,, r,) is less than e = 105^2 ■ The probability that the area of some specific triangle is less than 's 'ess than 16tt ^ 0.6 lD7re = ... „ < If X denotes the number of triangles with area less than -r^n, then 0 irir)nz ' E[X] = ElX™,n] < ( \0.6n-2< 3 lOOn2 - n2 This is also the expected value of XPhqhn. Finally, by throwing away an arbitrary vertex from each of such "small area triangles", we are left with a new set 5" of points the expected size of which (of S"), is not less than n, in which no small-area-triangles exist. Therefore, there exists a set S", of size n, such that T(S") > 7755-2 ■ IV054 1. Probabilistic Method 47/72 IV054 1. Probabilistic Method 48/72 EXAMPLE - INDEPENDENT SETS OF VERTICES PROOF Create a set S C V by putting into S each vertex independently with probability p (to be We show a lower bound on the size of the largest independent set of vertices in certain specified later). It therefore holds for the average size of S that: E[|S|] = np. Let Gs be graphs. the subgraph of G — (V, E), induced by S. Definition An independent set of a graph G — (V, E) is a subset of vertices of V such For any e £ E let Ye be the indicator variable that has value 1 if e £ E(G$) - the set of that no two vertices in the set are adjacent. Denote by a(G) the size of the largest edges of Gs - and 0 otherwise. independent set of vertices of the graph G. E[ye] = p2 because an edge belongs to E(Gs) iff both if its endpoints are in S, what Our aim is to prove the following lower bound (for any integer k): happens with probability p2. Let Y — \E(Gs)\. It holds Theorem If \V\ = n and \E\ = nk/2 for a graph G = (V, E), then a(G) > fk. e€E e€E Proof ideas: After deleting all edges from Gs, by dropping a vertex from each of such edges, it ■ To choose randomly a subset of vertices that would be a candidate for an remains a set S* of the expected size E[|S*|] = E[|S| — V], and therefore independent set. ■ To show, using the probabilistic argument, that there is a subset of the chosen set of E[|S|-Y] = E[|S|]-E[Y] = np-^p2. vertices that has many more vertices than edges. The last expression has the largest value for p = j and in such a case ■ By deleting one vertex from each of such edges, an independent set is produced. E[|S*|] = E[|S|-Y] = ^. IV054 1. Probabilistic Method 49/72 IV054 1. Probabilistic Method 50/72 EXPANDING GRAPHS Informally, an expanding graph is a graph in which the number of neighbors of any Theorem: There is an integer no such that for all n > no there is an (n, 18, |,2) OR-concentrator. sufficiently small set of vertices S is larger than c\S\ for some positive constant c > 1. Proof: The first part of the proof will be for all (n, d, c, a) OR-concentrators. OR-concentrators are a special type of expanding graphs. Consider a random bipartite graph with two disjoint sets of vertices, L and R, each of n vertices, in which each vertex of L chooses randomly and independently d Definition:An (n, d, a, c) OR-concentrator is a bipartite multigraph G — (L, R, E) with vertices from R as neighbours. independent sets of vertices L and R, each of cardinality n, such that For any integer s let £s denote the event that a (bad) subset of s vertices of L has □ Every vertex in L has degree at most d; fewer than cs neighbours in R. B For any subset S of vertices from L such that |5| < an there are more than c\S\ We first derive an upper bound on Pr[£s], for any particular fixed s, and then we show neighbors in R. the upper bound on the sum of Pr[£s] over all s < an. This way we obtain a non-trivial For applications, it is usually desirable to have d as small and c as large as possible. upper bound on the probability that a random graph with parameters we seek, fails to be an OR-concentrator. Of particular interest is to study OR-concentrators in which a, c and d are constants fixed independently of n, with c > 1. Fix any subset S C L of size s, and any subset T C R of size cs. Finding an explicit construction of OR-concentrators is a non-trivial task. However, the probabilistic method can be used to show the existence of such concentrators. (There are ^ " ^ ways of choosing S, and ^ ^ ways of choosing T.) The probability that T contains all of at most ds neighbours of the vertices in S is (^)ds. IV054 1. Probabilistic Method 51/72 IV054 1. Probabilistic Method 52/72 The probability of the event that all ds edges going out from some s vertices of L fall within any cs vertices of R is bounded by Pr[&] < n \ f cs es I \ n Using the inequality ( " j < (^Y we obtain Pr[6] < n \ / cs cs I \ n < ne\s /ne s / \cs S\d-c-l n cs / cs \ ds e c IV054 1. Probabilistic Method 53/72 In a special case, for a — \ and s (1 + 6)(jl] < F+(/i, 5) < e-^ (Chapter 6, page 10), to obtain (for /i = n2,S — 1) that the probability that more than 2n2 of the algorithms in A are bad for 7r, is < e~. Let £>, denote the bad event that more than 2n2 algorithms in A are bad for ■k-,. Then, for n > 4 n! n! 2 Pr[|JB'] - £ PriBi) < n! e^T" < 1 (by Stirling's formula for n!) Therefore, with positive probability, not more than 2n2 algorithms in A are bad for any 7T,. Hence, there exists a subset of n3 algorithms from {Ai,..., An"} with the property that at most 2n2 in this subset are bad for any 7r,. Let us denote this subset B — {6,1;..., 6,n3}. B is an efficient routing scheme: for any 7T, a randomly chosen algorithm form B fails to route 7r, within 14n steps with probability at most H- — -■ n From that one can deduce that the expected number of steps using an algorithm randomly chosen from B is less than 15n. IV054 1. Probabilistic Method 61/72 IV054 1. Probabilistic Method 62/72 THE LOVASZ LOCAL LEMMA THE LOVASZ LOCAL LEMMA - MOTIVATION 1 This is one of the most elegant and useful tools to apply the probabilistic method. Suppose that we have a finite set A of bad events such that each of them may not happen with a non-zero probability. We want to show that under certain circumstances none of these events happen. This is easy to show for the case events are independent. Indeed, in such a case Pr P| A = Y\ PrM > °-[agA J AeA Lovasz Local lemma handle the situation for the case where events are generally not independent of each other, but each collection of events that are not independent of some particular event A has low total probability. The proof of the original version of Lovasz Local Lemma was non-constructive - it gave no guidance how to find a particular outcome that makes all the events false. Later, it has been shown that when events are determined by some underlying sets of independent variables and independence between two events is detected by having non-overlapping sets of underlying variables, an actual solution can be found in polynomial expected time. IV054 1. Probabilistic Method 63/72 IV054 1. Probabilistic Method 64/72 THE LOWASZ LOCAL LEMMA - SYMMETRIC VERSION In order to formulate so called symmetric version of the lemma we need the following definition of mutual independence. An event E is mutually independent of events Ei,..., En, if for any / C [l,n], Pr(^e\ Qe)j =Pr(e). Dependency between events can be represented in terms of a dependency graph. Definition: Dependency graph for a set of events E\,... ,E„ is a graph G — (V, E) such that V — {1,..., n} and for / = 1,..., n, the event E is mutually independent of the events {Ej\(i,j) £ E}. Lovasz Local Lemma Let E\,... ,E„ be events and p, d be fixed numbers such that ■ for all /, Pr(E) < p; ■ the degree of the dependency graph given by E\,... ,E„ is bounded by a cf; 4dp < 1. Then Pr(f)l1Ei) > 0. IV054 1. Probabilistic Method 65/72 APPLICATION - EDGE-DISJOINT PATHS ■ Assume that n pairs of users need to communicate using edge-disjoint paths, from a fixed set of paths, on a given network . ■ Assume that each /th pair of users can choose a path from a collection F-, of m paths for a fixed m. m We show, using simple version of Lovasz local lemma, that if possible paths do not share too many edges, then there is a way to choose n edge-disjoint paths connecting the n given pairs. Theorem: If, for a fixed k, any path in any F; shares edges with no more than k paths in any FjJ ^ i, and 8nk/m < 1, then there is a way to choose n edge-disjoint paths connecting the n given pairs. IV054 1. Probabilistic Method 66/72 PROOF of THEOREM THE LOVASZ LOCAL LEMMA - GENERAL CASE Let each /th pair chooses a path from F, randomly, with probability ^. Let Ejj be event that paths chosen by pairs / and j share at least one edge. Since for any / and j ^ i the path chosen from F, shares edges with at most k paths in any Fj,j ^ i, we have p=Pr(E}J)<^. Let d be the degree of the dependency graph of all events Ej. Since the event Ej is independent of all events E,/j/, when /' ^ {',_/} and j' ^ we have d < In. Since Adp < - < 1 m all conditions of the Lovasz local lemma are satisfied and therefore vQ 7 >0 and therefore there is such a choice of n paths that are edge-disjoint. Suppose we have n events each of which occur with probability at most |. Let each of these events corresponds to one of n ways in which a probabilistic experiment could fail. If the event were independent, we could then assert that at such an experiment with probability at least 2~", none of the events occurs. The Lovasz Local Lemma generalizes the above setting and result to the case where each of the events is independent of all but small number of other events. Lovasz Local Lemma: Let G — (V, E) be the dependency graph for events £i,... ,£„ in a probability space. Suppose that there exist x, £ [0,1], for 1 < / < n, such that prie] < n t1 - Then IV054 1. Probabilistic Method 61/12 ^rn^nt1-*')- IV054 1. Probabilistic Method 68/72 PAUL ERDOS THOUGHTS ABOUT ERDOS ■ Paul Erdos, a Hungarian mathematician, died in September 1996 at the age of 83. ■ He was the most prolific mathematicians of the twentieth century with over 1500 papers written and more than 490 collaborators. ■ He can be seen as the founder (in 1947) of the probabilistic method. ■ In our century, in which mathematics is so strongly dominating by "theory constructors" Erdos remained to be the "prince of problem solvers" and the "absolute monarch of problem posters/formulators". (E. Strauss) ■ Erdos had no job though he worked constantly. He had no home -the world was his home. Possessions were for him a nuisance, money a bore.He lived "on a web of trust", traveling from Center to Center, spreading his mathematical pollen (pel in Czech). His enormous talents and energies were given entirely to the "Temple of Mathematics". IV054 1. Probabilistic Method 69/72 IV054 1. Probabilistic Method 70/72 STORIES about ERDOS STORY about the BOOK ■ It is six in the morning. The house is sleeping. 1 prove and conjecture. Paul Erdos in a letter to Vera Sos ■ Story about The Book. Erdos liked to talk about The Book, that contains all theorems of mathematics and for each of them one proof -beautiful, aesthetic and insightful - so called The Book proof. Each time when some of his conjectures was resolved in "an ugly way" Erdos congratulated the prover, but added "let us now look for a Book proof. ■ In 1985 he started his lecture in a math camp by saying: "You do not have to believe in the God, but you should believe in The Book". IV054 1. Probabilistic Method 71/72 IV054 1. Probabilistic Method 72/72