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$.
 A: 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.
A: 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} $$
