2
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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$
    – SBF
    Commented Aug 28, 2013 at 20:14
  • $\begingroup$ Use Lemma 2.1.9 or Theorem 2.1.10 $\endgroup$
    – ofer zeitouni
    Commented Aug 29, 2013 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$
    – SBF
    Commented Aug 29, 2013 at 8:06
  • $\begingroup$ Yes, you are right $\endgroup$
    – ofer zeitouni
    Commented Aug 29, 2013 at 8:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .