I have a certain population U. The members x of U each either satisfy or don't satisfy a property p. That is, p(x) is either true or false for each x in U.

I want to get an estimate of the fraction of members of U that satisfy p. I do this by repeatedly sampling from U (with replacement) for some fixed time such as 60 seconds. (This is a computer program I'm talking about.)

After sampling n items, I conclude the proportion is the number of items I found for which p is true divided by n. Let f be this fraction (with 0 <= f <= 1).

That's all simple enough. What I want to know is whether I can establish (a reasonably tight) upper-bound, b, on the error of f.

I naively assumed that the error b would be the abs(f - f') where f' is the fraction calculated after n - 1 samples. From experimentation, I discovered this assumption was wrong.

Is there a way to get a reasonably tight bound b?

  • $\begingroup$ What do you mean by "reasonably tight"? Do you mean (a) a bound unlikely to be violated in practice or (b) a bound that, if made even narrower, would often be violated? The two are opposite: (a) would be a conservatively large bound while (b) would be as small as possible. I ask this because (b) seems to conform with the conventional idea of a "tight" bound whereas you have accepted a reply that implicitly assumes you meant the opposite, (a). $\endgroup$
    – whuber
    Jun 7 '12 at 20:09
  • $\begingroup$ I mean (a) a bound unlikely to be violated in practice. $\endgroup$ Jun 8 '12 at 14:29
  • $\begingroup$ Then the best possible answer to your question, Paul, is $b=1$! $\endgroup$
    – whuber
    Jun 8 '12 at 14:30

By sampling with replacement the number of selected items having p true out of the total selected will be binomial with parameter n and r where r is the actual proportion having p true. If X is the number having p true then X/n is an unbiased estimate of r and its variance is r(1-r)/n. Now since r(1-r) is maximized at r=1/2 the absolute bound on the variance is 1/(4n). So the standard deviation for X/n the estimate of f is < 1/(2√n). So that is a guaranteed bound on the standard deviation of the estimate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.