Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
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). – whuber♦ Jun 7 '12 at 20:09
I mean (a) a bound unlikely to be violated in practice. – Paul Reiners Jun 8 '12 at 14:29
Then the best possible answer to your question, Paul, is $b=1$! – whuber♦ Jun 8 '12 at 14:30

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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