Minimax signal detection and separation rates — Examples and Counterexamples

Substitution gives $\lambda =(1+1)\mathrm{/}2-1=0$ and $\mathrm{\Lambda }=(2\mathrm{/}(1+1){)}^{1\mathrm{/}4}=1$. To prove the rate order, first let $r\mathrm{/}{r}_{\epsilon }^{\ast }\to 0$, set $n=\lfloor 1\mathrm{/}(4r)\rfloor$, and for each $i\in \{n+1,\dots ,2n\}$ use the two alternatives with sole nonzero coordinate ${\eta }_i=\pm r\mathrm{/}i$. Each lies in ${\mathrm{\Theta }}_1(r)$ because $ri\le 1$ and $i^2{\eta }_i^2=r^2$. Put ${\mu }_i=r\mathrm{/}(\epsilon i)$; then their standardized means satisfy $\mathrm{\mid }{\eta }_i\mathrm{\mid }\mathrm{/}\epsilon ={\mu }_i\le 4r^2\mathrm{/}\epsilon$. If $s=r\mathrm{/}{r}_{\epsilon }^{\ast }\to 0$, then ${\max }_i{\mu }_i^2\le 16{\epsilon }^{-2}{r}^4=16s^4\log ({\epsilon }^{-1})=o(\log n)$, because $\log n\ge c\log ({\epsilon }^{-1})$ for some $c>0$ when $r\le r_{\epsilon }^{\ast }$ and $\epsilon$ is small. For each location $i$, the shifted scalar density divided by the null density is $e^{\pm {\mu }_i{G}_i-{\mu }_i^2\mathrm{/}2}$, where $G_i=Y_i\mathrm{/}\epsilon$ under the null; averaging the two signs gives $L_i=e^{-{\mu }_i^2\mathrm{/}2}\cosh ({\mu }_i{G}_i)$. Completing the square using [F3] and [F4] gives ${\mathbb{E}}_0{L}_i=1$ and ${\mathbb{E}}_0{L}_i^2=\cosh ({\mu }_i^2)$. The measure $L_{i}d{P}_0$ is therefore a probability measure. Finite-coordinate factorization in [F2] identifies its value on every finite-coordinate rectangular cylinder with the sign-mixture sampling law at location $i$: only the $i$th scalar density changes and all other coordinates retain their null law. These cylinders generate the sequence sigma-algebra, so finite-measure uniqueness in [F2] identifies the two measures on all measurable events. For distinct locations, [F2] also gives ${\mathbb{E}}_0{L}_i{L}_j=1$. Thus the uniform mixture $L=n^{-1}{\sum }_i{L}_i$ satisfies ${\mathbb{E}}_0(L-1{)}^2=n^{-2}{\sum }_i(\cosh ({\mu }_i^2)-1)\le n^{-1}\exp ({\max }_i{\mu }_i^2)=n^{-1}\exp (o(\log n))\to 0$. Since ${\mathbb{E}}_0(L-1)=0$, its positive and negative parts have equal integrals, so for every event $E$, $\mathrm{\mid }{P}_{\pi }(E)-P_0(E)\mathrm{\mid }\le \frac{1}{2}{\mathbb{E}}_0\mathrm{\mid }L-1\mathrm{\mid }\le \frac{1}{2}\sqrt{{\mathbb{E}}_0(L-1{)}^2}$. Approximation by averages of event indicators gives the same bound for randomized tests. Therefore the mixture total variation tends to zero, ${\gamma }_{\epsilon }({\mathrm{\Theta }}_1(r))\to 1$, and every level-$\alpha$ test has maximal type-II error at least $1-\alpha -o(1)$. The constant randomized test $\psi \equiv \alpha$ gives the matching upper bound $1-\alpha$.

