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.

  • $\begingroup$ Since all the true probabilities are known and small, this would seem to be a gross overestimate. $\endgroup$ – whuber Feb 24 '16 at 19:48
  • $\begingroup$ @whuber I think the original post indicates the probabilities aren't known except that they're within some range. $\endgroup$ – dsaxton Feb 24 '16 at 20:48
  • $\begingroup$ (+1) Ah, I see you're right--I skimmed over that crucial word "unknown" in the question! $\endgroup$ – whuber Feb 24 '16 at 21:47
  • $\begingroup$ 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? $\endgroup$ – nwp Feb 25 '16 at 17:12
  • $\begingroup$ 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$. $\endgroup$ – 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} $$

  • $\begingroup$ 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$"? $\endgroup$ – whuber Feb 24 '16 at 19:39
  • $\begingroup$ 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. $\endgroup$ – MikeP Feb 24 '16 at 20:49
  • $\begingroup$ 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. $\endgroup$ – whuber Feb 24 '16 at 21:48
  • $\begingroup$ @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. $\endgroup$ – nwp Feb 24 '16 at 22:05
  • $\begingroup$ 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. $\endgroup$ – whuber Feb 24 '16 at 22:08

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.