Re: Multiplicative Chernoff bound

In article <1176886617.984566.34750@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
ALiX <alix.tofigh@xxxxxxxxx> wrote:
I got this as a special case from the inequality given in

http://en.wikipedia.org/wiki/Chernoff_bounds.

Using the chernoff bound you mentioned I came up with a procedure. I
would be grateful for any thoughts about it.

As before I have a random process whose outcome is either success or
failure. I am sampling (independant trials) to estimate the
probability p of success. First I decide on some confidence level, say
c = 0.9. While sampling I keep track of how many time I have sampled,
and the average number of failures and successes m per sample. I use
the chernoff bound to find e such that with probability c, m-e < p < m
+e. I stop when this interval is small enough to ensure that the
relative error of my estimation m of p is as small as I want (with
probability c). What do you think?

/ALiX

If c is as low as .9, the Chernoff bounds are likely to
be too crude. In addition, and some of my colleagues
have been working on the problem, confidence intervals
for the binomial are notoriously difficult, although
the usual asymptotic approximations are good in large
samples.

Also, have you stated your problem correctly? A relative
error at p = .1 and at p = .9 are of quite different
magnitudes, while absolute magnitudes turn out the same.

One thing you can do is to get a posterior Bayes interval;
unless you are considering p near to 0 or 1, it matters
little, but if you are concerned about these extremes,
I would suggest the improper prior density for p,
1/(p(1-p)). Then one can compute the posterior distribution,
and the confidence intervals from this will be asymptotically
equivalent to the classical ones. This will work well for
the relative error for p near 0.

One can do this sequentially, but once one has a reasonable
size sample, one can get a good idea of how many more to
sample, and if observations are taken in batches, this can
be updated. For p near 0, the number of successes will be
the important datum to specify, rather than the sample size,
and the relative error is reasonable.


--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.

Relevant Pages

  • Re: Error on kurtosis and skewness
    ... I'm used to thinking of confidence intervals ... distribution could be any uniform distribution. ... there is 100% chance that theta lies within the interval. ... Even though some of them have a 100% probability of containing theta, ...
    (sci.stat.math)
  • Re: Martingale in the field
    ... The chances of getting *any* specific fair coin flipping ... rolls, just much less likely than ALL the other sets of rolls put ... This same principle can be illustrated by examining the probability ... Probability of exactly 0 successes in 10 trials is 0.000976562 ...
    (rec.gambling.craps)
  • Re: please check my homework
    ... > /* return the probability of x successes in n events, ... > given the probability p for success in a single event, ... In the above comment you should specify that n must be a positive integer, ...
    (comp.programming)
  • Re: Probability problem
    ... Since the population mean and standard deviation are ... he does have 100% confidence intervals on the ... the probability that a single time reading will be ... This is another example of why no one should ever use Afonso statistics. ...
    (sci.stat.math)
  • Re: Simple binomial test question
    ... getting the P-value, and it's the P-value that tells you what ... Tests and confidence intervals have different purposes, ... parameter" ("what is the probability of heads when I toss this coin"). ... A test answers the question "is the population parameter equal to this ...
    (sci.stat.math)