Analyzing Randomized Algorithms: Linearity of Expectation and Applications
Explore the concept of linearity of expectation in randomized algorithms, a crucial tool for analysis. Learn about random variables, expected values, and solve problems using this fundamental concept.
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 4 Linearity of Expectation with applications (Most important tool for analyzing randomized algorithms) 1
Random variable Definition: A random variable defined over a probability space ( ,P) is a mapping R. Examples: o The number of HEADS when a coin is tossed 5 times. o The sum of numbers seen when a dice is thrown 3 times. o The number of comparisons during Randomized Quick Sort on an array of size n. Notations for random variables : X, Y, U, (capital letters) X( ) denotes the value of X on elementary event . 3
Expected Value of a random variable (average value) Definition: Expected value of a random variable X defined over a probability space ( ,P) is E[X] = X( ) P( ) X= c X= b X= a E[X] = a Xa P(X = a) 4
Examples Random experiment 1: A fair coin is tossed n times Random Variable X: The number of HEADS E[X] = ?? P(X =?) ? ? ( 12)? ( 12)? ? = ? ? ? = 2 Random Experiment 2: 4 balls into 3 bins Random Variable X: The number of empty bins E[X] = ?? P(X =?) 5
Can we solve these problems ? Random Experiment 1 ? balls into ? bins Random Variable X: The number of empty bins E[X]= ?? Random Experiment 2 Randomized Quick sort on?elements Random Variable Y: The number of comparisons E[Y]= ?? 6
Balls into Bins (number of empty bins) 1 2 3 4 5 m-1 m A subset of ? bins 1 2 3 n Question : X is random variable denoting the number of empty bins. E[X]= ?? Attempt 1: (based on definition of expectation) E[X] = ?? P(X =?) = ?? (? ?) P(a specific subset of? bins are empty and rest are nonempty) = ?? (? ?) (1 ? ?)? (1 p p(? ?,?)) This is a right but useless answer ! 7
Randomized Quick Sort (number of comparisons) Question : Y is random variable denoting the number of comparisons. E[Y]= ?? Attempt 1: (based on definition of expectation) E[Y] = ?? P(Y =?) A recursion tree associated with Randomized Quick Sort We can not proceed from this point 8
Balls into Bins (number of empty bins) 1 2 3 4 5 m-1 m 1 2 3 n Randomized Quick Sort (number of comparisons) 9
Balls into Bins (number of empty bins) 1 2 3 4 5 m-1 m 1 2 3 ? n Question: Let ?? be a random variable defined as follows. ?? = 1 if ?th bin is empty 0 otherwise What is E[??] ? Answer : E[??] = 1 P(?th bin is empty) + 0 P(?th bin ?? ??? empty) = P(?th bin is empty) = (1 1 ?)? 10
Balls into Bins (any relation between ? and ?? s ?) Consider any elementary event. 1 2 3 4 5 6 An elementary event 1 2 3 4 5 ? = ? ??( ) ??( ) ??( ) ??( ) ??( ) 0 1 0 1 0 ? =?? +?? +?? +?? +?? 11
Sum of Random Variables Definition:Let ?,?,?be random variables defined over a probability space ( ,P) such that ? = ? + ?( ) for each Then ? is said to be the sum of random variables ? and ?. A compact notation : ? = ? + ? Definition:Let ? and ??,??, ,?? be random variables defined over a probability space ( ,P) such that ? = ?? + ?? + + ?? for each Then ? is said to be the sum of random variables ??,??, ,??. A compact notation : ? = ??+ ??+ + ?? 12
Randomized Quick Sort (number of comparisons) ?? Elements of A arranged in Increasing order of values Question : Let ??? , for any 1 ? < ? ?, be a random variable defined as follows. ??? = 1 if ?? is compared with ?? during Randomized Quick Sort of A 0 otherwise What is E[???] ? Answer : E[???] = 1 P(?? is compared with ??) + 0 P(?? is ??? compared with ??) = P(?? is compared with ??) 2 = ? ?+1 13
Randomized Quick Sort (any relation between ? and ??? s ?) Consider any elementary event. Any elementary event ???( ) ???( ) ???( ) ???( )???( ) ?? ? ?( ) 1 0 0 1 1 0 Question: What is relation between and ? and ??? ? Answer:? = ?<???? Hence? = ?<???? 14
What have we learnt till now? Balls into Bin experiment X: random variable denoting the number of empty bins Aim:E[X]= ?? Randomized Quick Sort Y: random variable for the number of comparisons Aim:E[Y]= ?? Hence? = ?<???? ? = ? ??? ?)? E[??] = (1 1 2 E[???] = ? ?+1 E[?] ? ?E[??] E[?] ?<?E[???] 15
The main question ? Let ?,?,?be random variables defined over a probability space ( ,P) such that ? = ? + ?, ?[?] ?[?] + ?[?] ?[?] = ?( ) P( ) = (?( ) + ?( )) P( ) = ( ?( ) P( ) + ?( ) P( ) ) = ?( ) P( )+ =?[?] + ?[?] ?( ) P( ) 16
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. ? = ? ??? Using Linearity of Expectation ?[?] = ? ??[??] = ? ?(1 1 =?(1 1 =?/?for? = ? ?)? ?)? 17
Randomized Quick Sort (number of comparisons) ?: r. v. for the no. of comparisons during Randomized Quick Sort on ? elements. ? = ?<???? Using Linearity of expectation: ?[?] = ?<??[???] 2 = ?<? ? ?+1 2 ? ? = ?=1 ?=?+1 ? ?+1 ?[ 1 2+1 1 = 2 ?=1 3+ + 2+1 ? ?+1 ] ?[ 1 +1 3+ +1 < 2 ?=1 ? ] 2? = 2?l???? ?(?) ?? l???? + 0.58 18
Linearity of Expectation Theorem: (For sum of 2 random variables) If ?,?,?are random variables defined over a probability space ( ,P) such that ? = ? + ?, then ? ? = ?[?] + ?[?] If ? = ???, then ?[?] = ??[??] (For sum of more than 2 random variables) 19
Where to use Linearity of expectation ? Whenever we need to find E[U] but none of the following work E[?] = ?( ) P( ) E[?] = a ?a P(?= a) In such a situation, Try to express ?as ???, such that it is easy to calculate ?[??]. Then calculate ?[?] using ?[?] = ??[??] 20
Think over the following questions? Let ?,?,?be random variables defined over a probability space ( ,P) such that ? = ?? + ??, for some real no. ?,? then ? ? ??[?] + ??[?] Answer: yes (prove it as homework) Why does linearity of expectation holds always ? (even when ? and ? are not independent) Answer: (If you have internalized the proof of linearity of expectation, this question should appear meaningless.) 21
Think over the following questions? Definition: (Product of random variables) Let ?,?,?be random variables defined over a probability space ( ,P) such that ? = ? ?( ) for each Then ? is said to be the product of random variables ? and ?. A compact notation is ? = ? ? If ? = ? ?, then ? ? ?[?] ?[?] Answer: No (give a counterexample to establish it.) If ? = ? ? and both ? and ? are independent then ? ? = ?[?] ?[?] Answer: Yes (prove it rigorously and find out the step which requires independence) 22
Independent random variables In the previous slides, we used the notion of independence of random variable. This notion is identical to the notion of independence of events: Two random variables are said to be independent if knowing the value of one random variable does not influence the probability distribution of the other. In other words, ? ? = ? ? = ?) = ?(? = ?)for all ? ? and ? ?. 23
Some Practice problems as homework Balls into bin problem: What is the expected number of bins having exactly 2 balls ? We toss a coin n times, what is the expected number of times pattern HHT appear ? A stick has n joints. The stick is dropped on floor and in this process each joint may break with probability p independent of others. As a result the stick will be break into many substicks. What is the expected number of substicks of length 3 ? What is the expected number of all the substicks ? 24
Fingerprinting Techniques Problem 1: Given three ? ? matrices ?,?, and ?, determine if ? = ? ?. Best deterministic algorithm: ? ? ? ; Verify if ? = ? ? Time complexity: ?(?2.37) Randomized Monte Carlo algorithm: Time complexity: ?(?2 ??? ? ) Error probability: < ? ? for any ?. 26
Fingerprinting Techniques Problem 2: Given two large files A and B of ? bits located at two computers which are connected by a network. We want to determine if A is identical to B. The aim is to transmit least no. of bits to achieve it. Randomized Monte Carlo algorithm: Bits transmitted : ?(??? ? ) Error probability: < ? ? for any ?. 27