First suppose $r\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$ and $r\to 0$. Put $N=\lceil 2\mathrm{/}r\rceil$, $t_N=4\sqrt{\log N}$, and reject if ${\max }_{i\le N}\mathrm{\mid }{Y}_i\mathrm{\mid }\mathrm{/}\epsilon >t_N$. Under the null, [F5] and a union bound give type-I error at most $2N{e}^{-t_N^2\mathrm{/}2}=2N^{-7}\to 0$. For any alternative, $\mathrm{\mid }{\eta }_i\mathrm{\mid }\le i^{-2}$ follows from [F1], so the omitted weighted energy obeys ${\sum }_{i>N}{i}^2{\eta }_i^2\le N^{-2}{\sum }_{i>N}{i}^2\mathrm{\mid }{\eta }_i\mathrm{\mid }\le N^{-2}\le r^2\mathrm{/}4$. Hence ${\sum }_{i\le N}{i}^2{\eta }_i^2\ge 3r^2\mathrm{/}4$. On the event that all $N$ null-noise coordinates satisfy $\mathrm{\mid }{\xi }_i\mathrm{\mid }\le t_N\mathrm{/}2$, nonrejection would imply $\mathrm{\mid }{\eta }_i\mathrm{\mid }\le (3\mathrm{/}2)\epsilon t_N$ for every $i\le N$, and therefore ${\sum }_{i\le N}{i}^2{\eta }_i^2\le (3\mathrm{/}2)\epsilon t_N{\sum }_{i\le N}{i}^2\mathrm{\mid }{\eta }_i\mathrm{\mid }\le (3\mathrm{/}2)\epsilon t_N$. But $r\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$ makes $r^2\mathrm{/}(\epsilon \sqrt{\log N})\to \mathrm{\infty }$, a contradiction for small $\epsilon$. The probability that the stated noise event fails is at most $2N{e}^{-(t_N\mathrm{/}2{)}^2\mathrm{/}2}=2\mathrm{/}N\to 0$, so the maximal type-II error tends to zero.

For an arbitrary positive radius sequence with $r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$, use the positive representative $r_{\epsilon }^{\ast }={\epsilon }^{1\mathrm{/}2}(\log {\epsilon }^{-1}{)}^{1\mathrm{/}4}$ and put ${\bar{r}}_{\epsilon }=\min \{r_{\epsilon },\sqrt{r_{\epsilon }^{\ast }}\}$. Then ${\bar{r}}_{\epsilon }\to 0$, ${\bar{r}}_{\epsilon }\le r_{\epsilon }$, and ${\bar{r}}_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }=\min \{r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast },1\mathrm{/}\sqrt{r_{\epsilon }^{\ast }}\}\to \mathrm{\infty }$. Apply step 2.1 with ${\bar{r}}_{\epsilon }$ in place of $r_{\epsilon }$. Its cutoff $N=\lceil 2\mathrm{/}{\bar{r}}_{\epsilon }\rceil$ now tends to infinity, so both its null-size bound $2N^{-7}$ and its noise-event bound $2\mathrm{/}N$ vanish, and the energy-tail and signal-to-threshold estimates in that step apply at ${\bar{r}}_{\epsilon }$. Since ${\mathrm{\Theta }}_1(r_{\epsilon })\subseteq {\mathrm{\Theta }}_1({\bar{r}}_{\epsilon })$, the same test has unchanged null size and no larger maximal type-II error on the requested alternative. Its total error therefore tends to zero, and its null size is eventually below any fixed significance level, giving both consistency limits in [F1]. For an empty requested alternative both minimax risks are zero by that definition, with the never-reject test attaining zero total error. This covers the nonvanishing-radius case without using a bounded or nondiverging cutoff.

The impossibility implication in step 1.1 and the all-positive-radius consistency implication in step 3.1 establish the separation-rate order ${\epsilon }^{1\mathrm{/}2}(\log {\epsilon }^{-1}{)}^{1\mathrm{/}4}$. The parameter and constant were computed in step 1.1, proving the example.

