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


1 Answer 1


You should include the sample size the following way. You need to understand the use of product measure in mathematical statistics.

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

  • $\begingroup$ 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...) $\endgroup$
    – M.B.M.
    Oct 26, 2011 at 2:19
  • $\begingroup$ 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? $\endgroup$
    – M.B.M.
    Oct 26, 2011 at 2:26
  • $\begingroup$ Allright, I am satisfied with the KL-based bounds I found. Thank you for your help, @robin girard! $\endgroup$
    – M.B.M.
    Oct 27, 2011 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.