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.

  • $\begingroup$ If I understand correctly, you are mixing distributions with random variables here. Imagine you have a zero-mean gaussian rv P and your Q = -P. Then they have have the same distributions but E|P - Q| = 2E|P| > 0. Maybe give some details about what for you need the L_1 distance? $\endgroup$ Oct 18 '14 at 18:54
  • $\begingroup$ @ŁukaszKidziński: Thanks, I made the notation more rigorous. Hopefully it is clear now. I am thinking of algorithms for density estimation and I am using the L1 distance between the pmfs as a measure of quality. $\endgroup$
    – Jyothi
    Oct 18 '14 at 19:39
  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

  • 2
    $\begingroup$ Welcome to the site. Perhaps you could edit to include a proper citation for the paper, and briefly state the relevant results. We try to do that because it preserves information in case links go dead, and also makes an answer self-contained. Otherwise, comments are a good option for just linking to a reference. $\endgroup$
    – user20160
    Sep 5 '18 at 3:34

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


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.