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?

  • 2
    You can approximately answer such questions using the central limit theorem.2012-11-20
  • 0
    @Qiaochu Yuan, How does one apply the central limit theorem as an approximation for large N rolls? Thank you.2016-09-19

1 Answers 1

4

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.

  • 0
    How did you apply the central limit theorem as an approximation for large N rolls? Thank you.2016-09-19
  • 0
    @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}$)2016-09-19
  • 0
    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.2016-09-19
  • 0
    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 https://en.wikipedia.org/wiki/Discrete_uniform_distribution2016-09-19
  • 0
    I just followed your advice and asked a new question, http://math.stackexchange.com/questions/1933507/what-is-the-analytical-expression-which-shows-the-convergence-of-a-6-sided-fair-dice. Please take a look at it when you have time. Thank you. Frank2016-09-19