, and

# The Impossibility Region for Detecting Sparse Mixtures using the Higher
Criticism

David L<EMAIL_ADDRESS>[ Alon
<EMAIL_ADDRESS>[  Department of Statistics, Stanford
University, Stanford, CA 94041, USA

###### Abstract

Consider a multiple hypothesis testing setting involving rare/weak effects:
relatively few tests, out of possibly many, deviate from their null hypothesis
behavior. Summarizing the significance of each test by a $P$-value, we
construct a global test against the null using the Higher Criticism (HC)
statistics of these P-values. We calibrate the rare/weak model using
parameters controlling the asymptotic distribution of non-null $P$-values near
zero. We derive a region in the parameter space where the HC test is
asymptotically powerless. Our derivation involves very different tools than
previously used to show powerlessness of HC, relying on properties of the
empirical processes underlying HC. In particular, our result applies to
situations where HC is not asymptotically optimal, or when the asymptotically
detectable region of the parameter space is unknown.

multiple testing,

empirical process,

higher criticism,

phase transition,

###### keywords:

##  1 Background

Multiple hypothesis testing involving rare/weak effects has attracted
significant interest in statistics and machine learning over the last two
decades Donoho and Jin (2004, 2008, 2009); Hall and Jin (2010); Cai et al
(2011); Arias-Castro et al (2011); Cai and Wu (2014); Arias-Castro and Wang
(2015); Li and Siegmund (2015); Moscovich et al (2016); Gontscharuk et al
(2016); Kipnis (2019); Donoho and Kipnis (2020). Roughly speaking, the
rare/weak effect setting proposes that the non-null effect is only moderately
large, and, the non-null effects are present only in a relatively small,
unknown subset of the tests. Here ‘moderately large’ means that the effects
are not so large that they are individually obvious; e.g. they do not
individually stand out after straightforward Bonferroni correction, but they
might conceivably still be detectable using more sensitive methods.

Many of the works cited above show that the Higher Criticism (HC) test of
Donoho and Jin (2004) has interesting optimality properties under a phase
diagram analysis in which the phase space quantifies how rare and how weak the
non-null effects are. In this paper, we derive a region in the phase space
where HC is asymptotically powerless, in the sense that the sum of its Type I
and Type II errors approaches one within this region.

All previous works deriving a region where HC is powerless argue that over the
given region, all possible multiple hypothesis tests must be asymptotically
powerless. Consequently, this derivation settles matters only in cases where
HC is asymptotically fully powerful inside the complement of the derived
region. In such settings, HC will have the optimal phase diagram.

Actually, because the HC statistic is a practitioner’s - rather than a
theoretician’s - tool, it can be used in a wide variety of multiple testing
situations. We have no reason to believe that it has the optimal phase diagram
in general. In situations where HC does not have the optimal phase diagram,
the existing strategy for establishing its region of powerlessness does not
settle matters. There remains the possibility that in certain settings, a
region exists where HC is powerless, and yet some more sensitive multiple
testing approach is fully powerful. As an example when this situation can
arise, suppose that there exists a covariate predicting the presence/absence
of the rare and weak effects. A naive approach is to ignore this covariate and
apply HC to P-values obtained by testing each feature independently. Arguably,
a better approach is to reduce each equivalence class indicated by levels of
the covariate by combining the responses within this class, and applying HC to
the collection of P-values obtained from each equivalent class after this
reduction. As another example, suppose that many effects exist under the
alternative hypothesis, but these effects are too weak for HC to be effective.
Therefore, a test based on a statistics that aggregates the individual weak
effects is expected to be much more powerful than HC. In Section 3 below we
provide specific cases corresponding to these two examples.

##  2 Problem Formulation and Statement of the Main Result

###  2.1 Rare/Weak Features

Consider a multiple hypothesis testing situation involving a collection of
P-values $\pi_{1},\ldots,\pi_{n}$ associated with many independent, although
not necessarily identical, tests. We are interested in testing the global null

$\displaystyle
H_{0}~{}~{}:~{}~{}\pi_{i}\overset{\mathsf{iid}}{\sim}\mathrm{Unif}(0,1),\quad\forall
i=1,\ldots,n,$ (1a) against an alternative of the form $\displaystyle
H_{1}^{(n)}~{}~{}:~{}~{}\pi_{i}\sim(1-\epsilon_{n})\mathrm{Unif}(0,1)+\epsilon_{n}G_{n,i},\quad\text{independently},\quad\forall
i=1,\ldots,n.$ (1b)

Here $\epsilon_{n}=n^{-\beta}$, $\beta\in(0,1)$ is the _rarity_ parameter.
$G_{n,i}$ is a probability distribution stochastically dominated by
$\mathrm{Unif}(0,1)$ that specifies the behavior of the $i$th test whenever
this hypothesis is non-null. We assume that, for $X\sim G_{n,i}$ and $q>0$,

$\displaystyle\max_{i=1,\ldots,n}\left(-\log\left(\Pr(X<n^{-q})\right)\right)\leq\log(n)\left(\alpha(q,r)+o(1)\right),$
(2)

for some bivariate function $\alpha(q,r)$ that is continuous, non-negative,
increasing in $q$ and decreasing in $r$, and $o(1)$ indicates a sequence
tending to zero uniformly in $i$ and $q\in[1/2,1]$ as $n$ goes to infinity.
Note that, because $G_{n,i}$ is stochastically smaller than
$\mathrm{Unif}(0,1)$, only the case $\alpha(q,r)\leq q$ is interesting. As it
turns out, the large $n$ behavior of our test to be defined below only depends
on the bound of the near-zero ”tail” behavior of $G_{n,i}$ specified by
$\alpha(q,r)$ in (2). Effectively, (2) characterizes the way $G_{n,i}$ is
smaller than $\mathrm{Unif}(0,1)$ on values scaling as $n^{-q}$, $q>0$. This
characterization arises in several studies of rare/weak effects considered in
the past:

  * (i)

The normal means model of Donoho and Jin (2004) corresponds to:

$\alpha(q,r)=(\sqrt{q}-\sqrt{r})^{2}.$

  * (ii)

The two-sample normal means and the two-sample _large_ Poisson means models of
Donoho and Kipnis (2020) correspond to:

$\alpha(q,r)=(\sqrt{q}-\sqrt{r/2})^{2}.$

  * (iii)

The two-sample _small_ Poisson means model of Donoho and Kipnis (2020)
corresponds to:

$\alpha(q,r)=q\frac{\log\left(\frac{2q}{r\log(2)}\right)-1}{\log(2)}+\frac{r}{2}.$

  * (iv)

The normal heteroscedastic mixture model of Cai et al (2011) corresponds to:

$\displaystyle\alpha(q,r;\sigma^{2})=(\sqrt{q}-\sqrt{r})^{2}/\sigma^{2},\quad\sigma^{2}>0.$
(3)

More generally, (3) arises under a verity of models in which the non-null
effects are on the moderate deviation scale Kipnis (2021).

###  2.2 Higher Criticism

Let

$\mathrm{HC}_{n,i}\equiv\sqrt{n}\frac{i/n-\pi_{(i)}}{\sqrt{\pi_{(i)}\left(1-\pi_{(i)}\right)}},$

where $\pi_{(i)}$ is the $i$-th order statistic of
$\\{\pi_{i},\,i=1,\ldots,n\\}$. The HC statistic is:

$\displaystyle\mathrm{HC}_{n}^{\star}\equiv\underset{{1\leq i\leq
n\gamma_{0}}}{\max}\mathrm{HC}_{n,i},$ (4)

where $0<\gamma_{0}<1$ is a tunable parameter that does not affect the
asymptotic properties of $\mathrm{HC}_{n}^{\star}$ under $H_{1}^{(n)}$. It
would simplify certain arguments below to fix it at some value smaller than
$1/2$, eg. $1/10$.

The HC test rejects $H_{0}$ for large values of $\mathrm{HC}_{n}^{\star}$.

###  2.3 Impossibility of Detection

We say that a sequence of tests $\\{T_{n}\\}$ based on the P-values
$\pi_{1},\ldots,\pi_{n}$ is _asymptotically powerless_ if

$\Pr_{H_{0}}\left(T_{n}>h(n)\right)+\Pr_{H_{1}^{(n)}}\left(T_{n}\leq
h(n)\right)\to 1,$

for any sequence $\\{h(n)\\}_{n\in\mathbb{N}}$.

Consider the curve $\rho(\beta)$ defined in the plane $(\beta,r)$ as

$\displaystyle\rho(\beta)\equiv\sup\left\\{r>0:\,\max_{q\in(0,1]}\left(\frac{1+q}{2}-\alpha(q,r)-\beta\right)<0\right\\}.$
(5)

Our main result implies that a test based on $\mathrm{HC}_{n}^{\star}$ is
asymptotically powerless when $r<\rho(\beta)$.  Namely, whenever $(\beta,r)$
satisfies

$\displaystyle\max_{q\in(0,1]}\left(\frac{1+q}{2}-\alpha(q,r)-\beta\right)<0.$

######  Theorem 2.1.

Consider testing $H_{0}$ against $H_{1}^{(n)}$. Assume that $G_{n,i}$ has a
continuous density $f_{i}$, and that, for some $C<\infty$,
$\|f_{i}\|_{\infty}=C$ for all $i=1,\ldots,n$. $\mathrm{HC}_{n}^{\star}$ is
asymptotically powerless if $r<\rho(\beta)$.

##  3 Stylized Applications

This paper’s characterization of the region of powerlessness for HC would not
be necessary in situations where some lower bound argument exists showing that
no statistic – including HC – can be powerful over that region. The
powerlessness characterization is much more useful in cases where we want to
show that HC does not have the optimal phase diagram, i.e., in cases where
there exists some other multiple testing procedure that is powerful within the
region where HC is powerless. In such situations, this paper’s
characterisation may allow us to establish limitations on HC which some other
procedures escape. We discuss two situations of this form.

###  3.1 Coupled rare and weak effects

Suppose that we have an array of $n\times k$ response variables
$\\{X_{i,j}\\}_{1\leq i\leq n,1\leq j\leq k}$ experiencing rare and weak
effects where the noise is independent but the signal has structure: If the
rare effect is present in some variable $X_{i_{0},j_{0}}$, it is also present
in the entire row $\\{X_{i_{0},j}\\}_{j=1,\ldots,k}$. This scenario is a
stylized version of the situation mentioned earlier, when a covariate
predicting the presence/absence of the rare and weak effects exists. In this
scenario, rather than considering each pair $(i,j)$ separately, one might
instead combine data within each row to a P-value per row $i$ and then apply
HC to the $n$ per-row P-values associated with each row.

As a concrete model, consider the following rare and weak normal means
setting,

$\displaystyle\begin{split}H_{0}\,&:\,X_{i,j}\overset{\mathsf{iid}}{\sim}\mathcal{N}(0,1)\quad
i=1,\ldots,n,\quad j=1,\ldots,k\\\
H_{1}\,&:\,(X_{i,1},\ldots,X_{i,k})\overset{\mathsf{iid}}{\sim}(1-\epsilon_{n})\mathcal{N}^{k}(0,1)+\epsilon_{n}\cdot\mathcal{N}^{k}(\mu_{n},1),\qquad
i=1,\ldots,n,\end{split}$ (6)

where $\mu_{n}$ and $\epsilon_{n}$ are calibrated to $n$ in the standard
manner:

$\displaystyle\mu_{n}=\sqrt{2r\log(n)},\qquad\epsilon_{n}=n^{-\beta}.$ (7)

We compare the asymptotic power of HC in testing $H_{0}$ versus $H_{1}$ under
two collections of P-values:

$\displaystyle\pi_{i,k}$ $\displaystyle=\Pr(X_{i,j}\geq\mathcal{N}(0,1)),\quad
i=1,\ldots,n,\quad j=1,\ldots,k,$ (8a) versus $\displaystyle\bar{\pi}_{i}$
$\displaystyle=\Pr(\frac{1}{\sqrt{k}}\sum_{j=1}^{k}X_{i,j}\geq\mathcal{N}(0,1)),\quad
i=1,\ldots,n.$ (8b)

Note that
$X_{i,j}\sim(1-\epsilon_{n})\mathcal{N}(0,1)+\epsilon_{n}\mathcal{N}(\mu_{n},1)$
under $H_{1}$, hence (2) holds for $X\sim\mathcal{N}(\mu_{n},1)$ with
$\alpha(q,r)=(\sqrt{q}-\sqrt{r})^{2}$. The upper boundary for the of
impossibility in (5) evaluates to

$\displaystyle\tilde{\rho}(\beta)\equiv\begin{cases}\beta-1/2&\frac{1}{2}<\beta<\frac{3}{4},\\\
1-(1-\sqrt{\beta})^{2}&\frac{3}{4}\leq\beta<1.\end{cases}$

It is straightforward to extend the results in Section 2 to the case where the
response variables are exchangeable but not necessarily independent as in (6),
implying that HC of the usual P-values (8a) is asymptotically powerless
whenever $r<\tilde{\rho}$. On the other hand, in view of (7) and (8b), the
effect in $\bar{\pi}_{i}$ under $H_{1}$ is $k$ times stronger than the effect
in $\pi_{i,j}$, while the linear reduction in the sample size from $n\cdot k$
to $n$ when moving from $\\{\pi_{i,j}\\}$ to $\\{\bar{\pi}_{i}\\}$ does not
affect the asymptotic performance of HC. Consequently, a standard analysis of
HC applied to $\\{\bar{\pi}_{i}\\}$ implies that it has full power whenever
$r>\tilde{\rho}/k$ Donoho and Jin (2004).

In short, the region of full power in the phase diagram based on reduction to
$\bar{\pi}_{i}$ is considerably larger than the region of full power for the
usual p-values ${\pi}_{i}$, thereby enabling a comparison between a better
phase diagram and a less good one.

###  3.2 Many weak effects but too few moderately large ones

Another situation where HC is ineffective compared to other tests is in the
presence of a mixture of two types of effects: many weak effects and rare,
moderately large effects. In certain settings it can be better to aggregate
all the individual responses before reducing each response to a P-value.

As a specific model, consider the multiple hypothesis testing problem

$\displaystyle
H_{0}\,:\,X_{i}\overset{\mathsf{iid}}{\sim}\mathcal{N}(0,1),\quad
i=1,\ldots,n,$ (9) $\displaystyle
H_{1}\,:X_{i}\overset{\mathsf{iid}}{\sim}(1-\epsilon_{n})\mathcal{N}(a_{n},1)+\epsilon_{n}\mathcal{N}(\mu_{n},1),\quad
i=1,\ldots,n,$ (10)

where $\epsilon_{n}$ and $\mu_{n}$ are calibrated as in (7). If $a_{n}\to 0$
and $r<\tilde{\rho}(\beta)$, then the analysis provided in this paper implies
that HC is asymptotically powerless. Nevertheless, an easy calculation shows
that a test that is based on $\sum_{i=1}^{n}X_{i}^{2}$ is asymptotically
powerful provided $a_{n}n^{1/2}\to\infty$.

##  4 Proof of Theorem 2.1

###  4.1 Coupling

Let $I$ be a random subset of indices in $[n]\equiv\\{1,\ldots,n\\}$ such that
$i\in I$ with probability $\epsilon_{n}=n^{-\beta}$, for $i=1,\ldots,n$. An
equivalent way of specifying $H_{1}^{(n)}$ of (1b) sets

$\displaystyle\pi_{i}\sim\begin{cases}G_{n,i}&i\in I\\\
\mathrm{Unif}(0,1)&i\neq I.\end{cases}$ (11)

Let $Q_{i}^{(0)}$ and $Q_{i}^{(1)}$ denote the realized P-values under $H_{0}$
and $H_{1}^{(n)}$, respectively. On a common probability space, we couple
these P-values so that

$\displaystyle\begin{split}Q_{i}^{(0)}&\neq Q_{i}^{(1)},\quad i\in I,\\\
Q_{i}^{(0)}&=Q_{i}^{(1)},\quad i\in I^{c}.\end{split}$ (12)

For $h\in\\{0,1\\}$, define

$\displaystyle\mathrm{HC}_{n}^{(h)}$
$\displaystyle=\max_{i=1,\ldots,\gamma_{0}n}\sqrt{n}\frac{\frac{i}{n}-Q_{(i)}^{(h)}}{\sqrt{Q_{(i)}^{(h)}(1-Q_{(i)}^{(h)})}}.$

For $h=0,1$, the joint distribution of the collection
$\\{Q_{i}^{(h)}\\}_{i=1}^{n}$ is identical to the joint distribution of
$\\{\pi_{i}\\}_{i=1}^{n}$ under $H_{h}^{(n)}$. The coupling device should make
clear to the reader that the vast majority of P-values are the same actual
numbers under either hypothesis; the ones that are different appear
sporadically in $[n]$; they are concentrated in the index list $I$. We will
argue that under certain conditions, the different P-values are so thinned out
that their differences are not sufficient to allow the HC statistic to behave
differently between the two hypotheses.

######  Theorem 4.1.

Let $\mathrm{HC}_{n}^{(0)}$ and $\mathrm{HC}_{n}^{(1)}$ be defined on a common
probability space where the underlying P-values $\\{Q_{i}^{(0)}\\}_{i=1}^{n}$
and $\\{Q_{i}^{(1)}\\}_{i=1}^{n}$ are coupled as in (12). Assume that
$G_{n,i}$ has a continuous density $f_{i}$, and that, for some $C<\infty$,
$\|f_{i}\|_{\infty}=C$ for all $i=1,\ldots,n$. Suppose that $(r,\beta)$ obeys
$r<\rho(\beta)$. Then, for $c>0$,

$\Pr\left(\mathrm{HC}_{n}^{(1)}>\mathrm{HC}_{n}^{(0)}+c\right)\to
0,\quad\text{ as }n\to\infty.$

Theorem 2.1 follows immediately. The proof of Theorem 4.1 requires additional
notation and preliminary technical lemmas as provided below.

###  4.2 Preliminaries

For any $(\beta,r)\in(1/2,1)\times(0,\infty)$,

$\displaystyle\max_{q\in(0,1]}\left(\frac{1+q}{2}-\alpha(q,r)-\beta\right)<0\Leftrightarrow
r<\rho(\beta).$ (13)

The condition:

$\displaystyle 1-\alpha(1,r)-\beta<0$ (14)

coincides with the condition $r<\rho(\beta)$ only if $q=1$ is the maximizer of
(13). Therefore, any $(\beta,r)$ such that $r<\rho(\beta)$ also satisfies
(14).

Denote by $M\equiv M_{n}\sim\mathrm{Bin}(n,\epsilon_{n})$ the RV indicating
the cardinality of $I$. For $h\in\\{0,1\\}$, denote by

$F_{n}^{(h)}(t)\equiv\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}(Q_{i}^{(h)}\leq t),$

the empirical CDF of the P-values $\\{Q^{(h)}_{i}\\}_{i=1}^{n}$, and denote by

$\displaystyle H^{(h)}(u)\equiv\frac{1}{M}\sum_{i\in
I}\mathbf{1}(Q_{i}^{(h)}\leq u),$ (15)

the empirical CDF’s of P-values in the thin subset $I$. Define

$\Delta_{n}(t)\equiv F_{n}^{(1)}(t)-F_{n}^{(0)}(t).$

Also, set

$\displaystyle\tilde{F}^{(h)}(t)\equiv\frac{M}{n}H^{(h)}(t).$ (16)

Note that although $\tilde{F}^{(h)}(u)$ is scaled like the empirical CDF of
$n$ random variables, there are actually only $M$ RVs involved. Furthermore,

$\displaystyle\Delta_{n}(t)=\tilde{F}^{(1)}(t)-\tilde{F}^{(0)}(t).$ (17)

It is crucial for our analysis that the difference CDF is normalized in some
sense by $n$, while coupling shows that it involves only $M$ nontrivial
contributions.

Enumerate the elements of $I$ with indices $i_{1},\ldots,i_{M}$ :

$\bar{Q}_{j}^{(h)}\equiv Q_{i_{j}}^{(h)},\quad i\in I.$

Our key assumption (1b) implies that

$\displaystyle-\log(\Pr(\bar{Q}_{j}^{(1)}<n^{-q}))=\log(n)\left(\alpha(q,r)+o(1)\right),$
(18)

where the term $o(1)$ is independent of $j$. Finally, consider a grid

$\displaystyle\mathcal{U}_{n}=\\{u_{k;n}\\}\subset(0,1)$ (19)

with spacing $n^{-3}$.

In what follows, we state and prove a series of preliminary technical lemmas.

######  Lemma 4.2.

For $\beta\in(0,1)$ and $\eta>0$ such that $1-\beta+\eta>0$, define the event

$\displaystyle\Omega_{n}\equiv\\{M<n^{1-\beta+\eta}\\}.$ (20)

There exists $n_{0}\equiv n_{0}(\beta,\eta)$ such that

$\displaystyle\Pr(\Omega_{n})\leq e^{-n^{1-\beta+\eta}},\qquad n\geq n_{0}.$
(21)

#### Proof of Lemma 4.2

As $M\sim\mathrm{Bin}(n,n^{-\beta})$, by the Chernoff bound (Mitzenmacher and
Upfal, 2017, Ch. 4),

$\displaystyle\Pr\left(M\geq
n^{1-\beta+\eta}\right)\leq\exp(-nD(n^{-\beta+\eta}\parallel n^{-\beta})),$
(22)

where $D(x\parallel y)\equiv x\log(x/y)+(1-y)\log((1-x)/(1-y))$. Inspection of
the first term $x\log(x/y)$ shows that, for some $c>0$ and
$n_{0}=n_{0}(\beta,c)$ we have:

$\displaystyle nD(n^{-\beta+\eta}\parallel n^{-\beta})\geq
n^{1-\beta+\eta}\log(n)\cdot c,\quad n\geq n_{0}$ (23)

for all $n\geq n_{0}(\beta,c)$. Now combine (22) with (23). ∎

The next lemma expresses a key insight. Consider the relatively few $P$-values
that are different under $H_{0}$ and $H_{1}$; the smallest of any of these is
still much much larger than many $P$-values that are the same under $H_{0}$
and $H_{1}$. Hence the “place” we will be looking for differences in the
behavior of $F_{n}^{(h)}(x)$ will not be at the far extreme $x\approx 0$.

######  Lemma 4.3.

Let $\bar{Q}_{-}=\min\\{\bar{Q}_{(1)}^{(0)},\bar{Q}_{(1)}^{(1)}\\}$ and
$Q_{-}=\min\\{Q_{(1)}^{(0)},Q_{(1)}^{(1)}\\}$. Suppose that $(\beta,r)$
satisfies (14). Then, for $\delta>0$,

$\displaystyle\Pr\left(n\bar{Q}_{-}>n^{\delta}\right)\to 1,$ (24)

and

$\displaystyle\Pr\left(Q_{-}<\bar{Q}_{-}\right)\to 1.$ (25)

#### Proof of Lemma 4.3

As $(\beta,r)$ satisfies (14) and since $\alpha(q,r)$ is continuous in a semi-
neighborhood around $q<1$, there exists $\delta>0$ and $\eta>0$ such that

$1-\alpha(1-\delta,r)-\beta-\eta<0.$ (26)

From (18), we have, conditionally on $M$,

$\displaystyle\Pr\left(\bar{Q}_{(1)}^{(1)}\leq
n^{-1+\delta}{|M}\right)={1-\Pr(\bar{Q}_{j}^{(h)}>n^{-1+\delta},j=1,\dots,M)}$
$\displaystyle=1-\prod_{j=1}^{M}\left(1-\Pr\left(\bar{Q}_{{j}}^{(1)}\leq
n^{-1+\delta}\right)\right)$ $\displaystyle\leq
1-\left(1-n^{{-\alpha(1-\delta,r)}+o(1)}\right)^{M}\leq
Mn^{{-\alpha(1-\delta,r)}+o(1)},$

where in the last transition we used the inequality111Indeed,
$M\cdot\log(1+x)>\log(1+Mx)$. $(1+x)^{M}\geq 1+Mx$, $x\geq-1$; where, of
course, the term $n^{{-\alpha(q,r)}+o(1)}<1$ (ie. it represents a term which
always belongs to $(0,1)$). Hence unconditionally, by Lemma 4.2,

$\displaystyle\Pr\left(\bar{Q}_{(1)}^{(1)}\leq n^{-1+\delta}\right)$
$\displaystyle\leq\Pr\left(M\cdot
n^{-\alpha(1-\delta,r)+o(1)}\mid\Omega_{n}\right)+P(\Omega_{n}^{c})$
$\displaystyle\leq n^{1-\beta+\eta}\cdot
n^{-\alpha(1-\delta,r)+o(1)}+e^{-n^{1-\beta+\eta/2}}.$

Our assumption $r<\rho(\beta)$ yields (26) and, so

$\displaystyle\Pr\left(\bar{Q}_{(1)}^{(1)}\leq n^{-1+\delta}\right)$
$\displaystyle\leq n^{-\eta/2+o(1)}+o(1)\to 0;$

hence $\Pr\left(n\bar{Q}_{(1)}^{(1)}\geq n^{\delta}\right)\to 1$. Similarly,
conditionally on $M$, $\bar{Q}_{(1)}^{(0)}$ is the minimum of $M$ random
variables $(W_{j})_{j=1}^{M}$ (say) iid uniform over $(0,1)$, and so:

$\displaystyle\Pr\left(\bar{Q}_{(1)}^{(0)}\leq n^{\delta-1}|M\right)$
$\displaystyle\geq 1-\Pr\\{W_{j}>n^{\delta-1},j=1,\dots,M\\}$
$\displaystyle=1-\left(1-n^{\delta-1}\right)^{M}$ $\displaystyle\leq
Mn^{-1}\leq n^{-\beta}(1+o(1)),$

Unconditionally,

$\Pr\left(\bar{Q}_{(1)}^{(1)}\leq n^{-1+\delta}\right)\leq
n^{-\beta}(1+o(1))+P(\Omega_{n}^{c})\rightarrow 0,$

using $\beta>0$ and (by Lemma 4.2) $\Pr(\Omega_{n})\to 1$. Hence
$\Pr\left(n\bar{Q}_{(1)}^{(0)}\geq n^{\delta}\right)\to 1$ and (24) follows.
For the claim in (25), note that $Q_{(0)}^{(0)}$ is the minimum of $n$ iid RVs
uniform over $(0,1)$, hence

$\displaystyle\Pr\left(Q_{(0)}^{(0)}\leq\frac{\log(n)}{n}\right)=1-\left(1-\frac{\log(n)}{n}\right)^{n}\to
1,$

while (24) implies

$\displaystyle\Pr\left(\bar{Q}_{-}\leq\frac{\log(n)}{n}\right)\to 0.$

Consequently,

$\displaystyle\Pr\left(Q_{-}<\bar{Q}_{-}\right)$
$\displaystyle\geq\Pr\left(Q_{(1)}^{(0)}\leq\frac{\log(n)}{n}<\bar{Q}_{-}\right)$
$\displaystyle\geq
1-\Pr\left(Q_{(1)}^{(0)}>\frac{\log(n)}{n}\right)-\Pr\left(\bar{Q}_{-}\leq\frac{\log(n)}{n}\right)\to
1.$

######  Lemma 4.4.

Under the conditions of Lemma 4.3, we may define

$Q_{+}\triangleq\max\\{Q_{i}^{(0)}\,:\,Q_{i}^{(0)}<\bar{Q}_{-}\\}.$

Then for $\delta_{1}>0$,

$\displaystyle n^{1-\delta_{1}}\left|Q_{+}-\bar{Q}_{-}\right|\to_{p}0.$ (27)

Furthermore, for $\delta_{2}>0$,

$\displaystyle\Pr\left(nQ_{+}>n^{\delta_{2}}\right)\to 1.$ (28)

#### Proof of Lemma 4.4

Set $S\equiv\bar{Q}_{(1)}^{(0)}-Q_{+}$, so that
$S\geq\left|\bar{Q}_{-}-Q_{+}\right|$. Now, $Q_{+}$ and $\bar{Q}_{(1)}^{(0)}$
correspond to a consecutive pair in
$\\{Q_{(1)}^{(0)},\ldots,Q_{(n)}^{(0)}\\}$. Therefore,
$S\sim\mathrm{Beta}(1,n)$, i.e., $\Pr(S\leq t)=1-(1-t)^{n}$. Consequently, for
any $\epsilon>0$,

$\Pr\left(n^{1-\delta_{1}}\left|\bar{Q}_{-}-Q_{+}\right|<\epsilon\right)\leq\Pr\left(S<\epsilon
n^{\delta_{1}-1}\right)=1-(1-\epsilon n^{\delta_{1}-1})^{n}\sim 1-e^{-\epsilon
n^{\delta_{1}}}\to 0.$

This proves the claim (27). Next, fix $\delta_{2}>0$. From Lemma 4.3,

$\Pr\left(n\bar{Q}_{-}>n^{\delta_{2}}\right)\to 1.$

Take $\delta_{1}<\delta_{2}$. We have
$\bar{Q}_{i}-Q_{+}=o_{p}(1)n^{\delta_{1}-1}\leq o_{p}(1)n^{\delta_{2}-1}\leq
o_{p}(1)\bar{Q}_{-}$, hence

$Q_{+}=(1+o_{p}(1))\bar{Q}_{-},$

and

$\displaystyle\Pr\left(nQ_{+}>n^{\delta_{2}}\right)$
$\displaystyle=\Pr\left(n\bar{Q}_{-}(1+o_{p}(1))>n^{\delta_{2}}\right)\to 1,$

which implies (25). ∎

Fix $t_{1}<1/2$. Let
$\bar{Q}_{-}\equiv\min\\{\bar{Q}_{(1)}^{(0)},\bar{Q}_{(1)}^{(1)}\\}$ and
$Q_{-}=\min\\{Q_{(1)}^{(0)},Q_{(1)}^{(1)}\\}$. Suppose that
$Q_{-}<\bar{Q}_{-}$. Then the set
$\\{Q_{i}^{(0)}\,:\,Q_{i}^{(0)}<\bar{Q}_{-}\\}$ is non-empty by Lemma 4.3.
Define $Q_{+}=\max\\{Q_{i}^{(0)}\,:\,Q_{i}^{(0)}<\bar{Q}_{-}\\}$.

######  Lemma 4.5.

We have

$\mathrm{HC}^{(1)}-\mathrm{HC}^{(0)}\leq\sup_{t\in[Q_{+},t_{1}]}\sqrt{n}\Delta_{n}(t)w(t),$

where

$w(t)\equiv\frac{1}{\sqrt{t(1-t)}}.$

####  4.2.1  Proof of Lemma 4.5

Because $Q_{(1)}^{(0)}<\bar{Q}_{-}$, it is also true that
$Q_{(1)}^{(1)}<\bar{Q}_{-}$ and, moreover, that
$Q_{(1)}^{(1)}=Q_{(1)}^{(0)}=Q_{-}$. In fact,

$\displaystyle\left\\{Q_{i}^{(0)}:Q_{i}^{(0)}<\bar{Q}_{-}\right\\}=\left\\{Q_{i}^{(1)}:Q_{i}^{(1)}<\bar{Q}_{-}\right\\},$
(29)

and the set defined this way is nonempty. Also $Q^{+}$ is a jump point of both
$F_{n}^{(0)}(t)$ and of $F_{n}^{(1)}(t)$.

For any left-closed interval $D=[a,b)$ or $D=[a,b]$, define

$\displaystyle\mathrm{HC}^{(h)}_{D}=\max_{{t\in\\{Q_{i}^{(h)}\\}\cap
D}}\sqrt{n}\cdot{\left(F_{n}^{(h)}(t)-t\right)}w(t);$ (30)

i.e. in each case we are maximizing of the jump points of $F_{n}^{(h)}(t)$ in
$D$. From (29),

$\displaystyle\mathrm{HC}^{(0)}_{[Q_{-},Q_{+}]}$
$\displaystyle=\mathrm{HC}^{(1)}_{[Q_{-},Q_{+}]}=\mathrm{HC}^{(0)}_{[Q_{(1)}^{(0)},Q_{+}]}$
$\displaystyle=\mathrm{HC}^{(1)}_{[Q_{(1)}^{(1)},Q_{+}]}=\mathrm{HC}^{(1)}_{[Q_{-},Q_{+}]}.$

Now, observe that, for $h\in\\{0,1\\}$,

$\mathrm{HC}^{(h)}=\max\left(\mathrm{HC}^{(h)}_{[Q_{(1)}^{(h)},Q_{+}]},\mathrm{HC}^{(h)}_{[Q_{+},t_{1}]}\right).$

It follows that

$\mathrm{HC}^{(1)}-\mathrm{HC}^{(0)}\leq\mathrm{HC}^{(1)}_{[Q_{+},t_{1}]}-\mathrm{HC}^{(0)}_{[Q_{+},t_{1}]}.$

For a right-open interval $D=[a,b)$ or $(a,b)$, define

$\overline{\mathrm{HC}}_{D}^{(h)}=\sup_{t\in
D}\sqrt{n}\left(F_{n}^{(h)}(t)-t\right)w(t);$

i.e. the definition is maximizing over all points in $D$. Note that if the
left endpoint $a$ of $D=[a,b)$ coincides with one of the jump points of
$F_{N}^{(h)}(t)$, then

$\mathrm{HC}_{D}^{(h)}=\overline{\mathrm{HC}}_{D}^{(h)}.$

Indeed, $F_{n}^{(h)}(t)$ is piecewise constant with positive jumps, so that
$t\to F_{n}^{(h)}(t)-t$ is strictly decreasing. Meanwhile, for $t\leq
t_{1}<1/2$, $t\to w(t)$ is strictly decreasing. Hence, the supremum over $t\in
D=[Q_{i}^{(h)},t]$ always occurs at some jump point $Q_{j}^{(h)}\in D$. Now,
for the interval $D=[Q_{+},t]$, $Q_{+}$ is a jump point of both
$F_{N}^{(0)}(t)$ and $F_{N}^{(1)}(t)$ – because of the set equality (29).
Hence

$\mathrm{HC}^{(h)}_{[Q_{+},t_{1}]}=\overline{\mathrm{HC}}^{(h)}_{[Q_{+},t_{1}]},\quad
h\in\\{0,1\\}.$

Finally, since $\Delta_{n}(t)=F_{n}^{(1)}(t)-F_{n}^{(0)}(t)$, we have

$\overline{\mathrm{HC}}^{(1)}_{[Q_{+},t_{1}]}-\overline{\mathrm{HC}}^{(0)}_{[Q_{+},t_{1}]}\leq\sup_{t\in[Q_{+},t_{1}]}\sqrt{n}\Delta_{n}(t)w(t).$

∎

######  Lemma 4.6.

Let $U_{(1)}\leq\ldots\leq U_{(n)}$ denote uniform order statistics. Set
$U_{(0)}=0$, $U_{(n+1)}=1$, and $S_{i}\equiv U_{(i+1)}-U_{(i)}$,
$i=0,\ldots,n$. Let $\eta>0$.

$\Pr(\min_{i}S_{i}>n^{-2-\eta})\rightarrow 1,\qquad n\rightarrow\infty.$

also

$\Pr(n^{2+\eta}\min_{i}S_{i}\rightarrow\infty)=1.$

#### Proof of Lemma 4.6

We invoke familiar properties of the minimum of uniform spacings Bairamov et
al (2010), Set $t=x/(n(n+1))$; then for $x\geq 0$ we have

$\displaystyle\Pr(n(n+1)\min_{i}S_{i}>x)=\Pr(\min_{i}S_{i}>t)=(1-t(n+1))^{n}=\left(1-\frac{x}{n}\right)^{n}{\rightarrow
e^{-x}.}$ (31)

Both conclusions follow directly. ∎

######  Lemma 4.7.

Consider the grid $\mathcal{U}_{n}$ of (19). For
$U_{1},\ldots,U_{n}\overset{\mathsf{iid}}{\sim}\mathrm{Unif}(0,1)$, let
$\Omega_{n}^{(1)}$ denote the event that there exists, for $i=1,\ldots,n$, at
least one grid point situated between each consecutive pair
$[U_{(i)},U_{(i+1)}]$, $1\leq i\leq n-1$. Then

$\Pr(\Omega_{n}^{(1)})\to 1.$

#### Proof of Lemma 4.7

Lemma 4.6 implies that the maximal spacing between each consecutive pair
eventually exceeds $n^{-2-\eta}$, for each $\eta>0$. Because the spacings in
$\mathcal{U}_{n}$ all equal $n^{-3}$, the probability that there exists at
least one grid point between each consecutive pair tends to one. ∎

######  Lemma 4.8.

Consider $X_{i}\sim P_{X_{i}}$, for $i=1,\ldots,n$ independently, where we
assume that each $P_{X_{i}}$ has a continuous density function $f_{X_{i}}$,
and that $\|f_{X_{i}}\|_{\infty}=C<\infty$ for all $i=1,\ldots,n$ for some
$C>0$. Consider the grid $\mathcal{U}_{n}=\\{u_{k}\\}$ of (19). Set
$T_{i}\equiv X_{(i+1)}-X_{(i)}$. Then for $\eta>0$,

$\displaystyle\Pr\left\\{n^{2+\eta}\min_{i}T_{i}>x\right\\}\rightarrow 1,$
(32)

and

$\Pr(n^{2+\eta}\min_{i}T_{i}\rightarrow\infty)=1.$

#### Proof of Lemma 4.8

Let $F_{X}=\mathrm{Ave}\\{F_{X_{i}}\\}_{i=1}^{n}$ denote the marginal
distribution; it has continuous density $f_{X}$ obeying $f_{X}\leq C$ as well.
Now define RV’s $U_{{(i)}}$ by

$F_{X}(X_{i})=U_{i},\quad i=1,\ldots,n.$

These are iid uniform RV’s obeying

${F_{X}(X_{(i)})=U_{(i)},\quad i=1,\ldots,n.}$

Set $X_{(0)}=0$, $X_{(n+1)}=1$ The RV’s $T_{i}=X_{(i)}-X_{(i-1)}$, for
$i=1,\dots,n+1$ may be written as

$T_{i}=\frac{U_{{(i)}}-U_{{(i-1)}}}{f_{X}(x_{i}^{*})},\qquad=1,\dots,n+1,$

where $x_{i}^{*}$ is chosen by the mean value theorem to obey

$U_{{(i+1)}}-U_{{(i)}}=F_{X}(X_{(i+1)})-F_{X}(X_{(i)})=f_{X}(x_{i}^{*})\left(X_{(i+1)}-X_{(i)}\right).$

Because $f_{X}(x_{i}^{*})\leq C$,

$T_{i}=X_{(i)}-X_{(i-1)}\geq\frac{1}{C}\left(U_{{(i+1)}}-U_{{(i)}}\right).$

Set $S_{i}=U_{{(i+1)}}-U_{{(i)}}$, $i=1,\dots,n$. Lemma 4.6 implies

$\displaystyle\Pr\left\\{n^{2+\eta}\min T_{i}\geq x\right\\}$
$\displaystyle\geq\Pr\left\\{Cn^{2+\eta}\min S_{i}\geq x\right\\}\rightarrow
1.$ (33)

######  Lemma 4.9.

Let $\Omega_{n}^{(2)}$ denote the event that there exists, for $i=1,\ldots,n$,
at least one grid point situated between each consecutive pair
$[Q^{(1)}_{(i)},Q^{(1)}_{(i+1)}]$, $1\leq i\leq n-1$. Then
$\Pr(\Omega_{n}^{(2)})\to 1$

#### Proof of Lemma 4.9

Using Lemma 4.8 with $X_{i}=Q_{i}^{(1)}$, for $i=1,\ldots,n$, and $x=\log(n)$,
there exists $n_{0}$ such that

$\displaystyle\Pr\left\\{Cn(n+1)\min T_{i}\geq\log(n)\right\\}<1/n,\quad n\geq
n_{0}.$ (34)

Consequently, the probability that the minimal spacing between each
consecutive pair among $\\{Q_{i}^{(1)},\,i=1,\ldots,n\\}$ is greater than
$n^{-2.5}$ is tending to 1. The stated claim follows because the spacings in
the grid $\mathcal{U}_{n}$ all equal $n^{-3}$.

######  Lemma 4.10.

Let $F(x)$ denote the empirical CDF of $x_{1},\ldots,x_{n}\subset(0,1)$, and
let $\mathcal{U}_{n}=\\{u_{k}\\}$ be the grid of (19). Assume that there
exists, for $i=1,\ldots,n-1$, at least one grid point situated between each
consecutive pair $(x_{(i)},x_{(i+1)})$. Then for all sufficiently large $n$,

$\displaystyle\max_{i=1,\ldots,n}\sqrt{n}\frac{F(x_{i})-x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\max_{u_{k}\in\mathcal{U}_{n}}\sqrt{n}\frac{F(u_{k})-u_{k}}{\sqrt{u_{k}(1-u_{k})}}\leq
n^{-1}.$

#### Proof of Lemma 4.10

###### Proof.

Let $u_{k(i)}$ denote the smallest value of $u_{k}$ satisfying
$u\in(x_{(i)},x_{(i+1)})$ and $u\in\mathcal{U}_{n}$. Then

$F_{n}^{(1)}(x_{i})=F_{n}^{(1)}(u_{k(i)}),\qquad i=1,\dots,n.$ (35)

Hence:

$\displaystyle\max_{i=1,\ldots,n}$
$\displaystyle\left(\frac{F(x_{i})}{\sqrt{x_{i}(1-x_{i})}}-\frac{F(u_{k(i)})}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right)$
$\displaystyle=$
$\displaystyle\max_{i=1,\ldots,n}F(x_{i})\left(\frac{1}{\sqrt{x_{i}(1-x_{i})}}-\frac{1}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right)$
$\displaystyle\leq$
$\displaystyle\max_{i=1,\ldots,n}\left|\frac{1}{\sqrt{x_{i}(1-x_{i})}}-\frac{1}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right|.$

Also

$\max_{u_{k}\in\mathcal{U}_{n}}\frac{F(u_{k})-u_{k}}{\sqrt{u_{k}(1-u_{k})}}\geq\max_{i=1,\ldots,n}\frac{F(u_{k(i)})-u_{k(i)}}{\sqrt{u_{k(i)}(1-u_{k(i)})}},$

admittedly, generally with equality. Combining these:

$\displaystyle\max_{i=1,\ldots,n}$
$\displaystyle\frac{F(x_{i})-x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\max_{u_{k}\in\mathcal{U}_{n}}\frac{F(u_{k})-u_{k}}{\sqrt{u_{k}(1-u_{k})}}$
$\displaystyle\leq$
$\displaystyle\max_{i=1,\ldots,n}\left(\frac{F(x_{i})-x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\frac{F(u_{k(i)})-u_{k(i)}}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right)$
$\displaystyle\leq$
$\displaystyle\max_{i=1,\ldots,n}\left|\frac{F(x_{i})}{\sqrt{x_{i}(1-x_{i})}}-\frac{F(u_{k(i)})}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right|$
$\displaystyle+$
$\displaystyle\max_{i=1,\ldots,n}\left|\frac{x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\frac{u_{k(i)}}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right|$
$\displaystyle\leq$
$\displaystyle\max_{i=1,\ldots,n}\left|\frac{1}{\sqrt{x_{i}(1-x_{i})}}-\frac{1}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right|$
$\displaystyle+$
$\displaystyle\max_{i=1,\ldots,n}\left|\frac{x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\frac{u_{k(i)}}{\sqrt{u_{k(i)}(1-u_{k(i)})}}\right|$
$\displaystyle\leq$ $\displaystyle\qquad 2/n^{9/4}+4/n^{9/4}.$

where the last step holds for $n>n_{0}$ by the next lemma. Reinstating the
original $\sqrt{n}$ normalization gives the bound

$\max_{i=1,\ldots,n}\sqrt{n}\frac{F(x_{i})-x_{i}}{\sqrt{x_{i}(1-x_{i})}}-\max_{u_{k}\in\mathcal{U}_{n}}\sqrt{n}\frac{F(u_{k})-u_{k}}{\sqrt{u_{k}(1-u_{k})}}\leq
n^{1/2}\cdot\frac{6}{n^{9/4}},\qquad n>n_{0}.$

As soon as $n>\max(n_{0},6^{4/3})$, our main claim follows, as then
$n^{-1}>6/n^{7/4}$. ∎

######  Lemma 4.11.

Let $(x_{i})_{i=1}^{n}$ denote a numerical sequence taking values in $(0,1)$,
obeying

$n^{-3/2}<\min_{i}x_{i}\leq\max_{i}x_{i}<1-n^{-3/2}.$

Let, for each $i$, $u_{k}(i)$ denote the closest grid point from our
equispaced grid $\mathcal{U}_{n}$ that is as large or larger. Then

$\left|u_{k(i)}-x_{i}\right|\leq n^{-3};\qquad i=1,\dots,n.$ (36)

For $n>n_{0}$, and $i=1,\dots,n$,

$\left|\frac{1}{\sqrt{u_{k(i)}(1-u_{k(i)})}}-\frac{1}{\sqrt{x_{i}(1-x_{i})}}\right|\leq
2\cdot n^{-9/4}$ (37)
$\left|\sqrt{\frac{u_{k(i)}}{1-u_{k(i)}}}-\sqrt{\frac{x_{i}}{1-x_{i}}}\right|\leq
4\cdot n^{-9/4}$ (38)

###### Proof.

(36) follows essentially by definition.

The function $w(x)=\frac{1}{\sqrt{x(1-x)}}$ is convex on $(0,1)$, with
derivative $w^{\prime}(x)=\frac{(1/2-x)}{(x(1-x))^{3/2}}$. Now
$|w^{\prime}(x)|\leq(d(x,\\{0,1\\})/2)^{-3/2}/2$. Since
$\min_{i}d(x_{i},\\{0,1\\})\geq n^{-3/2}$, we get

$\max_{i}|w^{\prime}(x_{i})|\leq(n^{-3/2}/2)^{-3/2}/2=n^{3/4}\cdot\sqrt{2}.$

On $0<x<u<1/2$, $w$ is convex decreasing, so
$w(x)>w(u)>w(x)+w^{\prime}(x)|u-x|$; so there,
$|w(x)-w(u)|\leq(\max_{i}|w^{\prime}(x_{i})|)\cdot|u-x|$. Since $|u-x|\leq
n^{-3}$ we have

$|w(x)-w(u)|\leq\sqrt{2}\cdot n^{3/4}\cdot n^{-3}=\sqrt{2}\cdot n^{-9/4};\quad
0<x<u<1/2.$

Arguing similarly for $1/2\leq x<u<1$, where $w$ is convex increasing,
$w(u)-w^{\prime}(u)|u-x|\leq w(x)<w(u)$. To determine
$\max_{1/2<x_{i}<1}|w^{\prime}(u_{k(i)})|$, use
$|w^{\prime}(u)|\leq(d(u,\\{0,1\\})/2)^{-3/2}/2$ and notice that
$\min_{i}d(u_{k(i)},\\{0,1\\})\geq n^{-3/2}-n^{-3}>n^{-3/2}/2$; hence

$\max_{1/2<x_{i}<1}|w^{\prime}(u_{k(i)})|\leq(n^{-3/2}/4)^{-3/2}/2\leq
n^{3/4}\cdot 2,$

since $4^{3/2}/2=2$. Combining
$|w(x)-w(u)|\leq(\max_{i}|w^{\prime}(u_{k(i)})|)\cdot|u-x|$ and $|u-x|\leq
n^{-3}$, (37) follows for the case $1/2\leq x<u<1$. We omit the argument for
the case $1/2-n^{-1/3}\leq x\leq 1/2\leq u\leq 1/2+n^{-1/3}$. (37) follows.

Now consider the function $h(x)=\sqrt{\frac{x}{1-x}}$; this is increasing on
$(0,1)$, with derivative $h^{\prime}(x)=x^{-1/2}(1-x)^{-3/2}/2$. Now
$|h^{\prime}(x)|\leq(d(x,\\{0,1\\})/2)^{-3/2}$. Since
$\min_{i}d(x_{i},\\{0,1\\})\geq n^{-3/2}$, we get
$\max_{i}|h^{\prime}(x_{i})|\leq n^{-3/4}\cdot 2^{3/2}$.

On $0<x<u<1/2$, $h$ is concave, so $h(x)<h(u)<h(x)+h^{\prime}(x)|u-x|$; so
there, $|h(x)-h(u)|\leq(\max_{i}|h^{\prime}(x_{i})|)\cdot|u-x|$; since
$|u-x|\leq n^{-3}$ we get

$|h(x)-h(u)|\leq 2^{3/2}\cdot n^{3/4}\cdot n^{-3}=4n^{-9/4};\qquad 0<x<u<1/2.$

On $1/2\leq x<u<1$, $h$ is convex, and $h(u)-h^{\prime}(u)|u-x|\leq
h(x)<h(u)$; we have the bound
$|h(x)-h(u)|\leq(\max_{i}|h^{\prime}(u_{k(i)})|)\cdot|u-x|$, which requires us
to bound $\max_{1/2<x_{i}<1}|h^{\prime}(u_{k(i)})|$. We notice that
$\min_{i}d(u_{k(i)},\\{0,1\\})\geq n^{-3/2}-n^{-3}>n^{-3/2}/2$; hence

$\max_{1/2<x_{i}<1}|h^{\prime}(u_{k(i)})|\leq(n^{-3/2}/4)^{-3/2}/2\leq
n^{3/4}\cdot 2,$

\- again since $4^{3/2}/2=2$. Again using $|u-x|\leq n^{-3}$, we get

$|h(x)-h(u)|\leq 2^{3/2}\cdot n^{3/4}\cdot n^{-3}\leq 4n^{-9/4};\qquad
1/2<x<u<1-n^{-3}.$

We again omit the argument for the case $1/2-n^{-1/3}\leq x\leq 1/2\leq u\leq
1/2+n^{-1/3}$. (38) follows. ∎

######  Lemma 4.12.

For any $\eta>0$ and $a>0$, uniformly in $u\in[n^{\eta-1},1/2]$,

$\displaystyle\Pr\left(\sqrt{n}\left(\tilde{F}^{(0)}_{n}(u)-\mathbb{E}\left[\tilde{F}^{(0)}_{n}(u)\right]\right)>a\sqrt{u(1-u)}\right)\leq
e^{-{a\cdot c}\cdot n^{\eta/2}}+e^{-n^{1-(\beta+1/2)/2}},$

for some $c=c(\beta)>0$.

####  4.2.2 Proof of Lemma 4.12

$\displaystyle\sqrt{n}\left(\tilde{F}^{(0)}(u)-\mathbb{E}\left[\tilde{F}^{(0)}(u)\right]\right)=\sqrt{n}\frac{M}{n}\left(H^{(0)}(u)-u\right),$
(39)

so, conditional on $M$,

$\displaystyle\Pr$
$\displaystyle\left(\sqrt{n}\left(\tilde{F}^{(0)}(u)-\mathbb{E}\left[\tilde{F}^{(0)}(u)\right]\right)>a\sqrt{u(1-u)}|M\right)$
(40)
$\displaystyle{=}\Pr\left(H^{(0)}(u)-u>a\frac{\sqrt{n}}{M}\sqrt{u(1-u)}|M\right)$
(41) $\displaystyle=\Pr\left(H^{(0)}(u)>(1+\kappa)u|M\right)=:P_{n,M},$ (42)

say, where

$\displaystyle\kappa:=\kappa(u;n,M,a):=a\frac{\sqrt{n}}{M}\sqrt{\frac{1-u}{u}}.$
(43)

Conditional on $M$, apply the Chernoff inequality (Mitzenmacher and Upfal,
2017, Ch. 4):

$\displaystyle P_{M,n}\leq\exp\left(-M\frac{\kappa^{2}}{1+\kappa}u\right).$
(44)

Consider now the event $\Omega_{n}\equiv\\{M<n^{1-\beta+\eta_{1}}\\}$. From
Lemma 4.2, for any $\eta_{1}>0$, there exists $n_{0}\equiv
n_{0}(\beta,c^{\prime},\eta_{1})$ such that

$\Pr(\Omega_{n})\leq c^{\prime}e^{{-}n^{1-\beta+\eta_{1}}},\qquad n\geq
n_{0}.$

Since $\beta\in(1/2,1)$ we may specifically choose $\eta_{1}=(\beta-1/2)/2>0$,
yielding $1-\beta+\eta_{1}=1-(\beta+1/2)/2>0$.

At the same time, this choice of $\eta_{1}$ gives us
$-1/2+\beta-\eta_{1}=(\beta-1/2)/2$ ($>0$, as $\beta>1/2$). We are assuming
$u\leq 1/2$ so on the event $\Omega_{n}$:

$\displaystyle\kappa=a\frac{\sqrt{n}}{M}\sqrt{\frac{1-u}{u}}\geq a\cdot
n^{-1/2+\beta-\eta_{1}}{=a}\cdot n^{(\beta-1/2)/2}\to\infty.$ (45)

Consequently, $\frac{\kappa^{2}}{1+\kappa}=\kappa\cdot(1+o(1))$ and, for large
$n$, $M\frac{\kappa^{2}}{2+\kappa}\geq c^{\prime\prime}M\cdot\kappa$ for
$c^{\prime\prime}=c^{\prime\prime}(\beta)$. Now $M\kappa
u=a\sqrt{n}\sqrt{u(1-u)}$, and since $u<1/2$,

$M\kappa u=a\sqrt{n}\sqrt{u(1-u)}>{a\sqrt{nu/2}}.$

By hypothesis, $u\geq n^{\eta-1}$, hence

$\displaystyle M\cdot\frac{\kappa^{2}}{2+\kappa}\cdot u\geq a\cdot
c^{\prime\prime\prime}\cdot n^{\eta/2},$ (46)

for $n>n^{\prime\prime\prime}(\beta)$, where
$c^{\prime\prime\prime}=c^{\prime\prime\prime}(\beta)$. Equation (44) and
$\Omega_{n}$ together imply that for $n>n^{\prime\prime\prime}(\beta)$

$\displaystyle{P_{M,n}\leq\exp\\{{-{a\cdot c^{\prime\prime\prime}}\cdot
n^{\eta/2}}\\}}.$ (47)

Let $P_{n}$ denote the probability mentioned in the statement of the lemma; we
conclude that

$\displaystyle{P_{n}\leq\Pr(\Omega_{n}^{c})+P_{M,n}}\leq
e^{-n^{1-(\beta+1/2)/2}}+e^{-{a\cdot c^{\prime\prime\prime}}\cdot
n^{\eta/2}}.$ (48)

as advertised. ∎

######  Lemma 4.13.

Fix $t_{1}<1/2$ and let $t_{0}=n^{-1}$. For any $\epsilon>0$, there exists
$n_{0}\equiv n_{0}(\epsilon)$ such that, if $r<\rho(\beta)$, then

$\displaystyle\sup_{t\in(t_{0},t_{1})}\sqrt{n}\left|\mathbb{E}\left[\tilde{F}^{(1)}(t)\right]-\mathbb{E}\left[\tilde{F}^{(0)}(t)\right]\right|w(t)\leq\epsilon,$

for all $n\geq n_{0}$.

####  4.2.3 Proof of Lemma 4.13

We have $\mathbb{E}\left[\tilde{F}^{(0)}(t)|M\right]=tM/n$ for $t\in(0,1)$.
Consider $t_{n}\in(t_{0},t_{1})$, parameterized as $t_{n}=n^{-q_{n}}$, where
$q_{n}\in(-\log(t_{1})/\log(n),1)$. From (18), we have

$\displaystyle\mathbb{E}\left[\tilde{F}^{(1)}(t_{n})|M\right]=\frac{M}{n}n^{-\alpha(q,r)(1+o_{p}(1))},$
(49)

as $n\to\infty$. Let $\eta>0$. On the event
$\Omega_{n}\equiv\\{M<n^{1-\beta+\eta}\\}$, using also that
$q\geq\alpha(q,r)$, we get that $M/n<n^{-\beta+\eta}$; since $w(t_{n})\leq
2\cdot n^{q_{n}/2}$ we have (here $q=q_{n}$):

$\displaystyle\sqrt{n}\left|\mathbb{E}\left[\tilde{F}^{(1)}(t_{n})\mid
M\right]-\mathbb{E}\left[\tilde{F}^{(0)}(t_{n})\mid M\right]\right|w(t_{n})$
(50)
$\displaystyle\leq{\sqrt{n}\cdot\frac{M}{n}\left|n^{-\alpha(q,r)(1+o_{p}(1))}-n^{-q}\right|\cdot
n^{q/2}\cdot 2}$ (51) $\displaystyle\leq{n^{1/2}\cdot n^{-\beta+\eta}\cdot
n^{-\alpha(q,r)(1+o_{p}(1))}\cdot n^{q/2}\cdot 2}$ (52)
$\displaystyle=n^{-\beta+\eta{+\frac{1+q}{2}}-\alpha(q,r)+o_{p}(1)\alpha(q,r)}.$
(53)

As $(\beta,r)$ satisfy (13), we can choose $\eta>0$ such that

$\kappa\equiv\beta+\alpha(q,r){-\frac{1+q}{2}}-\eta>0.$

Now, $\alpha(q,r)$ is continuous in $q$ by assumption and hence bounded for
$q\in[0,1]$, so $\alpha(q,r)o_{p}(1)=o_{p}(1)$. It follows that, on the event
$\Omega_{n}$, for all $n$ large enough,

$\displaystyle\sup_{t\in(t_{0},t_{1})}\sqrt{n}\left|\mathbb{E}\left[\tilde{F}^{(1)}(t)\mid
M\right]-\mathbb{E}\left[\tilde{F}^{(0)}(t)\mid M\right]\right|w(t)$ (54)
$\displaystyle\leq\max_{q\in[0,1]}n^{-\beta+\eta{+\frac{1+q}{2}}-\alpha(q,r)+o_{p}(1)}$
(55) $\displaystyle=n^{-\kappa+o_{p}(1)}\to 0.$ (56)

Since $F^{(h)}(t)\in[0,1]$,

$|\mathbb{E}\left[\mathbb{E}\left[\tilde{F}^{(h)}(t)\mid
M\right]|\Omega_{n}\right]-\mathbb{E}\left[\tilde{F}^{(h)}(t)\right]|\leq
2\cdot\Pr(\Omega_{n}^{c});\qquad h\in\\{0,1\\}.$

Moreover $\sqrt{n}\cdot w(t_{n})\leq n$ over the range
$t_{n}\in(n^{-1},t_{1})$. Finally, by Lemma 4.2, $n\cdot\Pr(\Omega_{n}^{c})\to
0$ at an exponential rate that only depends on $\eta$. ∎

######  Lemma 4.14.

Consider a fixed $u\in(0,1)$. Then for $a>0$ and $\beta\in(1/2,1)$,

$\displaystyle\Pr\left(\sqrt{n}\left(\tilde{F}_{n}^{(1)}(u)-\mathbb{E}\left[\tilde{F}_{n}^{(1)}(u)\right]\right)>a\sqrt{u(1-u}\right)\leq
e^{-a\sqrt{nu(1-u)}}+e^{-n^{1/4}}.$ (57)

#### Proof of Lemma 4.14

Define

$\delta=\delta(u;n,M,{a})\equiv\frac{a\sqrt{n}\sqrt{u(1-u)}}{M\cdot\mathbb{E}\left[H_{M}^{(1)}(u)\right]}.$

Conditioning on $M$,

$\displaystyle\Pr\left(\sqrt{n}\left(\tilde{F}_{n}^{(1)}(u)-\mathbb{E}\left[\tilde{F}_{n}^{(1)}(u)\right]\right)>a\sqrt{u(1-u)}{\mid
M}\right)$
$\displaystyle=\Pr\left(H^{(1)}_{M}(u)-\mathbb{E}\left[H^{(1)}_{M}(u)\right]>\frac{a\sqrt{n}}{M}\sqrt{u(1-u)}\right)$
$\displaystyle=\Pr\left(H^{(1)}_{M}(u)>(1+\delta)\mathbb{E}\left[H^{(1)}_{M}(u)\right]\right)\leq\exp\left\\{-M\frac{\delta^{2}}{1+\delta}\mathbb{E}\left[H^{(1)}_{M}(u)\right]\right\\},$

The last step follows by the Chernoff inequality:

$\displaystyle\Pr\left(X\geq(1+\delta)\mu\right)\leq\left(\frac{e^{-\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}\leq
e^{-\mu\frac{\delta^{2}}{1+\delta}},$ (58)

This is valid for any $\delta>1$, where $X$ is the sum of $M$ independent
Bernoulli random variables with $\mu=\mathbb{E}\left[X\right]$ (Mitzenmacher
and Upfal, 2017, Ch. 4).

Set $\eta_{1}=(\beta-1/2)/2$. Since
${\mathbb{E}\left[H^{(h)}_{M}(u)\right]}\leq 1$, on the event
$\Omega_{n}\equiv\\{M\leq n^{1-\beta+\eta_{1}}\\}$, we have

$\displaystyle\delta$
$\displaystyle\geq\frac{a\cdot\sqrt{n}}{n^{1-\beta+\eta_{1}}}\frac{\sqrt{(1-u)u}}{\mathbb{E}\left[H^{(h)}_{M}(u)\right]}$
(59) $\displaystyle\geq a\cdot n^{\beta-1/2-\eta_{1}}\sqrt{(1-u)u}.$ (60)

Since $\beta>1/2$, our choice of $\eta_{1}$ gives
$\beta-1/2-\eta_{1}=(\beta-1/2)/2>0$, and so $\delta\to\infty$ with increasing
$n$. Hence $\frac{\delta^{2}}{1+\delta}=\delta(1+o(1))$, and so for large $n$

$M\frac{\delta^{2}}{1+\delta}\mathbb{E}\left[H^{(1)}_{M}(u)\right]\geq\frac{1}{2}M\cdot\delta\cdot\mathbb{E}\left[H^{(1)}_{M}(u)\right]=\frac{a}{2}\sqrt{n}\sqrt{u(1-u)}.$

Therefore, on $\Omega_{n}$,

$\displaystyle\Pr\left(\sqrt{n}\left(\tilde{F}_{n}^{(1)}(u)-\mathbb{E}\left[\tilde{F}_{n}^{(1)}(u)\right]\right)>a\sqrt{u(1-u)}{\mid
M}\right)\leq\exp\left\\{-\frac{a}{2}\sqrt{n}\sqrt{u(1-u)}\right\\}.$

Finally, Lemma 4.2 implies that $\Pr(\Omega_{n})<e^{-n^{1-\beta+\eta_{1}}}$.
Our choice $\eta_{1}=(\beta-1/2)/2$ gives $1-\beta+\eta_{1}=3/4-\beta/2>1/4$
since $1>\beta$, and so

$\displaystyle\Pr\left(\sqrt{n}\left(\tilde{F}_{n}^{(1)}(u)-\mathbb{E}\left[\tilde{F}_{n}^{(1)}(u)\right]\right)>a\sqrt{u(1-u)}\right)$
$\displaystyle\leq e^{-a\sqrt{n}\sqrt{u(1-u)}}+e^{-n^{(3-2\beta)/4}}$ (61)
$\displaystyle\leq e^{-a\sqrt{n}\sqrt{u(1-u)}}+e^{-n^{1/4}}$ (62)

∎

######  Lemma 4.15.

Fix $0<\eta<1/2$. Using the grid $\mathcal{U}_{n}$ of (19), define the subgrid
$\mathcal{U}^{\eta}_{n}\equiv\mathcal{U}_{n}\cap(n^{-1+\eta},1/2)$. For $c>0$,
and $h\in{0,1}$,

$\displaystyle\Pr\left\\{{\max_{u\in\mathcal{U}^{\eta}_{n}}}\sqrt{n}\left(\tilde{F}^{{(h)}}(u)-\mathbb{E}\left[\tilde{F}^{{(h)}}(u)\right]\right)w(u)\geq
c\right\\}\to 0.$ (63)

#### Proof of Lemma 4.15

Lemmas 4.12 and 4.14 each imply exponential inequalities of the form

$\displaystyle\max_{u\in(n^{-1+\eta},1/2)}\Pr\left\\{\sqrt{n}\frac{\tilde{F}^{{(h)}}(u)-\mathbb{E}\left[\tilde{F}^{{(h)}}(u)\right]}{\sqrt{u(1-u)}}\geq
c\right\\}\leq{2\cdot e^{-(a+bc)\cdot n^{\delta}}},$ (64)

where $a,b\geq 0$, $a+bc>0$, $\delta=\delta(\eta)>0$ \- valid for all $n\geq
n_{0}(c)$. Therefore, applying the union bound across the individual grid
points, we get, for $h\in\\{0,1\\}$,

$\displaystyle\Pr\left\\{{\max_{u\in\mathcal{U}^{\eta}_{n}}}\sqrt{n}\frac{\tilde{F}^{{(h)}}(u)-\mathbb{E}\left[\tilde{F}^{{(h)}}(u)\right]}{\sqrt{u(1-u)}}\geq
c\right\\}$ (65)
$\displaystyle\leq\sum_{{u\in\mathcal{U}^{\eta}_{n}}}\Pr\left\\{\sqrt{n}\frac{\tilde{F}^{{(h)}}(u)-\mathbb{E}\left[\tilde{F}^{{(h)}}(u)\right]}{\sqrt{u(1-u)}}\geq
c\right\\}$ (66) $\displaystyle\leq{\mathrm{card}(\mathcal{U}^{\eta}_{n})\cdot
2e^{-(a+b{c})n^{\delta}}=O(n^{4}e^{-(a+bc)n^{\delta}})}\to 0,$ (67)

since $\mathrm{card}(\mathcal{U}_{n})\leq n^{4}$. ∎

###  4.3 Proof of Theorem 4.1

Set $t_{1}=\gamma_{0}n<1/2$ and $t_{0}=\bar{Q}_{-}$. Fix $\delta>0$. Denote by
$\Psi_{n}$ the event that between each consecutive pair
$(Q_{(i)}^{(h)},Q_{(i+1)}^{(h)})$, there exists at least one grid point. From
Lemmas 4.7 and 4.9, we have that $\Pr(\Psi_{n})>1-\delta/2$ for all $n\geq
n_{1}(\delta)$ for some $n_{1}(\delta)$. Conditioning on $\Psi_{n}$, Lemma
4.5, implies

$\displaystyle\mathrm{HC}_{n}^{(1)}-\mathrm{HC}_{n}^{(0)}\leq\sup_{t\leq
t_{1}}\sqrt{n}\Delta_{n}(t)w(t)=\sup_{t\in[t_{0},t_{1}]}\sqrt{n}\Delta_{n}(t)w(t),$
(68)

while Lemma 4.10 further implies that

$\displaystyle\sup_{t\in(t_{0},t_{1})}\sqrt{n}\Delta_{n}(t)w(t)\leq\max_{u_{k}\in\mathcal{U}_{n}\cap(t_{0},t_{1})}\sqrt{n}\Delta_{n}(u_{k})w(u_{k})+2n^{-1}.$
(69)

Write

$\displaystyle\Delta_{n}(t)$
$\displaystyle=\left(\tilde{F}^{(1)}(t)-\mathbb{E}\left[\tilde{F}^{(1)}(t)\right]\right)+\left(\mathbb{E}\left[\tilde{F}^{(1)}(t)\right]-\mathbb{E}\left[\tilde{F}^{(0)}(t)\right]\right)$
$\displaystyle\qquad+\left(\mathbb{E}\left[\tilde{F}^{(0)}(t)\right]-\tilde{F}^{(0)}(t)\right).$

Fix $\eta>0$ and $\epsilon>0$. From Lemma 4.3, $n^{\eta-1}\bar{Q}_{-}>1$ with
probability at least $1-\delta/2$ for all $n\geq n_{2}(\eta,\delta)$.
Therefore, Lemmas 4.12 and 4.14, via Lemma 4.15, imply that

$\displaystyle\max_{u_{k}\in\mathcal{U}_{n}\cap(t_{0},t_{1})}\sqrt{n}\left(\tilde{F}^{(0)}(u_{k})-\mathbb{E}\left[\tilde{F}^{(0)}(u_{k})\right]\right)w(u_{k})\leq\epsilon,$

and

$\displaystyle\max_{u_{k}\in\mathcal{U}_{n}\cap(t_{0},t_{1})}\sqrt{n}\left(\tilde{F}^{(1)}(u_{k})-\mathbb{E}\left[\tilde{F}^{(1)}(u_{k})\right]\right)w(u_{k})\leq\epsilon,$

for $n\geq n_{3}(\eta,\epsilon)$ with probability greater than $1-\delta/2$.
From Lemma 4.13 we have that

$\displaystyle\sup_{t\in(t_{0},t_{1})}\sqrt{n}\left(\mathbb{E}\left[\tilde{F}^{(1)}(t)\right]-\mathbb{E}\left[\tilde{F}^{(0)}(t)\right]\right)w(t)\leq\epsilon,$

for all $n\geq n_{3}(\epsilon)$. Putting it all together,

$\displaystyle\mathrm{HC}_{n}^{(1)}-\mathrm{HC}_{n}^{(0)}\leq
3\epsilon+2n^{-1},$ (70)

with probability at least $1-\delta$ for all $n\geq
n_{4}(\epsilon,\eta,\delta)$. As $\delta$, $\eta$ and $\epsilon$ are
arbitrary, the proof is completed.

This work is supported in part by funding from the Koret Foundation and the
NSF under Grant No. DMS-1816114.

## References

  * Arias-Castro and Wang (2015) Arias-Castro E., Wang M. (2015) The sparse Poisson means model. Electronic Journal of Statistics 9(2):2170–2201
  * Arias-Castro et al (2011) Arias-Castro E., Candès E. J., Plan Y. (2011) Global testing under sparse alternatives: Anova, multiple comparisons and the higher criticism. The Annals of Statistics 39(5):2533–2556
  * Bairamov et al (2010) Bairamov I., Berred A., Stepanov A. (2010) Limit results for ordered uniform spacings. Statistical Papers 51(1):227
  * Cai and Wu (2014) Cai T. T., Wu Y. (2014) Optimal detection of sparse mixtures against a given null distribution. IEEE Transactions on Information Theory 60(4):2217–2232
  * Cai et al (2011) Cai T. T., Jeng J. X., Jin J. (2011) Optimal detection of heterogeneous and heteroscedastic mixtures. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 73(5):629–662
  * Donoho and Jin (2004) Donoho D. L., Jin J. (2004) Higher criticism for detecting sparse heterogeneous mixtures. The Annals of Statistics 32(3):962–994
  * Donoho and Jin (2008) Donoho D. L., Jin J. (2008) Higher criticism thresholding: Optimal feature selection when useful features are rare and weak. Proceedings of the National Academy of Sciences 105(39):14,790–14,795
  * Donoho and Jin (2009) Donoho D. L., Jin J. (2009) Feature selection by higher criticism thresholding achieves the optimal phase diagram. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 367(1906):4449–4470
  * Donoho and Kipnis (2020) Donoho D. L., Kipnis A. (2020) Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences. (in preparation) URL https://arxiv.org/abs/2007.01958, 2007.01958
  * Gontscharuk et al (2016) Gontscharuk V., Landwehr S., Finner H., et al (2016) Goodness of fit tests in terms of local levels with special emphasis on higher criticism tests. Bernoulli 22(3):1331–1363
  * Hall and Jin (2010) Hall P., Jin J. (2010) Innovated higher criticism for detecting sparse signals in correlated noise. The Annals of Statistics 38(3):1686–1732
  * Kipnis (2019) Kipnis A. (2019) Higher criticism for discriminating word-frequency tables and testing authorship. URL https://arxiv.org/abs/1911.01208, 1911.01208
  * Kipnis (2021) Kipnis A. (2021) Sparsely log chi-squared p-values of rare and weak features. In preparation.
  * Li and Siegmund (2015) Li J., Siegmund D. (2015) Higher criticism: $p$-values and criticism. The Annals of Statistics 43(3):1323–1350
  * Mitzenmacher and Upfal (2017) Mitzenmacher M., Upfal E. (2017) Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press
  * Moscovich et al (2016) Moscovich A., Nadler B., Spiegelman C. (2016) On the exact berk-jones statistics and their $p$-value calculation. Electronic Journal of Statistics 10(2):2329–2354