<p>You might find <a href="https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/learning.pdf" rel="noreferrer">this short note</a> helpful ($\LaTeX$ code available [1]
 if the binary link breaks). I am reproducing the relevant part below:</p>

<blockquote>
  <p><strong>Theorem.</strong> (Folklore)  Learning an unknown distribution over a known domain of size $n$, up to total variation $\varepsilon\in(0,1]$, and with error probability $\delta\in(0,1]$, has sample complexity $O\!\left(\frac{n+\log(1/\delta)}{\varepsilon^2}\right)$. (Moreover, this can be done efficiently.)</p>
</blockquote>

<hr>

<p><strong>Proof</strong>. Consider the empirical distribution $\tilde{p}$ obtained by drawing $m$ independent samples $s_1,\dots,s_m$ from the underlying distribution $p\in\Delta([n])$:
\begin{equation}\label{def:empirical}
\tilde{p}(i) = \frac{1}{m} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}, \qquad i\in [n]
\end{equation}</p>

<ul>
<li><p>First, we bound the <em>expected</em> total variation distance between $\tilde{p}$ and $p$, by using $\ell_2$ distance as a proxy:
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }
    =\frac{1}{2}\mathbb{E}{ \lVert{p-\tilde{p}}\rVert_1} 
    =\frac{1}{2}\sum_{i=1}^n\mathbb{E}{ \lvert{p(i)-\tilde{p}(i)}\rvert }
    \leq\frac{1}{2}\sum_{i=1}^n\sqrt{\mathbb{E}{ (p(i)-\tilde{p}(i))^2} }
$$
the last inequality by Jensen. But since, for every $i\in[n]$, $m\tilde{p}(i)$ follows a $\operatorname{Bin}({m},{p(i)})$ distribution, we have
$\mathbb{E}{ (p(i)-\tilde{p}(i))^2} = \frac{1}{m^2}\operatorname{Var}[m\tilde{p}(i)] = \frac{1}{m}p(i)(1-p(i))$, from which
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) } \leq\frac{1}{2\sqrt{m}}\sum_{i=1}^n\sqrt{p(i)} \leq \frac{1}{2}\sqrt{\frac{n}{m}}
$$
the last inequality this time by Cauchy—Schwarz. Therefore, for $m\geq \frac{n}{\varepsilon^2}$ we have $\mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }\leq \frac{\varepsilon}{2}$.</p></li>
<li><p>Next, to convert this expected result to a <em>high probability</em> guarantee, we apply McDiarmid's inequality to the random variable $f(s_1,\dots,s_m) \stackrel{\rm def}{=} d_{\rm TV}(p,\tilde{p})$, noting that changing any single sample cannot change its value by more than $c\stackrel{\rm def}{=} 1/m$:
$$
    \mathbb{P}\left\{ \lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \geq \frac{\varepsilon}{2} \right\} \leq 2e^{-\frac{2\left(\frac{\varepsilon}{2}\right)^2}{mc^2}} = 2e^{-\frac{1}{2}m\varepsilon^2}
$$
and therefore as long as $m\geq \frac{2}{\varepsilon^2}\ln\frac{2}{\delta}$, we have $\lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \leq \frac{\varepsilon}{2}$ with probability at least $1-\delta$. $\square$</p></li>
</ul>

<hr>

