The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged

0

Just posting an answer to close the question. See the helpful comments to the question which contain all the info; Yes it is vaccous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much. Better bounds are known (...


3

$\newcommand{\bm}{\boldsymbol}$The two scenarios are not equal even when $s = t$. In the $s,t$ case you always re-sample the same number of bits, while in the $\delta$ case you get a binomial distribution in the number of bits flipped. Let us define $\text{Maj}$ in a slightly different way than you might be used to, but assure yourself it is correct. $$\...


Top 50 recent answers are included