upper bound on power of neyman-pearson hypothesis test

Let $$H_0$$ and $$H_1$$ be two distributions. The Neyman-Pearson lemma says that of all rejection regions $$R$$ with fixed probability $$\alpha$$ under $$H_0$$, the one with maximal probability under $$H_1$$ is the set of the form $$R = \{x: \frac{p_1(x)}{p_0(x)} \ge c\}$$ with $$c$$ chosen such that $$\mathbb{P}_{x \sim H_0}(x \in R) = \alpha$$. The power of the test is then $$\mathbb{P}_{x \sim H_1}(x \in R)$$.

In my case, $$H_0 = \mathcal{N}(0, \tau^2 I_d)$$ and $$H_1 = \mathcal{N}(\mu, \sigma^2 I_d)$$ with $$\tau > \sigma$$. The dimension is high (hundreds of thousands).

For this choice of $$H_0$$ and $$H_1$$, computing the rejection region in closed form does not appear to be possible, so I'd like to compute an upper bound on the power of the NP test at level $$\alpha$$ without actually computing the rejection region.

Are there any generic methods to compute an upper bound on the power of a Neyman-Pearson test at level $$\alpha$$? I'm looking for an exact bound, not an approximate bound based on e.g. the CLT.

In textbooks and papers, I've seen many ways to upper-bound the power as a function of $$c$$ (the likelihood ratio threshold), but none to upper-bound the power as a function of $$\alpha$$. That said, if I had a right tail bound on $$\frac{p_1(x)}{p_0(x)}$$ under $$H_1$$ and a left tail bound on $$\frac{p_1(x)}{p_0(x)}$$ under $$H_0$$, I could combine those to get an upper bound on the power as a function of $$\alpha$$.

• For this choice of H0 and H1, computing the rejection region in closed form does not appear to be possible, Why? It is just a quadratic inequality with $|X|^2$ and $\langle X,\mu\rangle$. The more difficult question is, of course, how $c$ depends on $\alpha$, but if the dimension is really high, you can be pretty sure that the sections of the corresponding body of revolution are either of nearly $0$ measure, or of nearly full measure with rather sharp transition from one case to another, so you can approximate pretty well by a simple cutoff function. Nov 18, 2018 at 21:52
• Yeah, I meant that computing $c$ for a fixed $\alpha$ doesn't appear possible. Under $H_0$, if you complete the square you'll see that the the log of the likelihood ratio is distributed as a non-central chi-squared distribution, shifted, so to compute $c$ i'd need the inverse CDF of a non-central chi-squared, and then computing the power gets still uglier. I'm hoping that there's a generic solution to this problem based on some information theoretic divergence. Nov 18, 2018 at 21:59
• Thanks for taking the time. What do you mean by a simple cutoff function? Nov 18, 2018 at 21:59

$$\renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\la}{\lambda} \newcommand{\D}{\overset{\text{D}}=} \newcommand{\eD}{\overset{\text{D}}\to} \newcommand{\si}{\sigma} \newcommand{\tZ}{\tilde Z}$$

Let $$(X_1,\dots,X_d)$$ be the observed normal random vector. Then the Neyman--Pearson test will reject $$H_0$$ if $$S:=\sum_1^d(X_i-k\mu_i)^2, where $$\mu=:(\mu_1,\dots,\mu_d)$$ and $$c$$ is a critical value and $$\begin{equation*} k:=\frac{\tau^2}{\tau^2-\sigma^2}. \tag{0.1} \end{equation*}$$ With $$\al\in(0,1)$$ fixed, for large $$d$$ the hypotheses $$H_0$$ and $$H_1$$ will be too easy to distinguish from each other (so that the power be close to $$1$$) unless $$H_0$$ and $$H_1$$ are close enough to each other. The following rather natural conditions will provide for that: $$\begin{equation*} d\to\infty,\quad\tau^2\to\tau_0^2\in(0,\infty),\quad \frac{\tau^2-\si^2}{\si^2}=\frac{\tau^2}{\si^2}-1\sim\frac{w^2}{\sqrt d},\quad \frac{\|\mu\|^2}{\si^2}\sim b^2 \tag{0.2} \end{equation*}$$ for some fixed $$w,b$$ in $$(0,\infty)$$, so that $$\begin{equation*} \tau\sim\si,\quad k\sim\frac{\sqrt d}{w^2}\to\infty. \tag{0.3} \end{equation*}$$

Let $$Z,Z_1,Z_2,\dots$$ be iid standard normal random variables. Under $$H_0$$, by the spherical symmetry, $$\begin{equation*} S\D\sum_1^d(\tau Z_i-k\mu_i)^2 \D\tau^2((a_0+Z_1)^2+Z_2^2+\dots+Z_d^2), % \eD\tau^2(a_0^2+d+Z\sqrt{2d}), \end{equation*}$$ where $$\D$$ means the equality in distribution and $$\begin{equation*} a_0^2:=(k/\tau)^2\|\mu\|^2\sim k^2b^2\sim\frac{b^2}{w^2}\,d\to\infty. \tag{1} \end{equation*}$$ By the central limit theorem, $$\begin{equation*} \frac{Z_2^2+\dots+Z_d^2-d}{\sqrt d}\eD Z\sqrt2, \end{equation*}$$ where $$\eD$$ means the convergence in distribution. Also, by (1), $$\begin{equation*} \frac{(a_0+Z_1)^2-a_0^2}{\sqrt d}=\frac{2a_0Z_1+Z_1^2}{\sqrt d}\to\frac{2b}w\,Z_1 \end{equation*}$$ pointwise and hence in distribution. Thus, under $$H_0$$, $$\begin{equation*} (H_0):\quad \frac{S/\tau^2-(a_0^2+d)}{\sqrt d}\eD \frac{2b}w\,Z_1+Z\sqrt2\D\la Z,\quad \la:=\sqrt{\frac{4b^2}{w^2}+2}. \tag{2} \end{equation*}$$

Similarly, under $$H_1$$, $$\begin{equation*} S\D\sum_1^d(\si Z_i-(k-1)\mu_i)^2 \D\si^2((a_1+Z_1)^2+Z_2^2+\dots+Z_d^2), % \eD\si^2(a_1^2+d+Z\sqrt{2d}), \end{equation*}$$ where $$\begin{equation*} a_1^2:=((k-1)/\si)^2\|\mu\|^2\sim a_0^2\sim\frac{b^2}{w^2}\,d\to\infty, \tag{3} \end{equation*}$$ and hence, under $$H_1$$, $$\begin{equation*} (H_1):\quad \tZ:=\frac{S/\si^2-(a_1^2+d)}{\la \sqrt d}\eD Z; \tag{3.1} \end{equation*}$$ cf. (2).

Choosing now the critical value $$\begin{equation*} c:=\tau^2(a_0^2+d+z_\al\la\sqrt{d}), \tag{3.2} \end{equation*}$$ where $$z_\al:=\Phi^{-1}(\al)$$ and $$\Phi$$ is the standard normal cdf, we see that the size of the test is $$\begin{equation*} \P_{H_0}(S as desired.

Recalling (3.1), (3.2), (1), (3), (0.3), (0.2), the relation $$k^2-(k-1)^2\sim2k$$, and the definition of $$\la$$ in (2), for the power of the test we now have \begin{align*} \P_{H_1}(S which latter is $$>\al$$, and it is close to $$1$$ if either $$w$$ or $$b$$ is large, which seems to agree with the intuition.

• I have rewritten the answer in a completely rigorous manner. Nov 19, 2018 at 16:01
• Thank you! I've been traveling with no time to read this yet. Nov 20, 2018 at 16:23