Sieve metric entropy produces uniform exponential tests

Put $\eta :=1\mathrm{/}128$ and, for integers $j\ge 0$, set $a_j:=(M+j){ϵ}_n$ and $S_{n,j}:=\{p\in {\mathcal{F}}_n:a_j<d(p,p_0)\le a_j+{ϵ}_n\}$. These shells cover every $p$ with $d(p,p_0)>M{ϵ}_n$. The selected metrics are bounded on probability densities: $h^2\le 2$ by [F1], $d_1\le 2$ by [F17] and the unit-mass densities, and in the $d_2$ branch only, [A2] and [F17] give $d_2^2\le \int (p+p_0{)}^{2}d\mu \le 2B\int (p+p_0)d\mu =4B$. Thus only finitely many shells are nonempty for fixed $n$. For each nonempty shell choose a maximal subset $Q_{n,j}\subseteq S_{n,j}$ whose distinct points are more than $r_j:=\eta a_j$ apart. Such a finite maximal set exists: the attainable cardinalities of finite $r_j$-separated subsets form a nonempty bounded subset of $\mathbb{N}$, so a largest cardinality is attained. Since $a_j\ge M{ϵ}_n$ and $M\ge 128$, $r_j\ge {ϵ}_n$; its size is at most $D({ϵ}_n,{\mathcal{F}}_n,d)\le e^{n{ϵ}_n^2}$. Maximality puts every shell member within $r_j$ of a center, and the triangle inequality gives $d(q,p_0)>(1-\eta )a_j$ for each center. Only finitely many choices are made for each $n$, so no arbitrary-index choice axiom is used to form the nets.

Now let $d=d_1$. For a center $q$ in shell $j$, put $s:=d_1(q,p_0)>(1-\eta )a$, $r=\eta a$, and $f(x):=\mathrm{sign}(q(x)-p_0(x))$, with $\mathrm{sign}(0)=1$. By [F15, F16], $f$ is measurable, so its sample mean and threshold event are measurable. Then $\mathrm{\mid }f\mathrm{\mid }\le 1$, $P_{q}f-P_{0}f=s$, and every $p$ with $d_1(p,q)\le r$ satisfies $P_{p}f-P_{0}f\ge \mathrm{\Delta }:=s-r>(1-2\eta )a$. Test by whether the sample mean of $f(X_i)$ is at least $P_{0}f+\mathrm{\Delta }\mathrm{/}2$. Under either law, the centered summands have variance at most one and absolute value at most two; also $\mathrm{\Delta }\le s\le 2$. Bernstein [F4] with $t=n\mathrm{\Delta }\mathrm{/}2$, total variance at most $n$ and bound $b=2$ gives exponent at least $n{\mathrm{\Delta }}^2\mathrm{/}[8(1+\mathrm{\Delta }\mathrm{/}3)]\ge 3n{\mathrm{\Delta }}^2\mathrm{/}40$, so each error is at most $\exp (-3n{\mathrm{\Delta }}^2\mathrm{/}40)$. Thus this branch has $c_1=3(1-2\eta {)}^2\mathrm{/}40$.

Now let $d=d_2$ and assume [A2]. At center $q$, put $s:=\parallel q-p_0{\parallel }_2>(1-\eta )a$, $r=\eta a$, and $f:=q-p_0$. This is measurable by [F15]. Then $P_{q}f-P_{0}f=s^2$. Since $r\mathrm{/}s<\eta \mathrm{/}(1-\eta )<1\mathrm{/}2$, every $p$ with $\parallel p-q{\parallel }_2\le r$ satisfies, by [F10], $P_{p}f-P_{0}f\ge \mathrm{\Delta }:=s^2-rs\ge s^2\mathrm{/}2$. Also $\mathrm{\Delta }\le s^2$, ${\mathbb{E}}_{R}f(X{)}^2\le B{s}^2$ for $R=P_0$ or $P$ by [A2] and monotonicity [F17], and $\mathrm{\mid }f(X)-Rf\mathrm{\mid }\le 2B$ under either law because $\mathrm{\mid }f\mathrm{\mid }\le B$. Testing the sample mean at threshold $P_{0}f+\mathrm{\Delta }\mathrm{/}2$ and applying [F4] with total variance at most $nB{s}^2$, bound $b=2B$, and $t=n\mathrm{\Delta }\mathrm{/}2$ gives exponent at least $3n{s}^2\mathrm{/}(128B)\ge 3n{a}^2\mathrm{/}(512B)$. Thus each error is at most $\exp (-3n{a}^2\mathrm{/}(512B))$ and $c_2=3\mathrm{/}(512B)$.

