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.