Probabilistic Methods in Randomized Algorithms: Exploring Min-Cuts and Acute Triangles

Randomized Algorithms CS648 Lecture 20 Probabilistic Method (part 1) 1

PROBABILISTIC METHOD 2

Probabilistic methods Methods that use Probability theory Randomized algorithm to prove deterministic combinatorial results 3

PROBLEM 1 HOW MANY MIN CUTS ? 4

Min-Cut ? = (?,?) : undirected connected graph Definition (cut): A subset ? ? whose removal disconnects the graph. Definition (min-cut): A cut of smallest size. Question: How many cuts can there be in a graph? Question: How many min-cuts can there be in a graph? ?? ? ? 5

Algorithm for min-cut Min-cut(?): { Repeat ? ? times { Let ? ??; ? Contract(?,?). } return the edges of multi-graph ?; } Running time: ?(??) Question: What is the sample space of the output of the algorithm ? Answer: all-cuts of ?. 6

Analysis of Algorithm for min-cut Let ?be any arbitrary min-cut. Question: What is probability that ? is preserved during the algorithm ? Answer: 1 ? ?. 1 ? ? ? 3 ? 5.2 4.1 ? ?. 1 3 ? ? ? ? ? ? ?. ? ? ? ? 3 5.2 4.1 . = 3 = ? ? ?. ? ? 7

Number of min-cuts Let there be ? min-cuts in ?. Let these min-cuts be ??,??, ,??. Define event ?: output of the algorithm Min-cut(?) is ?? . P( ?) ? ? ?(? ?) P( ? ?) ? P( ?)+P( ?)+...P( ?) = ? P( ?) = ? ? ?(? ?) Surely P( ? ?) 1 ?(? ?) ? ? 8

PROBLEM 2 HOW MANY ACUTE TRIANGLES ? 9

How many acute triangles Problem Definition: There is a set ? of ??? points in plane and no three of them are collinear. How many triangles formed by these points are acute ? Answer: At most ??% Solution: Let ? : probability that a triangle formed by 3 random points from ? is acute. Total number of acute triangles All possible triangles using? points Show that ? ?.? ? = 10

? points Case 1: Sum of the four angles is???. at least one of them has to be 90 Hence, at least one of the four triangles is non-acute. 11

? points Case 2: Sum of the three angles at the center is???. at least two of these angles have to be > 90 at least 2 of the four triangles is non-acute. 12

? points ? points Lemma1: A triangle formed by selecting 3 points randomly uniformly from 4 points is acute triangle with probability at most ?.??. Lemma2: A triangle formed by selecting 3 points randomly uniformly from 5 points is acute triangle with probability at most ?.?. (Do it as a simple exercise using Lemma 1.) 13

Two stage sampling ?: a set of ? elements. ? ? ? Let ? be a uniformly random sample of ? elements from ?. Let ? be a uniformly random sample of ? elements from ?. Question: What can we say about (probability distribution of) ? ? Answer: ? is a uniformly random sample of ? elements from ?. (Do it as a simple exercise. It uses elementary probability) Can you use this answer to calculate? ? 14

Number of acute triangles ?: set of ? points. ? : probability that a triangle formed by 3 random points from ? is acute. ? = ? ? : a uniformly random sample of ? points from ?. ? : a uniformly random sample of ? points from ?. ? = P(a random triangle from ? is acute) // use previous slide and elementary prob. ? ?.?? 15

PROBLEM 3 SUM FREE SUBSET OF LARGE SIZE 16

Large subset that is sum-free Problem Definition: There is a set ? of ? positive integers. Aim is to compute a large subset ? ? such that there do not exist three elements ?,?,? ? such that ? + ? = ? How large can ? be for any arbitrary ?? Answer: At least ?/? Spend some time to understand this problem and to realize its difficulty. 17

Large subset that is sum-free Let? > ? be a prime number. Let ? = ?? + ?. //The other choice ?? + ? is also fine here. A randomized algorithm: Select a random number ? from {1,? ?}. Map each element ? ? to ??mod?. ? all those elements of ? that get mapped to {? + ?, ,?? + ?} ? Return ?; Question: What is the expected number of elements from ? that are mapped to {? + ?, ,?? + ?} ? Answer: > ?/? To prove it, use the fact that mapping is 1-1 and uniform. and Linearity of expectation. 18

Large subset that is sum-free Let? > ? be a prime number. Let ? = ?? + ?. A randomized algorithm: Select a random number ? from {1,? ?}. Map each element ? ? to ??mod?. ? all those elements of ? that get mapped to {? + ?, ,?? + ?} ? Return ?; Claim: ? is sum-free. Try to prove it before going to the next slide 19

Showing that ? is sum-free. Let ? and ? be any two elements in ?. Let ? gets mapped to ? and ? gets mapped to ? and ?,? [? + ?,2? + ?] 1 2 ?? + ? ?? + ? 3? + ? ? ? Hence ? = ?? ??? ? and ? = ?? ??? ? we just need to show that ? + ? , if present in ?, must not be mapped in [? + ?,2? + ?]. ? + ? will be mapped to ?? Give suitable arguments to conclude that (? + ?) must be greater than 2? + ?. If(? + ?) > ?, then (? + ?)??? ? would be strictly less than ?. (? + ?)??? ? 20

Try to ponder over the entire solution given for the Large sum-free subset problem. Try to realize the importance of each part of the solution (primality of ?, the choice of middle third, ) This solution is one of those gems of discrete probability / randomized algorithm which you would like to revisit even after this course. I just wonder how such a great solution can come to one s mind 21

PROBLEM 4 LARGE CUT IN A GRAPH 22

Large cut in a graph Problem Definition: Let ? be an undirected graph on ? vertices and ? edges. How large can any cut in ? be ? Answer: At least ?/? Spend some time to find out a proof for this bound. Hopefully, after 3 problems, you would have realized the way probabilistic method works. 23

Large cut in a graph A randomized algorithm: ? ; Add each vertex from ? to ? randomly independently with probability ? ?. Return the cut defined by ?. 24

Large cut in a graph ?: size of cut (?, ?) returned by the randomized algorithm. E[?] = ?? ??: ? if ? is present in the cut ? otherwise ? = ??? E[?] = ??[??] = ??(??= ?) ? ? = ? =? ? 25

Large cut in a graph Now use the following result which is simple but very useful. Let ? is a random variable defined over a probability space (?,?). If ? ? = ?, then there exists an elementary event ? ?, such that ? ? ?. Use it to conclude that there is a cut of size at least ? ?. 26