The following problem was considered in
Cohen and Kontorovich, "Local Glivenko-Cantelli",
<https://arxiv.org/abs/2209.04054>,
to appear in COLT 2023 (henceforth, CK'23).


Let $Y\_j$, $j\in\mathbb{N}$
be a sequence of independent
$\operatorname{Binom}(n,p\_j)$
random variables,
where $n\in\mathbb{N}$
and $1/2\ge p\_j\downarrow 0$
as $j\to\infty$.
Since $\mathbb{E} Y\_j=np\_j$,
let us consider
the centered, normalized process
$\bar Y\_j:=
n{^{-1}} Y\_j-p\_j
$.


Finally, we define
$\Delta\_n$ to be the
expected uniform absolute deviation:
$$
\Delta\_n :=
\mathbb{E}\sup\_{j\in\mathbb{N}}|\bar Y\_j|.
$$


CK'23
gave an exact
characterization
of the $p\in[0,{\frac12}]^{\mathbb{N}}\_{\downarrow0}$
(that is, $p\in[0,{\frac12}]^{\mathbb{N}}$
with $p\_j\downarrow 0$)
for which $\Delta\_n\to0$
as $n\to\infty$.
Namely, they defined the functional
$$
T(p) := \sup\_{j\in\mathbb{N}}\frac{\log (j+1)}{\log(1/p\_j)}
.
$$
and showed that
$\Delta\_n\to0$
iff
$T(p)<\infty$.
They also gave the finite-sample
bound
$$
\Delta\_n
\le
c\left(
\sqrt{\frac{S(p)}{n}}
+\frac{T(p)\log n}{n}
\right),
\qquad n\ge \mathrm{e}^3
\qquad(\*)
$$
where $c>0$ is an absolute constant
and
$$
S(p) := \sup\_{j\in\mathbb{N}}p\_j\log (j+1).
$$
We conjecture that the $\log n$
factor in $(\*)$ is superfluous. This conjecture is motivated by the
asymptotic
lower bounds
$$
\liminf\_{n\to\infty}
\sqrt n
\Delta\_n
\ge
c\sqrt{S(p)},
$$
$$
\liminf\_{n\to\infty}
n
\Delta\_n
\ge
cT(p)
,
$$
where $c>0$ is a universal constant.
This shows that beyond the conjecturally
removable $\log n$ factor,
$(\*)$ is tight up to constants.


**Open problem.** Is the
$\log n$ factor in
$(\*)$
necessary, or can it be removed?


**UPDATE** 21-Jul-2023.
This was presented as an open problem at COLT'23:
<https://proceedings.mlr.press/v195/cohen23b.html>


Within days of the announcement and independently of each other,
Moïse Blanchard, Václav Voráček, and Jaouad Mourtada
obtained essentially the same substantial improvement.
Formally, their results show that there is an absolute $c\_1>0$ such that for any constant $c>0$ there is an $n\_0$ such that for all $n>n\_0$ there is a sequence
$p\in[0,{\frac12}]^{\mathbb{N}}\_{\downarrow0}$
for which
$$
\Delta\_n(p) > c\sqrt{\frac{S(p)}{n}}
+
c\_1\frac{T(p)\log n}{n\log\log n}.
\qquad(\*\*)
$$


This certainly dashes any hope of removing the $\log n$ factor in $(\*)$ entirely; the best one could aim for is replacing it by
$\log(n)/\log\log(n)$.


This raises a number of fascinating questions. First: Is there a *fixed* sequence $p\_j$ (i.e., independent of $n$) for which
$$
\liminf\_{n\to\infty}
\frac{n\log\log n}{\log n}
\Delta\_n
\ge
cT(p)
,
$$
where $c>0$ is a universal constant?


Second: Is there a functional $\tilde T(p)$ and a monotonically increasing $\varphi:\mathbb{N}\to \mathbb{N}$ such that
$$
c\tilde T(p)
\le
\liminf\_{n\to\infty}
\varphi(n)
\Delta\_n
\le
\limsup\_{n\to\infty}
\varphi(n)
\Delta\_n
\le
c'\tilde T(p)
$$
for absolute constants $c,c'>0$?


**UPDATE** 25-Jul-2023. We congratulate
Moïse Blanchard on resolving the gap entirely, by
exhibiting a $p$ for which
$$
\Delta\_n(p) > c\sqrt{\frac{S(p)}{n}}
+
c\_1\frac{T(p)\log n}{n}
$$
(all constants and quantifiers as in $(\*\*)$).


Additionally, it has been pointed out to us by
Moïse, Václav, Jaouad
that the
"lower bound"
$
\liminf\_{n\to\infty}
n
\Delta\_n
\ge
cT(p)
$
is trivial, since for nontrivial $p$,
$\Delta\_n$ will be at least $1/\sqrt n$ for $n$ large enough, meaning that
$\liminf\_{n\to\infty}
n
\Delta\_n
=\infty$.
We have corrected this with the following non-trivial lower bound:
Theorem (Cohen, K., 2023):
There is an absolute constant $c>0$ such that
$$
\Delta\_n(p) \ge c\left(1\wedge\frac{T}{n}\right),
$$
for all $n\in\mathbb{N}$ and
$p\in[0,{\frac12}]^{\mathbb{N}}\_{\downarrow0}$.


Thus, currently, the two open questions are:


1. Is there a *fixed* sequence $p\_j$ (i.e., independent of $n$) for which
$$
\Delta\_n(p) \ge c\left(1\wedge\frac{T\log n}{n}\right),
$$
for some $c>0$?
2. Is there a functional $\tilde T(p)$ and a monotonically increasing $\varphi:\mathbb{N}\to \mathbb{N}$ such that
$$
\Delta\_n
\le
c\left(
\sqrt{\frac{S(p)}{n}}
+\frac{\tilde T(p)}{\varphi(n)}
\right)
$$
and
$$
\Delta\_n(p) \ge c'\left(1\wedge\frac{\tilde T(p)}{\varphi(n)}\right),
$$
for absolute constants $c,c'>0$
and all $n\in\mathbb{N}$,
$p\in[0,{\frac12}]^{\mathbb{N}}\_{\downarrow0}$?



Open problem: $\log n$ factor in Binomial empirical process
See the preprint by
Moïse Blanchard and Václav Voráček, titled "Tight Bounds for Local Glivenko-Cantelli", available here:
<https://arxiv.org/abs/2308.01896>
.


It clearly explains their construction.


