Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
You can approximately answer such questions using the central limit theorem. –  Qiaochu Yuan Nov 20 '12 at 23:43
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.