Let $m$ be the largest active index, so $A{m}^{2\alpha }<1\le A(m+1{)}^{2\alpha }$ and $(m+1{)}^{-2\alpha }\le A<m^{-2\alpha }$. For $j\le m\mathrm{/}2$, $1-A{j}^{2\alpha }\ge 1-2^{-2\alpha }>0$. For any fixed $p>0$, ${\sum }_{j\le m}{j}^p\le m^{p+1}$ and ${\sum }_{m\mathrm{/}4\le j\le m\mathrm{/}2}{j}^p\ge c_p{m}^{p+1}$ for all sufficiently large $m$, by counting at least $m\mathrm{/}8$ terms each at least $(m\mathrm{/}4{)}^p$. Applying these bounds with $p=4\beta$ and $p=4\beta +2\alpha$ gives $J_1\asymp m^{4\beta +1},J_0\asymp m^{4\beta +1},J_2=A{\sum }_{j\le m}{j}^{4\beta +2\alpha }(1-A{j}^{2\alpha })\asymp m^{4\beta +1}\mathrm{.}$ Thus [F1] yields $r^2\asymp A\asymp m^{-2\alpha }$ and $u_{\epsilon }^2\asymp {\epsilon }^{-4}{r}^4{m}^{-(4\beta +1)}$.

Since $m\asymp r^{-1\mathrm{/}\alpha }$, the last expression becomes $u_{\epsilon }^2\asymp {\epsilon }^{-4}{r}^{4+(4\beta +1)\mathrm{/}\alpha }=(r\mathrm{/}{\epsilon }^{4\alpha \mathrm{/}(4\alpha +4\beta +1)}{)}^{4+(4\beta +1)\mathrm{/}\alpha }$. Hence radii with ratio tending to zero give $u_{\epsilon }\to 0$, and [F1] gives the indistinguishability limits. For a ratio tending to infinity, if $r_{\epsilon }$ does not tend to zero, replace it by ${\bar{r}}_{\epsilon }=\sqrt{r_{\epsilon }{r}_{\epsilon }^{\ast }}$: nonempty alternatives satisfy $r_{\epsilon }\le a_1^{-1}$, so ${\bar{r}}_{\epsilon }\to 0$, ${\bar{r}}_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$, and ${\mathrm{\Theta }}_2(r_{\epsilon })\subseteq {\mathrm{\Theta }}_2({\bar{r}}_{\epsilon })$. The consistent tests from [F1] at ${\bar{r}}_{\epsilon }$ therefore also work at $r_{\epsilon }$. This proves the stated separation rate.

Let $m$ be the largest active index. Then $A{e}^{2\alpha m}<1\le A{e}^{2\alpha (m+1)}$, so $t=A{e}^{2\alpha m}\in [e^{-2\alpha },1)$. For $j=m-\mathrm{\ell }$ with $0\le \mathrm{\ell }<m$, the profile factor is ${\rho }_{\mathrm{\ell }}=1-t{e}^{-2\alpha \mathrm{\ell }}$. For $\mathrm{\ell }\ge 1$, $1-e^{-2\alpha }\le {\rho }_{\mathrm{\ell }}\le 1$. Hence the terms with $1\le \mathrm{\ell }\le m\mathrm{/}2$ give a lower bound for $J_1$ and $J_0$, while the full sums are bounded above by ${\sum }_{j\le m}{j}^{4\beta }\le m^{4\beta +1}$. Thus $J_1\asymp J_0\asymp m^{4\beta +1}$. In $J_2$, the summand at $\mathrm{\ell }$ is $t{e}^{-2\alpha \mathrm{\ell }}(m-\mathrm{\ell }{)}^{4\beta }{\rho }_{\mathrm{\ell }}$. Its sum is at most $m^{4\beta }{\sum }_{\mathrm{\ell }\ge 0}{e}^{-2\alpha \mathrm{\ell }}\le C_{\alpha }{m}^{4\beta }$, and the $\mathrm{\ell }=1$ term is at least $c_{\alpha ,\beta }{m}^{4\beta }$ for $m\ge 2$. Therefore $J_2\asymp m^{4\beta }$. Formula [F1] gives $r^2\asymp e^{-2\alpha m}m,u_{\epsilon }^2\asymp {\epsilon }^{-4}{r}^4{m}^{-(4\beta +1)}\mathrm{.}$ Taking logarithms of the first relation shows $m\asymp \log (1\mathrm{/}r)$.

