Solution Sketch(PSI-P4): 2eieg={0交8oe由e e a0 andupu 1 ther
Solution Sketch (PS1-P4): 2. For each i ∈ [k], let X , we do the following: i = { 1 si = 0 0 si > 0 Let X¯ = , output HIGH if and output LOW otherwise 1 k k ∑ i=1 Xi X¯ ≥ 0.44
Solution Sketch(PSI-P4): For cacdo the following Le and outu ther To analyze the error probability,note that E[]=Pr[s =0] Recall that Pr[s =0]1/e if T<lo and Pr[s =1/2 if T>o It suffices to show that Pr[|X-E[|≥0.05]≤exp(-⊙k)≤δ One can use either concentration bounds(Chernoff,Heoffding,etc.)or Stirling's approximation Formula for binomial coefficients
Solution Sketch (PS1-P4): 2. For each i ∈ [k], let X , we do the following: i = { 1 si = 0 0 si > 0 Let X¯ = , output HIGH if and output LOW otherwise 1 k k ∑ i=1 Xi X¯ ≥ 0.44 To analyze the error probability, note that 𝔼[X¯] = Pr[s = 0] Recall that Pr[s = 0] < 1/e if T < , and if 1 2 ∥x∥0 Pr[s = 0] > 1/2 T > 2∥x∥0 It suffices to show that Pr[| X¯ − 𝔼[X¯]| ≥ 0.05] ≤ exp(−Θ(k)) ≤ δ One can use either concentration bounds (Chernoff, Heoffding, etc.) or Stirling’s approximation Formula for binomial coefficients
Solution Sketch(PSI-P4): 2肉ux={0gs0 )0we do the following: To analyze the error probability,note that E[]=Pr[s =0] Recall that Pr[s =0]1/e if T<lo and Pr[s =1/2 if T>o It suffices to show that Pr[|X-E[]|≥0.05]≤exp(-Ok)≤δ One can use either concentration bounds(Chernoff,Heoffding,etc.)or Stirling's approximation Formula for binomial coefficients 3.Set NlogN -and use binary search to find F in O(log N)repetitions.Analyze the error probability using union bound
Solution Sketch (PS1-P4): 2. For each i ∈ [k], let X , we do the following: i = { 1 si = 0 0 si > 0 Let X¯ = , output HIGH if and output LOW otherwise 1 k k ∑ i=1 Xi X¯ ≥ 0.44 To analyze the error probability, note that 𝔼[X¯] = Pr[s = 0] Recall that Pr[s = 0] < 1/e if T < , and if 1 2 ∥x∥0 Pr[s = 0] > 1/2 T > 2∥x∥0 It suffices to show that Pr[| X¯ − 𝔼[X¯]| ≥ 0.05] ≤ exp(−Θ(k)) ≤ δ One can use either concentration bounds (Chernoff, Heoffding, etc.) or Stirling’s approximation Formula for binomial coefficients 3. Set and use binary search to find in repetitions. Analyze the error probability using union bound. δ = 1 N log N F O(log N)
Problem Set 2-Problem 1 Suppose we want to estimate the value of Z.Letbe an algorithm that outputs 2satisfying 3 Prtl-eZ≤2≤（l+e☑]≥We runrimnn,乙.，2，and output the median X.Find the number s such that Pr[(1-g)Z<X<(1 +g)Z]>1-6
Suppose we want to estimate the value of . Let be an algorithm that outputs satisfying . We run independently for times, obtaining and output the median . Find the number such that . Z 𝒜 Z ̂ 𝖯𝗋[(1 − ε)Z ≤ Z ̂ ≤ (1 + ε)Z] ≥ 3 4 𝒜 s Z ̂ 1, Z ̂ 2, …, Z ̂ s X s 𝖯𝗋[(1 − ε)Z ≤ X ≤ (1 + ε)Z] ≥ 1 − δ Problem Set 2-Problem 1
Problem Set 2-Problem 1 Suppose we want to estimate the value of Z.Letbe an algorithm that outputs 2satisfying 3 Prtl-eZ≤2≤（l+e☑]≥We runrimnn,乙.，2，and output the median X.Find the number s such that Pr[(1-e)Z≤X≤(1+e)Z☑≥1-δ. Solution sketch: Let Yi= 1(1-e)Z≤2≤(1+e)Z 0 otherwise ≥氵→a-ez≤X≤1+8z i=l Use any suitable concentration bound(i.e.,Chernoff of Heoffding) to bound Pr 2”引
Suppose we want to estimate the value of . Let be an algorithm that outputs satisfying . We run independently for times, obtaining and output the median . Find the number such that . Z 𝒜 Z ̂ 𝖯𝗋[(1 − ε)Z ≤ Z ̂ ≤ (1 + ε)Z] ≥ 3 4 𝒜 s Z ̂ 1, Z ̂ 2, …, Z ̂ s X s 𝖯𝗋[(1 − ε)Z ≤ X ≤ (1 + ε)Z] ≥ 1 − δ Problem Set 2-Problem 1 Solution sketch: Let Use any suitable concentration bound (i.e., Chernoff of Heoffding) to bound Yi = { 1 (1 − ε)Z ≤ Z ̂ i ≤ (1 + ε)Z 0 otherwise s ∑ i=1 Yi ≥ s 2 ⟹ (1 − ε)Z ≤ X ≤ (1 + ε)Z 𝖯𝗋 [ s ∑ i=1 Yi < s 2]