Understanding Mergers and Random Sources in Data Analysis
Exploring the concepts of mergers, minimal entropy, statistical distance, and somewhere random sources in data analysis. Discover how convex combinations play a crucial role in extracting randomness from different sources for improved data processing.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Curve Merger (Dvir & Widgerson, 2008) Aviv Gil-Ad
Our schedule for today: Sources Mergers The curve merger Analysis
Sources A few definitions
Min-Entropy The min-entropy of a random variable ? is defined as 1 ? ? = ? ???? ?log min Pr ? = ? The uniform distribution ??over 0,1?satisfies ? ?? = ?.
Example ? ? 1 1 0.75 0.75 0.5 0.5 0.25 0.25 0 0 0 1 2 3 0 1 2 3 ? ? = 2 ? ? = 1
Statistical Distance The statistical distance between two random variables ?,? distributed over is defined as ? ?1=1 2 ? = max ? Pr ? ? Pr ? ? Pr ? = ? Pr ? = ? ? and ?are called ?-close if ? ?1 ?, and ?-far otherwise.
Example ? ? 1 1 1 1 2 ? =1 20.25 + 0.25 + 0.05 + 0.05 = 0.3 Pr ? = ? Pr ? = ? 0.75 0.75 0.75 0.5 0.5 0.5 max ? Pr ? ? Pr ? ? = Pr ? 1,2 0.25 0.25 0.25 Pr ? 1,2 = 0.3 0 0 0 0 0 1 2 3 0 1 2 3 1 2 3
Convex combinations ? is a convex combination of ?1, ,?? if there exist 0 ?1, ,?? 1 such that ? Pr ? = ? = ??Pr ??= ? ?=1 and ? ??= 1 ?=1
Somewhere Random Sources Let ? = ?1, ,?? a random variable such that each ?? is distributed over 0,1?. ? is a simple somewhere random source if there exists ? ? such that ??= ??. ? is a somewhere random source if it is a convex combination of simple somewhere random sources.
A challenge Let s say we have two sources, ?,?, over 0,1?. We flip a coin ?. ?|? = 0 and ?|? = 1 are uniform. Can you extract a bit of randomness out of ?,? ?
Mergers The main definition for today
What is a merger? 0,1? ? 0,1? 0,1? is an ?,? - A function ?: merger if for every somewhere random source ? over 0,1? ?, the distribution of ? ?,?? is ?-close to some distribution with min-entropy of at least ?.
Another view 0,1? ? 0,1? 0,1? ?: The input, composed of ? coordinates, each distributed over 0,1? The output, a random variable over 0,1? Random seed, uniform over 0,1?
Other parameters ? the distance of the output from a good source. We want ? to be small. ? the min-entropy of the output ( ?). Clearly, ? ?. We want ? to be very close to ?. We also want an explicit merger: a merger that we can compute in polynomial time.
The Curve Merger Finally, the main construction
A solution for our challenge Find a finite field ?? of sufficient size. Treat the input ?,? as a member of ?? Pass a line between 0,? and 1,? : ? ?,?,? = ?? + 1 ? ? Return a random point on the line. ? ?? ?.
Constructing the merger Let ? be a finite field and ?1, ,?? ? be distinct field elements. We define the following ? polynomials in ? ? : ? ?? ?? ?? ??? ? ? ? Notice that ???? = 1 ? = ? ? ? 0
Constructing the merger, continued We define the function ?: ?? ? ? ?? as follows: ? ? ?1, ,??,? ??? ?? ?=1 Which is the polynomial curve of degree ? 1 passing through all ??,??.
Another example, ? = 3 ? ?0,?1,?2,? ? 1 ? 2 1 2 ?0+? ? 2 1 1?1+? ? 1 = ?2 2 1
Analysis Proving the existence of good mergers
The main theorem For every ? > 0, there exists an explicit ?,? -merger ?: 0,1? ? 0,1? 0,1?, with: ? = 1 ? ? ? = ? log? + log? ? = ? ?? 1
Parameters Let ? be a finite field of size ? = 2? such that 4 ?< ? 2 ?? 4 ? ?? We will assume w.l.o.g that ? ? a constant number of bits of entropy). Therefore, we can treat each ?? as distributed over ??. Our merger will be ?: ?? ? ? ?? from the previous construction. ? (otherwise we can lose
Parameters, continued Notice that ? = log? = ? log? + log? . Let ? = ? ? 4 ?. 4 2 ?? We will assume w.l.o.g that ? is a simple somewhere random source and that ?1 is uniform.
Proof sketch Assume the output of our merger is bad. Find a way to distinguish between our output and any source with high min-entropy. Use it to construct something impossible.
Proof, part 1 Let ? = ? ?,?? denote the output of our merger. Assume ? is ?-far from having min-entropy 1 ? ?.
Proof, part 2 Define ? = ? ??Pr ? = ? 2 1 ? ?. Notice that ? 21 ? ?= ?? 1 ? and Pr ? ? ?. Let ? = ?1 ? ?1 ? 2 ? 4 2. Observe that: ? ? ? ? ?? 1 ? ? ?
Proof, part 3 ? is a lower bound on the number of monomials of ? variables and degree at most ?. (Why?) ? ? Therefore, we can solve a series of linear equations and find a non-zero polynomial ? ? ?1, ,?? of degree ? such that ? ? = 0 for all ? ?. We will show that ? has many more zeroes in ??, thus deriving a contradiction.
Finding the zeroes For each ? ?? let ??= Pr ? ? ?1= ? . Let ? = ? ???? ? 2. By an averaging argument, Pr ?1 ? ? 2. 1 ? Pr ? ? = Pr ?1 ? Pr ? ? ?1 ? + Pr ?1 ? Pr ? ? ?1 ? 1 ? 2
Nested proof Claim: for all ? ?, ? ? = 0. Proof: Let ?1 ?. Since Pr ? ? ?1= ?1 ? fix all other ??in a way that preserves our advantage , meaning: 2, we can ? Pr ? ? ? = ?1, ,?? 2 (Where does this randomness come from?) Let ? = ? ?1, ,??,? ? ? .
Nested proof, continued Proof (cont.): The restriction of ? to ? is given by the polynomial ? = ? ? ?1, ,??,? degree ? ? 1 . ? is zero on at least ? ? ? 1 < ?? < ?1 ? , which has 2 of the points in ? (why?) and since 2 ? ? 4 = ? ? 4 < ? 2? ? 2 We get from the degree mantra that is the zero polynomial. Therefore 0 = ?1 = ? ?=1 ? ??? ?? = ? ?1.
Back to the main proof So far, we have proved that ? is a non-zero polynomial of degree ?, such that ? is zero on all ?. We now get a contradiction, since ? ? 2 ??> ? ?? 1 Thus, such ? does not exist, such ? does not exist, and ? is indeed a ? = 1 ? ?,? merger.
