Confidence Bands for Distribution Functions:\\ A New Look at the Law of the Iterated Logarithm
Lutz D\"umbgen$^*$ and Jon A.\ Wellner$^{**
We present a general law of the iterated logarithm for stochastic processes on the open unit interval having subexponential tails in a locally uniform fashion. It applies to standard Brownian bridge but also to suitably standardized empirical distribution functions. This leads to new goodness-of-fit tests and confidence bands which refine the procedures of \nocite{Berk_Jones_1979{Berk and Jones (1979) and \nocite{Owen_1995{Owen (1995). Roughly speaking, the high power and accuracy of the latter procedures in the tail regions of distributions are essentially preserved while gaining considerably in the central region.
NonGaussLIL.tex
\documentclass[a4paper,twoside,reqno,11pt,tbtags]{article}

\usepackage{amssymb,amsmath,amsthm,mathrsfs}
\usepackage{graphicx}
\usepackage{times}

\textwidth 15cm
\textheight 23cm
\topmargin -1.5cm
\oddsidemargin .7cm
\evensidemargin .7cm

\parskip = 0.25\baselineskip
\leftmargini=\baselineskip

\newtheoremstyle{localthm}
	{5pt} % space above
	{5pt} % space below
	{\sl} % Body font
	{} % Indent amount
	{\bf} % Theorem head font
	{{\rm.}} % Punctuation after theorem head
	{.7em} % Space after theorem head
	{} % Theorem head spec ?

\theoremstyle{localthm}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}


\newtheoremstyle{localrem}
	{5pt} % space above
	{5pt} % space below
	{\rm} % Body font
	{} % Indent amount
	{\bf} % Theorem head font
	{{\rm.}} % Punctuation after theorem head
	{.7em} % Space after theorem head
	{} % Theorem head spec ?

\theoremstyle{localrem}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Condition}[Theorem]{Condition}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Example}[Theorem]{Example}


%\numberwithin{equation}{section}

\def\Ex{\mathop{\mathrm{I\!E}}\nolimits}
\def\Pr{\mathop{\mathrm{I\!P}}\nolimits}
\def\Std{\mathop{\mathrm{Std}}\nolimits}
\def\Cov{\mathop{\mathrm{Cov}}\nolimits}
\def\Var{\mathop{\mathrm{Var}}\nolimits}

\def\eps{\varepsilon}

\newcommand{\R}{\mathbb{R}}

\newcommand{\FF}{\mathcal{F}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\NN}{\mathcal{N}}
\newcommand{\TT}{\mathcal{T}}

\newcommand{\argmin}{\mathop{\mathrm{arg\,min}}}
\newcommand{\argmax}{\mathop{\mathrm{arg\,max}}}
\newcommand{\logit}{\mathop{\mathrm{logit}}\nolimits}

\def\bs{\boldsymbol}

\def\hat{\widehat}
%\def\tilde{\widetilde}

\def\gnt{\tilde{\gamma}_n}


%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%

\title{Confidence Bands for Distribution Functions:\\
A New Look at the Law of the Iterated Logarithm}
\author{Lutz D\"umbgen$^*$ and Jon A.\ Wellner$^{**}$}
\date{March 2014}
\maketitle

\begin{abstract}
We present a general law of the iterated logarithm for stochastic processes on the open unit interval having subexponential tails in a locally uniform fashion. It applies to standard Brownian bridge but also to suitably standardized empirical distribution functions. This leads to new goodness-of-fit tests and confidence bands which refine the procedures of \nocite{Berk_Jones_1979}{Berk and Jones (1979)} and \nocite{Owen_1995}{Owen (1995)}. Roughly speaking, the high power and accuracy of the latter procedures in the tail regions of distributions are essentially preserved while gaining considerably in the central region.
\end{abstract}

\bigskip

\noindent
$^*$Work supported by Swiss National Science Foundation.

\noindent
$^{**}$Work supported in part by NSF DMS 11-04832 and NI-AID Grant 2R01 AI291968-04.


\paragraph{AMS subject classifications.}
%
62E20, 62G15, 62G30.

\paragraph{Key words.}
%
Confidence band, limit distribution, sub-exponential tails, submartingale, tail regions.


\addtolength{\baselineskip}{0.5\baselineskip}


%=======================
\section{Introduction}
\label{sec:introduction}
%=======================

Let $\hat{F}_n$ be the empirical distribution function of independent random variables $X_1, X_2, \ldots, X_n$ with unknown distribution function $F$ on the real line. Let us recall some well-known facts about $\hat{F}_n$ (cf.\ \nocite{Shorack_Wellner_1986}{Shorack and Wellner 1986}): The stochastic process $\bigl( \hat{F}_n(x) \bigr)_{x \in \R}$ has the same distribution as $\bigl( \hat{G}_n(F(x)) \bigr)_{x \in \R}$, where $\hat{G}_n$ is the empirical distribution of independent random variables $U_1, U_2, \ldots, U_n$ with uniform distribution on $[0,1]$. This enables us to construct confidence bands for the distribution function $F$. A well-known classical method are Kolmogorov-Smirnov confidence bands: Let
\[
	\mathbb{U}_n(t) \ := \ n^{1/2} (\hat{G}_n(t) - t) ,
\]
and let $\kappa_{n,\alpha}^{\rm KS}$ be the $(1 - \alpha)$-quantile of
\[
	\|\mathbb{U}_n\|_\infty \ := \ \sup_{t \in [0,1]} |\mathbb{U}_n(t)| .
\]
Then with probability at least $1 - \alpha$,
\begin{equation}
\label{eq:KSBand}
	F(x) \ \in \ [\hat{F}_n(x) \pm n^{-1/2} \kappa_{n,\alpha}^{\rm KS}]
	\quad\text{for all} \ x \in \R .
\end{equation}
Equality holds if $F$ is continuous. Since $\mathbb{U}_n$ converges in distribution in $\ell_\infty([0,1])$ to standard Brownian bridge $\mathbb{U}$, $\kappa_{n,\alpha}^{\rm KS}$ converges to the $(1 - \alpha)$-quantile $\kappa_\alpha^{\rm KS}$ of $\|\mathbb{U}\|_\infty$. In particular, the simultaneous confidence intervals in \eqref{eq:KSBand} have width $O(n^{-1/2})$ uniformly in $x \in \R$.

Another method, based on a goodness-of-fit test by \nocite{Berk_Jones_1979}{Berk and Jones (1979)}, was introduced by \nocite{Owen_1995}{Owen (1995)}: Let $\kappa_{n,\alpha}^{\rm BJ}$ be the $(1 - \alpha)$-quantile of
\[
	T_n^{\rm BJ} \ := \ n \sup_{t \in (0,1)} K(\hat{G}_n(t),t) ,
\]
where
\[
	K(s,t) \ := \ s \log \frac{s}{t} + (1 - s) \log \frac{1-s}{1-t}
\]
for $s \in [0,1]$ and $t \in (0,1)$. This leads to an alternative confidence band for $F$: With probability at least $1 - \alpha$,
\begin{equation}
\label{eq:BJBand}
	n K(\hat{F}_n(x),F(x)) \ \le \ \kappa_{n,\alpha}^{\rm BJ}
	\quad\text{for all} \ x \in \R .
\end{equation}
As shown by \nocite{Jager_Wellner_2007}{Jager and Wellner (2007)}, the asymptotic distribution of $T_n^{\rm BJ}$ remains the same if one replaces $K(s,t)$ by a more general function; in particular, one may interchange its two arguments. Moreover,
\[
	\kappa_{n,\alpha}^{\rm BJ} \ = \ \log\log(n) + 2^{-1} \log \log \log(n) + O(1) .
\]
From this one can deduce that \eqref{eq:BJBand} leads to confidence intervals with length at most
\[
	2 \bigl( 2 \gamma_n F(x)(1 - F(x)) \bigr)^{1/2} + 2 \gamma_n
	\quad\text{where}\quad
	\gamma_n := \frac{\kappa_{n,\alpha}^{\rm BJ}}{n} = (1 + o(1)) \frac{\log \log n}{n} ,
\]
uniformly in $x \in \R$; see (K.5) in Section~\ref{subsec:K}. Hence they are substantially shorter than the Kolmogorov-Smirnov intervals for $F(x)$ close to $0$ or $1$. But in the central region, i.e.\ when $F(x)$ is bounded away from $0$ and $1$, they are of width $O(n^{-1/2} (\log \log n)^{1/2})$ rather than $O(n^{-1/2})$. An obvious goal is to refine these methods and combine the benefits of the Kolmogorov-Smirnov and Berk-Jones confidence bands. Methods of this type have been proposed by various authors, see \nocite{Mason_Schuenemeyer_1983}{Mason and Schuenemeyer (1983)} and the references cited therein.

A key for understanding the asymptotics of $T_n^{\rm BJ}$ but also the new methods presented later are suitable variants of the law of the iterated logarithm (LIL). For Brownian bridge $\mathbb{U}$ the LIL states that
\begin{equation}
\label{eq:LIL.BB}
	\limsup_{t \downarrow 0} \frac{\mathbb{U}(t)}{\sqrt{2 t \log \log(1/t)}}
	\ = \ \limsup_{t \uparrow 1}
		\frac{\mathbb{U}(t)}{\sqrt{2 (1-t) \log \log(1/(1-t))}}
	\ = \ 1
\end{equation}
almost surely. Various refinements of this result have been obtained. One particular consequence of Kolmogorov's upper class test (cf.\ \nocite{Erdos_1942}{Erd\"os 1942}, or \nocite{Ito_McKean_1974}{Ito and McKean 1974}, Chapter~1.8) is the following result: For $t \in (0,1)$ define
\begin{align*}
	C(t) \
	&:= \ \log \log \frac{e}{4t(1-t)}
		\ = \ \log \bigl( 1 - \log(1 - (2t-1)^2) \bigr) \ \ge \ 0 , \\
	D(t) \
	&:= \ \log(1 + C(t)^2) \ \ge \ 0 .
\end{align*}
Then for any fixed $\nu > 3/4$,
\begin{equation}
\label{eq:additive.LIL.BB}
	\sup_{t \in (0,1)}
		\Bigl( \frac{\mathbb{U}(t)^2}{2t(1-t)}
			- C(t)
			- \nu D(t) \Bigr)
	\ < \ \infty
\end{equation}
almost surely. Note that $C(t) = C(1 - t)$, $D(t) = D(1 - t)$, and, as $t \downarrow 0$,
\begin{align*}
	C(t) \
	&= \ \log \log(1/t) + O \bigl( \log(1/t)^{-1} \bigr) , \\
	D(t) \
	&= \ 2 \log \log \log(1/t) + O \bigl( (\log \log(1/t))^{-1} \bigr) .
\end{align*}
This explains why \eqref{eq:additive.LIL.BB} follows from Kolmogorov's test and shows the connection between \eqref{eq:additive.LIL.BB} and \eqref{eq:LIL.BB}. Note also that
\[
	\lim_{t \to 1/2} \frac{C(t)}{(2t-1)^2}
	\ = \ \lim_{t \to 1/2} \frac{D(t)}{(2t-1)^4}
	\ = \ 1 .
\]

In the present paper we prove statements similar to \eqref{eq:additive.LIL.BB} for general stochastic processes on $(0,1)$. In Section~\ref{sec:LIL} we state a general condition on a stochastic process  $X = (X(t))_{t \in (0,1)}$ such that for any fixed $\nu > 1$,
\[
	\sup_{t \in (0,1)}
		\bigl( X(t) - C(t) - \nu D(t) \bigr)
	\ < \ \infty
\]
almost surely. In particular, the stochastic process
\[
	X(t) \ := \ \frac{\mathbb{U}(t)^2}{2t(1-t)}
\]
satisfies this condition. Then in Section~\ref{sec:EP} these general results are applied to
\[
	X_n(t) \ := \ n K(\hat{G}_n(t),t) .
\]
It turns out that for any fixed $\nu > 1$,
\begin{equation}
\label{eq:GoF.statistic.0}
	T_{n,\nu} \ := \ \sup_{t \in (0,1)}
		\bigl( n K(\hat{G}_n(t),t) - C(t) - \nu D(t) \bigr)
\end{equation}
converges in distribution to
\[
	T_\nu \ := \ \sup_{t \in (0,1)}
		\Bigl( \frac{\mathbb{U}(t)^2}{2t(1-t)} - C(t) - \nu D(t) \Bigr) .
\]
Asymptotic statements like this refer to $n \to \infty$, unless stated otherwise. Moreover, if $U_{n:1} < U_{n:2} < \cdots < U_{n:n}$ are the order statistics of $U_1, U_2, \ldots, U_n$, then for fixed $\nu > 1$,
\[
	\tilde{T}_{n,\nu} \ := \ \max_{j = 1,2,\ldots,n}
		\bigl( (n+1) K(t_{nj}, U_{n:j}) - C(t_{nj}) - \nu D(t_{nj}) \bigr)
	\ \to_{\LL} \ T_\nu ,
\]
where
\[
	t_{nj} \ := \ \frac{j}{n+1}
	\quad\text{for} \ j = 1,2,\ldots,n .
\]

To test the null hypothesis that $F$ is equal to a given continuous distribution function $F_o$, consider the test statistic
\begin{equation}
\label{eq:GoF.statistic}
	T_{n,\nu}(F_o) \ := \ \sup_{x \in \R}
		\bigl( n K(\hat{F}_n(x),F_o(x)) - C(F_o(x)) - \nu D(F_o(x)) \bigr) .
\end{equation}
Under the null hypothesis, $T_{n,\nu}(F_o)$ has the same distribution as $T_{n,\nu}$. Hence if $\kappa_{n,\nu,\alpha}$ denotes the $(1 - \alpha)$-quantile of $T_{n,\nu}$, one may reject the null hypothesis at level $\alpha \in (0,1)$ if $T_{n,\nu}(F_o)$ exceeds $\kappa_{n,\nu,\alpha}$. In Section~\ref{sec:GoF} we investigate the power of this new test in more detail. In particular we show that it attains the detection boundary for Gaussian mixture models as specified by \nocite{Donoho_Jin_2004}{Donoho and Jin (2004)}.

The statistic $\tilde{T}_{n,\nu}$ leads to a new confidence band for $F$: Let $- \infty = X_{n:0} < X_{n:1} \le X_{n:2} \le \cdots \le X_{n:n} < X_{n:n+1} = \infty$ be the order statistics of $X_1, X_2, \ldots, X_n$, and let $\tilde{\kappa}_{n,\nu,\alpha}$ and $\kappa_{\nu,\alpha}$ be the $(1 - \alpha)$-quantile of $\tilde{T}_{n,\nu}$ and $T_\nu$, respectively. Then $\tilde{\kappa}_{n,\nu,\alpha} \to \kappa_{\nu,\alpha}$, and with probability at least $1 - \alpha$, the following is true: For $0 \le j \le n$ and $X_{n:j} \le x < X_{n:j+1}$,
\[
	F(x) \ \in \ [a_{nj}, b_{nj}] ,
\]
where $a_{n0} := 0$, $b_{nn} := 1$ and
\begin{align*}
	a_{nj}
	&:= \min \bigl\{ u \in [0,1] : n K(t_{nj},u)
			\le C(t_{nj}) + \nu D(t_{nj})
				+ \tilde{\kappa}_{n,\nu,\alpha} \bigr\}
		\ \ \text{if} \ j > 0 , \\
	b_{nj}
	&:= \max \bigl\{ u \in [0,1] : n K(t_{n,j+1},u)
			\le C(t_{n,j+1}) + \nu D(t_{n,j+1})
				+ \tilde{\kappa}_{n,\nu,\alpha} \bigr\}
		\ \ \text{if} \ j < n .
\end{align*}
Since $C(t_{nj}) + \nu D(t_{nj}) + \tilde{\kappa}_{n,\nu,\alpha}$ is no larger than
\[
	C(t_{n1}) + \nu D(t_{n1}) + \tilde{\kappa}_{n,\nu,\alpha}
	\ = \ (1 + o(1)) \log\log n
\]
for $1 \le j \le n$, our confidence bands have similar accuracy as those of \nocite{Owen_1995}{Owen (1995)} in the tail regions while achieving the usual root-$n$ consistency everywhere. A more precise comparison is provided in Section~\ref{sec:CB}. Thereafter we relate our methods to a negative result of \nocite{Bahadur_Savage_1956}{Bahadur and Savage (1956)} about the nonexistence of confidence bands with vanishing width in the tails. Finally we discuss briefly an interesting alternative approach to goodness-of-fit tests and confidence bands by \nocite{Aldor-Noiman_etal_2013}{Aldor-Noiman et al.\ (2013)} and \nocite{Eiger_etal_2013}{Eiger et al.\ (2013)}.

All proofs and technical arguments are deferred to Section~\ref{sec:Proofs}. Section~\ref{sec:Supplements} contains supplementary material including a quantitative version of \nocite{Bahadur_Savage_1956}{Bahadur and Savage (1956, Theorem~2)} and decision theoretic considerations about the Gaussian mixture model of \nocite{Donoho_Jin_2004}{Donoho and Jin (2004)}.


%===================================
\section{A general non-Gaussian LIL}
\label{sec:LIL}
%===================================

Our conditions and results involve the function $\logit : (0,1) \to \R$ with
\[
	\logit(t) \ := \ \log \Bigl( \frac{t}{1 - t} \Bigr) .
\]
Its inverse is the logistic function $\ell : \R \to (0,1)$ with
\[
	\ell(x) \ := \ \frac{e^x}{1 + e^x} \ = \ \frac{1}{e^{-x} + 1} ,
\]
and
\[
	\ell'(x) \ = \ \ell(x) (1 - \ell(x))
	\ = \ \frac{1}{e^x + e^{-x} + 2} .
\]
We consider stochastic processes $X = (X(t))_{t \in \TT}$ on subsets $\TT$ of $(0,1)$ which have locally uniformly sub-exponential tails in the following sense:

\begin{Condition}
\label{C}
There exist a real constant $M \ge 1$ and a non-increasing funtion $L : [0,\infty) \to [0,1]$ such that $L(c) = 1 - O(c)$ as $c \downarrow 0$, and
\begin{equation}
\label{eq:subexp}
	\Pr \Bigl( \sup_{t \in [\ell(a), \ell(a+c)] \cap \TT} X(t) > \eta \Bigr)
	\ \le \ M \exp(- L(c) \eta)
\end{equation}
for arbitrary $a \in \R$, $c \ge 0$ and $\eta \in \R$.
\end{Condition}


\begin{Theorem}
\label{thm:LIL}
Suppose that $X$ satisfies Condition~\ref{C}. For arbitrary $\nu > 1$ and $L_o \in (0,1)$ there exists a real constant $M_o \ge 1$ depending only on $M$, $L(\cdot)$, $\nu$ and $L_o$ such that
\[
	\Pr \Bigl( \sup_{t \in \TT}
		\bigl( X(t) - C(t) - \nu D(t) \bigr)
			> \eta \Bigr)
	\ \le \ M_o \exp( - L_o \eta)
	\quad\text{for arbitrary} \ \eta \ge 0 .
\]
\end{Theorem}

\begin{Remark}
\label{rem:Limit.at.01}
Suppose that $X$ satisfies Condition~\ref{C}, where $\inf(\TT) = 0$ and $\sup(\TT) = 1$. For any $\nu > 1$, the supremum $T_\nu(X)$ of $X - C - \nu D$ over $\TT$ is finite almost surely. But this implies that
\[
	\lim_{t \to \{0,1\}} \bigl( X(t) - C(t) - \nu D(t) \bigr)
	\ = \ - \infty
\]
almost surely. For if $1 < \nu' < \nu$, then
\[
	X(t) - C(t) - \nu D(t)
	\ \le \ T_{\nu'}(X) - (\nu - \nu') D(t) ,
\]
so the claim follows from $T_{\nu'}(X) < \infty$ almost surely and $D(t) \to \infty$ as $t \to \{0,1\}$.
\end{Remark}

\begin{Remark}
Our definition of the function $D = \log(1 + C^2)$ may look somewhat arbitrary. Indeed, we tried various choices, e.g.\ $D = 2 \log(1 + C)$. Theorem~\ref{thm:LIL} is valid for any nonnegative function $D$ on $(0,1)$ such that $D(1-\cdot) = D(\cdot)$ and $D(t) / \log\log\log(1/t) \to 2$ as $t \downarrow 0$. The special choice $D = \log(1 + C^2)$ yielded a rather uniform distribution of $\argmax_{(0,1)} (X - C - \nu D)$ when $X(t) = \mathbb{U}(t)^2/(2t(1-t))$ and $\nu$ close to one.
\end{Remark}


Our first example for a process $X$ satisfying Condition~\ref{C} is squared and standardized Brownian bridge:

\begin{Lemma}
\label{lem:BB}
Let $\TT = (0,1)$ and $X(t) = \mathbb{U}(t)^2/(2t(1 - t))$ with standard Brownian bridge $\mathbb{U}$. Then Condition~\ref{C} is satisfied with $M = 2$ and $L(c) = e^{-c}$.
\end{Lemma}

\noindent In particular, Lemma~\ref{lem:BB} and Theorem~\ref{thm:LIL} yield \eqref{eq:additive.LIL.BB} for any $\nu > 1$.


%=======================================================
\section{Implications for the uniform empirical process}
\label{sec:EP}
%=======================================================

As indicated in the introduction, Theorem~\ref{thm:LIL} may be applied to the uniform empirical process $\hat{G}_n$ in two ways. A first version concerns $\TT = (0,1)$ and
\[
	X_n(t) \ := \ n K(\hat{G}_n(t),t) .
\]

\begin{Lemma}
\label{lem:UniformEP.1}
The stochastic process $X_n$ satisfies Condition~\ref{C} with $M = 2$ and $L(c) = e^{-c}$.
\end{Lemma}

\noindent
Combining this lemma, Theorem~\ref{thm:LIL} and Donsker's Theorem for the uniform empirical process yields the following result:

\begin{Theorem}
\label{thm:UniformEP.1}
For any fixed $\nu > 1$,
\[
	T_{n,\nu}
	\ = \ \sup_{t \in (0,1)}
		\bigl( X_n(t) - C(t) - \nu D(t) \bigr)
\]
converges in distribution to the random variable
\[
	T_\nu \ := \ \sup_{t \in (0,1)}
		\Bigl( \frac{\mathbb{U}(t)^2}{2t(1-t)} - C(t) - \nu D(t) \Bigr) .
\]
\end{Theorem}

For the computation of confidence bands it is more convenient to work with the following stochastic process on $\TT_n := \{t_{nj} : j = 1,2,\ldots,n\}$:
\[
	\tilde{X}_n(t_{nj}) \ := \ (n+1) K(t_{nj}, U_{n:j}) .
\]

\begin{Lemma}
\label{lem:UniformEP.2}
The stochastic process $\tilde{X}_n$ satisfies Condition~\ref{C} with $M = 2$ and $L(c) = e^{-c}$.
\end{Lemma}

\noindent
Again we may combine this with Theorem~\ref{thm:LIL} and Donsker's theorem for partial sum processes to obtain a new limit theorem:

\begin{Theorem}
\label{thm:UniformEP.2}
For any fixed $\nu > 1$,
\[
	\tilde{T}_{n,\nu}
	\ = \ \sup_{t \in \TT_n}
		\bigl( \tilde{X}_n(t) - C(t) - \nu D(t) \bigr)
\]
converges in distribution to the random variable $T_\nu$ defined in Theorem~\ref{thm:UniformEP.1}.
\end{Theorem}


%==============================
\section{Goodness-of-fit tests}
\label{sec:GoF}
%==============================

As explained in the introduction, we may reject the null hypothesis that $F$ is a given continuous distribution function $F_o$ at level $\alpha$ if
\[
	T_{n,\nu}(F_o) \ = \
	\sup_{x \in \R}
		\bigl( n K(\hat{F}_n(x), F_o(x)) - C(F_o(x)) - \nu D(F_o(x)) \bigr) ,
\]
exceeds $\kappa_{n,\nu,\alpha}$. Note also that the latter supremum may be expressed as the maximum of $2n + 1$ terms, replacing the argument $(x)$ with $(X_{n:i})$ and $(X_{n:i}\,-)$ for $1 \le i \le n$ or with $(F_o^{-1}(1/2))$.

As shown in the next lemma, for any fixed citical value $\kappa > 0$, the probability that $T_{n,\nu}(F_o) \le \kappa$ is small if the quantity
\[
	\Delta_n(F,F_o) \ := \ \sup_{\R}
		\frac{\sqrt{n} |F - F_o|}
		{\sqrt{\Gamma(F_o) F_o(1 - F_o)} + \Gamma(F_o)/\sqrt{n}}
\]
is large, where $\Gamma(t) := C(t) + 1$ for $t \in [0,1]$ with $C(0) := C(1) := \infty$. Note that $\Gamma(t) t(1 - t) \to 0$ as $(0,1) \ni t \to \{0,1\}$.

\begin{Lemma}
\label{lem:Power}
For any critical value $\kappa > 0$ there exists a constant $B_{\nu,\kappa}$ such that
\begin{equation}
\label{eq:Power}
	\Pr_{F} \bigl( T_{\nu,n}(F_o) \le \kappa \bigr)
	\ \le \ B_{\nu,\kappa} \, \Delta_n(F,F_o)^{-4/5} .
\end{equation}
\end{Lemma}

Here and subsequently, the subscript $F$ in $\Pr_{F}(\cdot)$ or $\Ex_{F}(\cdot)$ specifies the true distribution function of the random variables $X_1, X_2, \ldots, X_n$. Now consider an arbitrary sequence $(F_n)_n$ of distribution functions. Then for any fixed level $\alpha \in (0,1)$, Lemma~\ref{lem:Power} and the fact that $\kappa_{n,\nu,\alpha} \to \kappa_{\nu,\alpha} < \infty$ imply that
\[
	\Pr_{F_n} \bigl( T_{n,\nu}(F_o) > \kappa_{n,\nu,\alpha} \bigr)
	\ \to \ 1
\]
provided that
\begin{equation}
\label{eq:AsPower1}
	\Delta_n(F_n,F_o) \ \to \ \infty .
\end{equation}
In particular, \eqref{eq:AsPower1} is satisfied if $F_n \equiv F_* \not\equiv F_o$ for all sample sizes $n$. Thus our test has asymptotic power one for any fixed distribution function different from $F_o$.


\paragraph{Detecting Gaussian mixtures.}
%
We consider a testing problem studied in detail by \nocite{Donoho_Jin_2004}{Donoho and Jin (2004)}. The null hypothesis is given by $F_o = \Phi$, the standard Gaussian distribution function, whereas
\[
	F_n(x) \ := \ (1 - \eps_n) \Phi(x) + \eps_n \Phi(x - \mu_n)
\]
for certain numbers $\eps_n \in (0,1)$ and $\mu_n > 0$. By means of Lemma~\ref{lem:Power} one can derive the following result:

\begin{Lemma}
\label{lem:DonohoJin}
\textbf{(a)} Suppose that $\eps_n = n^{-\beta + o(1)}$ for some fixed $\beta \in (1/2,1)$. Further let $\mu_n = \sqrt{2 r \log(n)}$ for some $r \in (0,1)$. Then $\Delta_n(F_n,\Phi) \to \infty$ if
\[
	r \ > \ r_*(\beta) := \begin{cases}
		\beta - 1/2
			& \text{if} \ \beta \in (1/2, 3/4] , \\
		\bigl( 1 - \sqrt{1 - \beta} \bigr)^2
			& \text{if} \ \beta \in [3/4,1) .
	\end{cases}
\]
\textbf{(b)} Suppose that $\eps_n = n^{-1/2 + o(1)}$ such that $\pi_n := \sqrt{n} \eps_n \to 0$. Then $\Delta_n(F_n,\Phi) \to \infty$ if $\mu_n = \sqrt{2 s \log(1/\pi_n)}$ for some $s > 1$.
\end{Lemma}

As explained by \nocite{Donoho_Jin_2004}{Donoho and Jin (2004)}, any goodness-of-fit test at fixed level $\alpha \in (0,1)$ has trivial asymptotic power $\alpha$ whenever $\eps_n = n^{-\beta}$ for some $\beta \in (1/2,1)$ and $\mu_n = \sqrt{2 r \log(n)}$ with $r < r_*(\beta)$. Thus our new test provides another example of an asymptotically optimal procedure in this particular setting. Other procedures with asymptotic power one whenever $r > r_*(\beta)$ are Tukey's higher criticism test (\nocite{Donoho_Jin_2004}{Donoho and Jin 2004}) or the generalized Berk--Jones tests (\nocite{Jager_Wellner_2007}{Jager and Wellner 2007}).

In the setting of part~(b), the latter two classes of tests can fail to have asymptotic power one if $\mu_n = \sqrt{2 s \log(1/\pi_n)}$ for fixed $s > 1$ but $\pi_n \to 0$ sufficiently slow. On the other hand, one can show that any level-$\alpha$ test of $F_o$ versus $F_n$ has trivial asymptotic power whenever $\mu_n \le \sqrt{2 s \log(1/\pi_n)}$ for an arbitrary fixed $s < 1$. A rigorous proof is provided with the supplementary material.

Parts~(a) and (b) of Lemma~\ref{lem:DonohoJin} are well connected. For let $\eps_n = n^{-\beta + o(1)}$ for some $\beta \in (1/2,3/4]$, and $\mu_n = \sqrt{2 r \log(n)}$ for some $r > \beta - 1/2$. Then $s := r/(\beta - 1/2) > 1$ and with $\pi_n := \sqrt{n} \eps_n = n^{1/2 - \beta + o(1)}$ we may rewrite $\mu_n$ as
\[
	\mu_n \ = \ \sqrt{2 s (\beta - 1/2) \log(n)}
	\ = \ \sqrt{(2s + o(1)) \log(1 / \pi_n)} .
\]


%=========================
\section{Confidence bands}
\label{sec:CB}
%=========================

The confidence bands of \nocite{Owen_1995}{Owen (1995)} may be described as follows: For $0 \le j \le n$ let $s_{nj} := j/n$. With confidence $1 - \alpha$ we may claim that for $0 \le j \le n$ and $X_{n:j} \le x < X_{n:j+1}$,
\[
	F(x) \ \in \ [a_{nj}^{\rm BJO}, b_{nj}^{\rm BJO}] ,
\]
where
\begin{align*}
	b_{nj}^{\rm BJO} \
	&:= \ \begin{cases}
		\max \bigl\{ b \in (s_{nj},1) : K(s_{nj}, b) \le \gamma_n^{\rm BJ} \bigr\}
			&\text{for} \ 0 \le j < n , \\
		1
			&\text{for} \ j = n ,
		\end{cases} \\
	a_{nj}^{\rm BJO} \
	&:= \ 1 - b_{n,n-j}^{\rm BJO} ,
\end{align*}
and
\[
	\gamma_n^{\rm BJ} \ = \ \frac{\kappa_{n,\alpha}^{\rm BJ}}{n}
	\ = \ \frac{\log\log n}{n} (1 + o(1)) .
\]
Our new method is analogous: With confidence $1 - \alpha$, for $0 \le j \le n$ and $X_{n:j} \le x < X_{n:j+1}$, the value $F(x)$ is contained in $[a_{nj}, b_{nj}]$, where
\begin{align*}
	b_{nj} \
	&:= \ \begin{cases}
		\max \bigl\{ u \in (t_{n,j+1},1) :
			K(t_{n,j+1},u) \le \gamma_n(t_{n,j+1}) \bigr\}
			&\text{for} \ 0 \le j < n, \\
		1
			&\text{for} \ j = n ,
		\end{cases} \\
	a_{nj} \
	&:= \ 1 - b_{n,n-j} ,
\end{align*}
and
\[
	\gamma_n(t)
	\ := \ \frac{C(t) + \nu D(t) + \tilde{\kappa}_{n,\nu,\alpha}}{n+1}
\]
for $t \in \TT_n$. Asymptotically the new confidence band is everywhere at least as good as \nocite{Owen_1995}{Owen's (1995)} band, and in the central region it is infinitely more accurate:


\begin{Theorem}
\label{thm:AsEfficiency}
For any fixed $\alpha \in (0,1)$,
\[
	\max_{j=0,1,\ldots,n-1} \frac{b_{nj} - s_{nj}}{b_{nj}^{\rm BJO} - s_{nj}}
	\ = \
	\max_{j=1,2,\ldots,n} \frac{s_{nj} - a_{nj}}{s_{nj} - a_{nj}^{\rm BJO}}
	\ \to \ 1 , \\
\]
while
\begin{align*}
	\max_{j=0,1,\ldots,n} (b_{nj}^{\rm BJO} - s_{nj})
	\ = \
	\max_{j=0,1,\ldots,n} (s_{nj} - a_{nj}^{\rm BJO}) \
	&= \ (1 + o(1)) \sqrt{\frac{\log\log n}{2n}} , \\
	\max_{j=0,1,\ldots,n} (b_{nj} - s_{nj})
	\ = \
	\max_{j=0,1,\ldots,n} (s_{nj} - a_{nj}) \
	&= \ O(n^{-1/2}) .
\end{align*}
\end{Theorem}

To be honest, the asymptotic statement in the first part of Theorem~\ref{thm:AsEfficiency} requires huge sample sizes to materialize. In our numerical experiments it turned out that for sample sizes $n$ up to $10000$ and very small indices $j$, the ratio $(b_{nj} - s_{nj})/(b_{nj}^{\rm BJO} - s_{nj})$ is between $1.5$ and $2$ but drops off quickly as $j$ gets larger.

\paragraph{Numerical example.}
%
The left panel in Figure~\ref{fig:AsEfficiency.1} depicts for $n = 500$, $\nu = 1.1$ and $\alpha = 5\%$ the confidence limits $a_{nj}$ and $b_{nj}$ as functions of $j \in \{0,1,\ldots,n\}$. The dotted (yellow) line in the middle represents the values $s_{nj}$. The corresponding quantile $\tilde{\kappa}_{n,\nu,\alpha}$ was estimated in $40000$ Monte-Carlo simulations as $4.2471$, and this leads to the maximal value $\gamma_n(t_{n1}) = 0.0151$. In the right panel one sees the centered boundaries $a_{nj} - s_{nj}$ and $b_{nj} - s_{nj}$. In addition the centered boundaries $a_{nj}^{\rm BJO} - s_{nj}$ and $a_{nj}^{\rm BJO} - s_{nj}$ are shown as dashed (and cyan) lines, based on the estimated quantile $\kappa_{n,\alpha}^{\rm BJ} = 5.6615$ and $\gamma_n^{\rm BJO} = 0.0113$. The additional horizontal lines are the values $\pm n^{-1/2} \kappa_{n,\alpha}^{\rm KS} = \pm 0.0604$ for the Kolmogorov-Smirnov bands.

Figure~\ref{fig:AsEfficiency.2} shows the same as the right panel in Figure~\ref{fig:AsEfficiency.1}, but with sample sizes $n = 2000$ and $n = 8000$ in the left and right panel, respectively.

\begin{figure}
\includegraphics[width=0.49\textwidth]{CBs500a}
\hfill
\includegraphics[width=0.49\textwidth]{CBs500b}
\caption{The confidence limits $a_{nj},b_{nj}$ (left panel) and the centered confidence limits $a_{nj} - s_{nj}, b_{nj} - s_{nj}$ (right panel) for $n = 500$, $\nu = 1.1$ and $\alpha = 5\%$.}
\label{fig:AsEfficiency.1}
\end{figure}

\begin{figure}
\includegraphics[width=0.49\textwidth]{CBs2000b}
\hfill
\includegraphics[width=0.49\textwidth]{CBs8000b}
\caption{Centered confidence limits for $n = 2000, 8000$ and $\nu = 1.1$, $\alpha = 5\%$.}
\label{fig:AsEfficiency.2}
\end{figure}


\paragraph{Accuracy in the tails.}
%
The confidence bands described here yield an upper bound for $F$ with limit $b_{n0}^{\rm BJO}$ or $b_{n0}$ at $- \infty$ and a lower bound for $F$ with limit $a_{nn}^{\rm BJO}$ or $a_{nn}$ at $+\infty$. The proof of Theorem~\ref{thm:AsEfficiency} reveals that
\[
	b_{n0}^{\rm BJO}, b_{nn} \ = \ \frac{\log\log n}{n} (1 + o(1))
	\quad\text{and}\quad
	a_{nn}^{\rm BJO}, a_{nn} \ = \ 1 - \frac{\log\log n}{n} (1 + o(1)) .
\]
On the other hand, the proof of Theorem~2 of \nocite{Bahadur_Savage_1956}{Bahadur and Savage (1956)} shows that we cannot expect substantially more accuracy in the tails. Their arguments can be adpated to show that for any $(1 - \alpha)$-confidence band and any $c > 0$, the limit of the upper band at $-\infty$ is smaller than $c/n$ with probability at most $(1 - c/n)^{-n} \alpha$. The same bound holds true for the probability that the limit of the lower bound at $\infty$ is greater than $1 - c/n$. For a proof we refer to the supplementary material.


\paragraph{An alternative approach via the union-intersection principle.}
%
\nocite{Aldor-Noiman_etal_2013}{Aldor-Noiman et al.\ (2013)} and \nocite{Eiger_etal_2013}{Eiger et al.\ (2013)} propose to use a union-intersection type goodness-of-fit test and related confidence bands. Under the null hypothesis that $F \equiv F_o$, the test statistic $F_o(X_{n:i})$ and $U_{n:i}$ follow a beta distribution with parameters $i$ and $n+1-i$. Denoting its distribution function with $B_{ni}$, two resulting p-values would be $B_{ni}(F_o(X_{n:i}))$ and $1 - B_{ni}(F_o(X_{n:i}))$. Thus one can reject the null hypothesis at level $\alpha$ if the test statistic
\[
	\min_{i=1,2,\ldots,n} \
		\min \bigl\{ B_{ni}(F_o(X_{n:i})), 1 - B_{ni}(F_o(X_{n:i})) \bigr\}
\]
is lower or equal to the $\alpha$-quantile $\kappa_{n,\alpha}^{\rm UI}$ of
\begin{equation}
\label{eq:UITest0}
	\min_{i=1,2,\ldots,n} \
		\min \bigl\{ B_{ni}(U_{n:i}), 1 - B_{ni}(U_{n:i}) \bigr\} .
\end{equation}
A corresponding $(1 - \alpha)$-confidence band for $F$ may be constructed as follows: With confidence $1 - \alpha$ one may claim that for $0 \le j \le n$ and $X_{n:j} \le x < X_{n:j+1}$,
\[
	F(x) \ \in \ [a_{nj}^{\rm UI}, b_{nj}^{\rm UI}] ,
\]
where $a_{n0}^{\rm UI} := 0$, $b_{nn}^{\rm UI} := 1$, and
\begin{align*}
	a_{nj}^{\rm UI} \
	&:= \ B_{nj}^{-1}(\kappa_{n,\alpha}^{\rm UI})
		\quad\text{for} \ j > 1 , \\
	b_{nj}^{\rm UI} \
	&:= \ B_{nj}^{-1}(1 - \kappa_{n,\alpha}^{\rm UI})
		\quad\text{for} \ j < n .
\end{align*}

The results of \nocite{Eiger_etal_2013}{Eiger et al.\ (2013)} indicate that this goodness-of-fit test has similar properties as the one of \nocite{Berk_Jones_1979}{Berk and Jones (1979)}. Indeed, if one considers the closely related test statistic
\[
	\max_{i=1,2,\ldots,n} \, (n+1) K(t_{ni},F_o(X_{n:i}))
\]
one may consider $\exp \bigl( - (n+1) K(t_{ni},U_{ni}) \bigr)$ as a simple surrogate for the minimum of the two p-values $B_{ni}(F_o(X_{n:i}))$ and $1 - B_{ni}(F_o(X_{n:i}))$.

A possible weakness of the union-intersection approach is that it ignores correlations between the random variables $U_{n:i}$. Elementary calculations reveal that for $1 \le i < j \le n$,
\[
	\mathrm{Corr}(U_{n:i},U_{n:j})
	\ = \ \exp \bigl( - (\ell(t_{nj}) - \ell(t_{ni}))/2 \bigr) .
\]
Thus the correlation of two neighbors $U_{n:i}$ and $U_{n:i+1}$ is rather large if $t_{ni}$ is close to $1/2$ but much smaller if $t_{ni}$ is close to $0$ or $1$. As a result, the minimum in \eqref{eq:UITest0} tends to be attained for indices $i$ such that $t_{ni}$ is close to $0$ or $1$. With our additive correction term $- C(t_{ni}) - \nu D(t_{ni})$ we try to account for such effects.


%=================
\section{Proofs}
\label{sec:Proofs}
%=================

%--------------------------------------------
\subsection{Proofs for Section~\ref{sec:LIL}}
%-------------------------------------------.

\begin{proof}[\bf Proof of Theorem~\ref{thm:LIL}]
For symmetry reasons it suffices to prove upper bounds for
\[
	\Pr \Bigl( \sup_{\TT \cap [1/2,1)}
		\bigl( X - C - \nu D \bigr) > \eta \Bigr) .
\]
Note first that for $t,t' \in (0,1)$,
\begin{equation}
\label{eq:var.ratio.and.logit}
	\Bigl| \log \frac{t'(1-t')}{t(1-t)} \Bigr|
	\ \le \ \Bigl| \log \frac{t'}{t} \Bigr| + \Bigl| \log \frac{1-t'}{1-t} \Bigr|
	\ = \ \bigl| \logit(t') - \logit(t) \bigr| .
\end{equation}
Consequently,
\begin{align*}
	C(t') \
	&= \ \log \log \Bigl( \frac{e}{4t(1-t)} \frac{t(1-t)}{t'(1-t')} \Bigr) \\
	&\le \ \log \bigl( \exp(C(t)) + \bigl| \logit(t') - \logit(t) \bigr| \bigr) \\
	&= \ C(t) + \log \bigl( 1 + \exp(- C(t)) \bigl| \logit(t') - \logit(t) \bigr| \bigr) \\
	&\le \ C(t) + \bigl| \logit(t') - \logit(t) \bigr|
\end{align*}
and since $x \mapsto \log(1 + x^2)$ has derivative $2x/(1 + x^2) \le 1$,
\begin{align*}
	D(t')
	\ \le \ D(t) + \bigl| \logit(t') - \logit(t) \bigr| .
\end{align*}
Now let $(a_k)_{k \ge 0}$ be sequence of real numbers with $a_0 = 0$ such that
\begin{equation}
\label{eq:Partition.a}
	a_k \ \to \ \infty
	\quad\text{and}\quad
	0 < \delta_k := a_{k+1} - a_k \ \to \ 0
	\quad\text{as} \ k \to \infty .
\end{equation}
Then it follows from $0 \le \logit(t) - \logit(\ell(a_k)) \le \delta_k$ for $t \in [\ell(a_k),\ell(a_{k+1})]$ that
\begin{align*}
	\sup_{\TT \cap [\ell(a_k),\ell(a_{k+1})]}
	&\bigl( X - C - \nu D) \\
	&\le \ \sup_{\TT \cap [\ell(a_k),\ell(a_{k+1})]} X
		\, - \, C(\ell(a_k)) - \nu D(\ell(a_k))
		\, + \, (1 + \nu) \delta_k \\
	&\le \ \sup_{\TT \cap [\ell(a_k),\ell(a_{k+1})]} X
		\, - \, C(\ell(a_k)) - \nu D(\ell(a_k))
		\, + \, (1 + \nu) \delta_*
\end{align*}
with $\delta_* := \max_{k \ge 0} \delta_k$. Thus Condition~\ref{C} implies that
\begin{align*}
	\Pr \Bigl(
	&\sup_{\TT \cap [1/2,1)} (X - C - \nu D) > \eta \Bigr) \\
	&\le \ \sum_{k \ge 0}
		\Pr \Bigl( \sup_{\TT \cap [\ell(a_k), \ell(a_{k+1})]}
			(X - C - \nu D) > \eta \Bigr) \\
	&\le \ \sum_{k \ge 0}
		\Pr \Bigl( \sup_{\TT \cap [\ell(a_k), \ell(a_{k+1})]} X
			\, > \eta - (1 + \nu) \delta_*
				+ C(\ell(a_k)) + \nu D(\ell(a_k)) \Bigr) \\
	&\le \ M \exp( (1 + \nu)\delta_* ) \exp(- \eta L(\delta_*)) \cdot G ,
\end{align*}
where
\begin{align*}
	G \
	&:= \ \sum_{k \ge 0}
			\exp \bigl( - L(\delta_k) C(\ell(a_k))
				- L(\delta_k) \nu D(\ell(a_k)) \bigr) \\
	&= \ \sum_{k \ge 0}
		\Bigl( \log \frac{e}{4 \ell'(a_k)} \Bigr)^{-L(\delta_k)}
		\Bigl( 1 + \Bigl( \log \log \frac{e}{4 \ell'(a_k)} \Bigr)^2 \Bigr)^{- \nu L(\delta_k)} .
\end{align*}
For any number $a \ge 0$,
\[
	1 \ \le \ \log \frac{e}{4\ell'(a)}
	\ = \ \log \frac{e(e^a + e^{-a} + 2)}{4}
	\ \in \ \bigl( a + \log(e/4), a + 1 \bigr] .
\]
Now we define
\[
	a_k \ := \ \delta_* A(k)
	\quad\text{with}\quad
	A(s) \ := \ \frac{s}{\log(e + s)}
\]
for some $\delta_* > 0$ such that $L(\delta_*) \ge L_o \in (0,1)$. Note that $A(\cdot)$ is a continuously differentiable function on $[0,\infty)$ with $A(0) = 0$, limit $A(\infty) = \infty$ and derivative
\[
	A'(s) \ = \ \frac{1}{\log(e + s)}
		\Bigl( 1 - \frac{s}{(e + s) \log(e + s)} \Bigr)
	\ \in \ \Bigl( 0, \frac{1}{\log(e + s)} \Bigr) .
\]
This implies that \eqref{eq:Partition.a} is indeed satisfied with
\[
	\delta_k
	\ \le \ \frac{\delta_*}{\log(e + k)}
	\ = \ O \bigl( (\log k)^{-1} \bigr) \quad\text{as} \ k \to \infty .
\]
Moreover, as $k \to \infty$,
\begin{align*}
	\Bigl( \log & \frac{e}{4 \ell'(a_k)} \Bigr)^{-L(\delta_k)}
		\Bigl( 1 + \Bigl(\log \log \frac{e}{4 \ell'(a_k)} \Bigr)^2 \Bigr)^{- \nu L(\delta_k)} \\
	&= \ O \bigl( a_k^{-L(\delta_k)}
		\log(a_k)^{- 2\nu L(\delta_k)} \bigr) \\
	&= \ O \bigl( k^{-L(\delta_k)} (\log k)^{L(\delta_k)}
		(\log k)^{- 2\nu L(\delta_k)} \bigr) \\
	&= \ O \bigl( k^{-1 + O(1/\log k)} (\log k)^{- (2\nu - 1) L(\delta_k)} \bigr) \\
	&= \ O \bigl( k^{-1} (\log k)^{- (2\nu - 1 + o(1))} \bigr) .
\end{align*}
Since $2\nu - 1 > 1$, this implies that $G < \infty$. Hence the asserted inequality is true with $M_o = 2 M \exp((1 + \nu) \delta_*) \cdot G$.
\end{proof}


\begin{proof}[\bf Proof of Lemma~\ref{lem:BB}]
To verify Condition~\ref{C} here, recall that if $\mathbb{W} = (\mathbb{W}(t))_{t \ge 0}$ is standard Brownian motion, then $(\mathbb{U}(t))_{t \in (0,1)}$ has the same distribution as $\bigl( (1 - t) \mathbb{W}(s(t)) \bigr)_{t \in (0,1)}$ with $s(t) := t/(1 - t) = \exp(\logit(t))$. Hence for $a \in \R$ and $c \ge 0$,
\begin{align*}
	\sup_{t \in [\ell(a), \ell(a+c)]} X(t) \
	&=_{\LL} \ \sup_{t \in [\ell(a),\ell(a+c)]} \frac{(1 - t)^2 \mathbb{W}(s(t))^2}{2t(1 - t)} \\
	&= \ \sup_{t \in [\ell(a),\ell(a+c)]} \frac{\mathbb{W}(s(t))^2}{2 s(t)} \\
	&= \ \sup_{s \in [e^a, e^{a+c}]} \frac{\mathbb{W}(s)^2}{2 s} \\
	&=_{\LL} \ \sup_{u \in [1, e^c]} \frac{\mathbb{W}(u)^2}{2u} .
\end{align*}
But it is well-known that $(\mathbb{W}(u)/u)_{u \ge 1}$ is a reverse martingale. Thus $\bigl( \exp(\lambda W(u)/u) \bigr)_{u \ge 1}$ is a nonnegative reverse submartingale for arbitrary real numbers $\lambda$. Hence it follows from Doob's inequality for nonnegative submartingales that for any $\eta > 0$,
\begin{align*}
	\Pr \Bigl( \sup_{u \in [1,e^c]}
		\frac{\mathbb{W}(u)^2}{2u} \ge \eta \Bigr) \
	&\le \ \Pr \Bigl( \sup_{u \in [1,e^c]}
		\frac{\mathbb{W}(u)^2}{u^2} \ge \frac{2\eta}{e^c} \Bigr) \\
	&\le \ 2 \Pr \Bigl( \sup_{u \in [1,e^c]}
		\mathbb{W}(u)/u \ge \sqrt{2e^{-c}\eta} \Bigr) \\
	&= \ 2 \inf_{\lambda > 0} \, \Pr \Bigl( \sup_{u \in [1,e^c]}
		\exp \bigl( \lambda \mathbb{W}(u)/u \bigr)
			\ge \exp \bigl( \lambda \sqrt{2e^{-c}\eta} \bigr) \Bigr) \\
	&\le \ 2 \inf_{\lambda > 0} \,
		\Ex \exp \bigl( \lambda \mathbb{W}(1)/1 \bigr)
			\exp \bigl( - \lambda \sqrt{2e^{-c}\eta} \bigr) \\
	&= \ 2 \inf_{\lambda > 0} \,
		\exp \bigl( \lambda^2/2 - \lambda \sqrt{2e^{-c}\eta} \bigr) \\
	&= \ 2 \exp( - e^{-c} \eta) .
\end{align*}\\[-7ex]
\end{proof}


%---------------------------------------------------------------
\subsection{Various properties of the function $K(\cdot,\cdot)$}
\label{subsec:K}
%---------------------------------------------------------------

Before starting with a function $K(\cdot,\cdot)$ itself, let us introduce two auxiliary functions:
\begin{align*}
	H(x) \
	&:= \ x - \log(1 + x) , \quad x \in (-1,\infty) , \\
	\tilde{H}(z) \
	&:= \ - \log(1 - z) - z \ = \ H(-z) , \quad z \in (-\infty,1) .
\end{align*}
Elementary algebra shows that for $s,t \in (0,1)$,
\[
	K(s,t)
	\ = \ s H \Bigl( \frac{t - s}{s} \Bigr)
		+ (1 - s) \tilde{H} \Bigl( \frac{t-s}{1-s} \Bigr) .
\]
This representation will be useful for $s$ close to $0$ or $1$.

\begin{Lemma}
\label{lem:H}
Both functions $H : [0,\infty) \to [0,\infty)$ and $\tilde{H} : [0,1) \to [0,\infty)$ are bijective, strictly increasing and strictly convex. Moreover,
\begin{align*}
	H(x) \
	&\in \ \Bigl[ 1 + x - \sqrt{1 + 2x}, \frac{x^2}{2 + x} \Bigr]
		\quad\text{for} \ x \in [0,\infty) , \\
	\tilde{H}(z) \
	&\in \ \bigl[ - \log(1 - z^2)/2, - \log(1 - z) \bigr]
		\quad\text{for} \ z \in [0,1) .
\end{align*}
The inverse functions $H^{-1} : [0,\infty) \to [0,\infty)$ and $\tilde{H}^{-1} : [0,\infty) \to [0,1)$ are strictly increasing and strictly concave with
\begin{align*}
	H^{-1}(y) \
	&\in \ \bigl[ \sqrt{2y + y^2/4} + y/2, \sqrt{2y} + y \bigr] , \\
	\tilde{H}^{-1}(y) \
	&\in \ \bigl[ 1 - e^{-y}, \sqrt{1 - e^{-2y}} \bigr] .
\end{align*}
\end{Lemma}

The proof of this lemma is elementary and thus omitted. Now we are ready to state essential properties of $K(\cdot,\cdot)$:


\paragraph{(K.0)}
%
With the convention that $0 \log 0 := 0$ one can easily verify that the function $K : [0,1] \times (0,1) \to \R$ is continuous. In particular, $K(0,t) = - \log(1 - t)$ and $K(1,t) = - \log t$. Moreover, $K(1-s,1-t) = K(s,t)$ for arbitrary $s \in [0,1]$ and $t \in (0,1)$.

\paragraph{(K.1)}
%
For $s,t \in (0,1)$,
\[
	\frac{\partial K(s,t)}{\partial s}
	\ = \ \logit(s) - \logit(t)
	\quad\text{and}\quad
	\frac{\partial K(s,t)}{\partial t}
	\ = \ - \frac{s}{t} + \frac{1-s}{1-t}
	\ = \ \frac{t-s}{t(1-t)} .
\]
(The latter formula is true even for $s \in [0,1]$.) In particular, $K(s,t) \ge 0$ with equality if, and only if, $s = t$.

\paragraph{(K.2)}
%
For $s,t \in (0,1)$,
\begin{align*}
	\frac{\partial^2 K(s,t)}{\partial s^2} \
	&= \ \frac{1}{s(1-s)} ,
		\quad
		\frac{\partial^2 K(s,t)}{\partial s \partial t}
		\ = \ - \frac{1}{t(1-t)}
		\quad\text{and} \\
	\frac{\partial^2 K(s,t)}{\partial t^2} \
	&= \ \frac{s}{t^2} + \frac{1-s}{(1-t)^2}
		\ = \ \frac{(t-s)^2 + s(1-s)}{t^2(1-t)^2} .
\end{align*}
In particular, the Hessian matrix of $K$ at $(s,t)$ has positive diagonal elements and non-negative determinant $(t - s)^2 / (s(1-s) t^2(1-t)^2)$. This implies that $K$ is convex on $[0,1] \times (0,1)$.

\paragraph{(K.3)}
%
For fixed $u \in (0,1)$ and arbitrary $0 < t < t' < 1$,
\[
	\frac{K(0,t')}{K(0,t)}, \frac{K(t'u,t')}{K(tu,t)} , \frac{K(t',t'u)}{K(t,tu)}
	\ \in \ \Bigl( \frac{t'}{t}, \frac{t'(1-t)}{(1 - t')t} \Bigr) .
\]

\begin{proof}
Since $K(tu,tu) = 0$, it follows from (K.1) that
\[
	K(tu,t)
	\ = \ \int_{tu}^{t} \frac{\partial K(tu,x)}{\partial x} \, dx
	\ = \ \int_{tu}^{t} \frac{(x - tu)}{x(1 - x)} \, dx
	\ = \ \int_u^1 \frac{t(v-u)}{v(1 - tv)} \, dv .
\]
These formulae remain true if we replace $u$ with $0$. On the other hand, since $K(tu,tu) = 0 = \partial K(s,tu) / \partial s$ for $s = tu$, a suitable version of Taylor's formula and (K.2) imply that
\[
	K(t,tu)
	\ = \ \int_{tu}^{t} (t - x) \frac{\partial^2}{\partial x^2} K(x,tu) \, dx
	\ = \ \int_{tu}^{t} \frac{(t - x)}{x(1 - x)} \, dx
	\ = \ \int_u^1 \frac{t(1 - v)}{v(1 - tv)} \, dv ,
\]
But for any $v \in (0,1)$,
\[
	\frac{\partial}{\partial t} \log \frac{t}{1 - tv}
	\ = \ \frac{1}{t(1 - tv)}
	\ \in \ \Bigl( \frac{1}{t}, \frac{1}{t(1-t)} \Bigr)
	\ = \ \bigl( \log'(t), \logit'(t) \bigr) .
\]
Thus for $0 < t < t' < 1$,
\[
	\frac{t'}{1 - t' v} \Big/ \frac{t}{1 - tv}
	\ \in \ \Bigl( \frac{t'}{t}, \frac{t'(1 - t)}{(1 - t') t} \Bigr) ,
\]
and this entails the asserted inequalities for the three ratios $K(0,t')/K(0,t)$, $K(t'u,t')/K(tu,t)$ and $K(t',t'u)/K(t,tu)$.
\end{proof}

\paragraph{(K.4)}
%
To verify Theorems~\ref{thm:UniformEP.1}, \ref{thm:UniformEP.2} and \ref{thm:AsEfficiency} we have to approximate $K$ by a simpler function $\tilde{K}$ given by
\[
	\tilde{K}(s,t) \ := \ \frac{(s - t)^2}{2 t(1 - t)} .
\]
Indeed, for arbitrary $s,t \in (0,1)$ and $c := \bigl| \logit(s) - \logit(t) \bigr|$,
\[
	\frac{K(s,t)}{\tilde{K}(s,t)}, \frac{K(s,t)}{\tilde{K}(t,s)}
	\ \in \ [e^{-c},e^c] .
\]

\begin{proof}
It follows from (K.1-2) and Taylor's formula that
\[
	K(s,t) \ = \ \frac{(s - t)^2}{2 \xi(1 - \xi)}
\]
for some $\xi$ between $\min\{s,t\}$ and $\max\{s,t\}$. Hence
\[
	\frac{K(s,t)}{\tilde{K}(s,t)}
	\ = \ \frac{t(1-t)}{\xi(1-\xi)}
	\quad\text{and}\quad
	\frac{K(s,t)}{\tilde{K}(t,s)}
	\ = \ \frac{s(1-s)}{\xi(1-\xi)}
\]
are both contained in $[e^{-c}, e^c]$, according to \eqref{eq:var.ratio.and.logit}.
\end{proof}


\paragraph{(K.5)}
%
For arbitrary $\gamma > 0$ and $s \in [0,1]$, $t \in (0,1)$, the inequality $K(s,t) \le \gamma$ implies that
\[
	(t - s)^{\pm} \ \le \ \begin{cases}
		\sqrt{2\gamma s(1-s)} + (1 - 2s)^{\pm} \gamma , \\
		\sqrt{2\gamma t(1-t)} + (2t - 1)^{\pm} \gamma .
	\end{cases}
\]
In particular,
\[
	|s - t| \ \le \ \min \bigl\{ \sqrt{2s(1-s)\gamma}, \sqrt{2t(1-t)\gamma} \bigr\}
		+ \gamma .
\]


\begin{proof}
The first inequality has been proved by \nocite{Duembgen_1998}{D\"umbgen (1998)}, but for the reader's convenience and the proof of the new part, a complete derivation is given here: For symmetry reasons, it suffices to consider the case $0 \le s < t < 1$ and derive the upper bounds for $\delta := t - s = (t - s)^+$.

Let us first treat the case $s = 0$: Here $K(s,t) = - \log(1 - t) \ge t$. Thus $K(0,t) \le \gamma$ implies that $\delta = t \le \gamma = \sqrt{2\gamma s(1 - s)} + (1 - 2s)\gamma$. Moreover, $\sqrt{2\gamma t(1 - t)} + (2t - 1)^+ \gamma \ge t \bigl( \sqrt{2(1-t)} + (2t - 1)^+ \bigr)$, and elementary considerations show that $\sqrt{2(1-t)} + (2t - 1)^+ \ge 1$.

Now let $0 < s < t < 1$ and $\delta := t - s$. It follows from $K(s,s) = 0$ and (K.1) that
\[
	K(s,t)
	\ = \ \int_s^t \frac{\partial K(s,y)}{\partial y} \, dy
	\ = \ \int_0^\delta \frac{x}{(s+x)(1 - s - x)} \, dx
	\ \ge \ \int_0^\delta \frac{x}{s(1-s) + (1 - 2s) x} \, dx .
\]
In case of $s \ge 1/2$, the latter integral is not smaller than $\delta^2 /(2s(1-s))$, and $K(s,t) \le \gamma$ implies the upper bound $\delta \le \sqrt{2\gamma s(1-s)}$. In case of $s < 1/2$, we obtain the bound
\[
	K(s,t) \ \ge \ \int_0^\delta \frac{x}{\alpha + \beta x} \, dx
	\ = \ \frac{\delta}{\beta}
		- \frac{\alpha}{\beta^2} \log \Bigl( 1 + \frac{\beta\delta}{\alpha} \Bigr)
	\ = \ \frac{\alpha}{\beta^2} H \Bigl( \frac{\beta\delta}{\alpha} \Bigr)
\]
with $\alpha := s(1-s) > 0$, $\beta := 1-2s > 0$ and the auxiliary function $H$ from Lemma~\ref{lem:H}. Consequently, the inequality $K(s,t) \le \gamma$ entails that $H(\beta\delta/\alpha) \le \beta^2 \gamma/\alpha$, so
\[
	\delta \ \le \ (\alpha/\beta) H^{-1}(\beta^2 \gamma/\alpha)
	\ \le \ \sqrt{2\gamma \alpha} + \beta\gamma \ = \ \sqrt{2\gamma s(1-s)} + (1 - 2s) \gamma .
\]

On the other hand,
\[
	K(s,t)
	\ = \ \int_s^t \frac{y - s}{y(1-y)} \, dy
	\ = \ \int_0^\delta \frac{\delta - x}{(t-x)(1-t+x)} \, dx
	\ \ge \ \int_0^\delta \frac{\delta - x}{t(1 - t) + (2t - 1)x} \, dx .
\]
In case of $t \le 1/2$, the latter integral is at least $\delta^2/(2t(1-t))$, and we may conclude from $K(s,t) \le \gamma$ that $\delta$ is bounded by $\sqrt{2\gamma t(1 - t)}$. In case of $t > 1/2$, we define $a := t(1 - t) > 0$, $b := 2t-1 > 0$ and may write
\[
	K(s,t)
	\ \ge \ \int_0^\delta \frac{\delta - x}{a + bx} \, dx
	\ > \ \int_0^\delta \frac{x}{a + bx} \, dx
	\ = \ \frac{a}{b^2} H \Bigl( \frac{b\delta}{a} \Bigr) .
\]
The second inequality in the previous display follows from the fact that $f(x) := 1/(a + bx)$ is strictly decreasing on $[0,\delta]$. Thus $\int_0^\delta (\delta - x) f(x) \, dx - \int_0^\delta x f(x) \, dx$ equals
\[
	\int_0^\delta (\delta - 2x) f(x) \, dx
	\ = \ \int_0^\delta (\delta - 2x) (f(x) - f(\delta/2)) \, dx
\]
and is strictly positive. Hence the preceding considerations yield the upper bound $\sqrt{2\gamma a} + b\gamma = \sqrt{2\gamma t(1-t)} + (2t-1) \gamma$ for $\delta$.
\end{proof}


\paragraph{(K.6)}
%
For $s \in (0,1)$ and $\gamma > 0$ let $b = b(s,\gamma) \in (s,1)$ solve the equation
\[
	K(s,b) \ = \ \gamma .
\]
Then
\begin{equation}
\label{eq:K.small.s}
	\frac{b - s}{s H^{-1}(\gamma/s)}
	\ \begin{cases}
		\le \ 1 , \\
		\to \ 1 & \text{as} \ s,\gamma \to 0 ,
	\end{cases}
\end{equation}
\begin{equation}
\label{eq:K.intermediate.s}
	\frac{b-s}{\sqrt{2\gamma s(1-s)}}
	\ \to \ 1 \quad\text{as} \ \frac{\gamma}{s(1-s)} \to 0 ,
\end{equation}
\begin{equation}
\label{eq:K.large.s}
	\frac{b - s}{(1 - s) \tilde{H}^{-1}(\gamma/(1-s))}
	\ \in \ [s,1] .
\end{equation}

\begin{proof}
With $\delta := (b - s)/s > 0$ we may write
\[
	\frac{\gamma}{s} \ = \ \frac{K(s,s+s\delta)}{s}
	\ = \ H(\delta) + \frac{1-s}{s} \tilde{H} \Bigl( \frac{s\delta}{1 - s} \Bigr) .
\]
Since $\tilde{H} \ge 0$, this implies that $H(\delta) \le \gamma/s$, which is equivalent to $b - s \le s H^{-1}(\gamma/s)$. On the other hand, it follows from the expansion $-\log(1 - z) = \sum_{k=1}^\infty z^k/k = z + \tilde{H}(z)$ that
\[
	\frac{\gamma}{s}
	\ = \ H(\delta) + \frac{1-s}{s}
		\sum_{k=2}^\infty \Bigl( \frac{s\delta}{1 - s} \Bigr)^k / k
	\ \le \ H(\delta) + \frac{s \delta^2}{2(1 - s - s \delta)} .
\]
As $c := \max\{s,\gamma\} \to 0$, it follows from $\delta \le H^{-1}(\gamma/s) \le \sqrt{2\gamma/s} + \gamma/s$ that
\begin{align*}
	1 - s - s\delta \
	&\ge \ 1 - s - \sqrt{2 s\gamma} - \gamma \ = \ 1 - O(c) , \\
	s \delta^2 \
	&\le \ s \bigl( \sqrt{2\gamma/s} + \gamma/s \bigr)^2
		\ = \ O(c) \gamma/s ,
\end{align*}
whence
\[
	\frac{\gamma}{s} \ \le \ H(\delta) + O(c) \frac{\gamma}{s} .
\]
Consequently,
\[
	b - s \ \ge \ s H^{-1} \bigl( (1 - O(c)) \gamma/s \bigr)
	\ \ge \ (1 - O(c)) \, s H^{-1}(\gamma/s) ,
\]
the latter inequality following from concavity of $H^{-1}$. This proves \eqref{eq:K.small.s}.

As to \eqref{eq:K.intermediate.s}, let $c := \sqrt{\gamma /(s(1-s))} < 1/2$, and define the points $t(x) = t(s,\gamma,x) := s + \sqrt{2\gamma s(1 - s) x} = s + cs(1-s) \sqrt{2x}$ for $x \in [0,2]$. Then
\[
	0 \ < \ \logit(t(x)) - \logit(s) \ < \ \log \frac{1 + 2c}{1 - 2c}
	\ \to \ 0 \quad\text{as} \ c \to 0 .
\]
Consequently, by (K.4),
\[
	K(s,t(x)) \ = \ (1 + o(1)) \tilde{K}(t(x),s) \ = \ (1 + o(1)) \gamma x
\]
uniformly in $x \in [0,2]$. This shows that $b(s,\gamma) = t(1 + o(1)) = s + \sqrt{2\gamma s(1-s)} (1 + o(1))$ as $c \to 0$.

Finally, let $\delta := (b - s)/(1 - s)$. Then it follows from $\tilde{H}(z) \ge z^2/2 \ge H(z)$ that
\[
	\frac{\gamma}{1-s}
	\ = \ \frac{s}{1-s} H \Bigl( \frac{1-s}{s} \delta \Bigr) + \tilde{H}(\delta)
	\ \begin{cases}
		\ge \ \tilde{H}(\delta) , \\
		\le \ (1 - s) \delta^2 / (2s) + \tilde{H}(\delta)
			\ \le \ \tilde{H}(\delta)/s .
	\end{cases}
\]
Consequently, by concavity of $\tilde{H}^{-1}(\cdot)$,
\[
	s \tilde{H}^{-1}(\gamma/(1-s)) \ \le \ \tilde{H}^{-1}(s \gamma/(1-s))
	\ \le \ \delta \ \le \ \tilde{H}^{-1}(\gamma/(1-s)) ,
\]
which yields \eqref{eq:K.large.s}.
\end{proof}


%-------------------------------------------
\subsection{Proofs for Section~\ref{sec:EP}}
%-------------------------------------------

Before proving Lemma~\ref{lem:UniformEP.1} let us recall that for $s \in \R$ and $t \in (0,1)$,
\[
	K(s,t) \ := \ \sup_{\lambda \in \R} \,
		\bigl( \lambda s - \log(1 - t + te^\lambda) \bigr)
	\ = \ \begin{cases}
		\displaystyle
		s \log \frac{s}{t} + (1 - s) \log \frac{1-s}{1-t}
			& \text{if} \ s \in [0,1] , \\
		\infty
			& \text{else} .
	\end{cases}
\]
Indeed, \nocite{Hoeffding_1963}{Hoeffding (1963)} showed that for a random variable $Y \sim \mathrm{Bin}(n,t)$ and $s \in \R$,
\begin{align*}
	\Pr(Y \ge ns) \
	&\le \ \exp \Bigl( - n \sup_{\lambda \ge 0} \,
		\bigl( \lambda s - \log(1 - t + te^\lambda) \bigr) \Bigr)
		\ = \ \exp(- n K(s,t))
		\quad\text{if} \ s \ge t , \\
	\Pr(Y \le ns) \
	&\le \ \exp \Bigl( - n \sup_{\lambda \le 0} \,
		\bigl( \lambda s - \log(1 - t + te^\lambda) \bigr) \Bigr)
		\ = \ \exp(- n K(s,t))
		\quad\text{if} \ s \le t .
\end{align*}


\begin{proof}[\bf Proof of Lemma~\ref{lem:UniformEP.1}]
We imitate and modify a martingale argument of \nocite{Berk_Jones_1979}{Berk and Jones (1979, Lemma~4.3)} which goes back to \nocite{Kiefer_1973}{Kiefer (1973)}. Note first that $\hat{G}_n(t)/t$ is a reverse martingale in $t \in (0,1)$, that means,
\[
	\Ex \bigl( \hat{G}_n(s)/s \,\big|\, (\hat{G}_n(t'))_{t' \ge t} \bigr)
	\ = \ \hat{G}_n(t)/t
	\quad\text{for} \ 0 < s < t < 1 .
\]
Consequently, for $0 < t < t' < 1$ and $0 \le u \le 1$,
\begin{align*}
	\Pr \Bigl( \inf_{s \in [t,t']} \hat{G}_n(s)/s \le u \Bigr) \
	&= \ \inf_{\lambda \le 0} \,
		\Pr \Bigl( \sup_{s \in [t,t']} \exp(\lambda \hat{G}_n(s)/s - \lambda u) \ge 1 \Bigr) \\
	&\le \ \inf_{\lambda \le 0} \,
		\Ex \exp(\lambda \hat{G}_n(t)/t - \lambda u)
\end{align*}
by Doob's inequality for non-negative submartingales. But $n \hat{G}_n(t) \sim \mathrm{Bin}(n,t)$, so
\begin{align*}
	\inf_{\lambda \le 0} \, \Ex \exp(\lambda \hat{G}_n(t)/t - \lambda u) \
	&= \ \inf_{\lambda \le 0} \, \Ex \exp \bigl( \lambda n \hat{G}(t) - n\lambda tu \bigr) \\
	&= \ \exp \Bigl( - n \sup_{\lambda \le 0}
		\bigl( \lambda tu - \log(1 - t + t e^\lambda) \bigr) \Bigr) \\
	&= \ \exp(- n K(tu,t)) .
\end{align*}
Thus
\[
	\Pr \Bigl( \inf_{s \in [t,t']} \hat{G}_n(s)/s \le u \Bigr)
	\ \le \ \exp(- n K(tu,t))
	\quad\text{for all} \ u \in [0,1] .
\]
One may rewrite this inequality as
\[
	\Pr \Bigl( \sup_{s \in [t,t']} n K \bigl( t \min\{\hat{G}_n(s)/s, 1\}, t \bigr) \ge \eta \Bigr)
	\ \le \  \exp(- \eta)
	\quad\text{for all} \ \eta \ge 0 .
\]
For if $\eta > - n \log(1 - t)$, the probability on the left hand side equals $0$. Otherwise there exists a unique $u = u(t,\eta) \in [0,1]$ such that $n K(tu,t) = \eta$. But then
\[
	n K \bigl( t \min\{\hat{G}_n(s)/s, 1\}, t \bigr) \ge \eta
	\quad\text{if, and only if,}\quad
	\hat{G}_n(s)/s \le u .
\]
Finally, it follows from property (K.3) of $K(\cdot,\cdot)$ that for $t \le s \le t'$,
\[
	K \bigl( \min\{\hat{G}_n(s),s\}, s \bigr)
	\ = \ K \bigl( s \min\{\hat{G}_n(s)/s, 1\}, s \bigr)
	\ \le \ e^c K \bigl( t \min\{\hat{G}_n(s)/s, 1\}, t \bigr)
\]
with $c := \logit(t') - \logit(t)$. Hence
\[
	\Pr \Bigl( \sup_{s \in [t,t']} n K \bigl( \min\{\hat{G}_n(s), s\}, s \bigr) \ge \eta \Bigr)
	\ \le \ \exp(- e^{-c} \eta)
	\quad\text{for all} \ \eta \ge 0 .
\]

Since $\bigl( \hat{G}_n(t) \bigr)_{t \in (0,1)}$ has the same distribution as $\bigl( 1 - \hat{G}_n((1 - t) \, -) \bigr)_{t \in (0,1)}$, and because of the symmetry relations $K(s,t) = K(1-s,1-t)$ and $\logit(1 - t) = - \logit(t)$, the previous inequality implies further that
\begin{align*}
	\Pr \Bigl(
	& \sup_{s \in [t,t']} n K \bigl( \max\{\hat{G}_n(s), s\}, s \bigr)
			\ge \eta \Bigr) \\
	&= \ \Pr \Bigl(
		\sup_{s \in [t,t']} n K \bigl( \min\{1 - \hat{G}_n(s), 1 - s\}, 1 - s \bigr)
			\ge \eta \Bigr) \\
	&= \ \Pr \Bigl(
		\sup_{s \in [1-t',1-t]} n K \bigl( \min\{\hat{G}_n(s), s\}, s \bigr)
			\ge \eta \Bigr) \\
	&\le \ \exp(- e^{-c} \eta)
		\quad\text{for all} \ \eta \ge 0 .
\end{align*}
Consequently, since $K(\cdot,s) = \max \bigl\{ K(\min\{\cdot,s\},s), K(\max\{\cdot,s\},s) \bigr\}$,
\[
	\Pr \Bigl( \sup_{s \in [t,t']} n K(\hat{G}_n(s),s) \ge \eta \Bigr)
	\ \le \ 2 \exp(- e^{-c} \eta)
	\quad\text{for all} \ \eta \ge 0 .
\]\\[-7ex]
\end{proof}


\begin{proof}[\bf Proof of Theorem~\ref{thm:UniformEP.1}]
For any fixed $\delta \in (0,1/2)$, it follows from Donsker's invariance principle for the uniform empirical process and the continuous mapping theorem that
\[
	\sup_{t \in [-\delta,\delta]}
		\Bigl( \frac{\mathbb{U}_n(t)^2}{2t(1-t)} - C(t) - \nu D(t) \Bigr)
	\ \to_{\LL} \ \sup_{[-\delta,\delta]}
		\bigl( X - C - \nu D \bigr) ,
\]
where $X(t) = \mathbb{U}(t)^2/(2t(1-t))$. With $X_n(t) = n K(\hat{G}_n(t),t)$ it follows from property (K.4) of $K(\cdot,\cdot)$ that
\[
	\frac{\mathbb{U}_n(t)^2}{2t(1-t)}
	\ = \ n \tilde{K}(\hat{G}_n(t),t)
	\ = \ X_n(t) (1 + r_n(t))
\]
with
\[
	\sup_{t \in [\delta,1-\delta]} |r_n(t)|
	\ \le \ \bigl( 1 - n^{-1/2} \delta^{-1} \|\mathbb{U}_n\|_\infty \bigr)^{-2} - 1
	\ = \ O_p(n^{-1/2}) .
\]
Thus
\[
	\sup_{[-\delta,\delta]} \bigl( X_n - C - \nu D \bigr)
	\ \to_{\LL} \ \sup_{[-\delta,\delta]} \bigl( X - C - \nu D \bigr) .
\]
But Theorem~\ref{thm:LIL} implies that for any $1 < \nu' < \nu$, the random variables $T_{n,\nu'}$ and $T_{\nu'}$ satisfy the inequalities $\Pr(T_{n,\nu'} > \eta) \le M_o \exp(- L_o\eta)$ and $\Pr(T_{\nu'} > \eta) \le M_o \exp(- L_o\eta)$ for arbitrary $\eta \in \R$ and some constants $L_o \in (0,1)$, $M_o \ge 1$. Consequently for any $\rho > 0$,
\begin{align*}
	\Pr \Bigl(
	&\sup_{[\delta,1-\delta]} (X_{n} - C - \nu D)
		< \sup_{(0,1)} (X_{n} - C - \nu D) \Bigr) \\
	&\le \ \Pr \bigl( T_{n,\nu'} - (\nu - \nu') D(\delta) > - \rho \bigr)
		+ \Pr \bigl( X_{n}(1/2) \le - \rho \bigr) \\
	&\le \ M_o \exp \bigl( L_o\rho - L_o (\nu - \nu') D(\delta) \bigr)
		+ \Pr(X(1/2) \le - \rho) + o(1)
\intertext{because $X_n(1/2) \to_{\LL} X(1/2)$, and}
	\Pr \Bigl(
	&\sup_{[\delta,1-\delta]} (X - C - \nu D)
		< \sup_{(0,1)} (X - C - \nu D) \Bigr) \\
	&\le \ M_o \exp \bigl( L_o\rho - L_o (\nu - \nu') D(\delta) \bigr)
		+ \Pr(X(1/2) \le - \rho) .
\end{align*}
Setting $\rho = (\nu - \nu') D(\delta)/2$, the limits of the right hand sides become arbitrarily small for sufficiently small $\delta$. This shows that $T_{n,\nu} = \sup_{(0,1)} \bigl( X_n - C - \nu D \bigr)$ converges in distribution to $T_\nu$.
\end{proof}


Our proof of Lemma~\ref{lem:UniformEP.2} involves an exponential inequality for Beta distributions from \nocite{Duembgen_1998}{D\"umb\-gen (1998)}. For the reader's convenience, its proof is included in the supplementary material.

\begin{Lemma}
\label{lem:Beta}
Let $s,t \in (0,1)$, and let $Y \sim \mathrm{Beta}(mt, m(1-t))$ for some $m > 0$. Then
\begin{align*}
	\Pr(Y \le s) \
	&\le \ \inf_{\lambda \le 0} \, \Ex \exp(\lambda Y - \lambda s)
		\ \le \ \exp( - m K(t,s))
		\quad\text{if} \ s \le t , \\
	\Pr(Y \ge s) \
	&\le \ \inf_{\lambda \ge 0} \, \Ex \exp(\lambda Y - \lambda s)
		\ \le \ \exp( - m K(t,s))
		\quad\text{if} \ s \ge t .
\end{align*}
\end{Lemma}


\begin{proof}[\bf Proof of Lemma~\ref{lem:UniformEP.2}]
We utilize a well-known representation of uniform order statistics: Let $E_1, E_2, \ldots, E_{n+1}$ be independent random variables with standard exponential distribution, i.e.\ $\mathrm{Gamma}(1)$, and let $S_j := \sum_{i=1}^j E_i$. Then
\[
	(U_{ni})_{i=1}^n
	\ =_{\LL} \ (S_i/S_{n+1})_{i=1}^n .
\]
In particular, $U_{n:i} \sim \mathrm{Beta}(i,n+1-i) = \mathrm{Beta} \bigl( (n+1)t_{ni},(n+1)(1 - t_{ni}) \bigr)$ and $\Ex U_{n:i} = t_{ni}$. Furthermore, for $2 \le k \le n+1$, the random vectors $(S_i/S_k)_{i=1}^{k-1}$ and $(S_i)_{i=k}^{n+1}$ are stochastically independent. This implies that $(U_{n:i}/t_{ni})_{i=1}^n$ is a reverse martingale, because for $1 \le j < k \le n$,
\[
	\Ex \Bigl( \frac{U_{n:j}}{t_{nj}}
		\,\Big|\, (S_i)_{i=k}^{n+1} \Bigr)
	\ = \ \Ex \Bigl( \frac{S_j}{t_{nj} S_k} \cdot \frac{S_k}{S_{n+1}}
		\,\Big|\, (S_i)_{i=k}^{n+1} \Bigr)
	\ = \ \frac{j}{t_{nj} k} \cdot \frac{S_k}{S_{n+1}}
	\ = \ \frac{U_{n:k}}{t_{nk}} .
\]
Consequently, for $1 \le j \le k \le n$ and $0 < u < 1$, it follows from Doob's inequality and Lemma~\ref{lem:Beta} that
\begin{align*}
	\Pr \Bigl( \min_{j \le i \le k} \frac{U_{n:i}}{t_{ni}} \le u \Bigr) \
	&= \ \inf_{\lambda < 0} \,
		\Pr \Bigl( \min_{j \le i \le k}
			\exp \Bigl( \lambda \frac{U_{n:i}}{t_{ni}} - \lambda u \Bigr) \ge 1 \Bigr) \\
	&\le \ \inf_{\lambda < 0} \,
		\Ex \exp \bigl( \lambda U_{n:j} - \lambda u t_{nj} \bigr) \\
	&\le \ \exp \bigl( - (n+1) K(t_{nj}, t_{nj} u) \bigr) .
\end{align*}
Again one may reformulate the previous inequalities as follows: For any $\eta > 0$,
\[
	\Pr \Bigl( \max_{j \le i \le k} (n+1)
		K \Bigl( t_{nj}, t_{nj} \min \Bigl\{ \frac{U_{n:i}}{t_{ni}}, 1 \Bigr\} \Bigr)
		\ge \eta \Bigr)
	\ \le \ \exp(- \eta) .
\]
But property (K.3) of $K(\cdot,\cdot)$ implies that for $j \le i \le k$,
\[
	K \bigl( t_{ni}, \min\{U_{n:i}, t_{ni}\} \bigr)
	\ \le \
	e^c K \Bigl( t_{nj}, t_{nj} \min \Bigl\{ \frac{U_{n:i}}{t_{ni}}, 1 \Bigr\} \Bigr)
\]
with $c := \logit(t_{nk}) - \logit(t_{nj})$. Consequently,
\[
	\Pr \Bigl( \max_{j \le i \le k} (n+1)
		K \bigl( t_{ni}, \min\{U_{n:i},t_{ni}\} \bigr) \ge \eta \Bigr)
	\ \le \ \exp(- e^{-c} \eta)
	\quad\text{for all} \ \eta > 0 .
\]
Since $(1 - U_{n:n+1-i})_{i=1}^n$ has the same distribution as $(U_{n:i})_{i=1}^n$, a symmetry argument as in the proof of Lemma~\ref{lem:UniformEP.1} reveals that
\[
	\Pr \Bigl( \max_{j \le i \le k} (n+1) K(t_{ni},U_{n:i}) \ge \eta \Bigr)
	\ \le \ 2 \exp(- e^{-c} \eta)
	\quad\text{for all} \ \eta > 0 .
\]\\[-7ex]
\end{proof}

\begin{proof}[\bf Proof of Theorem~\ref{thm:UniformEP.2}]
One can use essentially the same arguments as in the proof of Theorem~\ref{thm:UniformEP.1}. This time one has to utilize the well-known fact that
\[
	(U_{n:i})_{i=1}^n
	\ = \ \bigl( t_{ni} + n^{-1/2} \mathbb{V}_n(t_{ni}) \bigr)_{i=1}^n
\]
where the uniform quantile process $\mathbb{V}_n$ with $\mathbb{V}_n(t) := \sqrt{n} (\hat{G}_n^{-1}(t) - t)$ converges in distribution in $\ell_{\infty}([0,1])$ to a Brownian bridge $\mathbb{V}$; see e.g.\ \nocite{Shorack_Wellner_1986}{Shorack and Wellner (1986)}, pages 86, 93, and 637-644.
\end{proof}


%--------------------------------------------------------------
\subsection{Proofs for Sections~\ref{sec:GoF} and \ref{sec:CB}}
%--------------------------------------------------------------

\begin{proof}[\bf Proof of Lemma~\ref{lem:Power}]
%
Suppose that $T_{n,\nu}(F_o) \le \kappa$. Then the inequalities in (K.5) imply that
\[
	|\hat{F}_n - F_o|
	\ \le \ \sqrt{2 \tilde{\Gamma}(F_o) F_o(1 - F_o) / n}
		+ \tilde{\Gamma}(F_o)/n ,
\]
where $\tilde{\Gamma}(t) := C(t) + \nu D(t) + \kappa$. Multiplying this inequality with $n$ and utilizing the triangle inequality $|\hat{F}_n - F_o| \ge |F - F_o| - |\hat{F}_n - F|$ leads to
\begin{equation}
\label{eq:Power.Step1}
	n |F - F_o|
	\ \le \ \sqrt{2 n\tilde{\Gamma}(F_o) F_o(1 - F_o)}
		+ \tilde{\Gamma}(F_o) + n |\hat{F}_n - F| .
\end{equation}
Now our goal is to get rid of the term $n|\hat{F}_n - F|$ on the right hand side. Defining the auxiliary stochastic process
\[
	W_n \ := \ \frac{n (\hat{F}_n - F)^2}{F(1 - F)}
\]
with the convention $0/0 := 0$, we may rewrite \eqref{eq:Power.Step1} as
\begin{align}
	\nonumber
	n |F - F_o| \
	&\le \ \sqrt{2n \tilde{\Gamma}(F_o) F_o(1 - F_o)}
		+ \tilde{\Gamma}(F_o)
		+ \sqrt{W_n n F(1 - F)} \\
	\nonumber
	&\le \ \sqrt{2n \tilde{\Gamma}(F_o) F_o(1 - F_o)}
		+ \tilde{\Gamma}(F_o)
		+ \sqrt{W_n n F_o(1 - F_o)} + \sqrt{W_n n |F - F_o|} \\
\label{eq:Power.Step2}
	&\le \ \sqrt{n (4 \tilde{\Gamma}(F_o) + 2 W_n) F_o(1 - F_o)}
		+ \tilde{\Gamma}(F_o)
		+ \sqrt{W_n n |F - F_o|} ,
\end{align}
where we utilized the inequalities $|a(1-a) - b(1-b)| \le |a-b|$ for $a,b \in [0,1]$ and $\sqrt{c+d} \le \sqrt{c} + \sqrt{d} \le \sqrt{2c + 2d}$ for $c,d \ge 0$. Note that inequality \eqref{eq:Power.Step2} is of the form $Y_n \le V_n + \sqrt{W_nY_n}$ with the nonnegative processes $Y_n = n |F - F_o|$ and $V_n = \sqrt{n (4 \tilde{\Gamma}(F_o) + 2 W_n) F_o(1 - F_o)} + \tilde{\Gamma}(F_o)$. But $Y_n \le V_n + \sqrt{W_nY_n}$ is equivalent to $Y_n/V_n \le 1 + \sqrt{W_n/V_n} \sqrt{Y_n/V_n}$, and this may be rewritten as $\bigl( \sqrt{Y_n/V_n} - \sqrt{W_n/V_n}/2 \bigr)^2 \le 1 + (W_n/V_n)/4$, so
\[
	\sqrt{Y_n/V_n} \ \le \ \sqrt{W_n/V_n}/2 + \sqrt{1 + (W_n/V_n)/4}
	\ \le \ 1 + \sqrt{W_n/V_n} .
\]
Consequently,
\begin{align*}
	n |F - F_o| \
	&\le \ \bigl( 1 + \sqrt{W_n/V_n} \bigr)^2
		\Bigl( \sqrt{n (4 \tilde{\Gamma}(F_o) + 2 W_n) F_o(1 - F_o)}
			+ \tilde{\Gamma}(F_o) \Bigr) \\
	&\le \ \bigl( 1 + \sqrt{W_n/\kappa} \bigr)^2 \sqrt{4 + 2W_n/\kappa}
		\Bigl( \sqrt{n \tilde{\Gamma}(F_o) F_o(1 - F_o)}
			+ \tilde{\Gamma}(F_o) \Bigr) \\
	&\le \ 2 \bigl( 1 + \sqrt{W_n/\kappa} \bigr)^{5/2}
		\Bigl( \sqrt{n \tilde{\Gamma}(F_o) F_o(1 - F_o)}
			+ \tilde{\Gamma}(F_o) \Bigr) ,
\end{align*}
because $V_n \ge \tilde{\Gamma}(F_o) \ge \kappa$. Finally, since $B' = B'_{\nu,\kappa} := \max \bigl\{ \sup_{(0,1)} \tilde{\Gamma}/\Gamma, 1 \bigr\} < \infty$, we obtain the inequality
\begin{equation}
\label{eq:Power.Step3}
	\frac{n |F - F_o|}{\sqrt{n \Gamma(F_o) F_o(1 - F_o)} + \Gamma(F_o)}
	\ \le \ 2B' \bigl( 1 + \sqrt{W_n/\kappa} \bigr)^{5/2}
	\quad\text{if} \ T_{n,\nu}(F_o) \le \kappa .
\end{equation}
On the left hand side stands a function $\Delta_n = \Delta_n(\cdot,F,F_o)$, and its supremum over $\R$ equals $\Delta_n(F,F_o)$. Thus it suffices to show that for a suitable constant $B_{\nu,\kappa}$,
\[
	\Pr_F \Bigl(
		2B' \bigl( 1 + \sqrt{W_n(x)/\kappa} \bigr)^{5/2} \ge \Delta_n(x) \Bigr)
	\ \le \ B_{\nu,\kappa} \, \Delta_n(x)^{-4/5}
\]
for any $x \in \R$. Indeed, $2B' \bigl( 1 + \sqrt{W_n(x)/\kappa} \bigr)^{5/2} \ge \Delta_n(x)$ is equivalent to
\[
	W_n(x) \ \ge \ \kappa
		\max \bigl\{ 0, \Delta_n(x)^{2/5} (2B')^{-2/5} - 1 \bigr\}^2 .
\]
Since $\Ex W_n(x) \le 1$, it follows from Markov's inequality that the latter inequality occurs with probability at most
\[
	\kappa^{-1}
	\max \bigl\{ 0, \Delta_n(x)^{2/5} (2B')^{-2/5} - 1 \bigr\}^{-2}
	\ = \ \max \bigl\{ 0, B'' \Delta_n(x)^{2/5} - \kappa^{1/2} \bigr\}^{-2}
\]
with a certain constant $B'' = B''_{\nu,\kappa}$. This bound is trivial if $B'' \Delta_n(x)^{2/5} < 1 + \kappa^{1/2}$, which is equivalent to
$\Delta_n(x)^{4/5} < B_{\nu,\kappa} := (1 + \kappa^{1/2})^2 / (B'')^2$. Otherwise,
\begin{align*}
	\max \bigl\{ &
		0, B'' \Delta_n(x)^{2/5} - \kappa^{1/2} \bigr\}^{-2} \\
	&= \ \bigl( B'' - \kappa^{1/2} \Delta_n(x)^{-2/5} \bigr)^{-2}
		\Delta_n(x)^{-4/5}
		\ \le \ B \Delta_n^{-4/5} .
\end{align*}\\[-7ex]
\end{proof}


\begin{proof}[\bf Proof of Lemma~\ref{lem:DonohoJin}]
In what follows we use frequently the elementary inequalities
\begin{equation}
\label{eq:Mills.ratio}
	\frac{\phi(x)}{x+1} \le \ \Phi(-x) \ \le \ \frac{\phi(x)}{x}
	\quad\text{for} \ x > 0 ,
\end{equation}
where $\phi(x) := \Phi'(x) = \exp(- x^2/2) / \sqrt{2\pi}$. In particular, as $x \to \infty$,
\begin{align*}
	\Phi(-x) \
	&= \ \exp(- x^2/2 + O(\log x)) \quad\text{and} \\
	C(\Phi(x)) \
	&= \ \log \bigl( O(1) + \log(1/\Phi(-x)) \bigr)
		\ = \ 2 \log(x) - \log(2) + o(1) .
\end{align*}

Now consider two sequences $(x_n)_n$ and $(\mu_n)_n$ tending to $\infty$ and $F_o = \Phi$, $F_n = (1 - \eps_n) \Phi + \eps_n \Phi(\cdot - \mu_n)$. Then the inequalities \eqref{eq:Mills.ratio} imply that
\begin{align*}
	\Gamma(F_o(x_n)) F_o(x_n)(1 - F_o(x_n)) \
	&= \ (2 \log(x_n) + O(1)) \Phi(- x_n) (1 + o(1)) \\
	&= \ \exp \bigl( - x_n^2 / 2 + O(\log(x_n)) \bigr) .
\end{align*}
Moreover,
\[
	F_o(x_n) - F_n(x_n)
	\ = \ \eps_n \bigl( \Phi(\mu_n - x_n) - \Phi(- x_n) \bigr)
	\ = \ \eps_n \Phi(\mu_n - x_n) (1 + o(1)) ,
\]
because $\Phi(- x_n) \le \phi(x_n)/x_n$ while
\[
	\Phi(\mu_n - x_n) \ \ge \ \begin{cases}
		1/2
			& \text{if} \ \mu_n \ge x_n , \\
		\displaystyle
		\frac{\phi(x_n - \mu_n)}{x_n - \mu_n + 1}
		\ \ge \ \frac{\phi(x_n) \exp(\mu_n^2/2)}{x_n + 1}
			& \text{if} \ \mu_n < x_n .
	\end{cases}
\]
Consequently, $\Delta_n(F_n,\Phi) \to \infty$ if
\begin{equation}
\label{eq:critical.ratio}
	\frac{ n \eps_n \Phi(\mu_n - x_n)}
	{n^{1/2} \exp \bigl( - x_n^2/4 + O(\log(x_n)) \bigr) + O(\log(x_n))}
	\ \to \ \infty .
\end{equation}

In part~(a) with $\eps_n = n^{-\beta + o(1)}$ and $\beta \in (1/2,1)$ we imitate the arguments of \nocite{Donoho_Jin_2004}{Donoho and Jin (2004)} and consider
\[
	\mu_n \ = \ \sqrt{2 r \log(n)}
	\quad\text{and}\quad
	x_n \ = \ \sqrt{2 q \log(n)}
\]
with $0 < r < q \le 1$. Then by \eqref{eq:Mills.ratio},
\begin{align*}
	n \eps_n \Phi(\mu_n - x_n) \
	&= \ n^{1 - \beta - (\sqrt{q} - \sqrt{r})^2 + o(1)} , \\
	n^{1/2} \exp \bigl( - x_n^2/4 + O(\log(x_n)) \bigr) \
	&= \ n^{1/2 - q/2 + o(1)} , \\
	O(\log(x_n)) \
	&= \ n^{o(1)} ,
\end{align*}
so the left hand side of \eqref{eq:critical.ratio} equals
\[
	\frac{n^{1 - \beta - (\sqrt{q} - \sqrt{r})^2 + o(1)}}
		{n^{1/2 - q/2 + o(1)} + n^{o(1)}}
	\ = \ \frac{n^{1/2 - \beta + q/2 - (\sqrt{q} - \sqrt{r})^2 + o(1)}}
		{1 + n^{(q-1)/2 + o(1)}}
	\ = \ \frac{n^{1/2 - \beta + 2 \sqrt{r}\sqrt{q} - \sqrt{q}^2/2 - r + o(1)}}
		{1 + n^{(q-1)/2 + o(1)}} .
\]
The exponent in the enumerator is maximal in $q \in (r,1]$ if $\sqrt{q} = \min\{2 \sqrt{r},1\}$, i.e.\ $q = \min\{4r,1\}$, and this leads to
\[
	\begin{cases}
		1/2 - \beta + r & \text{if} \ r \le 1/4 , \\
		1 - \beta - (1 - \sqrt{r})^2 & \text{if} \ r \ge 1/4 .
	\end{cases}
\]
Thus when $\beta \in (1/2,3/4)$ we should choose $r \in (\beta - 1/2,1/4)$ and $q = 4r$. When $\beta \in [3/4,1)$ we should choose $r \in \Bigl( \bigl( 1 - \sqrt{1 - \beta} \bigr)^2, 1 \Bigr)$ and $q = 1$.

As to part~(b), we consider the more general setting that $\eps_n = n^{-\beta + o(1)}$ for some $\beta \in [1/2,3/4)$, where $\pi_n = \sqrt{n} \eps_n \to 0$. The latter constraint is trivial when $\beta > 1/2$ but relevant when $\beta = 1/2$. Now we consider
\[
	\mu_n \ := \ \sqrt{2 s \log(1/\pi_n)}
	\quad\text{and}\quad
	x_n \ := \ \sqrt{2 q \log(1/\pi_n)}
\]
with arbitrary constants $0 < s < q$. Now
\begin{align*}
	n \eps_n \Phi(\mu_n - x_n) \
	&= \ n^{1/2} \pi_n \Phi(\mu_n - x_n) \\
	&= \ n^{1/2} \pi_n^{1 + (\sqrt{q} - \sqrt{s})^2 + o(1)} , \\
	n^{1/2} \exp \bigl( - x_n^2/4 + O(\log(x_n)) \bigr) \
	&= \ n^{1/2} \pi_n^{q/2 + o(1)} , \\
	O(\log(x_n)) \
	&= \ \pi_n^{o(1)} ,
\end{align*}
so the left hand side of \eqref{eq:critical.ratio} equals
\[
	\frac{n^{1/2} \pi_n^{1 + (\sqrt{q} - \sqrt{s})^2 + o(1)}}
		{n^{1/2}\pi_n^{q/2 + o(1)} + \pi_n^{o(1)}}
	\ = \ \frac{\pi_n^{1 + \sqrt{q}^2/2 - 2 \sqrt{q}\sqrt{s} + s + o(1)}}
		{1 + n^{-1/2} \pi_n^{- q/2 + o(1)}}
	\ = \ \frac{\pi_n^{1 + \sqrt{q}^2/2 - 2 \sqrt{q}\sqrt{s} + s + o(1)}}
		{1 + n^{-1/2 + (\beta - 1/2)q/2 + o(1)}} .
\]
The exponent of $\pi_n$ becomes minimal in $q \in (s,\infty)$ if $\sqrt{q} = 2 \sqrt{s}$, i.e.\ $q = 4s$. Then we obtain
\[
	\frac{\pi_n^{1 - s + o(1)}}{1 + n^{-1/2 + (2\beta - 1) s + o(1)}}
	\ = \ \frac{\pi_n^{1 - s + o(1)}}{1 + \sqrt{n}^{(4\beta - 2) s - 1 + o(1)}} ,
\]
and this converges to $\infty$ if the exponents of $\pi_n$ and $\sqrt{n}$ are negative and non-positive, respectively. This is the case if $1 < s \le 1/(4\beta - 2)$. (Note that $4\beta - 2 < 1$ because $\beta < 3/4$.)
\end{proof}

\begin{proof}[\bf Proof of Theorem~\ref{thm:AsEfficiency}]
By symmetry it suffices to analyze the differences $b_{nj} - s_{nj}$ and $b_{nj}^{\rm BJO} - s_{nj}$ for $0 \le j < n$.

Recall the notation $b(s,\gamma)$ for the unique number $b \in (s,1)$ such that $K(s,b) = \gamma$, introduced in (K.6). There we considered only $s \in (0,1)$, but it follows from $K(0,b) = - \log(1 - b)$ that $b(0,\gamma) = 1 - \exp(-\gamma) = \gamma + o(1)$ as $\gamma \to 0$. For $0 \le j < n$, we may write
\[
	b_{nj}^{\rm BJO} \ = \ b(s_{nj}, \gamma_n^{\rm BJO})
	\quad\text{and}\quad
	b_{nj} \ \le \ b(t_{n,j+1}, \gamma_n(t_{n1}))
\]
Recall that
\[
	\gamma_n^{\rm BJ} \ = \ \frac{\log\log n}{n} (1 + o(1))
	\quad\text{and}\quad
	\gamma_n(t_{n1}) \ = \ \frac{\log\log n}{n} (1 + o(1)) .
\]
Moreover, since $K(s_{nj},\cdot)$ is convex on $[s_{nj},1)$, the numbers $b(s_{nj},\gamma)$ are concave in $\gamma \ge 0$. In particular, with $\gnt$ denoting the maximum of $\gamma_n^{\rm BJO}$ and $\gamma_n(t_{n1})$,
\[
	\frac{b_{nj}^{\rm BJO} - s_{nj}}{b(s_{nj}, \gnt) - s_{nj}}
	\ \ge \ \frac{\gamma_n^{\rm BJ}}{\gnt} \ \to \ 1
\]
uniformly in $0 \le j < n$. Hence it suffices to show that
\begin{equation}
\label{eq:ratio.le1}
	\limsup_{n \to \infty} \,
	\max_{0 \le j < n}
		\frac{b(t_{n,j+1},\gnt) - s_{nj}}
		     {b(s_{nj}, \gnt) - s_{nj}}
	\ \le \ 1 .
\end{equation}

First we consider indices $j \le j(n,1) := \lceil (\log\log n)^{1/2} \rceil$. Note that for $j = 0$,
\[
	b(s_{nj},\gnt) - s_{nj}
	\ = \ b(0,\gnt)
	\ = \ \gnt (1 + o(1)) ,
\]
and we may deduce from \eqref{eq:K.small.s} and $\lim_{y \to \infty} H^{-1}(y)/y = 1$ that
uniformly in $1 \le j \le j(n,1)$,
\begin{align*}
	b(s_{nj},\gnt) - s_{nj} \
	&\ge \ (1 + o(1)) s_{nj} H^{-1}(\gnt/s_{nj}) \\
	&= \ (1 + o(1)) \gnt \frac{H^{-1}(n \gnt/j)}{n \gnt/j} \\
	&\ge \ \gnt (1 + o(1)) .
\end{align*}
On the other hand, since
\[
	t_{n,j+1} - s_{nj} \ = \ \frac{1 - s_{nj}}{n+1} \ < \ n^{-1} \ = \ o(\gnt) ,
\]
we may conclude that uniformly in $0 \le j \le j(n,1)$,
\begin{align*}
	b(t_{n,j+1},\gnt) - s_{nj} \
	&\le \ b(t_{n,j+1},\gnt) - t_{n,j+1} + n^{-1} \\
	&\le \ t_{n,j+1} H^{-1}(\gnt/t_{n,j+1}) + n^{-1} \\
	&= \ \gnt \frac{H^{-1}(\gnt/t_{n,j+1})}{\gnt/t_{n,j+1}} + n^{-1} \\
	&\le \ \gnt (1 + o(1)) .
\end{align*}
Hence \eqref{eq:ratio.le1} holds true if we restrict $j$ to the interval $\{0,\ldots,j(n,1)\}$.

Next we consider indices $j$ between $j(n,1)$ and $j(n,2) := \lceil n \gnt^{1/3} \rceil$, i.e.\ $j(n,2)/n \to 0$ and $t_{n,j+1}/s_{nj} \to 1$ uniformly in $j(n,1) \le j \le j(n,2)$. Then it follows from \eqref{eq:K.small.s}, together with $H^{-1}(y) \ge y$ and monotonicity of $H^{-1}(\cdot)$, that uniformly in $j_{n1} \le j \le j_{n2}$,
\begin{align*}
	\frac{b(t_{n,j+1},\gnt) - s_{nj}}
	     {b(s_{nj}, \gnt) - s_{nj}} \
	&= \ (1 + o(1)) \frac{t_{n,j+1} H^{-1}(\gnt / t_{n,j+1}) + n^{-1}}
		{s_{nj} H^{-1}(\gnt / s_{nj})} \\
	&= \ (1 + o(1)) \frac{t_{n,j+1} H^{-1}(\gnt / t_{n,j+1})}
		{s_{nj} H^{-1}(\gnt / s_{nj})} \\
	&\le \ (1 + o(1)) \frac{t_{n,j+1}}{s_{nj}} \\
	&= \ 1 + o(1) .
\end{align*}
Hence \eqref{eq:ratio.le1} is satisfied with $\{j(n,1),\ldots,j(n,2)\}$ in place of $\{0,1,\ldots,n-1\}$.

Now consider $j(n,3) := n - j(n,2)$. Uniformly in $j(n,2) \le j \le j(n,3)$, the product $s_{nj}(1 - s_{nj})$ is larger than $\gnt^{1/3} (1 + o(1))$, so $\gnt /(s_{nj}(1 - s_{nj})) \to 0$. Moreover, $\logit(t_{n,j+1}) - \logit(s_{nj}) \to 0$, and it follows from \eqref{eq:K.intermediate.s} that
\begin{align*}
	\frac{b(t_{n,j+1},\gnt) - s_{nj}}
	     {b(j/n, \gnt) - s_{nj}} \
	&\le \ (1 + o(1)) \frac{\sqrt{2 \gnt t_{n,j+1}(1 - t_{n,j+1})} + n^{-1}}
		{\sqrt{2 \gnt s_{nj}(1 - s_{nj})}} \\
	&= \ 1 + o(1) + O(\gnt^{-1/3} n^{-1}) \\
	&= \ 1 + o(1)
\end{align*}
uniformly in $j(n,2) \le j \le j(n,3)$.

Finally, we may conclude from \eqref{eq:K.large.s}, concavity of $\tilde{H}^{-1}(\cdot)$ and the inequality $H^{-1}(y) \ge 1 - e^{-y}$ that
that uniformly for $j(n,3) \le j \le n-1$,
\begin{align*}
	\frac{b(t_{n,j+1},\gnt) - s_{nj}}
	     {b(j/n, \gnt) - s_{nj}} \
	&\le \ (1 + o(1)) \frac{(1 - t_{n,j+1}) \tilde{H}^{-1}(\gnt/(1 - t_{n,j+1}))
			+ (1 - s_{nj})/n}{(1 - s_{nj}) \tilde{H}^{-1}(\gnt/(1 - s_{nj}))} \\
	&\le \ (1 + o(1)) \Bigl( 1
		+ \frac{(1 - s_{nj})/n}{(1 - t_{n,j+1}) \tilde{H}^{-1}(\gnt/(1 - t_{n,j+1}))}
		\Bigr) \\
	&= \ (1 + o(1)) \bigl( 1 + O(n^{-1} \gnt^{-2/3}) \bigr) \\
	&= \ 1 + o(1) .
\end{align*}
These considerations prove \eqref{eq:ratio.le1}.

It remains to analyze the maximum of $b_{nj}^{\rm BJO} - s_{nj}$ and $b_{nj} - s_{nj}$, respectively, over $j= 0,1,\ldots,n$. Note first that by (K.5),
\[
	b_{nj}^{\rm BJO} - s_{nj}
	\ \le \ \sqrt{2 \gnt s_{nj}(1 - s_{nj})} + \gnt
	\ \le \ \sqrt{\gnt/2} + \gnt
	\ = \ (1 + o(1)) \sqrt{ \frac{\log\log n}{2n} } .
\]
On the other hand, for $j(n) := \lfloor (n+1)/2 \rfloor$, \eqref{eq:K.intermediate.s} implies that
\[
	b_{n,j(n)}^{\rm BJO} - s_{n,j(n)}
	\ \ge \ (1 + o(1)) \sqrt{ 2 \gamma_n^{\rm BJ} s_{n,j(n)}(1 - s_{n,j(n)})}
	\ = \ (1 + o(1)) \sqrt{ \frac{\log\log n}{2n} } .
\]
This proves the assertion about $\max_j (b_{nj}^{\rm BJO} - s_{nj})$. As to the new confidence bounds, note first that by (K.5),
\begin{align*}
	b_{nj} - s_{nj} \
	&\le \ b_{nj} - t_{nj} + n^{-1} \\
	&\le \ \sqrt{2 \gamma_n(t_{nj}) t_{nj}(1 - t_{nj})} + \gamma_n(t_{n1}) + n^{-1} \\
	&\le \ n^{-1/2}
		\sqrt{h(t_{nj}) + 2 t_{nj}(1 - t_{nj}) \tilde{\kappa}_{n,\nu,\alpha}}
		+ O(n^{-1} \log\log n) ,
\end{align*}
where $h(t) := 2t(1-t) \bigl( C(t) + \nu D(t) \bigr)$ is a continuous function on $(0,1)$ with limit $0$ as $t \to \{0,1\}$. Consequently, $\sup_{(0,1)} h$ is finite and
\[
	\max_{j=0,1,\ldots,n} \, (b_{nj} - s_{nj})
	\ \le \ n^{-1/2}
		\sqrt{\sup_{(0,1)} h + \tilde{\kappa}_{n,\nu,\alpha}/2} + O(n^{-1} \log\log n)
	\ = \ O(n^{-1/2}) .
\]\\[-5ex]
\end{proof}


\paragraph{Acknowledgements.}
%
We are grateful to Guenther Walther for stimulating talks about likelihood ratio tests in nonparametric settings. In particular, \nocite{Rivera_Walther_2013}{Rivera and Walther (2013)} inspired us to reformulate the Law of the Iterated Logarithm in terms of processes with subexponential tails. Many thanks go to Rudy Beran for drawing our attention to \nocite{Bahadur_Savage_1956}{Bahadur and Savage (1956)}.


%===========
% References 
%===========

%\bibliography{NonGaussLIL}
%\bibliographystyle{siam}

\begin{thebibliography}{10}

\bibitem{Aldor-Noiman_etal_2013}
{\sc S.~Aldor-Noiman, L.~D. Brown, A.~Buja, W.~Rolke, and R.~A. Stine}, {\em
  The power to see: A new graphical test of normality}, Amer. Statist., 67
  (2013), pp.~249--260.

\bibitem{Bahadur_Savage_1956}
{\sc R.~R. Bahadur and L.~J. Savage}, {\em The nonexistence of certain
  statistical procedures in nonparametric problems}, Ann. Math. Statist., 27
  (1956), pp.~1115--1122.

\bibitem{Berk_Jones_1979}
{\sc R.~H. Berk and D.~H. Jones}, {\em Goodness-of-fit test statistics that
  dominate the {K}olmogorov statistics}, Z. Wahrsch. Verw. Gebiete, 47 (1979),
  pp.~47--59.

\bibitem{Donoho_Jin_2004}
{\sc D.~Donoho and J.~Jin}, {\em Higher criticism for detecting sparse
  heterogeneous mixtures}, Ann. Statist., 32 (2004), pp.~962--994.

\bibitem{Duembgen_1998}
{\sc L.~D{\"u}mbgen}, {\em New goodness-of-fit tests and their application to
  nonparametric confidence sets}, Ann. Statist., 26 (1998), pp.~288--314.

\bibitem{Eiger_etal_2013}
{\sc A.~M. Eiger, B.~Nadler, and C.~Spiegelman}, {\em The calibrated
  kolmogorov-smirnov test}, tech. rep., Department of Computer Science,
  Weizmann Institute of Science; Department of Statistics, Texas A\&M
  University, 2013. (http://arxiv.org/abs/1311.3190)

\bibitem{Erdos_1942}
{\sc P.~Erd{\"o}s}, {\em On the law of the iterated logarithm}, Ann. of Math.
  (2), 43 (1942), pp.~419--436.

\bibitem{Hoeffding_1963}
{\sc W.~Hoeffding}, {\em Probability inequalities for sums of bounded random
  variables}, J. Amer. Statist. Assoc., 58 (1963), pp.~13--30.

\bibitem{Ito_McKean_1974}
{\sc K.~It{\^o} and H.~P. McKean, Jr.}, {\em Diffusion processes and their
  sample paths}, Springer-Verlag, Berlin, 1974.
\newblock Second printing, corrected, Die Grundlehren der mathematischen
  Wissenschaften, Band 125.

\bibitem{Jager_Wellner_2007}
{\sc L.~Jager and J.~A. Wellner}, {\em Goodness-of-fit tests via
  phi-divergences}, Ann. Statist., 35 (2007), pp.~2018--2053.

\bibitem{Kiefer_1973}
{\sc J.~Kiefer}, {\em Iterated logarithm analogues for sample quantiles when
  $p_n \downarrow 0$}, in Proceedings of the 6th Berkeley Symposium on
  Mathematical Statistics and Probability, vol.~1, University of California,
  1973, pp.~227--244.

\bibitem{LeCam_Yang_2000}
{\sc L.~Le~Cam and G.~L. Yang}, {\em Asymptotics in statistics -- Some basic
  concepts}, Springer Series in Statistics, Springer-Verlag, New York,
  second~ed., 2000.

\bibitem{Mason_Schuenemeyer_1983}
{\sc D.~M. Mason and J.~H. Schuenemeyer}, {\em A modified
  {K}olmogorov-{S}mirnov test sensitive to tail alternatives}, Ann. Statist.,
  11 (1983), pp.~933--946.

\bibitem{Owen_1995}
{\sc A.~B. Owen}, {\em Nonparametric likelihood confidence bands for a
  distribution function}, J. Amer. Statist. Assoc., 90 (1995), pp.~516--521.

\bibitem{Rivera_Walther_2013}
{\sc C.~Rivera and G.~Walther}, {\em Optimal detection of a jump in the
  intensity of a {P}oisson process or in a density with likelihood ratio
  statistics}, Scand. J. Statist., 40 (2013), pp.~752--769.

\bibitem{Shorack_Wellner_1986}
{\sc G.~R. Shorack and J.~A. Wellner}, {\em Empirical processes with
  applications to statistics}, Wiley Series in Probability and Mathematical
  Statistics: Probability and Mathematical Statistics, John Wiley \& Sons Inc.,
  New York, 1986.

\end{thebibliography}


\newpage

%===============================
\section{Supplementary material}
\label{sec:Supplements}
%===============================

%---------------------------------------------------
\subsection{A remark on moment-generating functions}
%---------------------------------------------------

Somewhat hidden in our proofs of Lemmas~\ref{lem:UniformEP.1} and \ref{lem:UniformEP.2} is a basic fact about moment generating functions which is stated in a slightly different form by \nocite{Rivera_Walther_2013}{Rivera and Walther (2013)} and possibly of independent interest: Suppose that $X$ is a real-valued random variable with mean $\mu$ and moment-generating function $m_X$,
\[
	m_X(t) \ := \ \Ex \exp(tX) .
\]
We assume that $m_X < \infty$ in a neighborhood of zero. In particular, all moments of $X$ are finite. A standard application of Markov's inequality yields
\begin{align*}
	\Pr(X \ge x) \
	&\le \ \exp \bigl( - K(x) \bigr)
		\quad\text{for all} \ x \ge \mu , \\
	\Pr(X \le x) \
	&\le \ \exp \bigl( - K(x) \bigr)
		\quad\text{for all} \ x \le \mu ,
\end{align*}
where
\[
	K(x)
	\ := \ \sup_{t \in \R} \bigl( tx - \log m_X(t) \bigr)
	\ \begin{cases}
		\displaystyle
		= \ \sup_{t \ge 0} \bigl( tx - \log m_X(t) \bigr)
		& \text{if} \ x \ge \mu , \\
		\displaystyle
		= \ \sup_{t \le 0} \bigl( tx - \log m_X(t) \bigr)
		& \text{if} \ x \le \mu .
	\end{cases}
\]
The latter facts follow from the fact that $\log m_X$ is a convex function with derivative $\mu$ at $0$. Note also that $K : \R \to [0,\infty]$ is a convex, lower semi-continuous function with $K(\mu) = 0$ and $\lim_{|x| \to \infty} K(x) = \infty$. From this one can derive the following inequalities:

\begin{Lemma}
\label{lem:K}
For arbitrary $\eta > 0$,
\[
	\left.\begin{array}{c}
	\Pr(K(X) \ge \eta \ \text{and} \ X \ge \mu) \\
	\Pr(K(X) \ge \eta \ \text{and} \ X \le \mu)
	\end{array}\!\!\right\}
	\ \le \ \exp(-\eta) ,
\]
and thus
\[
	\Pr(K(X) \ge \eta)
	\ \le \ 2 \exp(- \eta) .
\]
\end{Lemma}

\begin{proof}[\bf Proof of Lemma~\ref{lem:K}]
By symmetry, it suffices to show that $\Pr(K(X) \ge \eta \ \text{and} \ X \ge \mu)$ is not greater than $\exp(-\eta)$. Since $K : [\mu,\infty) \to [0,\infty]$ is convex and lower semi-continuous with $K(\mu) = 0$ and $\lim_{x \to \infty} K(x) = \infty$, the point
\[
	x_\eta \ := \ \max \bigl\{ x \ge \mu : K(x) \le \eta \bigr\}
\]
is well-defined. When $K(x_\eta) = \eta$, convexity of $K$ and 
$K(\mu) = 0$ imply that $K(x) < \eta$ for all $x \in [\mu,x_\eta)$. Hence
\[
	\Pr(K(X) \ge \eta \ \text{and} \ X \ge \mu)
	\ = \ \Pr(X \ge x_\eta)
	\ \le \ \exp(- K(x_\eta)) \ = \ \exp(-\eta) .
\]
When $K(x_\eta) < \eta$, we may conclude from monotonicity and lower semicontinuity of $K$ that $K(x) = \infty$ for all $x > x_\eta$. But this implies that
\[
	\Pr(K(X) \ge \eta \ \text{and} \ X \ge \mu)
	\ = \ \Pr(X > x_\eta)
	\ = \ \sup_{x > x_\eta} \Pr(X \ge x) \ = \ 0 .
\]\\[-7ex]
\end{proof}


%-----------------------------------------------------------
\subsection{Exponential inequalities for beta distributions}
%-----------------------------------------------------------

Let $s,t \in (0,1)$, and let $Y \sim \mathrm{Beta}(mt, m(1-t))$ for some $m > 0$. Then
\begin{align*}
	\Pr(Y \le s) \
	&\le \ \inf_{\lambda \le 0} \, \Ex \exp(\lambda Y - \lambda s)
		\ \le \ \exp( - m K(t,s))
		\quad\text{if} \ s \le t , \\
	\Pr(Y \ge s) \
	&\le \ \inf_{\lambda \ge 0} \, \Ex \exp(\lambda Y - \lambda s)
		\ \le \ \exp( - m K(t,s))
		\quad\text{if} \ s \ge t .
\end{align*}

\begin{proof}[\bf Proof]
%
In case of $s \ge t$, Markov's inequality yields that
\[
	\Pr(Y \ge s)
	\ = \ \inf_{\lambda \ge 0} \, \Pr(\lambda Y - \lambda s \ge 0)
	\ \le \ \inf_{\lambda \ge 0} \, \Ex \exp(\lambda Y - \lambda s)
	\ = \ \inf_{\lambda \ge 0} \, \Ex \exp(\lambda m Y - \lambda m s) .
\]
The latter step is trivial but convenient for the next consideration: We may write $Y = G/(G + G')$ with independent random variables $G \sim \mathrm{Gamma}(mt)$ and $G' \sim \mathrm{Gamma}(m(1-t))$. Moreover, it is well-known that $Y$ and $G+G'$ are stochastically independent with $\Ex(G + G') = m$. Consequently, by Jensen's inequality and Fubini's theorem,
\begin{align*}
	\Ex \exp(\lambda m Y - \lambda m s) \
	&= \ \Ex \exp \bigl( \lambda \Ex \bigl( G - s (G + G') \,\big|\, Y \bigr) \bigr) \\
	&= \ \Ex \exp \bigl( \lambda \Ex \bigl( (1 - s) G - \lambda s G' \,\big|\, Y \bigr) \bigr) \\
	&\le \ \Ex \Ex \bigl( \exp(\lambda(1 - s)G - \lambda s G') \,\big|\, Y \bigr) \\
	&= \ \Ex \exp(\lambda(1 - s)G - \lambda s G') \\
	&= \ \Ex \exp(\lambda(1 - s)G) \Ex \exp(- \lambda s G') \\
	&= \ (1 - \lambda(1 - s))^{-mt} (1 + st)^{-m(1-t)} \\
	&= \ \exp \Bigl( - m 
		\bigl( t \log(1 - \lambda(1-s))
			+ (1 - t) \log(1 + \lambda s) \bigr) \Bigr)
\end{align*}
for $0 \le \lambda < 1/(1-s)$. (For $\lambda \ge 1/(1-s)$ the expectation of $\exp(\lambda(1-s)G)$ would be infinite.) Elementary calculations show that $t \log(1 - \lambda(1-s)) + (1 - t) \log(1 + \lambda s)$ is maximal for $\lambda = (s - t)/(s(1-s)) \in [0,1/(1-s))$, and this yields the bound
\[
	\inf_{\lambda \ge 0} \, \Ex \exp(\lambda Y - \lambda s)
	\ \le \ \exp( - m K(t,s)) .
\]
In case of $s \le t$, the previous result may be applied to $1 - Y \sim \mathrm{Beta}(m(1-t),mt)$:
\begin{align*}
	\Pr(Y \le s)
	\ = \ \Pr(1 - Y \ge 1 - s
	&) \ \le \ \inf_{\lambda \ge 0} \, \Ex \exp( \lambda (1 - Y) - \lambda (1 - s) \bigr) \\
	&\begin{cases}
		\displaystyle
		= \ \inf_{\lambda \le 0} \, \Ex \exp( \lambda Y - \lambda s) , \\
		\le \ \exp(- m K(1-t,1-s)) \ = \ \exp(- m K(t,s)) .
	\end{cases}
\end{align*}\\[-7ex]
\end{proof}


%---------------------------------------------------
\subsection{Further details about Gaussian mixtures}
%---------------------------------------------------

As in Section~\ref{sec:GoF} we consider the standard Gaussian distribution function $\Phi$ and the alternative distribution functions
\[
	F_n \ := \ (1 - \eps_n) \Phi + \eps_n \Phi(\cdot - \mu_n) ,
\]
where $\eps_n \downarrow 0$ and $\mu_n \to \infty$. Optimal tests of $H_0 : F \equiv \Phi$ versus $H_1 : F \equiv F_n$ reject for large values of the log-likelihood ratio statistic
\[
	\sum_{i=1}^n \log \frac{dF_n}{d\Phi}(X_i)
	\ = \ \sum_{i=1}^n \log(1 + V_n(X_i))
\]
with
\[
	V_n(x) \ = \ \eps_n \bigl( \exp(\mu_n x - \mu_n^2/2) - 1 \bigr) .
\]
If $(\mu_n)_n$ is chosen such that
\begin{equation}
\label{eq:TrivialPower}
	\sum_{i=1}^n \log(1 + V_n(X_i))
	\ \to_p \ 0
	\quad\text{when} \ F \equiv \Phi ,
\end{equation}
then for any sequence of tests $\phi_n : \R^n \to [0,1]$,
\[
	\limsup_{n \to \infty} \bigl| \Ex_{F_n} \phi_n(X_1,\ldots,X_n)
		- \Ex_{\Phi} \phi_n(X_1,\ldots,X_n) \bigr|
	\ = \ 0 ;
\]
see \nocite{LeCam_Yang_2000}{LeCam and Yang (2000)}.

\begin{Lemma}
\label{lem:TrivialPower}
Suppose that $\eps_n = n^{- \beta + o(1)}$ for some $\beta \in [1/2,3/4)$ and $\pi_n = n^{1/2}\eps_n \to 0$. Then \eqref{eq:TrivialPower} is satisfied if $\mu_n = \sqrt{2 s \log(1/\pi_n)}$ for some fixed $s \in (0,1)$.
\end{Lemma}

\begin{proof}[\bf Proof of Lemma~\ref{lem:TrivialPower}]
Note that for $v > -1$,
\[
	\log(1 + v) \ = \ v - \frac{v^2}{2(1 + \xi(v))}
\]
with $\xi(v) \ge \min\{0,v\}$. Consequently, since $V_n > - \eps_n$,
\[
	\sum_{i=1}^n V_n(X_i)
		- \frac{1}{2(1 - \eps_n)} \sum_{i=1}^n V_n(X_i)^2
	\ \le \ \sum_{i=1}^n \log(1 + V_n(X_i))
	\ \le \ \sum_{i=1}^n V_n(X_i) .
\]
But it follows from $\Ex_{\Phi}(V_n(X_1)) = 0$ that
\begin{align*}
	\Ex_{\Phi} \biggl(
		\Bigl( \sum_{i=1}^n V_n(X_i) \Bigr)^2 \biggr) \
	&= \ n \Var_{\Phi}(V_n(X_1)) \\
	&= \ n \eps_n^2
		\bigl( \Ex_{\Phi} \exp(2 \mu_n X_1 - \mu_n^2) - 1 \bigr) \\
	&= \ \pi_n^2 (\exp(\mu_n^2) - 1) \\
	&= \ \pi_n^{2(1 - s)} - \pi_n^2 \\
	&\to \ 0
\end{align*}
because $s < 1$, and
\[
	\Ex_{\Phi} \Bigl( \frac{1}{2(1 - \eps_n)}
		\sum_{i=1}^n V_n(X_i)^2 \Bigr)
	\ = \ \frac{n \Var_{\Phi}(V_n(X_1))}{2(1 - \eps_n)}
	\ \to \ 0 .
\]\\[-7ex]
\end{proof}



%-----------------------------------------------
\subsection{Bahadur and Savage (1956) revisited}
%-----------------------------------------------

Let $(L_n,U_n)$ be a $(1-\alpha)$-confidence band for $F \in \FF$ with a given class $\FF$ of distribution functions. That means $L_n = L_n(\cdot,\bs{X}_n)$ and $U_n = U_n(\cdot,\bs{X}_n)$ are non-decreasing functions on the real line depending on the data vector $\bs{X}_n = (X_i)_{i=1}^n$ such that
\[
	\Pr_F \bigl( L_n \le F \le U_n \ \text{on} \ \R \bigr)
	\ \ge \ 1 - \alpha
	\quad\text{for any} \ F \in \FF .
\]
We assume that $\FF$ is convex and satisfies $F(\cdot - \mu) \in \FF$ for any $F \in \FF$ and $\mu \in \R$. This is true if, for instance, $\FF$ corresponds to all mixtures of Gaussian distributions with variance one. Then Theorem~2 of \nocite{Bahadur_Savage_1956}{Bahadur and Savage (1956)} may be modified as follows:

\begin{Theorem}
\label{thm:BahadurSavage}
Let $(L_n,U_n)$ be a $(1-\alpha)$-confidence band for $F \in \FF$. For any $\eps \in (0,1)$,
\begin{align*}
	\Pr_F \Bigl( \inf_{x \in \R} U_n(x) < \eps \Bigr) \
	&\le \ (1 - \eps)^{-n} \alpha , \\
	\Pr_F \Bigl( \sup_{x \in \R} L_n(x) > 1 - \eps \Bigr) \
	&\le \ (1 - \eps)^{-n} \alpha .
\end{align*}
\end{Theorem} 

Setting $\eps = c/n$ for some fixed $c > 0$ reveals that $\inf_{x \in \R} U_n(x) < c/n$ or $\sup_{x \in \R} L_n(x) \le 1 - c/n$ with probability at most $(1 - c/n)^{-n} \alpha = e^c \alpha + o(1)$, respectively.

\begin{proof}[\bf Proof of Theorem~\ref{thm:BahadurSavage}]
By symmetry, it suffices to prove the claim about $U_n$. By monotonicity of $U_n$,
\[
	\Pr_F \Bigl( \inf_{x \in \R} U_n(x) < \eps \Bigr)
	\ = \ \sup_{x \in \R, \delta \in (0,\eps)} \Pr_F(U_n(x) < \delta) .
\]
Hence it suffices to show that $\Pr_F(U_n(x) < \delta) \le (1 - \eps)^{-n} \alpha$ for any single point $x \in \R$ and $\delta \in (0,\eps)$. To this end consider $F_{\eps,\mu} := (1 - \eps) F + \eps F(\cdot - \mu)$ for our given $\eps$ and some $\mu \in \R$. Note that $\LL_{F_{\eps,\mu}}(\bs{X}_n)$ describes the distribution of
\[
	\tilde{\bs{X}}_n \ := \ \bigl( Y_i + \xi_i \mu \bigr)_{i=1}^n
\]
with $2n$ independent random variables $\xi_1, \xi_2, \ldots, \xi_n \sim \mathrm{Bin}(1,\eps)$ and $Y_1, Y_2, \ldots, Y_n \sim F$. In particular, for any event $A_n \subset \R^n$,
\begin{align*}
	\Pr_{F_{\eps,\mu}}(\bs{X}_n \in A_n) \
	&= \ \Pr(\tilde{\bs{X}}_n \in A_n) \\
	&\ge \ \Pr \bigl( \tilde{\bs{X}}_n \in A_n,
		\xi_1 = \xi_2 = \cdots = \xi_n = 0 \bigr) \\
	&= \ (1 - \eps)^n \Pr_F(\bs{X}_n \in A_n) .
\end{align*}
Consequently, since $F_{\eps,\mu} \in \FF$, too, we may conclude from
\[
	\Pr_{F_{\eps,\mu}}
		\bigl( L_n \le F_{\eps,\mu} \le U_n \ \text{on} \ \R \bigr)
	\ \ge \ 1 - \alpha
\]
that
\begin{align*}
	\alpha \
	&\ge \ \Pr_{F_{\eps,\mu}} \bigl( U_n(x) < F_{\eps,\mu}(x) \bigr) \\
	&\ge \ (1 - \eps)^n \Pr_F \bigl( U_n(x) < (1 - \eps) F(x) + \eps F(x - \mu) \bigr) \\
	&\ge \ (1 - \eps)^n \Pr_F \bigl( U_n(x) < \eps F(x - \mu) \bigr) .
\end{align*}
But for sufficiently small (negative) $\mu$, the value $\eps F(x - \mu)$ is greater than or equal to $\delta$. Then we may conclude that $\alpha \ge (1 - \eps)^n \Pr_F(U_n(x) < \delta)$.
\end{proof}

\end{document}
1402.2918.extracted_bib
{Aldor-Noiman_etal_2013 {\sc S.~Aldor-Noiman, L.~D. Brown, A.~Buja, W.~Rolke, and R.~A. Stine, {\em The power to see: A new graphical test of normality, Amer. Statist., 67 (2013), pp.~249--260.
1402.2918.extracted_bib
{Bahadur_Savage_1956 {\sc R.~R. Bahadur and L.~J. Savage, {\em The nonexistence of certain statistical procedures in nonparametric problems, Ann. Math. Statist., 27 (1956), pp.~1115--1122.
1402.2918.extracted_bib
{Berk_Jones_1979 {\sc R.~H. Berk and D.~H. Jones, {\em Goodness-of-fit test statistics that dominate the {Kolmogorov statistics, Z. Wahrsch. Verw. Gebiete, 47 (1979), pp.~47--59.
1402.2918.extracted_bib
{Donoho_Jin_2004 {\sc D.~Donoho and J.~Jin, {\em Higher criticism for detecting sparse heterogeneous mixtures, Ann. Statist., 32 (2004), pp.~962--994.
1402.2918.extracted_bib
{Duembgen_1998 {\sc L.~D{\"umbgen, {\em New goodness-of-fit tests and their application to nonparametric confidence sets, Ann. Statist., 26 (1998), pp.~288--314.
1402.2918.extracted_bib
{Eiger_etal_2013 {\sc A.~M. Eiger, B.~Nadler, and C.~Spiegelman, {\em The calibrated kolmogorov-smirnov test, tech. rep., Department of Computer Science, Weizmann Institute of Science; Department of Statistics, Texas A\&M University, 2013. (http://arxiv.org/abs/1311.3190)
1402.2918.extracted_bib
{Erdos_1942 {\sc P.~Erd{\"os, {\em On the law of the iterated logarithm, Ann. of Math. (2), 43 (1942), pp.~419--436.
1402.2918.extracted_bib
{Hoeffding_1963 {\sc W.~Hoeffding, {\em Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58 (1963), pp.~13--30.
1402.2918.extracted_bib
{Ito_McKean_1974 {\sc K.~It{\^o and H.~P. McKean, Jr., {\em Diffusion processes and their sample paths, Springer-Verlag, Berlin, 1974. \newblock Second printing, corrected, Die Grundlehren der mathematischen Wissenschaften, Band 125.
1402.2918.extracted_bib
{Jager_Wellner_2007 {\sc L.~Jager and J.~A. Wellner, {\em Goodness-of-fit tests via phi-divergences, Ann. Statist., 35 (2007), pp.~2018--2053.
1402.2918.extracted_bib
{Kiefer_1973 {\sc J.~Kiefer, {\em Iterated logarithm analogues for sample quantiles when $p_n \downarrow 0$, in Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, vol.~1, University of California, 1973, pp.~227--244.
1402.2918.extracted_bib
{LeCam_Yang_2000 {\sc L.~Le~Cam and G.~L. Yang, {\em Asymptotics in statistics -- Some basic concepts, Springer Series in Statistics, Springer-Verlag, New York, second~ed., 2000.
1402.2918.extracted_bib
{Mason_Schuenemeyer_1983 {\sc D.~M. Mason and J.~H. Schuenemeyer, {\em A modified {Kolmogorov-{Smirnov test sensitive to tail alternatives, Ann. Statist., 11 (1983), pp.~933--946.
1402.2918.extracted_bib
{Owen_1995 {\sc A.~B. Owen, {\em Nonparametric likelihood confidence bands for a distribution function, J. Amer. Statist. Assoc., 90 (1995), pp.~516--521.
1402.2918.extracted_bib
{Rivera_Walther_2013 {\sc C.~Rivera and G.~Walther, {\em Optimal detection of a jump in the intensity of a {Poisson process or in a density with likelihood ratio statistics, Scand. J. Statist., 40 (2013), pp.~752--769.
1402.2918.extracted_bib
{Shorack_Wellner_1986 {\sc G.~R. Shorack and J.~A. Wellner, {\em Empirical processes with applications to statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley \& Sons Inc., New York, 1986.