Monte-Carlo Algorithm for counting 'on' bits in a binary array

Question

Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2: $\frac b 3 \leq a \leq 3b$

How can I use A to build an algorithm that does the same, but with probability $poly(\frac 1 n)$ of success (success means $\frac b 3 \leq a \leq 3b$ ), using A? if A runs in $O(T(n))$ time ($T(n)$ is much smaller than $n$), what's the runtime of the new algorithm?

Answer 1

This is a standard technique. Run the algorithm multiple times and take the median answer. The median will be a success unless there are many failures; use a Chernoff bound to show that this many failures has the low probability you require. Typically, a constant number of runs will give a constant (but better than 1ドル/2$) failure probability, poly-log runs will give polynomially small failure probability and a polynomial number of runs will give exponentially small failure probability.

• Daniel Hoch: what am I doing wrong? $Pr(success) = \sum_{i=1}^{num-of-trials} {Pr(success | we-chose-the-ith-result) * Pr(we-chose-the-ith-result)} =$ (since every trial has an equal probability of being the median) $= \sum_{i=1}^{num-of-trials} \frac1 2 * \frac 1 {num-of-trials} = \frac 1 2$