Approximating distributions from samples

Question

One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\epsilon^2}\right)$ samples.

I do not seem to be able to find a proof of this anywhere. On trying to prove it, I seem to be able to prove it if I assume that there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$, where $P$ is the true distribution. However, I do not seem to be able to prove it in the general case.

My attempt at a proof is the following:

Let $P$ be any distribution over $[n]$. Let $X_1,X_2,\cdots,X_{\frac{n}{\epsilon^2}}$ be iid samples of $P$. Let $m=c\frac{n}{\epsilon^2}$. Define $C_i$, $1 \leq i \leq n$, as

$$C_i= \sum_{j=1}^{m} 1(X_j=i).$$

We note that $\mathbb{E}[C_i]= mP_i$.

Further from Chernoff bounding, we get that,

$$P[C_i > (1+\epsilon)mP_i] \leq \exp(-\epsilon^2 \frac{mP_i}{3})= \exp(-\frac{cnP_i}{3}).$$

Similarly, $$P[C_i < (1-\epsilon)mP_i] \leq \exp(-\frac{cnP_i}{2}).$$

Thus defining $\hat{P}_i= \frac{C_i}{m}$, and $\hat{P}=(\hat{P}_1,\cdots,\hat{P}_n)$, by union bounding, we get that with probability at least $1-\sum_{i=1}^n 2\exp(- \frac{cnP_i}{3})$, we have that $||\hat{P}-P||_1 \leq \epsilon$. This gives a proof of the claim as long as there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$ (as the probability can be made arbitrarily close to 1 by increasing the constant).

However, I do not know how I can generalise this result to the general case. I'd appreciate any help with respect to this.

Answer 1

I think it's a simple application of Hoeffding's inequality. Using your notation, let $Q_i = \frac1m C_i$, i.e. $Q$ is the empirical distribution that approximates $P$. The total variation distance between $P$ and $Q$, i.e. half the $\ell_1$ distance, is $$ \max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|. $$

Let $P(S):= \sum_{i \in S}{P_i}$ and define $Q(S)$ analogously. The expectation of $Q(S)$ is $P(S)$ and by Hoeffding, $$ \mathbb{P}(|Q(S) - P(S)| > \epsilon) \leq 2e^{-\epsilon^2 m} $$

If we take $m$ a large enough multiple of $n/\epsilon^2$, we have that $\mathbb{P}(|Q(S) - P(S)| > \epsilon) < 2^{-n}/3$ and by a union bound

$$ \mathbb{P}(\max_S |Q(S) - P(S)| > \epsilon) < 1/3. $$ So with probability at least 2/3, the total variation distance is at most $\epsilon$.

Answer 2

I seem to have resolved this question. The claim (on page 5 of this http://www.eccc.hpi-web.de/report/2015/063/ survey by Cannone) should have been that one can approximate a distribution to within $\ell_2$ distance $\epsilon$ in $O(\frac{n}{\epsilon^2})$ samples (He does not mention approximate in what sense).

This seems to follow directly from an inequality called the Dvoretzky–Kiefer–Wolfowitz inequality.

If anyone knows the stronger $\ell_1$ result to be true, I'd be grateful if they let me know.

Answer 3

Have a look at Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. J. ACM 60(1): 4 (2013) for a comprehensive treatment. The abstract states

*Given samples from two distributions over an n-element set, we wish to test whether these distributions are statistically close. We present an algorithm which uses sublinear in $n$, specifically, $O(n^{2/3} \epsilon^{−8/3} \log n)$, independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small, less than $$\max(\epsilon^{4/3}n^{−1/3}/32, \epsilon n^{−1/2}/4)$$ or large (more than $\epsilon$) in ${\ell}_1$ distance. This result can be compared to the lower bound of

$$\Omega(n^{2/3} \epsilon^{−2/3})$$

for this problem given by Valiant [2008]. Our algorithm has applications to the problem of testing whether a given Markov process is rapidly* mixing. We present sublinear algorithms for several variants of this problem as well.

They distinguish between light and heavy elements of the distribution, among other techniques, to obtain these results.