<p>I seem to have resolved this question. The claim (on page 5 of this  <a href="http://www.eccc.hpi-web.de/report/2015/063/" rel="nofollow">http://www.eccc.hpi-web.de/report/2015/063/</a> 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).</p>

<p>This seems to follow directly from an inequality called the Dvoretzky–Kiefer–Wolfowitz inequality. </p>

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

CC BY-SA 3.0
2015-10-26T14:32:01.433Z
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](http://cstheory.stackexchange.com/a/18498/13319).
Clement C.
CC BY-SA 3.0
2015-10-26T14:36:05.003Z
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](http://www.springer.com/us/book/9780387951171)" (2001, Chapters 3-4), or Theorems 2.1 and 2.2 of [this paper](http://dl.acm.org/citation.cfm?id=2627917) ("Learning mixtures of structured distributions over discrete domains," of Chan et al.)
Clement C.
CC BY-SA 3.0
2015-04-22T17:16:46.310Z
2015-04-22T18:31:31.490Z
2015-04-22T18:31:31.490Z
Devil
<p>Have a look at Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: <em>Testing Closeness of Discrete Distributions</em>. J. ACM 60(1): 4 (2013)
for a comprehensive treatment. The abstract states</p>

<p>*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 </p>

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

<p>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.</p>

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

CC BY-SA 3.0
2015-04-21T04:18:10.993Z
Actually i was reading this recent survey: http://www.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).
Devil
CC BY-SA 3.0
2015-04-22T20:15:38.853Z
This is a different problem than just learning the distribution. (And this bound has been improved since then.)
usul
CC BY-SA 3.0
2015-04-23T02:19:28.263Z
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?
kodlu
CC BY-SA 3.0
2015-04-21T04:03:17.150Z
2015-04-21T04:03:17.150Z
kodlu
<p>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|.
$$</p>

<p>Let $P(S):= \sum_{i \in S}{P_i}$ and define $Q(S)$ analogously. The expectation of $Q(S)$ is $P(S)$ and by <a href="http://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case">Hoeffding</a>, 
$$
\mathbb{P}(|Q(S) - P(S)| &gt; \epsilon) \leq 2e^{-\epsilon^2 m}
$$</p>

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

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

CC BY-SA 3.0
2015-04-22T18:25:19.617Z
2015-04-22T18:25:19.617Z
Sasho Nikolov
<p>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. </p>

<p>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&gt;0$, such that, $\min_{i \in [n]} P_i &gt; \delta$, where $P$ is the true distribution. However, I do not seem to be able to prove it in the general case.</p>

<p>My attempt at a proof is the following:</p>

<p>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</p>

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

<p>We note that $\mathbb{E}[C_i]= mP_i$.</p>

<p>Further from Chernoff bounding, we get that,</p>

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

<p>Similarly,
$$P[C_i &lt; (1-\epsilon)mP_i] \leq \exp(-\frac{cnP_i}{2}).$$</p>

<p>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&gt;0$, such that, $\min_{i \in [n]} P_i &gt; \delta$ (as the probability can be made arbitrarily close to 1 by increasing the constant).</p>

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

<pr.probability><st.statistics>
Approximating distributions from samples
Devil
# Approximating distributions from samples

(Asked by: username_0 on 2015-04-21)

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.

**Tags:** pr.probability, st.statistics


---

## 3 answers

### Answer by username_4 on 2015-04-22. Score: 9 | Accepted answer

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](http://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case),
$$
\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 by username_0 on 2015-04-22. Score: 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.

> **Comments:**
> **username_1**: 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](http://cstheory.stackexchange.com/a/18498/13319).  
> **username_1**: As for the $\ell_1$/TV case, you can show it directly at in username_4'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](http://www.springer.com/us/book/9780387951171)" (2001, Chapters 3-4), or Theorems 2.1 and 2.2 of [this paper](http://dl.acm.org/citation.cfm?id=2627917) ("Learning mixtures of structured distributions over discrete domains," of Chan et al.)  

---

### Answer by username_2 on 2015-04-21. Score: 0

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.

> **Comments:**
> **username_0**: Actually i was reading this recent survey: http://www.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).  
> **username_3**: This is a different problem than just learning the distribution. (And this bound has been improved since then.)  
> **username_2**: 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?  

---