<p>There is a second proof, somewhat more fun, given in that short note (credit to John Wright for pointing it out, and emphasizing it's the "fun" one). Here it is:</p>

<p><strong>Proof.</strong> Again, we will analyze the behavior of the empirical distribution $\tilde{p}$ over $m$ i.i.d. samples from the unknown $p$.  Recalling the definition of total variation distance, note that $d_{\rm TV}({p,\tilde{p}}) &gt; \varepsilon$ literally means there exists a subset $S\subseteq [n]$ such that $\tilde{p}(S) &gt; p(S) + \varepsilon$. There are $2^n$ such subsets, so we can do a union bound.</p>

<p>Fix any $S\subseteq[n]$. We have
$$
\tilde{p}(S) = \tilde{p}(i) = \frac{1}{m} \sum_{i\in S} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}
$$
and so, letting $X_j \stackrel{\rm def}{=} \sum_{i\in S}\mathbb{1}_{\{s_j=i\}}$ for $j\in [m]$, we have
$
\tilde{p}(S) = \frac{1}{m}\sum_{j=1}^m X_j
$ where the $X_j$'s are i.i.d. Bernoulli random variable with parameter $p(S)$. Then, by a Chernoff bound (actually, Hoeffding):
$$
    \mathbb{P}\left\{ \tilde{p}(S) &gt; p(S) + \varepsilon \right\} = \mathbb{P}\left\{ \frac{1}{m}\sum_{j=1}^m X_j &gt; \mathbb{E}\left[\frac{1}{m}\sum_{j=1}^m X_j\right] + \varepsilon \right\} \leq e^{-2\varepsilon^2 m}
$$
and therefore $\mathbb{P}\left\{ \tilde{p}(S) &gt; p(S) + \varepsilon \right\} \leq \frac{\delta}{2^n}$ for any $m\geq \frac{n\ln 2+\log(1/\delta)}{2\varepsilon^2}$. A union bound over these $2^n$ possible sets $S$ concludes the proof:
$$
    \mathbb{P}\left\{ \exists S\subseteq [n] \text{ s.t. }\tilde{p}(S) &gt; p(S) + \varepsilon \right\} \leq 2^n\cdot \frac{\delta}{2^n} = \delta
$$
and we are done. $\square$</p>

<hr>

<p><strong>Note:</strong> a lower bound of $\Omega(\frac{n}{\varepsilon^2})$ (also folklore) is easy to derive from <a href="https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/assouadlemma.pdf" rel="noreferrer">Assouad's lemma</a>, by considering the family of distributions over $[n]$ where each pair of consecutive elements $(2i,2i+1)$ has either probabilities $(\frac{1+c\varepsilon}{n},\frac{1-c\varepsilon}{n})$  or $(\frac{1-c\varepsilon}{n},\frac{1+c\varepsilon}{n})$ for some suitable constant $c&gt;0$. (Intuitively and a bit misleadingly: any learning algorithm has to "figure out" at least $\Omega(n)$ of these independent choices, but each of them requires $\Omega(1/\varepsilon^2)$ samples.)</p>

<hr>

<p>[1] Public GitHub: <a href="https://github.com/ccanonne/probabilitydistributiontoolbox" rel="noreferrer">https://github.com/ccanonne/probabilitydistributiontoolbox</a> (includes the source for the note on Assouad's lemma as well).</p>

CC BY-SA 3.0
2017-09-06T12:44:55.533Z
2017-09-06T14:08:21.977Z
2017-09-06T14:08:21.977Z
Clement C.
<p>Let's denote $N:=|\Omega|$. Then $\Theta(|N|/\epsilon^2)$ examples are both necessary and sufficient to learn the distribution to additive precision $\epsilon$ in total variation. This follows from classic VC analysis, since
for two distributions $p,q$ on $\Omega$, we have
$$ \sum_{x\in\Omega}|p_x-q_x| = 2\max_{A\subseteq\Omega}|p(A)-q(A)|.$$
Now the concept class $2^\Omega$ has VC-dimension $N$ and estimating the weight of each set uniformly is exactly equivalent to estimating $p$ in total variation. The lower bound is actually stronger: not only does the empirical average estimator, $\hat p_x:=m_x/m$, require at least $\Omega(|N|/\epsilon^2)$ examples, but so does <em>any other</em> estimator as well.</p>

<p>The upper bound follows from the Uniform Glivenko-Cantelli property of VC classes (and is achieved, in particular, by the empirical average estimator $\hat p_x$).</p>

<p>Both bounds are proved, for example, in these notes:
<a href="https://www.cs.bgu.ac.il/~asml162/Class_Material" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/Class_Material</a></p>

