Randomized Algorithms Methods and Limitations
Exploring Chebyshev and Chernoff inequalities, this content delves into the applications, limitations, and examples of randomized algorithms. It discusses scenarios where Chernoff bound is inapplicable and touches upon concepts such as balls into bins and number of triangles in a random graph.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 22 Chebyshev Inequality Method of Bounded Difference 1
Chernoff Bound Theorem : Suppose ??,??, ,??be ? independent Bernoulli random variables with parameters ??,??, ,??, that is, ?? takes value 1 with probability ?? and 0 with probability ? ??. Let ? = ??? and ? = ?[?] = ? ??. For any ? > ?, ? ?? ? ? ? + ? ? (? + ?)?+? ? ? ? ? ? ? ???/? Limitations: Works only for bounding sum of random variables. Requires independence among ??,??, ,??.
THREE EXAMPLES TO ILLUSTRATE THE INAPPLICABILITY OF CHERNOFF BOUND 3
Red-blue balls out of bin Randomized Experiment: There are ?red and ?blue balls in a bag. We take out ?balls from the bag uniformly randomly and without replacement. ?: no. of red balls in the sample. ??= ? if ?th ball in the sample is red ? otherwise ? = ??? ? ? = ??[??] Aim: To show ? is concentrated around ? =? ? ? = ??(??= ?)= ? ? ?. Question: Can we apply Chernoff bound ? Answer: NO because?? s are NOT independent. 4
Balls into Bins (number of empty bins) 1 2 3 4 5 m-1 m 1 2 3 n ? : random variable denoting the number of empty bins. ??= ? if ?th bin is empty ? otherwise ? = ? ??? ?[?] = ? ??[??] Aim: To show that ? is concentrated around ? ?)?= ?(1 1 ?)?=?/?for? = ? = ? ?(1 1 ?. Question: Can we apply Chernoff bound ? Answer: NO because?? s are NOT independent. 5
Number of Triangles in a random graph ?(?,?) : A graph on ? vertices where each edge is present with probability ? independent of others. ? ? ? ? ? ? : random variable denoting the number of triangles. ????= ? if triangle ??? is present in ? ? otherwise ?[?] = ?,?,? ??[????] Aim: To show that ? is concentrated around ?? =?? ?? for? =1 ? 3?3 = 2 ??. Question: Can we apply Chernoff bound ? Answer: NO because???? s are NOT independent. 6
Chebyshevs inequality Let ? be a random variable defined over a probability space. Question: How to capture deviation of ? from ? ? ? Define ? =? ? ? Question: What is ? ? ? Answer: ? ? Redefine ? = ? ? ? Question: What is ? ? ? Answer: ? ?? ? ? ? Called variance of ? 8
Chebyshevs inequality Let ? be a random variable defined over a probability space. ? ? ? ? = ? ? ? ? ? ? ?? Applying Markov Inequality, ?] ?[ ? ? ? ?? =? ?? ? ? ? ?? variance of ? ?? = Limitations: Calculating ? ?? is sometimes difficult. Usually gives bounds that are better than Markov Inequality but inferior to the bound achieved by other methods. Simple practice problems will be given to you on the use of Chebyshev Inequality. 9
METHOD OF BOUNDED DIFFERENCE (MOBD) The most powerful method for bounding the probability of deviation of a random variable from expected value 10
The Power of MOBD Tightest bound for Randomized Quick Sort was derived using MOBD. ??: number of comparisons during randomized quick sort on ? elements. ?(?? ? + ? ? ?? = ? ?? (log log ? + log log log ?) MOBD subsumes Chernoff bound. Based on theory of Martingales. Note: Proof similar and almost as hard as the proof of Chernoff bound. [Not part of the course] 11
Notations ??, ,?? : a sequence of ?random variables. ? = ?(??, ,??)be a function of ?random variables. Objective: to achieve a bound on the probability of deviation of ? from?[?]. ?(|? ? ? | > ?[?]|) = ? Notations: ?? (??, ,??) ?? (??, ,??) ??=?? means ??= ??, ,??= ?? 12
A new perspective The value of ? is well defined once the values taken by ??, ,?? is exposed. View the process of exposing the values of ??, ,?? happening gradually in ? steps. In the beginning, when none of the ??, ,?? is revealed, all we can say about value of ? is that its expected value is ?[?]. In first step, ?? is exposed. If ?? takes value ??, all we can say about value of ? is that its expected value is ?[?|??= ??]. In second step, ?? is also exposed. If ?? takes value ??, all we can say about value of ? is that its expected value is ?[?|??= ??]. The next slide will give a visual description of the process mentioned above. But ponder over this slide before pressing the next button. 13
The value of ? and the gradual exposition of ?? s ??= ?? ??= ?? ??= ?? ??= ?? ?[?|??= ??] ?[?|?? ?= ?? ?] ?[?] ?[?|??= ??] ?[?|??= ??] ?(??) Examples to illustrate the meaning of ?[?|??= ??] Algorithm : Quick sort ?: no. of comparisons during quick sort on ? elements. ?[?|??= ??] : Given first ? pivot elements, the expected number of comparisons during quick sort on ? elements. 14
The value of ? and the gradual exposition of ?? s ??= ?? ??= ?? ??= ?? ??= ?? ?[?|??= ??] ?[?|?? ?= ?? ?] ?[?] ?[?|??= ??] ?[?|??= ??] ?(??) Examples to illustrate the meaning of ?[?|??= ??] Stochastic Process : Ball-Bin problem ?: no. of empty bins ?[?|??= ??]: Given the destination of first ? balls, the expected number of empty bins. 15
Gradual exposition of ??s ??= ?? ??= ?? ??= ?? ??= ?? ?[?|??= ??] ?[?|?? ?= ?? ?] ?[?] ?[?|??= ??] ?[?|??= ??] ?(??) Examples to illustrate the meaning of ?[?|??= ??] Random Structure : Random graph ?: no. of triangles in ?(?,?) ?[?|??= ??]: Given the presence/absence of ??, ,?? edges, the expected number of triangles in the random graph. 16
THE INTUITION UNDERLYING MOBD 17
Method of Bounded Difference ?[?|??= ??,??+?= ?] ??= ?? ??= ?? ??+?= ? ?[?|??= ??] ?[?] ?[?|??= ??,??+?= ?] ?(??) 18
Method of Bounded Difference ?[?|??= ??,??+?= ?] ??= ?? ??= ?? ??+?= ? ?[?|??= ??] ?[?] ?[?|??= ??,??+?= ?] ?(??) For any ??, and any ?,? ??+?, if if |?[?|??= ??,??+?= ?] ?[?|??= ??,??+?= ?]| is small, then Most probably ?(??) will be close to ?[?]. Think for a while over the above statement before proceeding further. 19
Method of Bounded Difference - I ?[?|??= ??,??+?= ?] ??= ?? ??= ?? ??+?= ? ?[?|??= ??] ?[?] ?[?|??= ??,??+?= ?] ?(??) Theorem 1: If there are positive numbers ?? s such that for any ??, and any ?,? ??+?, |?[?|??= ??,??+?= ?] ?[?|??= ??,??+?= ?]| < ?? Then ??? ??? ?(|? ? ? | t t) ??? ? Note: In order to get a meaningful bound using Therem1, you must have small?? s . 20
Method of Bounded Difference - II Definition: function ?(??, ,??) is said to satisfy Lipschitz condition with parameters ?? s if ? ? ? ? For all ?,? that differ only at ?th coordinate. ?? Theorem 2: If ? satisfies Lipschitz condition and ??, ,?? are independent, then ?(|? ? ? | t t) ??? ??? ? ??? Remark: This form is easiest to use but requires independence. 21
MOBD subsumes Chernoff Bound ??, ,?? are 0-1 independent random variables. ? = ??? ? satisfies Lipschitz condition with parameters ??= ? Hence applying Theorem 2 ?(|? ? ? | t t) ??? ??? ? ??? = ??? ??? ? = ? ? l? ? for ? = ? ln ? = ? ? for ? = ? ln ? 23
PROBLEM 1 NO. OF EMPTY BINS 24
Balls into Bins (number of empty bins) 1 2 3 4 5 n-1 n 1 2 3 n ??: random variable denoting the number of balls in ?th bin. ?(??, ,??) : number of empty bins. Observation: ?? takes value in range [?,?]. Question: What is ?? s.t. |?[?|??= ?] ?[?|??= ?]| < ?? for any given ?,?? Answer: For ? = ?,? = ?, ??= ? ? (? ?) ? ? ? ? ? ? ? ? ? This will give very inferior bound 25
Balls into Bins (number of empty bins) 1 2 3 4 5 n-1 n 1 2 3 n ??: random variable denoting the destination of ?th ball. ?(??, ,??) : number of empty bins. Observation: ??, ,?? are independent. ? satisfies Lipschitz condition with parameters ??= ? Hence We failed because our choice of random variables ?? for defining ? was bad. Can you think of other random variables such that ? is a function of them ? = ??? ??? ??? ??? ?(|? ? ? | t t) ??? ? ? for ? > ? ln ? ? ? 26
Balls into Bins (number of empty bins) Theorem: If ?balls are thrown r.u.i. into ?bins, then the number of empty bins will be within range ? ? ? ln ? with probability at least ? ? ?. Lesson to be learnt from this exercise: Be careful in selecting the base random variables ??, ,?? used in defining ?. 27
PROBLEM 2 RED-BLUE BALLS OUT OF BIN 28
Red-blue balls out of bin Randomized Experiment: There are ?red and ?blue balls in a bag. We take out ?balls from the bag uniformly randomly and without replacement. ?: no. of red balls in the sample. ??= ? if ?th ball in the sample is red ? otherwise ? = ??? ? ? = ??[??] Observation: ?? are not independent Can apply Theorem 1 only. Question: What is ?? s.t. |?[?|?? ?= ?? ?,??= ?] |?[?|?? ?= ?? ?,??= ?]| < ?? for any given ?? ?,?,? ? =? ? 29
Red-blue balls out of bin ? ? balls ?? ? ?th ball Let ?? ?has ? red balls. ? ? ? ?? ? ?[?|?? ?= ?? ?,??= ?] = ? ? + ? + (? ?) ? ? ?? ? ?[?|?? ?= ?? ?,??= ?] = ? ? + (? ?) |?[?|?? ?= ?? ?,??= ?] ?[?|?? ?= ?? ?,??= ?]| < ? ??< ? Applying Applying Theorem 1 Theorem 1 < ??? ??? ??? ??? ? ? for ? > ? ln ? ?(|? ? ? | t t) ??? ? ? 30
Red-blue balls out of bin Theorem: There are ?red and ?blue balls in a bag. Suppose we take out ? balls from the bag uniformly randomly and without replacement. The number of red balls in the sample is within range ? probability at least ? ? ?. ? ? ln ? with 31
PROBLEM 3 NO. OF TRIANGLES IN RANDOM GRAPH Do it as exercise. This problem will also be posted in practice sheet. 32
