4
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The DKW inequality will give an upper bound in Kolmogorov distance ($\ell_\infty$ norm for the CDF's) using $O(1/\varepsilon^2)$ samples. (Interestingly, this does not assume anything on the support -- and applies indifferently to discrete and continuous distributions). The additive $\ell_2$ approximation using $O(1/\varepsilon^2)$ samples can be shown e.g. this way. $\endgroup$ – Clement C. Oct 26 '15 at 14:32
  • 2
    $\begingroup$ As for the $\ell_1$/TV case, you can show it directly at in Sasho Nikolov's answer, or from a more general result relating to "$\mathcal{A}$-norms" (of which the TV is a special case). See Devroye and Lugosi, Combinatorial Techniques in Density Estimation" (2001, Chapters 3-4), or Theorems 2.1 and 2.2 of this paper ("Learning mixtures of structured distributions over discrete domains," of Chan et al.) $\endgroup$ – Clement C. Oct 26 '15 at 14:36
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually i was reading this recent survey: eccc.hpi-web.de/report/2015/063. The author mentions this result in passing saying that this is a trivial upper bound for all closeness problems, because we can get the distribution within $\epsilon$ in that many samples (on the first page of chapter 3). $\endgroup$ – Devil Apr 21 '15 at 4:18
  • 1
    $\begingroup$ This is a different problem than just learning the distribution. (And this bound has been improved since then.) $\endgroup$ – usul Apr 22 '15 at 20:15
  • $\begingroup$ Yes, it seems it answers a different problem. Is the standard approach to then delete this question, to prevent misunderstandings? Am I able to delete my answer to a question? $\endgroup$ – kodlu Apr 23 '15 at 2:19

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.