Monday, August 19, 2019

probability - Number of die rolls needed for average to converge to roll expectancy?



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...