Problem Set 1-Problem 3 In balls-and-bins model,we throw n balls into n bins,in the following three paradigms,respectively: 2 n 1.The first-balls are thrown into bins independently and uniformly at random.The remaining 2 balls are thrown into bins using the two-choices paradigm. n n 2.The first balls are thrown into bins using the two-choices paradigm.The remainingballs are 2 thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence.The balls in even positions are thrown into bins using the two-choices paradigm.The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p.for each of the three paradigms. It's not hard to see the answer is a(a But how to prove this rigorously?(Two-choices paradigm is state-dependent) Choose suitable paradigms to compare with.(Coupling argument)
In balls-and-bins model, we throw balls into bins, in the following three paradigms, respectively: 1.The first balls are thrown into bins independently and uniformly at random. The remaining balls are thrown into bins using the two-choices paradigm. 2.The first balls are thrown into bins using the two-choices paradigm. The remaining balls are thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence. The balls in even positions are thrown into bins using the two-choices paradigm. The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p. for each of the three paradigms. n n n 2 n 2 n 2 n 2 Problem Set 1-Problem 3 It’s not hard to see the answer is . But how to prove this rigorously? (Two-choices paradigm is state-dependent) Choose suitable paradigms to compare with. (Coupling argument) Θ ( log n log log n)
Solution Sketch(PS1-P3): Let the paradigm be.To show the max load X is logn log logn with high probability, One necdo ho thar log 2 logn log logn/ and log logn with high probability
Solution Sketch (PS1-P3): Let the paradigm be . To show the max load is with high probability, One need to show that is and with high probability 𝒫 X Θ ( log n log log n) X O ( log n log log n) Ω ( log n log log n )
Solution Sketch(PS1-P3): Let the paradigm be To show the max load X is logn log logn with high probability, One necd to show that logn and logn with high probability log logn/ To show lower bound:compare with the paradigm when onlyballs areare thrown into bins independently and uniformly at random.Let the maximum load of this paradigm be Y.Show for any integer i≥0，Pr[X≥i]≥Pr[Y≥]by constructing a coupling that chooses the same bin for eachballs thrown independently u.a.r ineach paradigm
Solution Sketch (PS1-P3): Let the paradigm be . To show the max load is with high probability, One need to show that is and with high probability 𝒫 X Θ ( log n log log n) X O ( log n log log n) Ω ( log n log log n ) To show lower bound: compare with the paradigm when only balls are are thrown into bins independently and uniformly at random. Let the maximum load of this paradigm be . Show for any integer , by constructing a coupling that chooses the same bin for each balls thrown independently u.a.r in each paradigm. n 2 Y i ≥ 0 Pr[X ≥ i] ≥ Pr[Y ≥ i] n 2
Solution Sketch(PS1-P3): Let the paradigm be To show the max load X is logn with high probability, log logn One need to show that Xis logn logn and with high probability loglogn loglogn To show lower bound:compare with the paradigm when onlyballs are are thrown into bins independently and uniformly at random.Let the maximum load of this paradigm be Y.Show for any integer i≥O,Pr[X≥i]≥Pr[Y≥i]by constructing a coupling that chooses the same bin for each-balls thrown independently u.a.r in each paradigm. To show upper bound:compare with the paradigm when-n balls are are thrown into bins independently and uniformly at random.Let the maximum load of this paradigmbe Z.Show for any integer i≥O,Pr[X≥]≤Pr[Z≥i]by constructing a coupling that' chooses the same bin for each ball thrown u.a.r in and the same two bins for each throw using the method of 2-choices
Solution Sketch (PS1-P3): Let the paradigm be . To show the max load is with high probability, One need to show that is and with high probability 𝒫 X Θ ( log n log log n) X O ( log n log log n) Ω ( log n log log n ) To show lower bound: compare with the paradigm when only balls are are thrown into bins independently and uniformly at random. Let the maximum load of this paradigm be . Show for any integer , by constructing a coupling that chooses the same bin for each balls thrown independently u.a.r in each paradigm. n 2 Y i ≥ 0 Pr[X ≥ i] ≥ Pr[Y ≥ i] n 2 To show upper bound: compare with the paradigm when balls are are thrown into bins independently and uniformly at random. Let the maximum load of this paradigm be . Show for any integer , by constructing a coupling that chooses the same bin for each ball thrown u.a.r in and the same two bins for each throw using the method of -choices. 3 2 n 𝒫′ Z i ≥ 0 Pr[X ≥ i] ≤ Pr[Z ≥ i] 𝒫′ 𝒫 2
Problem Set 1-Problem 4 We want to estimate the number of distinct elements lxllo in a data stream (x;,+/-)(1<i<N)with both increment and decrement updates.It is guaranteedx;>0 at the end of the stream. 1. Assume we have access to a completely random hash function h:[N]-[0,1].For a given T,we maintain S= s we receive updates.Show that i:h(i)<l/2T 1 (1)TPrs01<le h (2)If T>2llxllo,Pr[s=0]>1/2 2. For a given T,design an algorithm that succeeds with probability 1-,outputting LOW ifand HIGH if T>xlo using k=O(log 1/6)independent random hash functions. 3. seNepeiinbveinmateuch thatwh
We want to estimate the number of distinct elements in a data stream with both increment and decrement updates. It is guaranteed at the end of the stream. 1. Assume we have access to a completely random hash function . For a given , we maintain as we receive updates. Show that (1) If , (2) If , 2. For a given , design an algorithm that succeeds with probability , outputting LOW if and HIGH if using independent random hash functions. 3. Use repetition of the above algorithm to obtain an estimate such that w.h.p. ∥x∥0 (xi , + / − ) (1 ≤ i ≤ N) xi ≥ 0 h : [N] → [0,1] T s = ∑ i:h(i)<1/2T xi T < 1 2 ∥x∥0 𝖯𝗋 h [s = 0] < 1/e T > 2∥x∥0 𝖯𝗋 h [s = 0] > 1/2 T 1 − δ T < 1 2 ∥x∥0 T > 2∥x∥0 k = O(log 1/δ) O(log N) F 1 4 ∥x∥0 ≤ F ≤ 4∥x∥0 Problem Set 1-Problem 4