# Error of empirical probability for unfair die

I roll an unfair $256$-sided die $n$ times ($n > 1'000'000$) and count the rolled numbers in a histogram. I then calculate the empirical probabilities ${p_e}_i$ for $i=1, ..., 256$ by taking the histogram values divided by $n$. What is the expected error $e = E(({p_e}_i - {p_t}_i)^2)$, where ${p_t}_i$ is the unknown true probability of landing with side $i$ facing up? If it matters you can assume that $0.5 / 256 < {p_t}_i < 2 / 256$.

There is a related question, but applying the answer gives me nonsensical results (such as the error increasing with $n$ when it should be decreasing). I expect the convergence ${p_e}_i \to {p_t}_i$ and $e \to 0$ for $n \to \infty$.

In general for a random variable $X$ with $\sigma^2 \equiv \text{Var}(X)$ the sample mean $\bar{X}$ has variance $\sigma^2 / n$ when our samples are uncorrelated (this follows from the basic properties of variance). In our case $X$ follows a Bernoulli distribution with some success probability $p$ (the chance that the given side comes up after we roll the die) and this distribution has variance $p (1 - p)$ (to see this simply note that $\text{Var}(X) = \text{E}(X^2) - \text{E}(X)^2 = p - p^2 = p(1 - p)$ since $X = X^2$) so the sample proportion has variance $p(1 - p) / n$.

However, we don't know what $p$ is, but we can use the fact that $p(1 - p)$ increases over $[0, 1/2)$ along with your condition to get the following upper bound

\begin{align} \text{Var} (\bar{X}) &\leq \frac{2/256(1 - 2/256)}{n} \\ &= \frac{508}{65536 n} . \end{align}

You can use this idea to choose $n$ so as to guarantee that the variance is smaller than any $\epsilon > 0$ you like.

• Since all the true probabilities are known and small, this would seem to be a gross overestimate. – whuber Feb 24 '16 at 19:48
• @whuber I think the original post indicates the probabilities aren't known except that they're within some range. – dsaxton Feb 24 '16 at 20:48
• (+1) Ah, I see you're right--I skimmed over that crucial word "unknown" in the question! – whuber Feb 24 '16 at 21:47
• I have been trying to apply your answer, but something doesn't work out. Say I want to know $p$ with an error of $\sqrt{\text{Var}(\bar{X})} = 0.01$. Solving for $n$ gives $n=10000 \cdot {508 \over 65536} = 77.5$. Approximating the probability of each side of a $256$-sided die with an expected error of $<0.01$ in $78$ rolls is impossible. What did I do wrong? – nwp Feb 25 '16 at 17:12
• I'm not sure how you got that value for $n$, but notice by looking at the upper bound that the variance is always smaller than $0.01$. For fixed $\epsilon$ solve the inequality $508 / 65536n \leq \epsilon$ for $n$ to get an appropriate sample size that bounds the variance from above by $\epsilon$. – dsaxton Feb 25 '16 at 17:25

let p be the specific $p_i$

The probability estimated is just the number of i's over n so $p_{ei}$ is just $n_{ei}$ / n $$E( ( p_{ei} – p_{ti} )^2 ) = E( ( n_{ei} / n – p )^2 )$$ mulitply inside by n^2 and outside by 1/n^2 $$E( ( p_{ei} – p_{ti} )^2 ) = \frac{1}{n^2} * E( ( n * n_{ei} / n – n * p )^2 )$$ The number observed $n_{ei}$ follows the binomial distribution $$E( ( p_{ei} – p_{ti} )^2 ) = \frac{1}{n^2} * \sigma_{binomial}^2$$ $$\sigma_{binomial}^2 = n p(1-p)$$ $$E( ( p_{ei} – p_{ti} )^2 ) = \frac{1}{n^2} n p (1-p)$$ $$E( ( p_{ei} – p_{ti} )^2 ) = \frac{p(1-p)}{n}$$

• It seems you begin with such a strong simplifying assumption that the answer becomes almost trivial. Presumably, by indexing the probabilities the question wants to address the case where they substantially vary. Did I misunderstand what you mean by "let $p$ be the specific $p_i$"? – whuber Feb 24 '16 at 19:39
• Ahhh, yes I was just calculating it for some p_i which I denoted p for simplicity. But if the question is the expected value for all pei-pti's then I think it would just be the weighted average of pi(1-pi)/ni where n is the number of times the value i came up and pi is the real probability thereof. – MikeP Feb 24 '16 at 20:49
• I'm not sure myself. I did notice there is no summation in the question, suggesting this problem may reduce to a straightforward Binomial calculation, as you point out. Maybe @nwp will clear this up for us with a comment or edit. – whuber Feb 24 '16 at 21:48
• @whuber There is no summation besides counting the rolls in the histogram. I suppose one could look at a specific die side, model the probability through a binomial distribution and arrive at $e = {p(1-p) \over n}$. Can I use the experimental ${p_e}_i$ instead of the true ${p_t}_i$ for that? If so this would be the answer. I do feel like information is lost by not using $\sum_{i=1}^{256} {p_e}_i = \sum_{i=1}^{256} {p_t}_i = 1$, but it should be close enough. – nwp Feb 24 '16 at 22:05
• Actually, no information is lost at all. This is because expectations are linear. By trying to use the experimental value you would be substantially changing your question. Currently, you are asking for a mathematical result: the expectation of a specified random variable (which happens to have a Binomial distribution). (The answer would, of course, be expressed in terms of the unknown probability.) By using the empirical probability you would turn it into a statistical question: how to estimate the expectation. Either form of the question has many answers elsewhere on this site. – whuber Feb 24 '16 at 22:08