Given a reservoir of size $S$ with each element taking a value of error or not an error, we attempt to estimate the number of errors inside the reservoir through the following

We poll the reservoir with $P$ samples, and verify that each sample is not an error (note this is ad hoc observed), we do this polling process $X$ trials

since the probability of $n$ error (set to some percentage of $S$ ) appearing in a trial is

$$ \approx {n \choose P} (\frac{n}{S})^n (1 - (\frac{n}{S})^{P- n}) $$

If the probability that no error appear in $X$ trials is low assuming there are $n$ errors in the reservoir, than we can assume that our observation of no errors guarantee that $n$ is fairly few in the resevoir

$$ P(no \:errors \: despite \: n \: errors \: exist) \approx (1 - \sum_{n= 1}^{n}{n \choose P} (\frac{n}{S})^n (1 - (\frac{n}{S})^{P- n}))^X$$

If $P(no \:errors \: despite \: n \: errors \: exist) << 1$ than the fact that we observe no errors means that $n$ is few

but what I found out is that

$$P(no \:errors \: despite \: n \: errors \: exist) = 1$$

wolfram calculation

This is counter intuitive, since if we set $n = 350$ , polling an error out of the reservoir of size $S = 70000$ with $P = 1$ have a probability of $0.005$ so polling at least 1 error out of 500 polls must be greater than $0.005$

Can someone point out where I made a mistake?

  • $\begingroup$ Your equations are inconsistent. What is $n$ in each case? Do you consider sampling with replacement? $\endgroup$ – d.k.o. Jul 9 '15 at 1:55
  • $\begingroup$ n is the number of errors we assume to exist (this is for all cases) and I was calculating using sampling with replacement $\endgroup$ – user411754 Jul 9 '15 at 2:25
  • $\begingroup$ Then this formula does not make sence: $$\approx {n \choose P} (\frac{n}{S})^n (1 - (\frac{n}{S})^{P- n})$$ $\endgroup$ – d.k.o. Jul 9 '15 at 2:42
  • $\begingroup$ In the second eq. you are summing up over $n$ from $1$ to $n$... $\endgroup$ – d.k.o. Jul 9 '15 at 2:43
  • $\begingroup$ $ {n \choose P}(\frac{n}{S})^n(1 - \frac{n}{S}^{P-n})$ account for all n errors occur in the sample, it doesn't account for $n - x$ errors where $x \leq n$ $\endgroup$ – user411754 Jul 9 '15 at 5:06

If I correctly understand the described procedure we have a population of size $S$ and the proportion of errors in the population is $p=n/S$. To estimate $p$ (or $n$) you repeat $M$ times (with replacement) a random sampling of $P$ items (without replacement) and count the number of errors in each sample.

Let $\{X_i,\dots,X_M\}$ denote the number of errors in each sample of size $P$. Then assuming $S$ large enough relative to $P$

$$P\{X_i=k\}\approx \binom{P}{k}p^k(1-p)^{P-k}$$


$$P\{X_1=0,\dots,X_M=0\}\approx (1-p)^{P\times M}$$

You may want to estimate $p$ from the data $\{X_1,\dots,X_M\}$, e.g. using maximum likelihood. In this case (using binomial approximation again)

$$\ln\mathcal{L}(p|X_1,\dots,X_M)=\sum_{i=1}^M\binom{P}{X_i}+\ln p\sum_{i=1}^MX_i+\ln(1-p)\sum_{i=1}^M(P-X_i)$$

Maximizing $\ln\mathcal{L}$ over $p$ yields the MLE

$$\hat p=\frac{1}{M}\sum_{i=1}^M\frac{X_i}{P}$$

Now you can test (statistically) whether $p$ (or $n$) is close to $0$ or not.

  • $\begingroup$ Intuitively, the final equation doesn't quite make sense to me, since $$\hat p=\frac{1}{M}\sum_{i=1}^M\frac{X_i}{P}$$ seems to say that when all $X_i$ are zero the probability of getting an error is zero, despite $M$ might be large, should the probability be normalized by the reservoir size? For example if you sampled 2 sample out of 10,000 samples , the fact that 2 samples are not error does not connotes that the global $p = 0$ but rather the local $p = 0$ and that this local $p$ have $1 - 2/10,000$ chance of not being correct, maybe I am getting something wrong $\endgroup$ – user411754 Jul 9 '15 at 15:18
  • $\begingroup$ No, it should not be normalized. This $\hat p$ maximizes the likelihood of observing particular sample. It may be zero as well despite the fact that the true $p>0$. This is called "estimation" in statistics. If you want to know the true $p$, you must examine the entire population. $\endgroup$ – d.k.o. Jul 9 '15 at 18:34
  • $\begingroup$ ah, that makes sense, is there also a way to measure the confidence of the estimation? $\endgroup$ – user411754 Jul 9 '15 at 20:17
  • $\begingroup$ @user411754: Actually, this is equivalent to drawing 1 sample of size $M\times P$ if $MP<< S$ (so that binomial approximation to hypergeom. works): onlinecourses.science.psu.edu/stat504/node/36 $\endgroup$ – d.k.o. Jul 9 '15 at 20:35

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.