L1 distance between empirical and true distribution for discrete distributions 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.
 A: *

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

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