I'm aware there are similar questions, but I haven't been able to find what I'm asking.
Say we have an $n$-sided die, labeled with 1 thru $n$ and roll it $N$ times. We take the average, call it $m$.
The die is fair, so the expectancy for the die roll is $E=\frac{n+1}{2}$.
How large must $N$ be for the average to be within $\epsilon$ from $E$ with a probability, say, $p$?
For example, 20-sided die: $E=10.5$, choose $\epsilon = 0.01$, and $p=0.99$.
So how many times do I have to roll the 20-sided die for the average to lie in the interval $[10.49, 10.51]$ with 99% probability?
Answer
The variance of a single roll is $\frac{n^2-1}{12}$ so the standard deviation of the average of $N$ rolls is $\sqrt{\frac{n^2-1}{12N}}$.
For a normal distribution, the probability of being within $\Phi^{-1}\left(\frac{p +1}{2}\right)$ standard deviations of the mean is $p$, where $\Phi^{-1}$ is the inverse of the cumulative distribution of a standard normal.
For large $N$ you can use the central limit theorem as an approximation, so you want $\sqrt{\frac{n^2-1}{12N}}\Phi^{-1}\left(\frac{p +1}{2}\right) \le \epsilon$, i.e. $$N \ge \left(\frac{n^2-1}{12}\right) \left(\frac{\Phi^{-1}\left(\frac{p +1}{2}\right)}{\epsilon}\right)^2. $$
So in your numerical example $\left(\frac{p +1}{2}\right)=0.995$, $\Phi^{-1}\left(\frac{p +1}{2}\right) \approx 2.5758 $, $\epsilon=0.01$ and $n=20$ so $$N \ge 2206103.1$$ which is certainly large.
No comments:
Post a Comment