Question

I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,

At some point they have a random algorithm (uses a tape of random bits) that solved a problem over $\mathbb Z_{|m|}^{n} = \{-m,..,m\}^n$ that succeeds with probability $1-\delta$

They want to reduce the number of bits needed for randomness used by that algorithm using via the following statement:

Theorem 9: Let A be a randomized automaton solving problem P on $\mathbb Z_{|m|}^{n}$ with failure probability at most $\delta$. There is a ranomized automaton B that only needs to pick uniformly at random one of $O(\delta ^{-2}nlogm)$ deterministic instances of A and solves P on $\mathbb Z_{|m|}^{n}$ with failure probability at most $2\delta$

Proof: Let $A_1 ,A_2 ,.., A_{O(n\delta ^{-2}logm)}$ be independent draws of deterministic automata picked by B.

Fix an input $x\in \mathbb Z_{|m|}^{n}$.

Let $p_A(x)$ be the fraction of automata among $A_1 ,A_2 ,.., > A_{O(n\delta ^{-2}logm)}$ that solve problem P correctly on x and $p_B(x)$ be the probability that B solves P on x correctly.

By a Chernoff bound, we have that $Pr\{|p_A(x)-p_B(x)|\geq \delta\} \leq exp(-O(nlogm)) < (2m+1)^{-2n}$.

Taking a union bound over all choices of $x\in \mathbb Z_{|m|}^{n}$, we have $Pr\{|p_A(x)-p_B(x)|\geq \delta \ for\ all\ x\} > 0$.

Therefore, there exists a set of $A_1 ,A_2 ,.., A_{O(n\delta > ^{-2}logm)}$ such that $|p_A(x)-p_B(x)|\leq \delta$ for all $x\in > \mathbb Z_{|m|}^{n}$. The automaton B simply samples uniformly at random from this set of deterministic automata

I am having trouble understanding some parts of the proof:

the random variable $p_A(x)$ should be the amount of $A_i$'s that succeeds divided by the amount of them that B has sampled?

if so than by the low of total probability its easy to see that:

$p_B(x) = \sum_{i}P[B\ choose\ A_i] P[B\ succeeds\ on\ x\ |\ B\ choose' A_i] = \sum_{i}\frac{1}{O(\delta^{-2}nlogm)} P[A_i\ succeeds\ on\ x] = p_A(x)$

where the last move comes from the fact the each instance $A_i$ is deterministic so its either 1 for success or 0 for failure.

So the whole $|p_A(x)-p_B(x)|$ they use is actually 0

I understand from the end of the proof that $|p_A(x)-p_B(x)|$ should some how represent the distance between A's success to B's success but could not see how this happen.

Also I did not understand the use of Chernoff the way they did.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top