# How does one express the decrease in minimal type II error bound for each observation added?

Problem: I have a "classifier" that uses some arbitrary hypothesis test on observations from one of two known probability distributions:

1. $P_0$ (null hypothesis $H_0$) is a zero-mean Gaussian $\mathcal{N}(0,\sigma_0^2)$
2. $P_1$ (alternate hypothesis $H_1$) is a mixture of the zero-mean Gaussian from $P_0$ and some other zero-mean Gaussian with a higher variance $p\mathcal{N}(0,\sigma_0^2)+(1-p)\mathcal{N}(0,\sigma_1^2)$ where $\sigma_0^2<\sigma_1^2$

The parameters $\sigma_0^2$, $\sigma_1^2$, and $p$ are assumed to be known. Think of it as testing a machine. $H_0$ means that the machine is operating in good state, and $H_1$ means that the machine needs service.

The "classifier" is allowed some fixed Type I Error $\alpha$. I am interested in determining how the lower bound on Type II Error $\beta$ behaves as I use more observations. Specifically, I am interested in how the lower bound on $\beta$ decreases for each additional observation. Reason for this is that there is cost per each observation I make.

Question: I am trying to find how much I can lower the lower bound on $\beta$ with each additional observation, and knowing the parameters $\sigma_0^2$, $\sigma_1^2$, and $p$ of the distributions being tested. Can it be related to the sum of errors for a single observation?

Prior knowledge: For a single observation, I know that I can bound the sum of errors $\alpha+\beta\geq 1-TV(P_0,P_1)$ where $TV$ is total variation distance per question I asked at math.SE. The total variation between the two distributions in my problem is actually quite nice, as it's just $pTV(\mathcal{N}(0,\sigma_0^2),\mathcal{N}(0,\sigma_1^2))$. I also know that I can upper-bound $TV$ by the square root of half of Kullback-Leibler divergence using Pinsker's Inequality (there are additional benefits to using KL bound which are out of scope of this question...) However, I do not know how to relate the bound on one observation to lowering of the bound with an additional observation.

My mathematical sophistication: I have graduate-level background in probability theory (the M.S. Engineering course). I also have graduate-level background in information theory and signal theory. Unfortunately, I have very limited knowledge of measure theory...

You observe $X_1,\dots,X_n$ iid from $P_i$ ($i=0$ or $i=1$). This can be rephrased by: you observe ${\bf P_i}=P_i\otimes P_i \otimes \dots \otimes P_i=P_i^{\otimes n}$, where $\nu \otimes \mu$ is the product measure obtained from $\nu$ and $\mu$.
Now $KL({\bf P_0},{\bf P_1})=n KL( P_0, P_1)$. I am sure you can easily get a result from that. Now if you are trying to work directlky with the TV distance (which is an idea, but certainly unpractical from my answer here), the thing you should try to evaluate (or upper bound) is:
$2*TV({\bf P_0},{\bf P_1})=\int_{\mathbb{R}^n}|\Pi_{j=1}^n\phi_1(x_j)-\Pi_{j=1}^n\phi_0(x_j)|dx_1\dots, dx_n$ (for $i=0,1$ $\phi_i$ density of $P_i$).
• Thanks for your answer! I have tried the KL bound on the product measure: \begin{align}2TV(\mathbf{P_0},\mathbf{P_1})&\leq& \sqrt{nKL(P_0,P_1)}\\ &\leq&\sqrt{npKL\left(\mathcal{N}(0,\sigma_0^2),\mathcal{N}(0,\sigma_1^2)\right)}\end{align} with the second line from using Jensen's inequality (and apologies for the abuse of notation). Unfortunately, that bound is not tight enough. (continued...) Oct 26 '11 at 2:19
• I've also gotten a bound in form of $$\sqrt{nKL(P_0,P_1)}\leq p\left(\frac{n\left(\sigma_0-\sqrt{2\sigma_0^2-\sigma_1^2}\right)}{\sqrt{2\sigma_0^2-\sigma_1^2}}\right)^{1/2}$$ using 2 degree Taylor expansion of $\sqrt{nKL(P_0,P_1)}$, which is better for small $p$ (which is the case here) and $2\sigma_0^2>\sigma_1^2$ (I can live with that). However, some of my experiments suggest the following upper bound: $$p\sqrt{n\log(\sigma_0^2/\sigma_1^2)}$$ but I have not idea how to get it analytically... Any other ideas? Oct 26 '11 at 2:26