Randomized Algorithms and Independence Concepts

Types of independence in randomized algorithms are explored alongside the concept of random bit complexity and generation. The idea of mutually independent random variables versus pairwise independent random variables is discussed, illustrating how to generate uniformly random and pairwise independent bits using a limited number of truly random bits. The theorem on reducing random bit complexity is proven through examples and explanations.

• Randomized algorithms
• Independence concepts
• Random bit complexity
• Pairwise independence
• Mutually independent

phan Follow

Uploaded on Feb 26, 2025 | 1 Views

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.

Presentation Transcript

1. Randomized Algorithms CS648 Lecture 24 Random bit complexity Derandomization 1

2. Random bit complexity Input A Randomized Algorithm (for Min-Cut, QuickSort, RIC, ) Random Bit generator Definition : The total number of random bits taken from the Random Bit Generator by the algorithm is called its Random bit complexity. 2

3. RECALL THE NOTION OF INDEPENDENCE 3

4. Types of independences Definition: ?1, ,?? are said to be mutually independent if ? ??? = ??(??) Definition: ?1, ,?? are said to be pairwise independent if for every 1 ? < ? ? ? ?? ?? = ?(??) ?(??) 4

5. Types of independences Definition: ?1, ,?? are said to be mutually independent random variables if for any ?1 ?1, ,?? ?? ? ?(??= ??) = ??(??= ??) Definition:?1, ,?? are said to be pairwise independent random variables if for every 1 ? < ? ?and every ?? ??,?? ?? ? (??= ??) (??= ??) = ?(??= ??) ?(??= ??) 5

6. Important facts A randomized algorithm typically require random bits/numbers that have a uniform distribution pairwise independence Random bit complexity can be reduced. Theorem: We can generate 2? 1 pairwise independent random bits using Only ? mutually independent random bits. We shall now prove this theorem. 6

7. GENERATING UNIFORMLY RANDOM AND PAIRWISE INDEPENDENT BITS using few truly random bits 7

8. Generating Uniformly Randomandpairwise independent Bits Let ?0, ,?? 1 be ? mutually independent random bits. Aim: To generate 2? 1 pairwise independent random bits {??} Key idea: Generate all non-empty subsets of {?0, ,?? 1} Ex:? = 3 2 1 0 Why the XOR operation ? You should get its answer yourself after a few slides 0 0 0 { ?0 } ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?0 0 0 1 0 1 0 { ?1 } ?1 0 1 1 { ?1,?0 } { ?2 } ?1 ?0 1 0 0 ?2 1 0 1 { ?2, ?0 } ?2 ?0 1 1 0 { ?2, ?1 } { ?2, ?1, ?0 } ?2 ?1 1 1 1 ?2 ?1 ?0 8

9. Generating Uniformly Randomandpairwise independent Bits Let ?0, ,?? 1 be ? mutually independent random bits. Aim: To generate 2? 1 pairwise independent random bits {??} Algorithm: For? = 1 to 2? 1 { Consider binary representation of ?; Let the bits at ?1, ,?? places only (in this representation) are 1; ?? ??1 ??2 ??? } 9

10. Generating Uniformly Randomandpairwise independent Bits ? [1, 2? 1] Lemma: Each ?? is a uniformly random bit. Proof: Let ?? = ??1 ??2 ??? ? ??= 1 = ? ??= 1|??2= ?2, ,???= ?? ? ??2= ?2, ,???= ?? ?2, ,?? {0,1} = ? ??1 ?2 ??= 1 ? ??2= ?2, ,???= ??? ?2, ,?? {0,1} ? ? ? ??2= ?2, ,???= ??? = ?2, ,?? {0,1} ? ? = 10

11. Generating Uniformly Randomandpairwise independent Bits ? [1, 2? 1] Lemma: ?? s are pairwise independent. Proof: Let ?? = ??1 ??2 ??? and ?? = ??1 ??2 ?? {?1, ?2, ,? } {?1, ?2, ,??} Without loss of generality, let ?1 {?1, ?2, ,??} Let ? = ??1, ,?? } {??1, ,???} \ {??1,??1}. ? ??= 1 ??= 0 = ? ??= 1 ??= 0|? = ? ?(? = ?) ? ? ? ? ? = ? ??= 1| ??= 0 ? = ? ? ??= 0|? = ? ?(? = ?) ? ? ? 1 4 ? ? = ? =? = ? ? ? 11

12. DERANDOMIZATION transforming a randomized algorithm into a deterministic algorithm 12

13. Large cut in a graph Theorem: (We proved in Lecture 20) Let ? be an undirected graph on ? vertices and ? edges. There exists a cut of size at least ?/?. 13

14. Large cut in a graph A randomized algorithm: ? ; Add each vertex from ? to ? randomly independently with probability ? ?. Return the cut defined by ?. ?: size of cut (?, ?) returned by the randomized algorithm. E[?] =?/? There exists an ? ?such that ? ? ?/? Question: What is the underlying sample space ?? Answer: Depends upon the random bits used by the algorithm. 14

15. Large cut in a graph Question: How to de-randomize the algorithm ? Answer: Compute cut associated with each ? ?and return the largest. Question: How many random bits does the algorithm require ? Answer: ? Question: If we use mutually independent bits for all vertices, what is the size of ? ? Answer: ??. Question: Do we really need mutually independent bits for all vertices ? Answer: NO IDEA : Use only pairwise independent random bits. But will it still ensure E[?] =?/?? Let us see 15

16. Large cut in a graph {??|? ?}: the ?pairwise independent random variable for each vertex. ?: size of cut (?, ?) returned by the randomized algorithm. E[?] = ?? ??: ? if ? is present in the cut ? otherwise ? = ?,? ???,? E[?] = ?,? ??[?(?,?)] = ?,? ??(?(?,?)= ?) = ?,? ??( ??= ? ??= ? ??= ? ??= ?) = ?,? ? ( ?( ??= ? ??= ?) + ?(??= ? ??= ?) ) =? ? ? ? ? ? ? ? = ?,? ? 16

17. Large cut in a graph Lemma: If we use only pairwise independent random bits, the expected size of cut will be at least ? ? Question: How many random bits does the algorithm require now ? Answer: log? (? + ?) Question: What is the size of ? now ? Answer: O(?). Deterministic algorithm: Just enumerate cuts associated with each ? ? and report the largest one. Running time: O(??) 17

18. Large cut in a graph Theroem: There is an O(??) time deterministic algorithm that computes a cut of size at least ?/? in a graph having ? edges and ? vertices. In the next class we shall discuss a powerful technique called Method of Conditional Expectation to design a O(?) time algorithm for computing a cut of size at least ?/? . We shall conclude this course with a beautiful puzzle. 18