0.20 Lower performance bounds for estimators  (Page 2/4)

• (i) $d(f,g)=d(g,f)\ge 0$ (Symmetric)
• (ii)
  $d(f,f)=0$
• (iii) $d(f,g)\le d(h,f)+d(h,g)$ (Triangle inequality)

E.g. with $f,g:{\mathbb{R}}^d\to \mathbb{R},d(f,g)\stackrel{\Delta }{=}\left|\right|f-{g\left|\right|}_2$ .

Suppose $d(.,.)$ is a semi-distance. Also suppose that we have constructed $f_0,\cdots ,f_M$ s.t. $d(f_j,f_k)\ge 2s_n$ , $\forall j\ne k$ . Take any estimator ${\widehat{f}}_n$ and define the test: ${\Psi }^{*}\circ {\widehat{f}}_n:\mathcal{Z}\to \{0,\cdots ,M\}$ as

Then ${\Psi }^{*}\left({\widehat{f}}_n\right)\ne j$ , implies $d({\widehat{f}}_n,f_j)\ge s_n$ .

Suppose ${\Psi }^{*}\left({\widehat{f}}_n\right)\ne j⟺\exists k\ne j:d({\widehat{f}}_n,f_k)\le d({\widehat{f}}_n,f_j)$ . Now

The previous lemma implies that

Therefore,

The third step follows since we are replacing the class of tests defined by ${\Psi }^{*}\left({\widehat{f}}_n\right)$ by a larger class of ALL possible tests ${\widehat{h}}_n$ , and hence the $inf$ taken over the larger class is smaller.

Now our goal throughout is going to be to find lower bounds for $P_{e,M}$ .

So we need to construct $f_0,\cdots ,f_M$ s.t. $d(f_j,f_k)\ge 2s_n$ , $j\ne k$ and $P_{e,M}\ge c>0$ . Observe that this requires careful construction since the first condition necessitates that $f_j$ and $f_k$ are far from each other, while the second condition requires that $f_j$ and $f_k$ are close enough so that it is harder to distinguish them based on a given sample of data, and hence the probability of error $P_{e,M}$ is bounded away from 0.

We now try to lower bound the probability of error $P_{e,M}$ . We first consider the case $M=1$ , corresponding to binary hypothesis testing.

M = 1: Let $P_0$ and $P_1$ denote the two probability measures, i.e. distributions of the data under models 0 and 1. Clearly if $P_0$ and $P_1$ are very “close", then it is hard to distinguish the two hypotheses, and so $P_{e,1}$ is large.

A natural measure between probability measures is the total variation , defined as:

where $p_0$ and $p_1$ are the densities of $P_0$ and $P_1$ with respect to a common dominating measure $\nu$ and $A$ is any subset of the domain. We will lower bound the probability of error $P_{e,1}$ using the total variation distance. But first, we establish the following lemma.

Scheffe's lemma

Recall the definition of the total variation distance:

Observe that the set $A$ maximizing the right hand side is given by either $\{Z\in \mathcal{Z}:p_0\left(Z\right)\ge p_1\left(Z\right)\}$ or $\{Z\in \mathcal{Z}:p_1\left(Z\right)\ge p_0\left(Z\right)\}$ .

Let us pick $A_0=\{Z\in \mathcal{Z}:p_0\left(Z\right)\ge p_1\left(Z\right)\}$ . Then

For the second part, notice that

Now consider

We are now ready to tackle the lower bound on $P_{e,1}$ . In this case, we consider all tests ${\widehat{h}}_n\left(Z\right):\mathcal{Z}\to \{0,1\}$ . Equivalently, we can define ${\widehat{h}}_n\left(Z\right)=1_A\left(Z\right)$ , where $A$ is any subset of the domain.

So if $P_0$ is close to $P_1$ , then $V(P_0,P_1)$ is small and the probability of error $P_{e,1}$ is large.

This is interesting, but unfortunately, it is hard to work with total variation, especially for multivariate distributions. Bounds involving the Kullback-Leibler divergence are much more convenient.