# Empirical distribution learns w.r.t total variation distance

I am trying to prove or disprove that the empirical distribution can learn any continuous distribution w.r.t the total variation distance. The context is the one of statistical learning.
I am quite sure that the proposition is false, but I might likely be wrong. I have looked online and into some books, but I couldn't find a similar formulation for the problem, so if you know some literature that would also be appreciated.

(edit: as pointed out in the comment, the distance I am defining here coincides with the total variation distance in this context.)

I am considering distributions on the real numbers and the set $$\mathcal F = \{ g \in \mathcal C^b(\mathbb R) \ \mid \ \lVert {g}\rVert_\infty \leq 1 \}$$ and the corresponding F-divergence $$d_\mathcal F (\mu \mid \nu ) = \sup_{g \in \mathcal F} \Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\nu \ \Big | .$$

I need to prove (or negate) the following:

For any $$\mu$$ continuous probability distribution, given i.i.d samples $$X_1, \dots , X_n$$ from $$\mu$$, prove that the empirical distribution $$\tilde \mu _n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i}$$ converges in probability to $$\mu$$ w.r.t $$d_\mathcal F$$, i.e. $$P( d_\mathcal F (\mu \mid \tilde \mu_n ) > \epsilon) \xrightarrow[ n \to \infty ]{} 0, \text{ } \ \forall \epsilon>0$$

With $$\delta_x$$ I am denoting Dirac's delta.

It can be proved that convergence w.r.t to $$d_\mathcal F$$ is equivalent to convergence with respect to $$\tilde d (\mu \mid \nu ) = \sup_{g \in \mathcal C^c(\mathbb R) \\ \lVert {g}\rVert_\infty \leq 1 } \Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\nu \ \Big | .$$ This might be helpful in proving the proposition, since $$\mathcal C^c(\mathbb R)$$ is separable: the countable and dense subset could be used to take care of the $$\sup$$ I believe, but I don't exactly see how. Moreover, I don't see how am I supposed to use the density of $$\mu$$.

Despite Chebyshev's inequality/WLLN proves convergence for any single $$g \in \mathcal F$$, with rate indipendent from $$g$$ $$P\Big (\Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\tilde \mu_n \ \Big | > \epsilon \Big ) \leq \frac{Var(g(X_1))}{\epsilon^2 n} \stackrel{g(X) \in [-1,1] \ P \ a.s. }{\leq} \frac{1}{\epsilon^2 n}$$ it seems quite hard to me that such convergence can happen uniformly over $$g$$.

One could restrict the problem to the subset of functions in $$\mathcal F$$ s.t. $$\mathbb E [g(X_1)] = 0$$ by taking the expected value inside the random variable, but that isn't much and I'm not even sure if that would be a good idea.

I have been thinking of using some trivial continuous distribution (such as the gaussian or uniform distributions) as a counterexample, but proving that converge doesn't happen in such case is still hard: my main problem is taking care of the $$\sup$$ inside the probability.

Maybe there's some known theorem which can be used and is going over my head: Glivenko-Cantelli guarantees that $$\tilde \mu _n$$ learns any probability distribution w.r.t to the divergence corresponding to the half-line's indicators, but I don't think that helps.

• Isn't $d_{\mathcal F}$ the total variation distance (or a multiple thereof) ? If you were to consider measures on a compact interval, e.g. $[0,1]$ then $TV$ gives the same topology as Wasserstein, and the statement is true. I don't know the answer in the unbounded case. Commented Sep 20, 2023 at 11:22
• @GabrielRomon that is true, $d_\mathcal F$ coincides with the total variation distance on continuous distributions (but I don't know whether it's equivalent or not for general measures). I will add that into the question, thank you Commented Sep 20, 2023 at 11:43

The proposition is false: the empirical distribution does not learn all continuous distributions w.r.t. $$d_{TV}$$.
Some days ago I found a proof: it holds that $$d_{TV}(\mu \ || \ \nu) = \sup_{g \in \mathcal F} \big | \mathbb E_\mu [g] - \mathbb E_\nu [g] \big |,$$ where $$\mathcal F$$ is the set of measurable functions bounded by 1 (there could be a 2 factor depending on your definition of $$d_{TV}$$). Once one utilises this, the proof is trivial.
For a given $$n\in \mathbb N$$, for samples $$X_1, \dots , X_n$$ one can consider $$f_n(x) = 1 - \unicode{x1D7D9} _{\{X_1, \dots , X_n\}}$$ which is in $$\mathcal F$$ for any sample realisation. Since it is Borel a.e. 1 it is s.t. $$\mathbb E_\mu [f_n] = 1$$ for any continuously distributed $$\mu$$. On the other side, $$\mathbb E_\mu [f_n] = \frac{1}{n} \sum_{i=1}^n f_n({X_i}) = 0 .$$ So $$d_{TV}(\mu \ || \ {\tilde \mu_n}) = \sup_{g \in \mathcal F} \big | \mathbb E_\mu [g] - \mathbb E_{\tilde \mu_n} [g] \big | \geq \big | \mathbb E_\mu [f_n] - \mathbb E_{\tilde \mu_n} [f_n] \big | = 1.$$ Since for any realisation of $$X_1, \dots , X_n$$ there is such an $$f_n$$, we cannot have probability convergence to any continuously distributed $$\mu$$.
I couldn't initially think of such a proof since I was still thinking about continuous functions $$f_n$$ to disprove the convergence, but once one finds the $$f_n$$ above one also sees how to build a continuous one. Since the proof seems correct to me, I'll close the question.
• According to this paper, p. 1438 it holds that $d_{\textrm{TV}}(\mu,\mu_n)=1$. Commented Oct 16, 2023 at 15:46
• @Snoop that totally makes sense, but I think that with the above definition it is equal to 2 (I have often seen $d_{TV}$ defined in an equivalent way which results in a divergence smaller of a factor $\frac{1}{2}$) Commented Oct 18, 2023 at 15:58