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

  • $\begingroup$ 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. $\endgroup$ – fedja Nov 18 '18 at 21:52
  • $\begingroup$ 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. $\endgroup$ – Jeremy Nov 18 '18 at 21:59
  • $\begingroup$ Thanks for taking the time. What do you mean by a simple cutoff function? $\endgroup$ – Jeremy Nov 18 '18 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<c$, 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<c)=\P_{H_0}\Big(\frac{S-\tau^2(a_0^2+d)}{\la\sqrt d}<z_\al\Big)\to\P(Z<z_\al)=\al, \end{equation*} 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<c)&=\P_{H_1}\Big(\tZ<z_\al\frac{\tau^2}{\si^2} +\frac{\tau^2-\si^2}{\la\si^2}\,\sqrt d +\frac{[k^2-(k-1)^2]\|\mu\|^2}{\la\si^2\sqrt{d}}\Big) \\ & \to\Phi\Big(z_\al+(w^2+2b^2/w^2)\Big/\sqrt{\frac{4b^2}{w^2}+2}\Big), \end{align*} which latter is $>\al$, and it is close to $1$ if either $w$ or $b$ is large, which seems to agree with the intuition.

  • $\begingroup$ I have rewritten the answer in a completely rigorous manner. $\endgroup$ – Iosif Pinelis Nov 19 '18 at 16:01
  • $\begingroup$ Thank you! I've been traveling with no time to read this yet. $\endgroup$ – Jeremy Nov 20 '18 at 16:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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