Set $L=\log {\epsilon }^{-1}$ and $r_{\epsilon }^{\ast }=\epsilon L^{\beta +1\mathrm{/}4}$. At this radius, $\log (1\mathrm{/}{r}_{\epsilon }^{\ast })\sim L$, so [F1] and step 1.1 give $u_{\epsilon }^2\asymp 1$. If $r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to 0$, then $\log (1\mathrm{/}{r}_{\epsilon })\ge \log (1\mathrm{/}{r}_{\epsilon }^{\ast })\sim L$ and $u_{\epsilon }^2\asymp (r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }{)}^4{\left(\frac{\log (1\mathrm{/}{r}_{\epsilon }^{\ast })}{\log (1\mathrm{/}{r}_{\epsilon })}\right)}^{4\beta +1}\to 0.$ If $r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$ and $r_{\epsilon }\to 0$, the logarithm ratio is at least one, so $u_{\epsilon }\to \mathrm{\infty }$. If the radii do not tend to zero, use ${\bar{r}}_{\epsilon }=\sqrt{r_{\epsilon }{r}_{\epsilon }^{\ast }}$. Nonempty alternatives satisfy $r_{\epsilon }^2\le a_1^{-2}$ because ${\sum }_j{\sigma }_j^2{\eta }_j^2\le a_1^{-2}{\sum }_j{a}_j^2{\sigma }_j^2{\eta }_j^2\le a_1^{-2}$. Hence ${\bar{r}}_{\epsilon }\to 0$, ${\bar{r}}_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$, and ${\mathrm{\Theta }}_2(r_{\epsilon })\subseteq {\mathrm{\Theta }}_2({\bar{r}}_{\epsilon })$; consistent tests for the larger class work on the original class. The two risk implications in [F1] prove the claimed rate.

Let $m$ be the largest active index, so $(m+1{)}^{-2\alpha }\le A<m^{-2\alpha }$, and write $\mathrm{\ell }=m-j$. For $1\le \mathrm{\ell }\le m\mathrm{/}2$, the mean-value theorem applied to $x^{2\alpha }$ on $[1\mathrm{/}2,1]$ gives $c_{\alpha }\frac{\mathrm{\ell }+1}{m}\le 1-A(m-\mathrm{\ell }{)}^{2\alpha }\le C_{\alpha }\frac{\mathrm{\ell }+1}{m}\mathrm{.}$ For $\mathrm{\ell }>m\mathrm{/}2$, the profile factor is at most one. Summing against ${\sigma }_j^4=e^{4\beta m}{e}^{-4\beta \mathrm{\ell }}$, the near terms are bounded by the convergent sums ${\sum }_{\mathrm{\ell }\ge 0}(\mathrm{\ell }+1)e^{-4\beta \mathrm{\ell }}$ and ${\sum }_{\mathrm{\ell }\ge 0}(\mathrm{\ell }+1{)}^2{e}^{-4\beta \mathrm{\ell }}$, and the far tail is exponentially smaller than $m^{-2}$. The $\mathrm{\ell }=1$ term supplies matching lower bounds. Thus $J_1\asymp J_2\asymp e^{4\beta m}\mathrm{/}m,J_0\asymp e^{4\beta m}\mathrm{/}{m}^2\mathrm{.}$ For $J_2$, its extra factor $A{a}_j^2$ is at most one and is bounded below by a positive constant at $j=m-1$. Consequently [F1] gives $r^2\asymp A\asymp m^{-2\alpha }$ and $u_{\epsilon }^2\asymp {\epsilon }^{-4}{r}^4{e}^{-4\beta m}$.

