Monte-Carlo Algorithm for counting 'on' bits in a binary array
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.