1

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$.

Community
  • 1
nwp
  • 111
  • 3

2 Answers2

3

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.

dsaxton
  • 11,397
  • 1
  • 23
  • 45
  • 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
2

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} $$

MikeP
  • 2,117
  • 8
  • 9
  • 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