New answers tagged

10 votes
Accepted

Proof for boosting success probability of a random algorithm with binary output

The proof I know of uses a weak version of Chernoff bound: If $X_1, X_2, …, X_n$ are independent Bernoulli random variables of same parameter $p$, and $X = \sum\limits_{i=1}^nX_i$, then: $$\mathbb{P}(...
Nathaniel's user avatar
  • 15k

Top 50 recent answers are included