2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You can approximately answer such questions using the central limit theorem. $\endgroup$ – Qiaochu Yuan Nov 20 '12 at 23:43
  • $\begingroup$ @Qiaochu Yuan, How does one apply the central limit theorem as an approximation for large N rolls? Thank you. $\endgroup$ – Frank Sep 19 '16 at 19:55
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How did you apply the central limit theorem as an approximation for large N rolls? Thank you. $\endgroup$ – Frank Sep 19 '16 at 19:54
  • $\begingroup$ @Frank: The distribution of the sample mean multiplied by $\sqrt{N}$ is, thanks to the Central Limit Theorem, approximately normal with mean of the population $\mu$ and standard deviation $\sigma$. So the distribution of the mean (or the sum) is approximately normal for large $N$ with mean $\mu$ (or $N\mu$ ) and standard deviation $\sigma/\sqrt{N}$ (or $\sigma \sqrt{N}$) $\endgroup$ – Henry Sep 19 '16 at 20:38
  • $\begingroup$ Thank you for your answer. May I ask the analytical expression which shows the convergence of a 6 sided fair dice's expected value to 3.5 as a function of number of rolls.? I realize that there may need to a confidence interval. Thank you. $\endgroup$ – Frank Sep 19 '16 at 21:28
  • $\begingroup$ Try asking a new question. The Central limit theorem can be demonstrated with characteristic functions. That for a discrete uniform distribution such as a $6$-sided die is at en.wikipedia.org/wiki/Discrete_uniform_distribution $\endgroup$ – Henry Sep 19 '16 at 21:39
  • $\begingroup$ I just followed your advice and asked a new question, math.stackexchange.com/questions/1933507/…. Please take a look at it when you have time. Thank you. Frank $\endgroup$ – Frank Sep 19 '16 at 22:13

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.