The cutoff relation implies $m\asymp r^{-1\mathrm{/}\alpha }$. For $r_{\epsilon }^{\ast }=(\log {\epsilon }^{-1}\mathrm{/}\beta {)}^{-\alpha }$, if $r_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to 0$, then $m\mathrm{/}(\log {\epsilon }^{-1}\mathrm{/}\beta )\to \mathrm{\infty }$, so the expression in step 1.1 tends to zero. If the ratio tends to infinity while $r_{\epsilon }\to 0$, then $m=o(\log {\epsilon }^{-1})$ and $\log u_{\epsilon }^2=4\log {\epsilon }^{-1}-4\beta m+4\log r_{\epsilon }+O(1)\to \mathrm{\infty }$, because $\log (1\mathrm{/}{r}_{\epsilon })=O(\log \log {\epsilon }^{-1})$. If $r_{\epsilon }$ does not tend to zero, reduce to ${\bar{r}}_{\epsilon }=\sqrt{r_{\epsilon }{r}_{\epsilon }^{\ast }}$. Nonempty alternatives satisfy $r_{\epsilon }^2\le a_1^{-2}$ by the two q=2 constraints, so ${\bar{r}}_{\epsilon }\to 0$ and ${\bar{r}}_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$. The inclusion ${\mathrm{\Theta }}_2(r_{\epsilon })\subseteq {\mathrm{\Theta }}_2({\bar{r}}_{\epsilon })$ transfers consistent tests to the original class. By [F1], these limits prove the displayed rate.

Let $m$ be the largest active index and put $t=A{e}^{2\alpha m}\in [e^{-2\alpha },1)$. For $j=m-\mathrm{\ell }$, the profile factor is ${\rho }_{\mathrm{\ell }}=1-t{e}^{-2\alpha \mathrm{\ell }}$. For every $\mathrm{\ell }\ge 1$, $1-e^{-2\alpha }\le {\rho }_{\mathrm{\ell }}\le 1$, while $0\le {\rho }_0\le 1$. The sums for $J_1$ and $J_0$ are geometric in $\mathrm{\ell }$; their $\mathrm{\ell }=1$ terms give positive lower bounds and the full geometric sums give upper bounds, so $J_1\asymp J_0\asymp e^{4\beta m}$. In $J_2$, the summands are $t{e}^{-(2\alpha +4\beta )\mathrm{\ell }}{\rho }_{\mathrm{\ell }}{e}^{4\beta m}$; the $\mathrm{\ell }=1$ term is bounded below by a positive constant times $e^{4\beta m}$, and the geometric series gives the matching upper bound. Thus $J_2\asymp e^{4\beta m}$. By [F1], $r^2\asymp A\asymp e^{-2\alpha m},u_{\epsilon }^2\asymp {\epsilon }^{-4}{r}^4{e}^{-4\beta m}\asymp {\epsilon }^{-4}{r}^{4+4\beta \mathrm{/}\alpha }\mathrm{.}$

The last expression is comparable to $(r\mathrm{/}{\epsilon }^{\alpha \mathrm{/}(\alpha +\beta )}{)}^{4+4\beta \mathrm{/}\alpha }$. Thus radii below the displayed scale by a factor tending to zero have $u_{\epsilon }\to 0$, and radii above it by a factor tending to infinity have $u_{\epsilon }\to \mathrm{\infty }$ when $r_{\epsilon }\to 0$. If $r_{\epsilon }$ does not tend to zero, reduce to ${\bar{r}}_{\epsilon }=\sqrt{r_{\epsilon }{r}_{\epsilon }^{\ast }}$. Nonempty alternatives satisfy $r_{\epsilon }^2\le a_1^{-2}$ by the two q=2 constraints, so ${\bar{r}}_{\epsilon }\to 0$ and ${\bar{r}}_{\epsilon }\mathrm{/}{r}_{\epsilon }^{\ast }\to \mathrm{\infty }$. The inclusion ${\mathrm{\Theta }}_2(r_{\epsilon })\subseteq {\mathrm{\Theta }}_2({\bar{r}}_{\epsilon })$ transfers consistent tests to the original class. The risk implications in [F1] establish the separation rate.