Fix a nonempty shell, write $a:=a_j$, $r:=\eta a$, and let $q\in Q_{n,j}$. First consider $d=h$. Write $s_0=(1-\eta )a$ and $\rho :=\int \sqrt{p_{0}q}d\mu =1-h(P_0,Q{)}^2\mathrm{/}2$. By [F10], $0\le \rho \le 1$; the affinity integrand is measurable by [F15, F16]. Since $h(P_0,Q)>s_0$, this gives $\rho \le 1-s_0^2\mathrm{/}2$. By step 1.1 and nonemptiness, $s_0^2\le 2$. Set $m:=\lceil 2\log (8)\mathrm{/}{s}_0^2\rceil$. For $u=s_0^2\mathrm{/}2\in [0,1]$, $e^{-u}-(1-u)$ has value zero at $u=0$ and derivative $1-e^{-u}\ge 0$ by monotonicity of the exponential; hence $1-u\le e^{-u}$. On a block of $m$ observations use $T=\mathbf{1}\{{\prod }_{i=1}^{m}q(X_i)>{\prod }_{i=1}^m{p}_0(X_i)\}$. The products and comparison event are measurable by [F15, F16]. Tonelli on the finite product space gives product affinity ${\rho }^m$, and ${\rho }^m\le (1-u{)}^m\le e^{-mu}\le 1\mathrm{/}8$. Its type-I error under $P_0^m$ is at most this affinity, since on $T=1$ the product density $p_0^{\otimes m}$ is at most $\sqrt{p_0^{\otimes m}{q}^{\otimes m}}$; its type-II error under $Q^m$ is at most the same bound by the symmetric inequality on $T=0$.

If $p$ lies in the Hellinger ball $h(P,Q)\le r$, then Tonelli on the measurable product densities gives $h(P^m,Q^m{)}^2=2(1-\rho (P,Q{)}^m)\le mh(P,Q{)}^2$, since $1-z^m=(1-z)(1+z+\cdots +z^{m-1})\le m(1-z)$ for $0\le z\le 1$. By [F2], $\parallel P^m-Q^m{\parallel }_{\mathrm{T}\mathrm{V}}\le h(P^m,Q^m)\le \sqrt{m}r$. Since $a\le \sqrt{2}$ for a nonempty Hellinger shell, $s_0^2\le 2$, $m\le 8\mathrm{/}{s}_0^2$, and $m{r}^2\le 8{\eta }^2\mathrm{/}(1-\eta {)}^2<1\mathrm{/}64$, so $\sqrt{m}r<1\mathrm{/}8$. Indeed, [F11] gives $e^3>1+3+9\mathrm{/}2>8$, hence $\log 8<3$; also $1-\eta >1\mathrm{/}2$. For the event $\{T=0\}$, the change in probability from $Q^m$ to $P^m$ is at most TV, so the type-II error is at most $1\mathrm{/}8+1\mathrm{/}8=1\mathrm{/}4$ uniformly over this ball.

Divide the first $Nm$ observations into $N:=\lfloor n\mathrm{/}m\rfloor$ disjoint blocks and reject when at least half of their block tests reject. The block indicators are independent under both $P_0^n$ and $P^n$ by [F5]–[F6]. Under $P_0$, each has mean at most $1\mathrm{/}8$; under the ball alternatives each has mean at least $3\mathrm{/}4$. Their variances are at most $1\mathrm{/}4$ and their centered absolute values at most one. Under $P_0$, rejection forces an upward deviation at least $3N\mathrm{/}8$, so [F4] gives $\exp [-(3N\mathrm{/}8{)}^2\mathrm{/}(2(N\mathrm{/}4+(3N\mathrm{/}8)\mathrm{/}3))]=e^{-3N\mathrm{/}16}\le e^{-3N\mathrm{/}32}$. Under an alternative, acceptance forces a downward deviation at least $N\mathrm{/}4$, so [F4] gives $\exp [-(N\mathrm{/}4{)}^2\mathrm{/}(2(N\mathrm{/}4+(N\mathrm{/}4)\mathrm{/}3))]=e^{-3N\mathrm{/}32}$. Since $m\le 32\mathrm{/}{a}^2$, $n{a}^2\to \mathrm{\infty }$ implies $n\mathrm{/}m\ge 2$ eventually and $N\ge n\mathrm{/}(2m)\ge n{a}^2\mathrm{/}64$; hence both errors are at most $e^{-3n{a}^2\mathrm{/}2048}$. Thus $c_h=3\mathrm{/}2048$.

In the selected branch let $c_d$ be its constant from steps 4.1, 1.2, or 1.3. If there are no nonempty shells, the alternative set is empty and define ${\varphi }_n\equiv 0$. Otherwise choose each center's local test and let ${\varphi }_n$ be their maximum over the finitely many centers in the nonempty shells. The local tests are measurable by the density-difference, product, and threshold measurability in [F15, F16]; a finite maximum remains measurable. For a fixed alternative in shell $j$, its nearby center supplies type-II error at most $e^{-c_{d}n{a}_j^2}\le e^{-c_d{M}^{2}n{ϵ}_n^2}$. For type I, the union bound over at most $e^{n{ϵ}_n^2}$ centers per shell gives $P_0^n({\varphi }_n=1)\le e^{n{ϵ}_n^2}{\sum }_{j=0}^{\mathrm{\infty }}{e}^{-c_{d}n(M+j{)}^2{ϵ}_n^2}\le 2e^{-(c_d{M}^2-1)n{ϵ}_n^2}$ for all sufficiently large $n$: writing $x=n{ϵ}_n^2$, the sum is $e^{-c_d{M}^{2}x}{\sum }_{j=0}^{\mathrm{\infty }}{e}^{-c_{d}x(2Mj+j^2)}$, whose consecutive-term ratio is at most $e^{-c_{d}x(2M+1)}\le 1\mathrm{/}2$. This proves the two test bounds for the same metric used in the packing condition.