CC BY-SA 3.0
2017-09-06T12:10:25.920Z
2017-09-06T12:10:25.920Z
Aryeh
<p>There is an obvious algorithm that tests any property of most discrete distributions. This algorithm works by learning the distribution. This is done by just learning the histogram for enough number of samples. In particular, I have the following analysis,
Let $p_x$ be the probability of item $x$ and $m_x$ be the number of occurrences of $x$ in $m$ samples. Then by Chernoff's bound, $Pr(|\frac{m_x}{m}-p_x|&gt;\epsilon)&lt;2.\exp(-2m\epsilon^2)$. Taking union bound over all $x$ in the sample space we can get $Pr(\sum_x|\frac{m_x}{m}-p_x|&gt;\epsilon|\Omega|)&lt;2|\Omega|\exp(-2m\epsilon^2)$. Scaling down $\epsilon$ by a factor of $|\Omega|$, we get $O(\ln |\Omega|\frac{|\Omega|^2}{\epsilon^2})$ samples are enough.</p>

<p>It seems there are folklore algorithm to do this in $O(\ln |\Omega|\frac{|\Omega|}{\epsilon^2})$ as well as in $O(\frac{|\Omega|}{\epsilon^2})$ samples. But I am unable to prove it. A similar question was asked here: <a href="https://cstheory.stackexchange.com/questions/12778/are-there-distribution-properties-which-are-maximally-hard-to-test">Are there distribution properties which are &quot;maximally&quot; hard to test?</a></p>

