2
$\begingroup$

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

$\endgroup$
3
  • $\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, 2018 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, 2018 at 21:59
  • $\begingroup$ Thanks for taking the time. What do you mean by a simple cutoff function? $\endgroup$
    – Jeremy
    Nov 18, 2018 at 21:59

1 Answer 1

0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .