How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred? - Cross Validated most recent 30 from stats.stackexchange.com 2019-09-20T20:46:56Z https://stats.stackexchange.com/feeds/question/198198 https://creativecommons.org/licenses/by-sa/4.0/rdf https://stats.stackexchange.com/q/198198 2 How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred? Michael https://stats.stackexchange.com/users/63648 2016-02-23T22:26:14Z 2016-02-25T14:19:03Z <p>For example, let's say that I have a bag of 100 marbles labeled 1 to 100. A "selection" is randomly picking a marble from the bag and then placing it back into the bag. The marble selected is not known.</p> <p>How many random selections do I need to make to be X% confidence that a specific marble was one of the marbles I selected, say marble #42?</p> <p>Is there a formula or a distribution that helps me solve for X (90%, 95%, 99% confidence)?</p> <p>Bernoulli or Binomial distributions seem close, but I can not quite make them solve for what I want.</p> https://stats.stackexchange.com/questions/198198/how-many-random-selections-needed-to-be-90-95-99-confident-that-a-specific/198201#198201 1 Answer by Salmonstrikes for How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred? Salmonstrikes https://stats.stackexchange.com/users/55589 2016-02-23T22:58:11Z 2016-02-23T22:58:11Z <p>Let $M=100$. Let's say you make $N$ selections and you are looking for the occurrence of marble $m$. </p> <p>Let $E_n$ be the event that marble $m$ is drawn at draw $n$. Let $F_n=E_n^c$ be the event that marble $m$ is NOT drawn.</p> <p>Note that $P(E_n)=1/M$. This means, $P(F_n)=1-1/M$.</p> <p>Let $F$ be the failure event that marble $m$ is not drawn for any $N$. Success is then $F^c$.</p> <p>$P(F^c)=1-P(F)$</p> <p>Assuming independent draws, we have:</p> <p>$P(F)=P(F_1 \cap F_2 \cap F_3 \cap \ldots \cap F_N)=\prod_{n=1}^N P(F_n)=(1-1/M)^N$</p> <p>Therefore, $P(F^c)=1-(1-1/M)^N$.</p> <p>For the $c \in [0,1]$ (e.g. $c=0.9 \equiv 90\%$ confidence) confidence, set the LHS to $c$ and solve for $N$.</p> <p>$\Rightarrow N=\dfrac{\ln(1-c)}{\ln(1-1/M)}$</p> https://stats.stackexchange.com/questions/198198/how-many-random-selections-needed-to-be-90-95-99-confident-that-a-specific/198202#198202 3 Answer by Tim for How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred? Tim https://stats.stackexchange.com/users/35989 2016-02-23T22:59:42Z 2016-02-25T14:19:03Z <p>If $X$ has $k$ distinct values, each appearing with equal probability $1/k$, then it follows <a href="https://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29" rel="nofollow noreferrer">discrete uniform</a> distribution. Probability of drawing a specific $x$ in a single draw is</p> <p>$$\Pr(X=x) = \frac{1}{k}$$</p> <p>probability of drawing value other than $x$ is</p> <p>$$\Pr(X \ne x) = \frac{k-1}{k} = 1-\frac{1}{k}$$</p> <p>so if you make $n$ draws, probability that in neither of the draws $x$ is drawn is</p> <p>$$\left(1-\frac{1}{k} \right)^n$$</p> <p>from here you can easily find that probability of drawing at least one $x$ in $n$ draws is</p> <p>$$1-\left(1-\frac{1}{k} \right)^n$$</p> <p>Now all you need to know is find such $n$ that leads to prespecified probability.</p> <p>This can be easily checked by simulation.</p> <pre class="lang-r prettyprint-override"><code>set.seed(123) f &lt;- function(n, k = 100) 1-((1-1/k)^n) g &lt;- function() which(sample(100, 1e4, replace = TRUE) == 42) sim &lt;- replicate(5e4, g()) </code></pre> <p>that returns</p> <pre class="lang-r prettyprint-override"><code>&gt; quantile(sim, c(0.9, 0.95, 0.99)) 90% 95% 99% 230.00 301.00 460.01 &gt; f(c(230, 301, 460))  0.9008952 0.9514495 0.9901782 </code></pre> <p>(Notice that example above concerns not with confidence intervals but with exact probabilities.)</p> <p>This shows us that we need to sample $n$ values until $x$ occurs, so we are talking about <a href="https://en.wikipedia.org/wiki/Negative_binomial_distribution" rel="nofollow noreferrer">negative binomial</a> distributed variable with parameters $p=1/k$ and $r=1$ (observe $n$ values until $X=x$ occurs once, where probability of observing $x$ is $1/k$). Results obtained using negative binomial distribution agree with the simulation.</p> <pre class="lang-r prettyprint-override"><code>&gt; pnbinom(c(230, 301, 460)-1, 1, 1/k)  0.9008952 0.9514495 0.9901782 </code></pre> <p><a href="https://i.stack.imgur.com/rvymP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rvymP.png" alt="enter image description here"></a></p> <p>So you intuition about binomial distribution was close, as it follows negative binomial distribution. Negative binomial with $r=1$ simplifies to <a href="https://en.wikipedia.org/wiki/Geometric_distribution" rel="nofollow noreferrer">geometric distribution</a>. This is how we ended up with distribution that is traditionally used for modeling discrete waiting times.</p> <pre class="lang-r prettyprint-override"><code>&gt; pgeom(c(230, 301, 460)-1, 1/k)  0.9008952 0.9514495 0.9901782 </code></pre> <p>In fact, if you recall, cumulative distribution function for geometric distribution is</p> <p>$$F(n) = 1 - (1-p)^n$$</p> <p>where $p$ is a probability of observing $x$ in a single draw. So geometric distribution can be used to obtain confidence intervals for the number of samples that need to be taken. </p> <pre class="lang-r prettyprint-override"><code># 95% CI using quantile function of geometric distribution &gt; qgeom(c(0.025, 0.975), 1/k)  2 367 </code></pre> https://stats.stackexchange.com/questions/198198/how-many-random-selections-needed-to-be-90-95-99-confident-that-a-specific/198205#198205 2 Answer by Greg Petersen for How many random selections needed to be 90%, 95%, 99% confident that a specific selection occurred? Greg Petersen https://stats.stackexchange.com/users/100606 2016-02-23T23:06:13Z 2016-02-23T23:06:13Z <p>Each time you grab a marble you have a 1 out of 100 chance of selecting the correct one. What you are asking is what are the odds that at least one of these will be correct which would be an inclusive "or" statement</p> <p>$$P_{selected} = p \cup p \cup p \cup p \cup p... \cup p$$</p> <p>However this is not trivial to calculate since you could select your marble multiple times. Thus it's better to use the negative of this and calculate when it was not selected.</p> <p>$$P_{selected}^\sim = (1-p)\cap(1-p)\cap(1-p)(1-p)\cap(1-p)...(1-p)\cap(1-p)$$</p> <p>which can be easily calculated to N times by</p> <p>$$P_{selected}^\sim = (1-p)^N$$</p> <p>Where you can then show</p> <p>$$P_{selected} = 1- P_{selected}^\sim = 1-(1-p)^N$$</p> <p>and after some algebra</p> <p>$$N = \frac{\ln(1-P_{selected})}{\ln(1-p)}$$</p> <p>so 90% confidence is N = 229.</p> <p>95% confidence is N = 298</p> <p>99% confidence is N = 458.</p>