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.


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

  • $\begingroup$ 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? $\endgroup$ – Ilya Aug 28 '13 at 20:14
  • $\begingroup$ Use Lemma 2.1.9 or Theorem 2.1.10 $\endgroup$ – ofer zeitouni Aug 29 '13 at 6:16
  • $\begingroup$ 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? $\endgroup$ – Ilya Aug 29 '13 at 8:06
  • $\begingroup$ Yes, you are right $\endgroup$ – ofer zeitouni Aug 29 '13 at 8:13

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.