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

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?

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.
• 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$ – Daniel Hoch Sep 25 '18 at 16:00