Approximately counting the number of marked elements in a list of n numbers Assume that we have n sealed boxes. There are k boxes with a ball inside. The goal is to approximate k  by an additive error epsilon, using the minimum number of box probing. I know that this is possible using O(n/k. 1/epsilon^2) box probing but I don't know the algorithm and its analysis.
You calculate the average number of balls in a box (k / n), and the variance. From this you calculate the estimated number of balls and the variance when probing m random boxes. Convert variance to standard deviation. The number of balls will be normal distributed, and there is a simple formula for diverging by more than k standard deviations.