# Empirical estimator fot the total variation distance on a finite space

I have two probability measures $p$ and $p'$ on a finite set $X$ which I do not know precisely, but which I can sample from. I would like to estimate their total variation (omitting multiplier $2$): $$\gamma := \|p - p'\| = \sum_{x\in X}|p(x) - p'(x)|.$$ Similarly to this paper I though it's naturally to draw independently $\xi_k$ from $p$ and $\xi'_k$ from $p'$ to define: $$p_n(\cdot):= \frac1n \sum_{k=1}^n1\{x_k\in \cdot\},\qquad p'_n(\cdot):= \frac1n \sum_{k=1}^n1\{x'_k\in \cdot\}$$ and declare that $\gamma_n:=\|p_n - p'_n\|$ is an estimator of $\gamma$.

Since $S$ is a finite set, the total variation distance coincides with the Wasserstein 1-distance for the discrete metric, and hence with the corresponding Kantorovich distance. Thus, if I'm not mistaken, from Proposition 3.2 here it follows that $\gamma_n\stackrel{a.s.}{\longrightarrow}\gamma.$ I wonder, however, whether it is possible to come up with bounds on the rate of convergence of the form $$\mathbb P(|\gamma_n-\gamma|\geq\delta)\leq\varepsilon \tag{1}.$$ If $\gamma_n$ would be an unbiased estimator of $\gamma$, that is $\mathbb E\gamma_n = \gamma$, it would be possible to apply Hoeffding's inequality to obtain $(1)$, however $\gamma_n$ does not seem to be an unbiased estimator. I hope to show that $$\lim_n\mathbb E\gamma_n = \gamma$$ which would allow to find $n$ big enough so that $|\mathbb E\gamma_n - \gamma|\leq\frac12\delta$ and then apply Hoeffding's inequality to $\gamma_n$. I would be happy to hear other ideas. Perhaps, this topic has been already explored.

## 1 Answer

Since your state space is finite, you will have that $\|p_n-p\|\to 0$ and $\|p_n'-p'\|\to 0$ at exponential rate of decay of probability (simply from finite alphabet large deviations - for example, use section 2.1 in Dembo-Zeitouni's large deviations book). That is, $P(\|p_n-p\|>\delta)\leq n^{|S|} e^{-n I(\delta)}$ where $I$ also depends on the size of the sample space. This immediately gives you (1) with $\epsilon$ decaying exponentially in $n$ (though not uniformly in $|S|$).

• Thank you very much for the answer - fortunately my library has the book, so I'm reading Section 2.1 now. Could you be more specific on how to derive those exponential bounds? – Ilya Aug 28 '13 at 20:14
• Use Lemma 2.1.9 or Theorem 2.1.10 – ofer zeitouni Aug 29 '13 at 6:16
• Thanks, I think I got that: in the notation of the book if we define $\mathfrak L^\delta_n(p):= \{\nu\in \mathfrak L_n:\|\nu - p\|\geq\delta\}$ then $H(\nu|p)\geq \delta^2$ on this set. On the other hand, $$\mathbb P_p(\|L^{\mathbf Y}_n - p\|\geq \delta) = \mathbb P_p(L^{\mathbf Y}_n \in \mathfrak L^\delta_n(p)) \leq \sum_{\nu\in \mathfrak L^\delta_n(p)}\mathrm e^{-nH(\nu|p)}\leq (n+1)^{|\Sigma|} \mathrm e^{-n\delta^2}.$$ which gives a desired bound - am I right? – Ilya Aug 29 '13 at 8:06
• Yes, you are right – ofer zeitouni Aug 29 '13 at 8:13