L1 distance between empirical and true distribution for discrete distributions

Question

I have a distribution over the finite set $\mathcal{A}$ where the probability mass function $p$ is:

$$p(a) = \mathbb{P}(A=a) \quad \quad \quad \quad \quad \quad \text{for all } a \in \mathcal{A}.$$

Given observed data $\mathbf{a} = (a_1,...,a_n)$ the empirical mass function $q_\mathbf{a}$ is defined as:

$$q_\mathbf{a}(a) = \frac{1}{n} \sum_{i=1}^n \mathbb{I}(a_i = a) \quad \quad \quad \text{for all } a \in \mathcal{A}.$$

Now, for a random sample $\mathbf{A} = (A_1,...,A_n) \sim \text{IID } p$, I want to bound from above and below the expectation of the rectilinear distance between the true mass function and the empirical mass function, denoted here by:

$$\phi_n \equiv \mathbb{E} \Big[ \|p-q_\mathbf{A}\|_1 \Big].$$

I would think that this is something well known, but I just can't seem to find a good reference. I tried using the DKW inequality and then applying Markov's inequality, but was unable to get anything from that. I also tried using Pinsker's inequality, but I couldn't bound the KL divergence.

Answer 1

1. Upper bound: Suppose $q(i) = \frac{n_i}{n}$. Note that $n_i$'s are binomial(n,p_i). $n_i$'s are dependent. (But sometimes people use poissonization trick to make it independent,i.e. $n$ is chosen as a sample from $poisson(n)$ and then we choose i.i.d samples)
   So $ E [ ||p - q||_1] = \sum_i E | p_i - \frac{n_i}{n}|$. Using Cauchy Schwartz we have $E | p_i - \frac{n_i}{n}|\le \sqrt{E ( p_i - \frac{n_i}{n})^2} = \sqrt{\frac{p_i(1 - p_i)}{n}}$. Hence $ E [ ||p - q||_1] \le \sum_i \sqrt{\frac{p_i(1 - p_i)}{n}} \le \sqrt{\frac{d-1}{n}}$.

2. I am not sure how to prove the lower bound (you can see Corollary 2, [1]) but it is of the same order $O(\sqrt{\frac{d-1}{n}})$.

Theorem 1 in reference [1] gives an upper bound over all possible distribution $p$'s

[1] Yanjun Han, Jiantao Jiao and Tsachy Weissman. ``Minimax Estimation of Discrete Distributions under ℓ1 Loss'' https://arxiv.org/pdf/1411.1467.pdf

The paper below has tight upper bounds

[2] Daniel Berenda, Aryeh Kontorovich ``A sharp estimate of the binomial mean absolute deviation'' with applications

Answer 2

Since $\mathbf{A} = (A_1,...,A_n) \sim \text{IID } p$, it follows that we have the marginal distributions:

$$n \cdot q_\mathbf{A}(a) = \sum_{i=1}^n \mathbb{I}(A_i = a) \sim \text{Bin}(n, p(a)) \quad \quad \quad \text{for all } a \in \mathcal{A}.$$

Hence, we can write the expectation as:

$$\begin{equation} \begin{aligned} \phi_n &= \mathbb{E} \Big[ \|p-q_\mathbf{A}\|_1 \Big] \\[6pt] &= \mathbb{E} \Bigg[ \sum_{a \in \mathcal{A}} |p(a) - q_\mathbf{A}(a)| \Bigg] \\[6pt] &= \sum_{a \in \mathcal{A}} \mathbb{E} \Bigg[ |p(a) - q_\mathbf{A}(a)| \Bigg] \\[10pt] &= \sum_{a \in \mathcal{A}} \sum_{r=0}^n |p(a) - r/n| \cdot \text{Bin}(r|n,p(a)) \\[10pt] &= \sum_{a \in \mathcal{A}} \sum_{r=0}^n |p(a) - r/n| \cdot {n \choose r} p(a)^r (1-p(a))^{n-r}. \\[6pt] \end{aligned} \end{equation}$$

---

The lower bound for this expectation is $\phi_n=0$. For any mass function $p$ that is a point-mass on a single elements of $\mathcal{A}$, we have $\|p-q_\mathbf{A}\|_1=0$ almost surely, which gives this lower bound.

---

The upper bound can be formed by taking the uniform distribution over the support. If $p(a) = 1/|\mathcal{A}|$ for all $a \in \mathcal{A}$ then we have:

$$\begin{equation} \begin{aligned} \phi_n &= \sum_{a \in \mathcal{A}} \sum_{r=0}^n |p(a) - r/n| \cdot {n \choose r} p(a)^r (1-p(a))^{n-r} \\[6pt] &\leqslant \sum_{a \in \mathcal{A}} \sum_{r=0}^n \Bigg| \frac{1}{|\mathcal{A}|} - \frac{r}{n} \Bigg| \cdot {n \choose r} \frac{1}{|\mathcal{A}|^n} \\[6pt] &= \frac{1}{|\mathcal{A}|^n} \sum_{a \in \mathcal{A}} \sum_{r=0}^n {n \choose r} \Bigg| \frac{1}{|\mathcal{A}|} - \frac{r}{n} \Bigg| \\[6pt] &= \frac{1}{n} \cdot \frac{1}{|\mathcal{A}|^{n-1}} \sum_{r=0}^n {n \choose r} \Bigg| \frac{n}{|\mathcal{A}|} - r \Bigg|. \\[6pt] \end{aligned} \end{equation}$$

This gives a relatively tight upper bound. A weaker upper bound can be obtained by applying Jensen's inequality, giving:

$$\begin{equation} \begin{aligned} \phi_n &= \sum_{a \in \mathcal{A}} \mathbb{E} \Bigg[ |p(a) - q_\mathbf{A}(a)| \Bigg] \\[6pt] &\leqslant \Bigg( \sum_{a \in \mathcal{A}} \mathbb{E} \Bigg[ (p(a) - q_\mathbf{A}(a))^2 \Bigg] \Bigg)^{1/2} \\[6pt] &= \frac{1}{n} \Bigg( \sum_{a \in \mathcal{A}} \mathbb{E} \Bigg[ (n \cdot q_\mathbf{A}(a) - n \cdot p(a))^2 \Bigg] \Bigg)^{1/2} \\[6pt] &= \frac{1}{n} \Bigg( \sum_{a \in \mathcal{A}} \mathbb{V} [ n \cdot q_\mathbf{A}(a) ] \Bigg)^{1/2} \\[6pt] &= \frac{1}{\sqrt{n}} \Bigg( \sum_{a \in \mathcal{A}} p(a) (1-p(a)) \Bigg)^{1/2} \\[6pt] &\leqslant \frac{1}{\sqrt{n}} \Bigg( 1-\frac{1}{|\mathcal{A}|} \Bigg)^{1/2} \\[6pt] &\leqslant \sqrt{\frac{1 - 1/ |\mathcal{A}|}{n}}. \\[6pt] \end{aligned} \end{equation}$$