CC BY-SA 3.0
2017-09-06T15:45:52.377Z
As a side comment: that obvious testing upperbound will *not* lead to an efficient testing algorithn in general: learning is efficient, but testing whether the hypothesis learnt is close to the property may be intractable.
Clement C.
CC BY-SA 3.0
2017-09-06T15:48:03.440Z
(and as a side side note: there exist optimal *and* efficient testing algorithms for some distribution properties that follow that testing-by-learning approach. Then just don't learn in TV distance, but under a different notion.)
Clement C.
CC BY-SA 3.0
2017-09-06T20:46:28.473Z
This is basically a duplicate of https://cstheory.stackexchange.com/q/31210/4896
Sasho Nikolov
CC BY-SA 3.0
2017-09-06T22:09:49.680Z
Possible duplicate of [Approximating distributions from samples](https://cstheory.stackexchange.com/questions/31210/approximating-distributions-from-samples)
Clement C.
<property-testing>
Trivial upper bound for distribution testing
user43170
# Trivial upper bound for distribution testing

(Asked by: username_0 on 2017-09-06)

There is an obvious algorithm that tests any property of most discrete distributions. This algorithm works by learning the distribution. This is done by just learning the histogram for enough number of samples. In particular, I have the following analysis,
Let $p\_x$ be the probability of item $x$ and $m\_x$ be the number of occurrences of $x$ in $m$ samples. Then by Chernoff's bound, $Pr(|\frac{m\_x}{m}-p\_x|>\epsilon)<2.\exp(-2m\epsilon^2)$. Taking union bound over all $x$ in the sample space we can get $Pr(\sum\_x|\frac{m\_x}{m}-p\_x|>\epsilon|\Omega|)<2|\Omega|\exp(-2m\epsilon^2)$. Scaling down $\epsilon$ by a factor of $|\Omega|$, we get $O(\ln |\Omega|\frac{|\Omega|^2}{\epsilon^2})$ samples are enough.

It seems there are folklore algorithm to do this in $O(\ln |\Omega|\frac{|\Omega|}{\epsilon^2})$ as well as in $O(\frac{|\Omega|}{\epsilon^2})$ samples. But I am unable to prove it. A similar question was asked here: [Are there distribution properties which are "maximally" hard to test?](https://cstheory.stackexchange.com/questions/12778/are-there-distribution-properties-which-are-maximally-hard-to-test)

**Tags:** property-testing

> **Comments:**
> **username_1**: As a side comment: that obvious testing upperbound will *not* lead to an efficient testing algorithn in general: learning is efficient, but testing whether the hypothesis learnt is close to the property may be intractable.  
> **username_1**: (and as a side side note: there exist optimal *and* efficient testing algorithms for some distribution properties that follow that testing-by-learning approach. Then just don't learn in TV distance, but under a different notion.)  
> **username_2**: This is basically a duplicate of https://cstheory.stackexchange.com/q/31210/4896  
> **username_1**: Possible duplicate of [Approximating distributions from samples](https://cstheory.stackexchange.com/questions/31210/approximating-distributions-from-samples)  

---

## 2 answers

### Answer by username_1 on 2017-09-06. Score: 7 | Accepted answer

You might find [this short note](https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/learning.pdf) helpful ($\LaTeX$ code available [1]
if the binary link breaks). I am reproducing the relevant part below:

> **Theorem.** (Folklore) Learning an unknown distribution over a known domain of size $n$, up to total variation $\varepsilon\in(0,1]$, and with error probability $\delta\in(0,1]$, has sample complexity $O\!\left(\frac{n+\log(1/\delta)}{\varepsilon^2}\right)$. (Moreover, this can be done efficiently.)

---

**Proof**. Consider the empirical distribution $\tilde{p}$ obtained by drawing $m$ independent samples $s\_1,\dots,s\_m$ from the underlying distribution $p\in\Delta([n])$:
\begin{equation}\label{def:empirical}
\tilde{p}(i) = \frac{1}{m} \sum\_{j=1}^m \mathbb{1}\_{\{s\_j=i\}}, \qquad i\in [n]
\end{equation}

* First, we bound the *expected* total variation distance between $\tilde{p}$ and $p$, by using $\ell\_2$ distance as a proxy:
  $$
  \mathbb{E}{ d\_{\rm TV}(p,\tilde{p}) }
  =\frac{1}{2}\mathbb{E}{ \lVert{p-\tilde{p}}\rVert\_1}
  =\frac{1}{2}\sum\_{i=1}^n\mathbb{E}{ \lvert{p(i)-\tilde{p}(i)}\rvert }
  \leq\frac{1}{2}\sum\_{i=1}^n\sqrt{\mathbb{E}{ (p(i)-\tilde{p}(i))^2} }
  $$
  the last inequality by Jensen. But since, for every $i\in[n]$, $m\tilde{p}(i)$ follows a $\operatorname{Bin}({m},{p(i)})$ distribution, we have
  $\mathbb{E}{ (p(i)-\tilde{p}(i))^2} = \frac{1}{m^2}\operatorname{Var}[m\tilde{p}(i)] = \frac{1}{m}p(i)(1-p(i))$, from which
  $$
  \mathbb{E}{ d\_{\rm TV}(p,\tilde{p}) } \leq\frac{1}{2\sqrt{m}}\sum\_{i=1}^n\sqrt{p(i)} \leq \frac{1}{2}\sqrt{\frac{n}{m}}
  $$
  the last inequality this time by Cauchy—Schwarz. Therefore, for $m\geq \frac{n}{\varepsilon^2}$ we have $\mathbb{E}{ d\_{\rm TV}(p,\tilde{p}) }\leq \frac{\varepsilon}{2}$.
* Next, to convert this expected result to a *high probability* guarantee, we apply McDiarmid's inequality to the random variable $f(s\_1,\dots,s\_m) \stackrel{\rm def}{=} d\_{\rm TV}(p,\tilde{p})$, noting that changing any single sample cannot change its value by more than $c\stackrel{\rm def}{=} 1/m$:
  $$
  \mathbb{P}\left\{ \lvert{f(s\_1,\dots,s\_m) - \mathbb{E}{f(s\_1,\dots,s\_m)}\rvert} \geq \frac{\varepsilon}{2} \right\} \leq 2e^{-\frac{2\left(\frac{\varepsilon}{2}\right)^2}{mc^2}} = 2e^{-\frac{1}{2}m\varepsilon^2}
  $$
  and therefore as long as $m\geq \frac{2}{\varepsilon^2}\ln\frac{2}{\delta}$, we have $\lvert{f(s\_1,\dots,s\_m) - \mathbb{E}{f(s\_1,\dots,s\_m)}\rvert} \leq \frac{\varepsilon}{2}$ with probability at least $1-\delta$. $\square$

---

There is a second proof, somewhat more fun, given in that short note (credit to John Wright for pointing it out, and emphasizing it's the "fun" one). Here it is:

**Proof.** Again, we will analyze the behavior of the empirical distribution $\tilde{p}$ over $m$ i.i.d. samples from the unknown $p$. Recalling the definition of total variation distance, note that $d\_{\rm TV}({p,\tilde{p}}) > \varepsilon$ literally means there exists a subset $S\subseteq [n]$ such that $\tilde{p}(S) > p(S) + \varepsilon$. There are $2^n$ such subsets, so we can do a union bound.

Fix any $S\subseteq[n]$. We have
$$
\tilde{p}(S) = \tilde{p}(i) = \frac{1}{m} \sum\_{i\in S} \sum\_{j=1}^m \mathbb{1}\_{\{s\_j=i\}}
$$
and so, letting $X\_j \stackrel{\rm def}{=} \sum\_{i\in S}\mathbb{1}\_{\{s\_j=i\}}$ for $j\in [m]$, we have
$
\tilde{p}(S) = \frac{1}{m}\sum\_{j=1}^m X\_j
$ where the $X\_j$'s are i.i.d. Bernoulli random variable with parameter $p(S)$. Then, by a Chernoff bound (actually, Hoeffding):
$$
\mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} = \mathbb{P}\left\{ \frac{1}{m}\sum\_{j=1}^m X\_j > \mathbb{E}\left[\frac{1}{m}\sum\_{j=1}^m X\_j\right] + \varepsilon \right\} \leq e^{-2\varepsilon^2 m}
$$
and therefore $\mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} \leq \frac{\delta}{2^n}$ for any $m\geq \frac{n\ln 2+\log(1/\delta)}{2\varepsilon^2}$. A union bound over these $2^n$ possible sets $S$ concludes the proof:
$$
\mathbb{P}\left\{ \exists S\subseteq [n] \text{ s.t. }\tilde{p}(S) > p(S) + \varepsilon \right\} \leq 2^n\cdot \frac{\delta}{2^n} = \delta
$$
and we are done. $\square$

---

**Note:** a lower bound of $\Omega(\frac{n}{\varepsilon^2})$ (also folklore) is easy to derive from [Assouad's lemma](https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/assouadlemma.pdf), by considering the family of distributions over $[n]$ where each pair of consecutive elements $(2i,2i+1)$ has either probabilities $(\frac{1+c\varepsilon}{n},\frac{1-c\varepsilon}{n})$ or $(\frac{1-c\varepsilon}{n},\frac{1+c\varepsilon}{n})$ for some suitable constant $c>0$. (Intuitively and a bit misleadingly: any learning algorithm has to "figure out" at least $\Omega(n)$ of these independent choices, but each of them requires $\Omega(1/\varepsilon^2)$ samples.)

---

[1] Public GitHub: <https://github.com/ccanonne/probabilitydistributiontoolbox> (includes the source for the note on Assouad's lemma as well).


---

### Answer by username_3 on 2017-09-06. Score: 2

Let's denote $N:=|\Omega|$. Then $\Theta(|N|/\epsilon^2)$ examples are both necessary and sufficient to learn the distribution to additive precision $\epsilon$ in total variation. This follows from classic VC analysis, since
for two distributions $p,q$ on $\Omega$, we have
$$ \sum\_{x\in\Omega}|p\_x-q\_x| = 2\max\_{A\subseteq\Omega}|p(A)-q(A)|.$$
Now the concept class $2^\Omega$ has VC-dimension $N$ and estimating the weight of each set uniformly is exactly equivalent to estimating $p$ in total variation. The lower bound is actually stronger: not only does the empirical average estimator, $\hat p\_x:=m\_x/m$, require at least $\Omega(|N|/\epsilon^2)$ examples, but so does *any other* estimator as well.

The upper bound follows from the Uniform Glivenko-Cantelli property of VC classes (and is achieved, in particular, by the empirical average estimator $\hat p\_x$).

Both bounds are proved, for example, in these notes:
<https://www.cs.bgu.ac.il/~asml162/Class_Material>


---

