∎

11institutetext: PoreLab, Department of Physics, Norwegian University of
Science and Technology, NO–7491 Trondheim, Norway.
11email<EMAIL_ADDRESS>

# Linearity of the co-moving velocity

Alex Hansen

(Received: date / Accepted: date)

###### Abstract

The co-moving velocity is a new variable in the description of immiscible two-
phase flow in porous media. It is the saturation-weighted derivatives of the
seepage velocities of the two immiscible fluids with respect to saturation. I
show that it is linear in the derivative of the average seepage velocity with
respect to the saturation. This is in accordance with recent measurements. Two
parameters are needed to describe it. In terms of relative permeability
theory, this linear relation leads to a differential equation relating the two
relative permeabilities describing the flow. I present this equation together
with a solution.

††journal: Transport in Porous Media

##  1 Introduction

The description of immiscible and incompressible two-phase flow in porous
media at scales large enough so that the porous medium may be seen as a
continuum has been a challenge for a long time. In 1936 Wyckoff and Botset
wyckoff1936flow  proposed a generalization of the Darcy equation
darcy1856fontaines  by splitting it into two independent Darcy type equations,
one for each fluid, based on the idea that what each fluid will experience ,is
the matrix and the other fluid together as the effective porous matrix. This
reduces the effective permeability for each fluid by a factor, the relative
permeability. It is then assumed that the two relative permeabilities depend
only on the saturation. If I assume steady-state flow and that there are no
continuum-scale gradients in the saturation, the theory is complete as
described. This theory has a dominating position in all practical
calculations.

The assumption that the relative permeabilies only depend on the saturation is
the weak part of the theory. It is correct in a window of capillary number.
However, outside this window, the pressure gradient enters and the theory
loses its predictive power. For example Tallakstad et al. found that the
average flow rate through a model porous medium over a rather wide range of
capillary numbers depends on the pressure drop across it to a power around two
tallakstad2009steady ; tallakstad2009steady2 . In their experiment, they
controlled the flow rates of the two immiscible fluids entering the porous
medium and could then measure the pressure drop and the saturation. But how to
construct two generalized relative permeabilities from this information?

Hansen et al. hansen2018relations ; feder2022physics  recognized that the
problem is that knowing the flow velocity of each fluid makes it possible to
find the combined average flow velocity, but the opposite is not. The combined
average flow velocity must be accompanied by a second independent velocity in
order to calculate the two separate fluid velocities. This would be the co-
moving velocity. Roy et al. roy2022co  measured the co-moving velocity from
relative permeability data from multiple sources and calculated it in a
dynamic pore network model finding that it would produce a straight line when
plotted against the derivative of the average flow velocity with respect to
the saturation, necessitating only two parameters, one setting the scale and
one determining the slope. In the co-moving velocity plots generated from the
relative permeability data, they observed that both parameters were constants.
However, when the dynamic pore network model went outside the limits of
relative permeability theory and into the non-linear flow regime, linearity of
the co-moving velocity was still in place, but the two parameters would now
depend on the pressure gradient. Hansen et al. hansen2023statistical
constructed a statistical mechanics for immiscible two-phase flow in porous
media under steady-state conditions that would explain why the derivative of
the average flow velocity with respect to the saturation would be the natural
variable for the co-moving velocity. Pedersen and Hansen
pedersen2023parameterizations  then presented an interpretation of the co-
moving velocity by exploring the geometry of the space of variables describing
the flow.

The last paper so far addressing the co-moving velocity is Alzubaidi et al.
alzubaidi2023impact  who measured it for a wide range of contact angles using
lattice Boltzmann computations on the reconstructed pore spaces of North Sea
Sandstone and Bentheimer Sandstone. In addition, they used experimental flow
data on Bentheimer sandstone zou2018experimental . Their surprising conclusion
was that the parameters characterizing the co-moving velocity were insensitive
to the contact angle.

The aim of the present note is to prove that the co-moving velocity is linear
when plotted against the derivative of the average flow velocity with respect
to the saturation.

In the next section, I review the central concepts surrounding the co-moving
velocity. In Section 3 I present the derivation of the linearity. Section 4 I
explore the consequences of this linearity for relative permeability theory.
In particular, I present an equation combining the two relative
permeabilities. Finally, I conclude in Section 5.

##  2 Central concepts

I assume a porous medium sample having an area $A$ transversal to the flow
direction and a porosity $\pi$. The sample is uniform. I inject under steady
state conditions a volumetric flow rate $Q_{w}$ of the more wetting fluid and
a volumetric flow rate $Q_{n}$ of the less wetting fluid. I assume the fluids
to be well mixed in the sample so that there are no sample-scale gradients in
the saturation. The total average flow rate is

$Q_{p}=Q_{w}+Q_{n}\;.$ (1)

The sub-area of the transversal area $A$ that cuts through the pores is
$A_{p}=\phi A$. The sub-area of the pore area $A$ that cuts through the more
wetting fluid is $A_{w}=S_{w}A_{p}$ and the sub-area that cuts through the
less wetting fluid is $A_{n}=S_{n}A_{p}$.

I can then define the seepage velocities. The seepage velocity of the more
wetting fluid is

$v_{w}=\frac{Q_{w}}{A_{w}}\;,$ (2)

and the less wetting fluid,

$v_{w}=\frac{Q_{n}}{A_{n}}\;.$ (3)

The combined average seepage velocity of the fluids is given by

$v_{p}=\frac{Q_{p}}{A_{p}}=S_{w}v_{w}+S_{n}v_{n}\;,$ (4)

where I in the last expression have use equations (1) – (3).

The three seepage velocities are all functions of the saturation $S_{w}$ and
the pressure gradient $p=|\nabla P|$, $v_{p}=v_{p}(p,S_{w})$,
$v_{w}=v_{w}(p,S_{w})$, and $v_{n}=v_{n}(p,S_{w})$.

The co-moving velocity is defined as hansen2018relations

$v_{m}=S_{w}\left(\frac{\partial v_{w}}{\partial
S_{w}}\right)_{p}+S_{n}\left(\frac{\partial v_{n}}{\partial
S_{w}}\right)_{p}\;.$ (5)

By taking the derivative of equation (4), I find that the co-moving velocity
may be written

$v_{m}=\left(\frac{\partial v_{p}}{\partial
S_{w}}\right)_{p}+v_{n}-v_{w}=v_{p}^{\prime}+v_{n}-v_{n}\;,$ (6)

where I have defined $v_{p}`=(\partial v_{p}/\partial S_{w})_{p}$.

Equations (4) and (5) constitute the mapping $(v_{w},v_{n})\to(v_{p},v_{m})$.
The inverse mapping, $(v_{p},v_{m})\to(v_{w},v_{n})$, is

$\displaystyle v_{w}=v_{p}+S_{n}(v_{p}^{\prime}-v_{m})\;,$ (7) $\displaystyle
v_{n}=v_{p}-S_{w}(v_{p}^{\prime}-v_{m})\;.$ (8)

Roy et al. roy2022co  and Alzubaidi et al. alzubaidi2023impact  observed the
co-moving velocity being linear when plotted against $v_{p}^{\prime}$,

$v_{m}=a(p)+b(p)v_{p}^{\prime}\;.$ (9)

The question I answer in the the next section is why this simple linear form?

##  3 Derivation

There are three steps to the derivation.

Step 1: Introduction of a velocity scale. The average seepage velocity $v_{p}$
contains an additive velocity scale that is lost when constructing
$v_{p}^{\prime}$ since

$v_{p}(S_{w})=\int_{S_{w,0}}^{S_{w}}\ dS_{w}\ v_{p}^{\prime}+v_{p,0}(S_{w,0})$
(10)

where the integration constant $v_{p,0})(S_{w,0})$ is the additive velocity
scale.

In the same way, the co-moving velocity $v_{m}$ will contain an additive
velocity scale. This is necessary from equation (6). I will call this scale
$a$ and define it as

$a=v_{m}(a,0)=[v_{n}-v_{w}]_{v_{p}^{\prime}=0}\;,$ (11)

where I from now on use the notation $v_{m}=v_{m}(a,v_{p}^{\prime})$. I also
refrain from writing the pressure gradient explicitly as it is not needed
explicitly in the following.

Step 2: Establishing that $v_{m}$ is an Euler homogeneous function in the
velocity scale. The co-moving velocity must be invariant with respect to a
change of velocity scale $v_{0}$. This was e.g., used in the analysis in Roy
et al. roy2022co , as this was the basis for using the relative permeability
data. This means that $v_{m}$ obeys the scaling relation

$\frac{v_{m}(a,v_{p}^{\prime})}{v_{0}}=v_{m}\left(\frac{a}{v_{0}},\frac{v_{p}^{\prime}}{v_{0}}\right)\;.$
(12)

Hence, $v_{m}$ is an Euler homogeneous function of order one in the variables
$a$ and $v_{p}^{\prime}$. Taking the derivative with respect to $1/v_{0}$ and
setting $v_{0}=1$ gives

$v_{m}(a,v_{p}^{\prime})=\left(\frac{\partial v_{m}}{\partial
a}\right)_{v_{p}^{\prime}}a+\left(\frac{\partial v_{m}}{\partial
v_{p}^{\prime}}\right)_{a}v_{p}^{\prime}\;.$ (13)

From equations (11) and (13), I must have

$\left(\frac{\partial v_{m}}{\partial a}\right)_{v_{p}^{\prime}}=1\;.$ (14)

Furthermore, I must have

$\left(\frac{\partial v_{m}}{\partial
v_{p}^{\prime}}\right)_{a}=b\left(\frac{v_{p}^{\prime}}{a}\right)\;,$ (15)

where $b(v_{p}^{\prime}/a)$ is a homogeneous function of degree zero. This
leads me to the following expression for $v_{m}$:

$v_{m}(a,v_{p}^{\prime})=a+b\left(\frac{v_{p}^{\prime}}{a}\right)\
v_{p}^{\prime}\;.$ (16)

Step 3: Combining the two previous steps. I now combine equations (14), (15)
and (16),

$\left(\frac{\partial v_{m}}{\partial
a}\right)_{v_{p}^{\prime}}=\left(\frac{\partial}{\partial
a}\right)_{v_{p}^{\prime}}\left[a+b\left(\frac{v_{p}^{\prime}}{a}\right)\
v_{p}^{\prime}\right]=1-\frac{db(u)}{du}\bigg{|}_{u=v_{p}^{\prime}/a}\left(\frac{v_{p}^{\prime}}{a}\right)^{2}=1\;,$
(17)

where the rightmost equality is equation (14). I have here defined the new
combined variable $u=v_{p}^{\prime}/a$. I see from equation (17) that

$\frac{db(u)}{du}=0\;.$ (18)

Hence, $b$ is a constant. Combining this result with equation (16) gives the
final result,

$v_{m}(a,v_{p}^{\prime})=a+b\ v_{p}^{\prime}\;.$ (19)

The co-moving velocity $v_{m}$ is linear in $v_{p}^{\prime}$.

##  4 Consequences for relative permeability theory

The generalized Darcy equations that forms the core of relative permeability
theory are

$\displaystyle v_{w}=-\frac{Kk_{rw}}{\mu_{w}\phi S_{w}}\ p\;,$ (20)
$\displaystyle v_{n}=-\frac{Kk_{rn}}{\mu_{n}\phi S_{n}}\ p\;,$ (21)

where $\mu_{w}$ and $\mu_{n}$ are viscosities, $K$ the permeability and
$k_{rw}(S_{w})$ and $k_{rn}(S_{w})$ are the relative permeabilities. The
saturations appear in the expressions since $v_{w}$ and $v_{n}$ are the
seepage velocities.

Following Roy et al. roy2022co , I define a velocity scale

$v_{0}=-\frac{K}{\mu_{w}\phi}\ p\;,$ (23)

which is the seepage velocity of the wetting fluid at saturation $S_{w}=1$. I
may then write the generalized Darcy equations as

$\displaystyle v_{w}$ $\displaystyle=$ $\displaystyle\frac{k_{rw}}{S_{w}}\
v_{0}\;,$ (24) $\displaystyle v_{n}$ $\displaystyle=$
$\displaystyle\frac{k_{rn}}{S_{n}}\ Mv_{0}\;,$ (25)

where I have defined the viscosity ratio $M=\mu_{w}/\mu_{n}$. I now combine
these two expressions with the co-moving velocity, equation (19) using
equation (6). I also make a change in notation by setting $a\to av_{0}$, as in
roy2022co . The resulting equation is

$(1-b)\frac{d}{dS_{w}}\left[k_{rw}+Mk_{rn}\right]-\frac{k_{rw}}{S_{w}}+\frac{Mk_{rn}}{S_{n}}=a\;.$
(27)

A simplified version of this equation was used in Alzubaidi et al.
alzubaidi2023impact  to determine the non-wetting relative permeability when
the wetting permeability, $a=0$ and $b$ is known. One way to use this equation
would be to plug the known $k_{rw}$ into it and then find $k_{rn}$ through
numerical integration.

It is also possible to find analytic solutions to equation (27). I give an
example in the following. Picci and Battiato picchi2019relative  suggested the
semi-empirical form (note that their viscosity ratio is the inverse of the
definition I use)

$\displaystyle k_{rw}$ $\displaystyle=$ $\displaystyle k_{rw}^{0}S_{w}^{2}\;,$
(28) $\displaystyle k_{rn}$ $\displaystyle=$ $\displaystyle
k_{rn}^{0}S_{n}^{2}\left[1+\frac{2S_{w}}{MS_{n}}\right]\;,$ (29)

where $k_{rw}^{0}$ and $k_{rn}^{0}$ are the end point relative permeabilities.
Setting

$b=\frac{1}{2}\;,$ (30)

and

$a=k_{rn}^{0}$ (31)

solves equation (27).

By solving for the saturation for which $v_{p}^{\prime}=0$, using equations
(28) and (29), we find that

$[v_{n}-v_{w}]_{v_{p}^{\prime}=0}=k_{rn}^{0}\;.$ (32)

According to equation (11) this is equal to $a$, as found solving equation
(27) directly, leading to (31).

The Corey empirical relative permeabilities are, on the other hand, not
solutions to equation (27). That is, when the Corey exponents are equal, they
are solutions, but with an unphysical $a=0$. When the exponents are different,
they are not solutions to the equation for any combination of $b$ and $a$.

##  5 Discussion and Conclusion

I have in this paper shown that the co-moving velocity is of the form given by
equation (19). The derivation is based on two assumptions, 1. the necessity of
an additive velocity scale $a$, and 2. the invariance of $v_{m}$ with respect
to a change of scale $v_{0}$. Both assumptions are weak and does not hinge on
any restrictions on the constitutive law for $v_{p}$, linear or non-linear. In
order to connect relative permeability theory to the formalism for which
$v_{m}$ is a central variable, the specific constitutive law

$v_{p}(p,S_{w})=\left[k_{rw}(S_{w})+Mk_{rn}(S_{w})\right]v_{0}(p)\;,$ (33)

is used. Equation (6), which is the combination of the relative permeability
constitutive laws with the linear equation for $v_{m}$, (19), leads to a
relation between the two relative permeabilities: knowing one, gives the other
one.

The parameter $a=[v_{n}-v_{w}]_{v_{p}^{\prime}=0}$, equation (11) is
understood. However, the second parameter, $b$ is not. It typically takes on a
value around 0.6–0.8 and seems quite insensitive to the contact angle between
the fluids and the matrix as shown by Alzubaidi et al. alzubaidi2023impact .
It is an open question why. Furthermore, from equation (6) one should think
that $b=1$. It is not. Why?

Declaration — The author declares no conflict of interest.

Acknowledgement — The author thanks R. T. Armstrong, C. F. Berg, S. Berg, E.
G. Flekkøy, J. E. McClure, B. Hafskjold, H. Pedersen, T. Ramstad, S. Roy, and
S. Sinha for countless discussions. This work was partly supported by the
Research Council of Norway through its Centres of Excellence funding scheme,
project number 262644.

## References

  * (1) R. Wyckoff, H. Botset, The flow of gas-liquid mixtures through unconsolidated sands, Physics 7(9), 325 (1936).  DOI 10.1063/1.1745402
  * (2) H. Darcy, _Les fontaines publiques de la ville de Dijon: exposition et application des principes à suivre et des formules à employer dans les questions de distribution d’eau_ , vol. 1 (Victor Dalmont, 1856)
  * (3) K.T. Tallakstad, H.A. Knudsen, T. Ramstad, G. Løvoll, K.J. Måløy, R. Toussaint, E.G. Flekkøy, Steady-state two-phase flow in porous media: statistics and transport properties, Physical review letters 102(7), 074502 (2009).  DOI 10.1103/PhysRevLett.102.074502
  * (4) K.T. Tallakstad, G. Løvoll, H.A. Knudsen, T. Ramstad, E.G. Flekkøy, K.J. Måløy, Steady-state, simultaneous two-phase flow in porous media: An experimental study, Physical Review E 80(3), 036308 (2009).  DOI 10.1103/PhysRevE.80.036308
  * (5) A. Hansen, S. Sinha, D. Bedeaux, S. Kjelstrup, M.A. Gjennestad, M. Vassvik, Relations between seepage velocities in immiscible, incompressible two-phase flow in porous media, Transport in Porous Media 125, 565 (2018).  DOI 10.1007/s11242-018-1139-6
  * (6) J. Feder, E.G. Flekkøy, A. Hansen, _Physics of flow in porous media_ (Cambridge University Press, 2022)
  * (7) S. Roy, H. Pedersen, S. Sinha, A. Hansen, The co-moving velocity in immiscible two-phase flow in porous media, Transport in Porous Media 143(1), 69 (2022).  DOI 10.1007/s11242-022-01783-7
  * (8) A. Hansen, E.G. Flekkøy, S. Sinha, P.A. Slotte, A statistical mechanics framework for immiscible and incompressible two-phase flow in porous media, Advances in Water Resources 171, 104336 (2023).  DOI 10.1016/j.advwatres.2022.104336
  * (9) H. Pedersen, A. Hansen, Parameterizations of immiscible two-phase flow in porous media, Frontiers in Physics 11, 116 (2023).  DOI 10.3389/fphy.2023.1127345
  * (10) F. Alzubaidi, J.E. McClure, H. Pedersen, A. Hansen, C.F. Berg, P. Mostaghimi, R.T. Armstrong, The impact of wettability on the co-moving velocity of two-fluid flow in porous media, arXiv preprint arXiv:2309.00362 (2023).  DOI 10.48550/arXiv.2309.00362
  * (11) S. Zou, R.T. Armstrong, J.Y. Arns, C.H. Arns, F. Hussain, Experimental and theoretical evidence for increased ganglion dynamics during fractional flow in mixed-wet porous media, Water Resources Research 54(5), 3277 (2018).  DOI 10.1029/2017WR022433
  * (12) D. Picchi, I. Battiato, Relative permeability scaling from pore-scale flow regimes, Water Resources Research 55(4), 3215 (2019).  DOI 10.1029/2018WR024251


#  Local Glivenko-Cantelli

Doron Cohen
Department of Computer Science
Ben-Gurion University of the Negev
Beer-Sheva, Israel
<EMAIL_ADDRESS>
Aryeh Kontorovich
Department of Computer Science
Ben-Gurion University of the Negev
Beer-Sheva, Israel
<EMAIL_ADDRESS>

###### Abstract

If $\mu$ is a distribution over the $d$-dimensional Boolean cube
$\left\\{0,1\right\\}^{d}$, our goal is to estimate its mean $p\in[0,1]^{d}$
based on $n$ iid draws from $\mu$. Specifically, we consider the empirical
mean estimator $\hat{p}_{n}$ and study the expected maximal deviation
$\Delta_{n}=\mathop{\mathbb{E}}\max_{j\in[d]}|\hat{p}_{n}(j)-p(j)|$. In the
classical Universal Glivenko-Cantelli setting, one seeks distribution-free
(i.e., independent of $\mu$) bounds on $\Delta_{n}$. This regime is well-
understood: for all $\mu$, we have $\Delta_{n}\lesssim\sqrt{\log(d)/n}$ up to
universal constants, and the bound is tight.

Our present work seeks to establish dimension-free (i.e., without an explicit
dependence on $d$) estimates on $\Delta_{n}$, including those that hold for
$d=\infty$. As such bounds must necessarily depend on $\mu$, we refer to this
regime as local Glivenko-Cantelli, and are aware of very few previous bounds
of this type — which are quite sub-optimal. Already the special case of
product measures $\mu$ is rather non-trivial. We give necessary and sufficient
conditions on $\mu$ for $\Delta_{n}\to 0$, and calculate sharp rates for this
decay. Along the way, we discover a novel sub-gamma-type maximal inequality
for shifted Bernoullis, of independent interest.

##  1 Introduction

Estimating the mean of a random variable $X\in\mathbb{R}^{d}$ from a sample of
independent draws $X_{i}$ is among the most basic problems of statistics. Much
of the theory has focused on obtaining efficient estimators $\hat{m}_{n}$ of
the true mean $m$ and analyzing the decay of
$\left\|\hat{m}_{n}-m\right\|_{2}$ as a function of sample size $n$, dimension
$d$, and various moment assumptions on $X$ (Devroye et al., 2016; Lugosi and
Mendelson, 2019a, b; Cherapanamjeri et al., 2019, 2020; Lugosi and Mendelson,
2021). In this work, we study this problem from a different angle. Inspired by
Thomas (2018), we consider a distribution $\mu$ on $\left\\{0,1\right\\}^{d}$
with mean $p\in[0,1]^{d}$. We stress that $p$ is not a distribution: the
$p(j)$ do not generally sum to $1$ and $\sum_{j=1}^{d}p(j)$ might well diverge
for $d=\infty$. Given $n$ iid draws of $X_{i}\sim\mu$, we denote by
$\hat{p}_{n}=n^{-1}\sum_{i=1}^{n}X_{i}$ the empirical mean. The central
quantity of interest in this paper is the uniform absolute deviation

$\displaystyle\Delta_{n}(\mu):=\mathop{\mathbb{E}}\left\|\hat{p}_{n}-p\right\|_{\infty}=\mathop{\mathbb{E}}\max_{j\in[d]}|\hat{p}_{n}(j)-p(j)|.$
(1)

A few immediate remarks are in order. It is obvious that $\Delta_{n}(\mu)\leq
1$ always, and $\Delta_{n}(\mu)\to 0$ as $n\to\infty$ whenever $d<\infty$; in
fact, it is well-known (and proven below for completeness) that

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\lesssim$
$\displaystyle\sqrt{\frac{\log(d+1)}{n}}.$ (2)

It is likewise clear that (2) is not tight for all distributions: if
$X\sim\mu$ satisfies $X(1)=X(2)=\ldots=X(d)$, then $\Delta_{n}(\mu)$ is
determined by the single parameter $p(1)=\mathop{\mathbb{E}}X(1)$, and does
not depend on $d$. Our goal is to understand how $\Delta_{n}$ depends on the
distribution $\mu$ in a dimension-free fashion — i.e., without an explicit
dependence on $d$.

We broaden our scope to encompass the infinite-dimensional case $d=\infty$,
where $\mu$ is a distribution on $\left\\{0,1\right\\}^{\mathbb{N}}$
(supported on the usual $\sigma$-algebra generated by the finite-dimensional
cylinders), and
$\Delta_{n}(\mu)=\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}|\hat{p}_{n}(j)-p(j)|$.
At the same time, for most of this paper we narrow the scope to the case where
$\mu$ is a product measure on $\left\\{0,1\right\\}^{\mathbb{N}}$. Thus, the
components $X(j)\sim\operatorname{Bernoulli}(p(j))$ are independent and $\mu$
is entirely determined by the sequence $p\in[0,1]^{\mathbb{N}}$; our notation
$\Delta_{n}(p)$ will indicate the product-measure setting.

For general $p\in[0,1]^{\mathbb{N}}$, it no longer necessarily holds that
$\Delta_{n}(p)\to 0$. Indeed, taking $p=(1/2,1/2,\ldots,)$ yields
$\Delta_{n}(p)=1/2$ for all $n$ (for the simple reason that if a random
variable has a positive chance of attaining a certain value and is given
infinitely many opportunities to do so, it almost surely will). A
straightforward generalization of this argument shows that
$\lim_{j\to\infty}\min\left\\{p(j),1-p(j)\right\\}=0$ is a necessary condition
for $\Delta_{n}(p)\to 0$. Since $|u-v|=|(1-u)-(1-v)|$, there is no loss of
generality in restricting our attention to
$p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}$ — and further, in light of the
preceding discussion, only to those $p$ for which $p(j)\to 0$. Any such $p$
has a non-increasing permutation $p^{\downarrow}$, and since
$\Delta_{n}(p)=\Delta_{n}(p^{\downarrow})$, we will henceforth additionally
assume, without loss of generality, that $p=p^{\downarrow}$.

Having restricted our attention to
$[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$ — that is, the
collection of all $p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}$ decreasing to
$0$ — we distinguish a subset
$\mathsf{LGC}\subseteq[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$
via the criterion $\Delta_{n}(p)\to 0$; those $p$ for which this holds will be
called local Glivenko-Cantelli. The central challenges posed in this paper are
to give a precise characterization of $\mathsf{LGC}$ as well as the rate at
which $\Delta_{n}(p)\to 0$ as a function of $n$ and $p$.

#### Notation.

Our logarithms will always be base $\mathrm{e}$ by default; other bases will
be explicitly specified. The natural numbers are denoted by
$\mathbb{N}=\left\\{1,2,3,\dots\right\\}$ and for $k\in\mathbb{N}$, we write
$[k]=\left\\{i\in\mathbb{N}:i\leq k\right\\}$. For $n,d\in\mathbb{N}$ and a
distribution $\mu$ over $\left\\{0,1\right\\}^{d}$, we will always denote by
$p,\hat{p}_{n}\in[0,1]^{d}$ the true and empirical means of $\mu$,
respectively, as defined immediately preceding (1). The $j$th coordinate of a
vector $v\in\mathbb{R}^{d}$ is denoted by $v(j)$. The expected maximal
deviation $\Delta_{n}(\mu)$ is defined in (1), and the notation
$[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$, $\mathsf{LGC}$ from
the preceding paragraph will be used throughout. We say that $\mu$ is a
product distribution on $\left\\{0,1\right\\}^{d}$ if it can be expressed as a
tensor product of $d$ distributions:
$\mu=\mu_{1}\otimes\mu_{2}\otimes\ldots\otimes\mu_{d}$; equivalently, for
$X\sim\mu$ we have that the random variables $\left\\{X(j):j\in[d]\right\\}$
are mutually independent.

These definitions continue to hold when $d=\infty$, though some care must be
taken in defining the $\sigma$-algebra on $\left\\{0,1\right\\}^{\mathbb{N}}$;
see, e.g., Kallenberg (2002). Alternatively, one consider a sequence of cubes
$\left\\{0,1\right\\}^{d}$, $d\in\mathbb{N}$, along with a sequence of
distributions $\mu_{d}$ on $\left\\{0,1\right\\}^{d}$, such that for each
$d^{\prime}<d^{\prime\prime}$, $\mu_{d^{\prime}}$ coincides with the marginal
distribution of $\mu_{d^{\prime\prime}}$ on the first $d^{\prime}$
coordinates. Then the Ionescu Tulcea extension Theorem (Kallenberg, 2002,
Theorem 5.17) guarantees that the $\mu_{d}$’s can be “stitched together” into
a coherent probability measure $\mu$ on $\left\\{0,1\right\\}^{\mathbb{N}}$
(equipped with the $\sigma$-algebra generated by the finite-dimensional
cylinders). Further, Lebesgue’s Monotone Convergence Theorem implies that

$\displaystyle\mathop{\mathbb{E}}_{X\sim\mu}\sup_{i\in\mathbb{N}}|\hat{p}_{n}(j)-p(j)|=\sup_{d\in\mathbb{N}}\mathop{\mathbb{E}}_{X\sim\mu_{d}}\max_{i\in[d]}|\hat{p}_{n}(j)-p(j)|.$
(3)

Anyone wishing to side-step the measure theory may take the right-hand-side of
(3) as the definition of the left-hand side.

For $f,g:\mathbb{N}\to(0,\infty)$, we write $f\lesssim g$ if
$\limsup_{n\to\infty}f(n)/g(n)<\infty$. Likewise, $f\gtrsim g\iff g\lesssim f$
and $f\asymp g$ if both $f\lesssim g$ and $f\gtrsim g$ hold. The floor and
ceiling functions, $\left\lfloor t\right\rfloor$, $\left\lceil t\right\rceil$,
map $t\in\mathbb{R}$ to its closest integers below and above, respectively;
also, $s\vee t:=\max\left\\{s,t\right\\}$, $s\wedge
t:=\min\left\\{s,t\right\\}$, and $\left[s\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}:=0\vee s$. Unspecified constants such as
$c,c^{\prime}$ may change value from line to line.

##  2 Main results

We begin with a characterization of $\mathsf{LGC}$. For each
$p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$, we define the
two key quantities,

$\displaystyle S(p)$ $\displaystyle:=$
$\displaystyle\sup_{j\in\mathbb{N}}p(j)\log(j+1),$ (4) $\displaystyle T(p)$
$\displaystyle:=$
$\displaystyle\sup_{j\in\mathbb{N}}\frac{\log(j+1)}{\log(1/p(j))}.$ (5)

For any (not necessarily product) probability measure $\mu$ on
$\left\\{0,1\right\\}^{\mathbb{N}}$, recall that
$p={\displaystyle\mathop{\mathbb{E}}_{X\sim\mu}[X]}$ and define
$\tilde{p}(j)=\min\left\\{p(j),1-p(j)\right\\}$, $j\in\mathbb{N}$. Whenever
$\tilde{p}(j)\to 0$, we have that ${\tilde{p}}^{\downarrow}$ is well-defined,
as are $S(\mu):=S({\tilde{p}}^{\downarrow})$ and
$T(\mu):=T({\tilde{p}}^{\downarrow})$; otherwise, $S(\mu),T(\mu):=\infty$.

######  Theorem 1 (Characterization of $\mathsf{LGC}$).

Any $p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$ satisfies
$\Delta_{n}(p)\to 0$ if and only if $T(p)<\infty$. Additionally, if $\mu$ is
any probability measure on $\left\\{0,1\right\\}^{\mathbb{N}}$ with
$T(\mu)<\infty$, then $\Delta_{n}(\mu)\to 0$.

It is immediate from the definitions of $S$ and $T$ that $S(p)\leq T(p)$ and
hence $S(p)<\infty$ whenever $p\in\mathsf{LGC}$. For these $p$, the asymptotic
decay of $\Delta_{n}(p)\to 0$ is determined by $S(p)$:

######  Theorem 2 (Coarse asymptotics of $\Delta_{n}$).

For every product probability measure $\mu$ on
$\left\\{0,1\right\\}^{\mathbb{N}}$ such that
$p=\mathop{\mathbb{E}}_{X\sim\mu}[X]\in\mathsf{LGC}$, we have

$\displaystyle
c\sqrt{S(p)}\leq\liminf_{n\to\infty}\sqrt{n}\Delta_{n}(p)\leq\limsup_{n\to\infty}\sqrt{n}\Delta_{n}(p)\leq
c^{\prime}\sqrt{S(p)},$

where $c,c^{\prime}$ are absolute constants. Additionally, if $\mu$ is any
probability measure on $\left\\{0,1\right\\}^{\mathbb{N}}$ and
$T(\mu)<\infty$, then $\limsup_{n\to\infty}\sqrt{n}\Delta_{n}(\mu)\leq
c^{\prime}\sqrt{S(\mu)}$.

This result may be informally summarized as
$\sqrt{n}\Delta_{n}(p)\asymp\sqrt{S(p)}$, for product measures. In addition to
the asymptotics, we obtain the finite-sample upper bound

######  Theorem 3.

For any probability measure $\mu$ on $\left\\{0,1\right\\}^{\mathbb{N}}$ with
$T(\mu)<\infty$,

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\leq$ $\displaystyle
c\left(\sqrt{\frac{S(\mu)}{n}}+\frac{T(\mu)\log n}{n}\right),\qquad
n\geq\mathrm{e}^{3},$

where $c>0$ is an absolute constant.

We conjecture that the $\log n$ factor multiplying $T(\mu)$ can be removed;
this would imply the improved asymptotic rate
$\Delta_{n}(\mu)\lesssim\sqrt{S(\mu)/n}+T(\mu)/n$. No further improvement is
possible, as evident from the $n\Delta_{n}(p)\gtrsim T$ asymptotic lower
bound:

######  Theorem 4 (Fine asymptotics of $\Delta_{n}$).

For every product probability measure $\mu$ on
$\left\\{0,1\right\\}^{\mathbb{N}}$ with $p=\mathop{\mathbb{E}}_{X\sim\mu}[X]$
such that $T(p)<\infty$, we have

$\displaystyle\liminf_{n\to\infty}n\Delta_{n}(p)\geq cT(p),$

where $c$ is an absolute constant.

Instrumental in proving Theorem 3 is a novel sub-gamma inequality for shifted
Bernoulli distributions, of independent interest:

######  Lemma 1 (Sub-gamma inequality for the shifted Bernoulli).

For all $0<p\leq s\leq\mathrm{e}^{-3}$ and $0\leq t<\log(1/p)/\log(1/s)$,

$\displaystyle\mathop{\mathbb{E}}_{X\sim\operatorname{Bernoulli}(p)}[\exp(t(X-s))]\leq\exp\left(\frac{pt^{2}}{2[1-t\log(1/s)/\log(1/p)]}\right).$

This is a refinement of Bernstein’s inequality: for $s=p$, the latter is
recovered up to constants. However, for $p\ll s$, the former is significantly
sharper.

Finally, we provide a fully empirical upper bound on $\Delta_{n}(\mu)$:

######  Theorem 5.

For any probability measure $\mu$ on $\left\\{0,1\right\\}^{\mathbb{N}}$, let
$\hat{\mu}_{n}$ be its empirical realization induced by an iid sample
$X_{i}\sim\mu$; thus,
$\hat{\mu}_{n}(x)=n^{-1}\sum_{i=1}^{n}\boldsymbol{1}[X_{i}=x]$ and
$\hat{p}_{n}={\displaystyle\mathop{\mathbb{E}}_{X\sim\hat{\mu}_{n}}[X]}$. Let
$\tilde{X}_{i}\sim\mu$ be another iid sample of size $n$ independent of
$X_{i}$ and define $\tilde{p}_{n}\in[0,1]^{\mathbb{N}}$ by
$\tilde{p}_{n}(j)=(1-a(j))\hat{p}_{n}(j)+a(j)(1-\hat{p}_{n}(j))$, where
$a(j)=\boldsymbol{1}[\sum_{i=1}^{n}\tilde{X}_{i}(j)>\frac{n}{2}]$ . Then

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\leq$
$\displaystyle\frac{16}{\sqrt{n}}\sqrt{S({\tilde{p}_{n}}^{\downarrow})}+\sqrt{\frac{8\log(1/\delta)}{n}}$

holds with probability at least $1-\delta$. (We interpret
$S({u}^{\downarrow})$ as $\infty$ when ${u}^{\downarrow}$ does not exist.)

An attractive feature of this bound is that it is stated entirely in terms of
quantities easily computed from the observed sample — unlike, say, the upper
bound in Theorem 3, which is stated in terms of the unknown $p(j)$. When
$S(\mu),T(\mu)$ are small, we expect, from Theorem 3 and (7),
$\left\|\hat{p}_{n}-p\right\|_{\infty}$ to be small — and hence,
$S({\tilde{p}_{n}}^{\downarrow})\approx S(\hat{\mu}_{n})\approx S(\mu)$. In
the “unlucky” case where Theorem 5 fails to give a good empirical bound, we
can chalk it up, with some confidence, to the badness of $\mu$. As will become
apparent from the proof, the claim holds for any choice of
$a\in[0,1]^{\mathbb{N}}$ — whether deterministic or a function of the
$\tilde{X}_{i}$. Of course, for imprudent choices of $a$, the quantity
$S({\tilde{p}_{n}}^{\downarrow})$ will fail to be small for “well-behaved”
distributions $\mu$. Tying the typical behavior of
$S({\tilde{p}_{n}}^{\downarrow})$ (for our choice of $a$) to the well-
behavedness of $\mu$ is a subject of future work.

#### Remark.

Our upper bounds hold for all probability measures $\mu$ on
$\left\\{0,1\right\\}^{\mathbb{N}}$, while the lower bounds in Theorem 1
($T(p)=\infty\implies p\notin\mathsf{LGC}$) and Theorem 2
($\liminf\sqrt{n}\Delta_{n}(p)\gtrsim\sqrt{S(p)}$) make critical use of the
product structure of $\mu$; the upper bounds are quite loose when the
coordinates $X(j)$ are strongly correlated. Understanding the behavior of
$\Delta_{n}(\mu)$ for non-product $\mu$ is an active current research
direction of ours.

##  3  Discussion and comparisons with known results

#### Discussion.

We argue that the bounds in Theorems 2 and 3 are at least mildly surprising.
Indeed, it is known that for $X\sim\operatorname{Bernoulli}(p)$, its optimal
sub-Gaussian variance proxy (i.e., the smallest $\sigma^{2}$ such that
$\mathop{\mathbb{E}}\mathrm{e}^{t(X-p)}\leq\exp(t^{2}\sigma^{2}/2)$) for all
$t\in\mathbb{R}$ is given by

$\displaystyle\sigma^{2}(p)$ $\displaystyle=$
$\displaystyle\frac{1-2p}{2\log(1/p-1)}$

(Kearns and Saul, 1998; Berend and Kontorovich, 2013b; Buldygin and
Moskvichova, 2013) — and hence, $X\sim\operatorname{Binomial}(n,p)/n$ is
$\sigma^{2}(p)/n$-sub-Gaussian. For $p\ll 1$, we have $\sigma^{2}(p)\asymp
1/\log(1/p)$. Thus, drawing intuition from the majorizing measure theorem (Van
Handel, 2014, Theorem 6.24), one might expect that
$\Delta_{n}(p)\lesssim\sqrt{T(p)/n}$ captures the correct behavior for the
case of product measures. While this estimate indeed holds (as an immediate
consequence of Lemma 8), it is far from tight, as evident from Theorem 2.
Instead, $\Delta_{n}(p)$ exhibits both a sub-Gaussian decay regime, with rate
$\sqrt{S(p)/n}$ and a sub-exponential regime, with rate $\lesssim T\log(n)/n$;
this type of decay (without the $\log n$ factor) is sometimes referred to as
sub-gamma (Boucheron et al., 2013).

Intuitively, the crucial difference between the (normalized) Binomial and the
Gaussian cases is that the former is absolutely bounded, while the latter is
not. Not only is $X\sim\operatorname{Binomial}(n,p)/n$ bounded in $[0,1]$, but
for $p\leq s\ll 1$ the shifted variable $X-s$ will typically attain very small
values111 Our motivation for considering $s>p$ will become apparent in the
sequel. . Bernstein’s classic inequality, up to constants, upper-bounds
$\log\mathop{\mathbb{E}}\mathrm{e}^{t(X-p)}$ by $pt^{2}/(1-t)$ and holds for
any $X$ with range in $[0,1]$, $\mathop{\mathbb{E}}X=p$, and variance
$\lesssim p$. The refined estimate in Lemma 1 shows that the “effective upper
range” of $X-s$ is, in a useful sense, something like $\log(1/p)/\log(1/s)$ —
which is much more delicate than bounding by the constant $1$ and is precisely
what allows us to obtain the sub-gamma tail.

#### Comparisons.

Thomas (2018) (effectively222 To be precise, the question was regarding the
tail behavior of $\left\|\hat{p}_{n}-p\right\|_{\infty}$ rather than its
expectation $\Delta_{n}(\mu)$. ) asked whether $\Delta_{n}(\mu)$ can be
bounded in terms of the entropy of $\mu$. For product measures on
$\left\\{0,1\right\\}^{\mathbb{N}}$ parametrized by
$p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$, the entropy is
given by

$\displaystyle H(p)=-\sum_{j\in\mathbb{N}}p(j)\log p(j)-(1-p(j))\log(1-p(j))$

and $H(p)<\infty$ is a much stronger condition than $T(p)<\infty$;333 If
$H(p)<\infty$ then certainly $\sum_{j\in\mathbb{N}}p(j)<\infty$, which implies
$T(p)<\infty$ via Lemma 3. On the other hand, for $p(j)=1/j$, we have
$T<\infty$ while $H=\infty$. We note in passing that for small $x$ and
$p=(x,0,0,\ldots)$, we have $T(p)=1/\log(1/x)\gg x\log(1/x)\approx H(p)$, so
$T(p)\leq aH(p)^{b}$ does not, in general, hold for any constants $a,b>0$.
thus, in light of Theorem 1, $H(p)$ is not, in general, the correct measure
for controlling the decay of $\Delta_{n}(\mu)$. (Of course, for non-product
measures $\mu$, the entropy $H(\mu)$ takes coordinate correlations into
account and can be significantly smaller than $T(\mu)$ and even than
$S(\mu)$.)

Already in Thomas (2018), it was observed that Hoeffding’s inequality together
with the union bound imply

$\displaystyle\mathbb{P}(\left\|\hat{p}_{n}-p\right\|_{\infty}\geq\varepsilon)\leq
2d\mathrm{e}^{-2n\varepsilon^{2}},\qquad\varepsilon>0,n\in\mathbb{N}.$ (6)

Hence, a sample of size $n\geq\frac{\log(2d/\delta)}{\varepsilon^{2}}$
suffices to achieve
$\mathbb{P}(\left\|\hat{p}_{n}-p\right\|_{\infty}\geq\varepsilon)\leq\delta$.
This easily implies (2), which is worst-case tight, as witnessed by the
uniform distribution. It was also noted therein that McDiarmid’s inequality
implies

$\displaystyle\mathbb{P}(\left\|\hat{p}_{n}-p\right\|_{\infty}\geq\Delta_{n}(\mu)+\varepsilon)\leq\mathrm{e}^{-2n\varepsilon^{2}},\qquad\varepsilon>0,n\in\mathbb{N},$
(7)

which reduces the problem to one of estimating $\Delta_{n}(\mu)$. A standard
Borel-Cantelli argument shows that $\Delta_{n}(\mu)\to 0$ if and only if
$\left\|\hat{p}_{n}-p\right\|_{\infty}\to 0$ almost surely. Moreover, classic
VC theory both implies that the distribution-free upper bound in (2) and shows
that it is worst-case tight not just for the empirical mean $\hat{p}_{n}$, but
also for any other estimator $\tilde{p}_{n}$, see Corollary 1.

Additional estimates on $\Delta_{n}(\mu)$ suggested in Thomas (2018) include

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{1}{n}\sum_{j\in\mathbb{N}}p(j)(1-p(j))}$

and

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{1}{2}H(\mu)}.$

The former is considerably inferior to the bound in Theorem 3, while the
latter does not decrease as $n\to\infty$.

##  4 Proofs

###  4.1 Proof of Lemma 1 (Sub-gamma inequality for the shifted Bernoulli)

Let us parameterize $t=a\log(1/p)/\log(1/s)$ for $0\leq a<1$; this captures
the exact range of the allowed values of $t$. Proving our inequality amounts
to showing that

$\displaystyle
F(a):=\log\left(\left(\frac{1}{p}\right)^{\frac{a(1-s)}{\log\left(\frac{1}{s}\right)}-1}+(1-p)\left(\frac{1}{p}\right)^{-\frac{as}{\log\left(\frac{1}{s}\right)}}\right)-\frac{a^{2}p\log^{2}\left(\frac{1}{p}\right)}{2(1-a)\log^{2}\left(\frac{1}{s}\right)}\leq
0.$

We claim that $F(0)=0$ and $F^{\prime}(a)\leq 0$. The former is immediate, and
to show the latter, we compute the derivative:

$\displaystyle
F^{\prime}(a)=\frac{\log\left(\frac{1}{p}\right)\left(2\log\left(\frac{1}{s}\right)\left(\frac{p^{1-\frac{a}{\log\left(\frac{1}{s}\right)}}}{p^{1-\frac{a}{\log\left(\frac{1}{s}\right)}}-p+1}-s\right)+\frac{(a-2)ap\log\left(\frac{1}{p}\right)}{(a-1)^{2}}\right)}{2\log^{2}\left(\frac{1}{s}\right)}.$

The factors $\log\left(\frac{1}{p}\right)$ and
$\log^{2}\left(\frac{1}{s}\right)$ are positive; additionally,
${p^{1-\frac{a}{\log\left(\frac{1}{s}\right)}}-p+1}\geq 1$; hence, it remains
to show that

$\displaystyle
G=2\log\left(\frac{1}{s}\right)\left(p^{1-\frac{a}{\log\left(\frac{1}{s}\right)}}-s\right)+\frac{(a-2)ap\log\left(\frac{1}{p}\right)}{(a-1)^{2}}<0,$

since $\operatorname{sgn}(G)\geq\operatorname{sgn}(F^{\prime}(a))$. Let us
parameterize by $u=1/\log(1/s)<1$; then

$\displaystyle
G=\frac{2\left(p^{1-au}-\mathrm{e}^{-1/u}\right)}{u}+\frac{(a-2)ap\log\left(\frac{1}{p}\right)}{(a-1)^{2}}.$

Now

$\displaystyle\frac{\partial G}{\partial
u}=-\frac{2\mathrm{e}^{-1/u}p^{-au}\left(-(u-1)p^{au}+ap\mathrm{e}^{1/u}u^{2}\log(p)+p\mathrm{e}^{1/u}u\right)}{u^{3}},$

and since both $u^{3}$ and $2\mathrm{e}^{-1/u}p^{-au}$ are non-negative, the
sign of $\frac{\partial G}{\partial u}$ is determined by

$\displaystyle
H=(u-1)p^{au}-ap\mathrm{e}^{1/u}u^{2}\log(p)-p\mathrm{e}^{1/u}u.$

Further,

$\displaystyle\frac{\partial H}{\partial
a}=u\log(p)\left((u-1)p^{au}-p\mathrm{e}^{1/u}u\right)\geq 0$

since $u<1$ and $\log p<0$. Thus, $H$ is maximized at $a=1$, with a value of

$\displaystyle
H_{1}=(u-1)p^{u}-p\mathrm{e}^{1/u}u^{2}\log(p)-p\mathrm{e}^{1/u}u.$

We now show that $H_{1}\leq 0$. We have $u\leq 1/3$ by the assumption
$s\leq\mathrm{e}^{-3}$. Then

$\displaystyle H_{1}$ $\displaystyle\leq$
$\displaystyle-\frac{2}{3}p^{1/3}-\mathrm{e}^{3}pu+u^{2}\mathrm{e}^{1/u}p\log\frac{1}{p}=:\tilde{H}_{1}.$

Now

$\displaystyle\frac{\partial\tilde{H}_{1}}{\partial u}$ $\displaystyle=$
$\displaystyle-p\left(e^{1/u}(1-2u)\log\frac{1}{p}+\mathrm{e}^{3}\right)\leq
0,$

whence $\tilde{H}_{1}$ is decreasing in $u$. Thus, to show that
$\tilde{H}_{1}<0$, it suffices to evaluate $\tilde{H}_{1}$ at the smallest
allowed value of $u=1/\log(1/p)$. The latter evaluates to

$\displaystyle-\frac{2}{3}p^{\frac{1}{\log\left(\frac{1}{p}\right)}}-\frac{\mathrm{e}^{3}p}{\log\left(\frac{1}{p}\right)}+\frac{1}{\log\left(\frac{1}{p}\right)},$

which is easily seen to be $\leq 0$ for $p\in[0,1/2]$. Indeed, parametrizing
$v=1/\log(1/p)$ and differentiating with respect to $v$, we get

$\displaystyle J(v)$ $\displaystyle:=$
$\displaystyle-\mathrm{e}^{3-\frac{1}{v}}v+v-\frac{2}{3e}$ $\displaystyle
J^{\prime}(v)$ $\displaystyle=$ $\displaystyle
1-\frac{\mathrm{e}^{3-\frac{1}{v}}(v+1)}{v}$ $\displaystyle
J^{\prime\prime}(v)$ $\displaystyle=$
$\displaystyle-\frac{\mathrm{e}^{3-\frac{1}{v}}}{v^{3}}<0.$

Solving for $J^{\prime}(v)=0$ yields
$v^{*}=\frac{1}{-W_{-1}\left(-\frac{1}{\mathrm{e}^{4}}\right)-1}\approx 0.21$,
where $W_{-1}$ is the Lambert $W$ function at the $-1$ branch. Since
$J(v^{*})\approx-0.071<0$, we conclude that $\tilde{H}_{1}(1/\log(1/p))\leq
0$.

It follows that $H\leq 0$, whence $\frac{\partial G}{\partial u}\leq 0$. Since
$G$ is decreasing in $u$, it is also decreasing in $s$ (because
$u(s)=1/\log(1/s)$ is monotonically increasing), and this it suffices to
evaluate $G$ at $s=p$, which yields

$\displaystyle\left(\frac{(a-2)ap}{(a-1)^{2}}+2\left(\mathrm{e}^{a}-1\right)(1-p)p\right)\log\left(\frac{1}{p}\right).$

Now

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}p}\left[\frac{(a-2)ap}{(a-1)^{2}}-2\left(\mathrm{e}^{a}-1\right)(1-p)p\right]=\frac{(a-2)a}{(a-1)^{2}}-2(\mathrm{e}^{a}-1)(1-2p)<0,$

so it suffices to consider $G$ at $s=p=0$, where it is $0$.

∎

###  4.2  Proof of Theorem 3

We argue that there is no loss of generality in assuming
$p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$: replacing
$X(j)$ by $1-X(j)$ does not affect $\Delta_{n}(\mu)$ — even in the non-product
case. Decompose:

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}{\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}\vee\left[p(j)-\hat{p}_{n}(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}+\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[p(j)-\hat{p}_{n}(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}.$

To bound the lower tail
$\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[p(j)-\hat{p}_{n}(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ we first invoke the Chernoff-type bound of
Okamoto (1959, Theorem 2, (ii)) (see also Boucheron et al. (2013, Exercise
2.1.2)) to obtain

$\displaystyle\mathop{\mathbb{P}}\left(p(j)-\hat{p}_{n}(j)\geq t\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{nt^{2}}{2p(j)(1-p(j))}\right),\qquad
j\in\mathbb{N},t\geq 0.$

Applying Lemma 8 with $Y_{j}=p(j)-\hat{p}_{n}(j)$ and
$\sigma_{j}^{2}=\frac{p(j)}{n}$ yields

$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[p(j)-\hat{p}_{n}(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$ $\displaystyle
4\sup_{j\in\mathbb{N}}\sqrt{\frac{p(j)}{n}\log(j+1)}\leq
4\sqrt{\frac{S(\mu)}{n}}.$ (8)

It remains to estimate the upper tail
$\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$. To this end, we decompose

$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)\geq\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}+\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ (9)

and focus on the first term
$\mathop{\mathbb{E}}\sup_{p(j)\geq\frac{1}{n}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$. For each $j$, we apply Bernstein’s
inequality (Wainwright, 2019, Proposition 2.14) to obtain

$\displaystyle\mathop{\mathbb{P}}\left(\hat{p}_{n}(j)-p(j)\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\varepsilon^{2}}{2\left(\frac{p(j)(1-p(j))}{n}+\frac{\varepsilon}{3n}\right)}\right),\qquad\varepsilon>0.$

Now invoke Lemma 9 with $Y_{i}=\hat{p}_{n}(i)-p(i),\
v_{i}=\frac{p(i)(1-p(i))}{n},\ a_{i}=\frac{1}{3n},\
I=\left\\{i\in\mathbb{N}\middle|p(i)\geq\frac{1}{n}\right\\}$ to yield

$\displaystyle\mathop{\mathbb{E}}{\sup_{p(j)\geq\frac{1}{n}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}}$ $\displaystyle\leq$ $\displaystyle
12\sup_{p(j)\geq\frac{1}{n}}\sqrt{\frac{p(j)(1-p(j))}{n}\log(j+1)}+\frac{16}{3n}\sup_{p(j)\geq\frac{1}{n}}\log(j+1)$
(10) $\displaystyle\leq$ $\displaystyle
12\sqrt{\frac{S(\mu)}{n}}+\frac{16}{3n}\sup_{p(j)\geq\frac{1}{n}}\log(j+1)$
$\displaystyle\leq$ $\displaystyle
12\sqrt{\frac{S(\mu)}{n}}+\frac{16T(\mu)\log n}{3n},$

where (10) holds because $\sup_{p(i)\geq
1/n}\frac{\log(i+1)}{\log(1/p(i))}\leq T$ implies $\log(i+1)\leq T\log n$. It
remains to estimate the second term in the right-hand side of (9), which we
decompose as

$\displaystyle\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-\frac{1}{n}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}+\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\frac{1}{n}-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ (11) $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-\frac{1}{n}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}+\frac{1}{n}.$

To upper-bound the first term
$\mathop{\mathbb{E}}\sup_{p(j)<\frac{1}{n}}\left[\hat{p}_{n}(j)-\frac{1}{n}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$, we will use Lemmas 1 and 9. Recall that
$p_{n}(j)-s:=\frac{1}{n}\sum_{i=1}^{n}X_{i}(j)-s$ where
$X_{i}(j)\sim\operatorname{Bernoulli}\left(p(j)\right)$ and
$X_{1}(j),X_{2}(j),\dots,X_{n}(j)$ are mutually independent. Let
$\mathrm{e}^{-3}>s\geq p(j)$ and let $0\leq t<\log(1/p(j))/\log(1/s).$ Then

$\displaystyle\mathop{\mathbb{E}}{\exp\left(t(p_{n}(j)-s)\right)}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\mathop{\mathbb{E}}{\exp\left(\frac{t}{n}(X_{i}(j)-s)\right)}$
$\displaystyle\leq$
$\displaystyle\prod_{i=1}^{n}\exp\left(\frac{p(j)t^{2}}{2n^{2}[1-t\log(1/s)/\
(n\log(1/p(j)))]}\right)$ $\displaystyle=$
$\displaystyle\exp\left(\frac{(p(j)/n)t^{2}}{2[1-t\log(1/s)/(n\log(1/p(j)))]}\right).$

Put $s={1}/{n}$ and apply Lemma 9 with $Y_{i}=\hat{p}_{n}(i)-\frac{1}{n}$,
$v_{i}=\frac{p(i)}{n}$, $a_{i}=\log(1/s)/(n\log(1/p(j)))$, and
$I=\left\\{i\in\mathbb{N}:p(i)<\frac{1}{n}\right\\}$, which yields, together
with (11),

$\displaystyle\mathop{\mathbb{E}}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
p(j)<\frac{1}{n}\end{subarray}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq
12\sup_{p(j)<\frac{1}{n}}\sqrt{\frac{p(j)}{n}\log(i+1)}+\frac{16\log(n)}{n}\sup_{p(j)<\frac{1}{n}}\frac{\log(j+1)}{\log(1/p(j))}+\frac{1}{n}$
$\displaystyle\leq 12\sqrt{\frac{S(\mu)}{n}}+\frac{16T(\mu)\log
n}{n}+\frac{1}{n}.$ (12)

Summing up (8), (10), and (12), we conclude that

$\displaystyle\Delta_{n}(\mu)\leq
28\left(\sqrt{\frac{S(\mu)}{n}}+\frac{T(\mu)\log n}{n}\right)+\frac{1}{n},$

which proves Theorem 3 for $T(\mu)$ sufficiently large — say,
$T(\mu)\geq\frac{1}{2}$. We now assume $T(\mu)<\frac{1}{2}$ and decompose as
in (9) but at a different the splitting point:

$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{j\leq
n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}+\mathop{\mathbb{E}}\sup_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}.$

In order to bound the first term, $\mathop{\mathbb{E}}\sup_{j\leq
n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$, we follow the same steps that we did to
bound
$\mathop{\mathbb{E}}\sup_{p(j)\geq\frac{1}{n}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ and get, instead of (10),

$\displaystyle\mathop{\mathbb{E}}\sup_{j\leq
n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$ $\displaystyle
12\sqrt{\frac{S(\mu)}{n}}+\frac{16}{3}\frac{T(\mu)\log n}{n({1-T(\mu)})}$ (13)
$\displaystyle\leq$ $\displaystyle
12\sqrt{\frac{S(\mu)}{n}}+11\frac{T(\mu)\log n}{n}.$

For the second term,
$\mathop{\mathbb{E}}\sup_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$, we note that for
$j>n^{\frac{T(\mu)}{1-T(\mu)}}$, we have

$\displaystyle
p(j)\leq\frac{1}{(j+1)^{1/T(\mu)}}\leq\frac{1}{\left(n^{\frac{T(\mu)}{1-T(\mu)}}+1\right)^{1/T(\mu)}}<\frac{1}{n}.$

It is well-known (Diaconis and Zabell, 1991; Berend and Kontorovich, 2013a,
Theorem 1) that for $p(j)\leq\frac{1}{n}$, we have
$\mathop{\mathbb{E}}\left|\hat{p}_{n}(j)-p(j)\right|\leq 2p(j)$. Consequently,

$\displaystyle\mathop{\mathbb{E}}\sup_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}\left[\hat{p}_{n}(j)-p(j)\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}\sup_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}\left|\hat{p}_{n}(j)-p(j)\right|$
(14) $\displaystyle\leq$
$\displaystyle\sum_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}2p(j)$ $\displaystyle\leq$
$\displaystyle\sum_{j>n^{\frac{T(\mu)}{1-T(\mu)}}}\frac{2}{(j+1)^{1/T(\mu)}}$
$\displaystyle\leq$
$\displaystyle\int_{{}_{\\!\\!\\!\\!\\!n^{\frac{T(\mu)}{1-T(\mu)}}}}^{\infty}\frac{2}{u^{1/T(\mu)}}\mathrm{d}u$
$\displaystyle=$
$\displaystyle\frac{2T(\mu)\left(n^{\frac{T(\mu)}{T(\mu)-1}}\right)^{\frac{1}{T(\mu)}-1}}{1-T(\mu)}$
$\displaystyle=$ $\displaystyle\frac{2T(\mu)}{n(1-T(\mu))}$
$\displaystyle\leq$ $\displaystyle\frac{4T(\mu)}{n}.$

Summing up (8), (13), and (14), we conclude

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle\leq$ $\displaystyle
16\left(\sqrt{\frac{S(\mu)}{n}}+\frac{T(\mu)}{n}\right)$

for $T(\mu)<\frac{1}{2}$. This completes the proof. ∎

###  4.3 Proof of Theorem 1

Theorem 3 immediately implies that $T(p)<\infty\implies p\in\mathsf{LGC}$.
Indeed, since $p\leq 1/\log(1/p)$, we have that $S(p)\leq T(p)$ and hence
$\Delta_{n}(\mu)\lesssim\sqrt{T(\mu)/n}+T(\mu)\log(n)/n$, which, for finite
$T(\mu)$, obviously decays to $0$ as $n\to\infty$.

The other direction, $p\in\mathsf{LGC}\implies T(p)<\infty$, is an immediate
consequence of Theorem 4. However, we find it instructive to give a more
elementary and intuitive (though less quantitative) proof, based on an
observation of Berend (2022). For any $p\in[0,1]^{\mathbb{N}}$, let us say
that it satisfies condition (B) if

$\displaystyle\text{(B)}\qquad\qquad\inf_{k\in\mathbb{N}}\sum_{j\in\mathbb{N}}p(j)^{k}<\infty$

(an appeal to Lebesgue’s monotone convergence theorem shows that the above
expression is either $0$ or $\infty$).

######  Lemma 2 (Berend (2022)).

If $p\in[0,1/2]^{\mathbb{N}}$ does not satisfy (B) then $\Delta_{n}(p)\geq
c>0$ for some absolute constant $c$.

###### Proof.

The negation of (B) means that $\sum_{j\in\mathbb{N}}p(j)^{k}=\infty$ for all
$k\in\mathbb{N}$. Thus,

$\displaystyle\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}|\hat{p}_{n}(j)-p(j)|$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\mathop{\mathbb{P}}\left(\sup_{j\in\mathbb{N}}\hat{p}_{n}(j)-p(j)\geq\frac{1}{2}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(1-\mathrm{e}^{-1}\right)\left(1\wedge\sum_{j\in\mathbb{N}}\mathop{\mathbb{P}}\left(\hat{p}_{n}(j)-p(j)\geq\frac{1}{2}\right)\right)\quad\text{(\cite[citet]{\@@bibref{Authors
Phrase1YearPhrase2}{van2014probability}{\@@citephrase{(}}{\@@citephrase{,
Problem~{}5.1a)}}})}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(1-\mathrm{e}^{-1}\right)\left(1\wedge\sum_{j\in\mathbb{N}}\mathop{\mathbb{P}}\left(\hat{p}_{n}(j)=1\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(1-\mathrm{e}^{-1}\right)\left(1\wedge\sum_{j\in\mathbb{N}}p(j)^{n}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\left(1-\mathrm{e}^{-1}\right).$

∎

######  Lemma 3.

For $p\in[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$, the
conditions (B) and $T(p)<\infty$ are equivalent.

Remark: Observe that (B) is permutation-invariant while $T(p)<\infty$ assumes
the decreasing ordering, hence the two conditions are only equivalent on
$[0,{\textstyle\frac{1}{2}}]^{\mathbb{N}}_{\downarrow 0}$.

###### Proof.

The direction $\text{(}B)\implies T(p)<\infty$ is obvious. Indeed,
$T(p)<\infty$ means that there is a $T>0$ such that $p(j)\leq 1/(j+1)^{1/T}$
for all $j\in\mathbb{N}$. Then
$\sum_{j=1}^{\infty}p(j)^{k}\leq\sum_{j=1}^{\infty}1/(j+1)^{k/T}<\infty$ for
$k>T$.

To show that $T(p)<\infty\implies\mathrm{(B)}$, assume $T(p)=\infty$ and
define $R(j):=\frac{\log(j+1)}{\log(1/p(j))}$, $j\in\mathbb{N}$; thus,
$T(p)=\sup_{j\in\mathbb{N}}R(j)$. We make two observations: (i)
$\limsup_{j\in\mathbb{N}}R(j)\geq T$ implies $p(j)\geq 1/(j+1)^{1/T}$ for
infinitely many $j$ and (ii) $R(j)\geq T$ implies $R(\lceil j/2\rceil)\geq
T-2$ via

$\displaystyle\log(\lceil j/2\rceil+1)/\log(1/p(\lceil j/2\rceil))$
$\displaystyle\geq$ $\displaystyle\log((j+2)/2)/\log(1/p(\lceil j/2\rceil))$
$\displaystyle\geq$ $\displaystyle(\log(j+2)-1)/\log(1/p(j))$
$\displaystyle\geq$ $\displaystyle(\log(j+1)-1)/\log(1/p(j))\geq R(j)-2,$

where the monotonicity of $p(j)$ was used. Assume, to get a contradiction,
that $\sum_{j\in\mathbb{N}}p(i)^{k}<\infty$ for some $k\in\mathbb{N}$ and
choose $T=2k+2$. By (i) and (ii) above, $R(j)\geq T$ and $R(\lceil
j/2\rceil)\geq T-2$ holds for infinitely many $j\in\mathbb{N}$. Invoking
monotonicity again,

$\displaystyle\sum_{i=1}^{\infty}p(i)^{k}$ $\displaystyle\geq$
$\displaystyle\sum_{i=\lceil j/2\rceil}^{j}p(i)^{k}$ $\displaystyle\geq$
$\displaystyle\sum_{i=\lceil j/2\rceil}^{j}\left[1/(i+1)^{1/(T-2)}\right]^{k}$
$\displaystyle\geq$ $\displaystyle\frac{j}{4}\cdot\frac{1}{(j+1)^{k/(T-2)}}$
$\displaystyle\geq$ $\displaystyle\frac{j}{4\sqrt{j+1}}.$

The latter holds for infinitely many $j$, whence the left-hand side is
unbounded — a contradiction. ∎

Combining Lemmas 2 and 3 immediately implies that $T(p)=\infty\implies
p\notin\mathsf{LGC}$.

###  4.4 Proof of Theorem 2

The upper estimate $\sqrt{n}\Delta_{n}(\mu)\lesssim\sqrt{S(\mu)}$ is immediate
from Theorem 3. Thus, it only remains to prove the lower estimate

$\displaystyle\liminf_{n\to\infty}\sqrt{n}\Delta_{n}(p)\geq c\sqrt{S(p)}$ (15)

for some absolute constant $c>0$. This result is actually subsumed in our
proof Theorem 4, but we include the somewhat simpler proof below, which also
has the advantage of yielding explicit constants.

We will use the following “Reverse Chernoff bound” due to Klein and Young
(2015, Lemma 4):

######  Lemma 4.

Suppose that $X\sim\operatorname{Binomial}(n,p)$, and $0<\varepsilon,p\leq
1/2$ satisfy $\varepsilon^{2}pn\geq 3$. Then

$\displaystyle\mathbb{P}(X\geq(1+\varepsilon)pn)$ $\displaystyle\geq$
$\displaystyle\exp\big{(}{-9\varepsilon^{2}pn}\big{)}.$

We will also use Berend and Kontorovich (2013a, Theorem 1):

######  Lemma 5.

Suppose that $n\geq 2$, $p\in[1/n,1-1/n]$, and
$X\sim\operatorname{Binomial}(n,p)$. Then

$\displaystyle\mathop{\mathbb{E}}|X-np|$ $\displaystyle\geq$
$\displaystyle\sqrt{\frac{1}{2}\mathop{\mathbb{E}}(X-np)^{2}}=\sqrt{\frac{1}{2}np(1-p)}$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}\sqrt{np},\qquad p\leq 1/2.$

Continuing with the proof of (15), we put
$\varepsilon=\sqrt{\frac{5\log(j+1)}{np(j)}}$. Then Lemma 4 implies that for
each $j\in\mathbb{N}$ verifying $\frac{20\log(j+1)}{n}\leq p(j),$

$\displaystyle\mathop{\mathbb{P}}\left(\left|\hat{p}_{n}(j)-p(j)\right|\geq\sqrt{\frac{5p(j)\log(j+1)}{n}}\right)$
$\displaystyle\geq$ $\displaystyle\frac{1}{\left(j+1\right)^{45}}.$

Since the $\hat{p}_{n}(j)$, $j\in\mathbb{N}$, are assumed to be independent,
for all natural $k\leq l$

$\displaystyle\mathbb{P}\left(\max_{j\in[k,l]}\left|\hat{p}_{n}(j)-p(j)\right|\leq\sqrt{\frac{5p(l)\log(k+1)}{n}}\right)\leq\left(1-\frac{1}{(k+1)^{45}}\right)^{l-k+1},$
(16)

whenever $p(l)\geq 20\log(k+1)/n$. For $k\in\mathbb{N}$, define

$\displaystyle
J(k):=\left\\{2^{45^{k-1}}-1,2^{45^{k-1}},2^{45^{k-1}}+1,2^{45^{k-1}}+2,\ldots,2^{45^{k}}\right\\}.$

A repeated application of (16) yields, for $p(2^{45^{k}})\geq
20\log(2^{45^{k-1}})/n$,

$\displaystyle\mathbb{P}\left(\max_{j\in
J(k)}\left|\hat{p}_{n}(j)-p(j)\right|\leq\frac{1}{\sqrt{45}}\sqrt{\frac{p(2^{45^{k}})\log{(2^{45^{k}})}}{n}}\right)$
$\displaystyle=\mathbb{P}\left(\max_{j\in
J(k)}\left|\hat{p}_{n}(j)-p(j)\right|\leq\sqrt{\frac{p(2^{45^{k}})\log{(2^{45^{k-1}})}}{n}}\right)$
$\displaystyle\leq\left(1-\frac{1}{2^{45^{k}}}\right)^{2^{45^{k}}-2^{45^{k-1}}}$
$\displaystyle\leq\exp\left(-2^{-45^{k}}\right)^{2^{45^{k}}-2^{45^{k-1}}}$
$\displaystyle=\exp\left(2^{-44\cdot 45^{k-1}}-1\right)$
$\displaystyle<\frac{1}{\mathrm{e}}.$

If follows that

$\displaystyle\Delta_{n}(p)$ $\displaystyle\geq$
$\displaystyle\max_{k\in\mathbb{N}}\mathop{\mathbb{E}}\max_{j\in
J(k)}\left|\hat{p}_{n}(j)-p(j)\right|$ (17) $\displaystyle\geq$
$\displaystyle\max_{\begin{subarray}{c}k\in\mathbb{N}\\\ np(2^{45^{k}})\geq
20\log\left(2^{45^{k-1}}\right)\end{subarray}}\left(1-\mathrm{e}^{-1}\right)\frac{1}{\sqrt{45}}\sqrt{\frac{p(2^{45^{k}})\log{(2^{45^{k}})}}{n}}$
$\displaystyle\geq$ $\displaystyle\max_{\begin{subarray}{c}k\in\mathbb{N}\\\
np(2^{45^{k}})\geq
20\log\left(2^{45^{k-1}}\right)\end{subarray}}\frac{1}{90}\sqrt{\frac{p(2^{45^{k}})\log{(2^{45^{k+1}})}}{n}}$
$\displaystyle\geq$ $\displaystyle\max_{\begin{subarray}{c}k\in\mathbb{N}\\\
np(2^{45^{k}})\geq 20\log\left(2^{45^{k-1}}\right)\end{subarray}}\max_{j\in
J(k+1)}\frac{1}{90}\sqrt{\frac{p(2^{45^{k}})\log{(j+1)}}{n}}$
$\displaystyle\geq$ $\displaystyle\max_{\begin{subarray}{c}k\in\mathbb{N}\\\
np(2^{45^{k}})\geq 20\log\left(2^{45^{k-1}}\right)\end{subarray}}\max_{j\in
J(k+1)}\frac{1}{90}\sqrt{\frac{p(j)\log{(j+1)}}{n}}$ $\displaystyle\geq$
$\displaystyle\max_{\begin{subarray}{c}k\in\mathbb{N}\end{subarray}}\max_{\begin{subarray}{c}j\in
J(k+1)\\\ np(j)\geq
20\log\left(j+1\right)\end{subarray}}\frac{1}{90}\sqrt{\frac{p(j)\log{(j+1)}}{n}}$
$\displaystyle=$
$\displaystyle\frac{1}{90\sqrt{n}}\max_{\begin{subarray}{c}j>2^{45}\\\
np(j)\geq 20\log\left(j+1\right)\end{subarray}}\sqrt{p(j)\log{(j+1)}}.$

Additionally, using
$\mathop{\mathbb{E}}\sup_{j\in\mathbb{N}}\left|\hat{p}_{n}(j)-p(j)\right|\geq\sup_{j\in\mathbb{N}}\mathop{\mathbb{E}}\left|\hat{p}_{n}(j)-p(j)\right|$
and Lemma 5 for $n\geq 2$, we have

$\displaystyle\Delta_{n}(p)$ $\displaystyle\geq$ $\displaystyle\max_{j\leq
2^{45}}\mathop{\mathbb{E}}\left|\hat{p}_{n}(j)-p(j)\right|$ (18)
$\displaystyle\geq$
$\displaystyle\frac{1}{2\sqrt{n}}\max_{\begin{subarray}{c}j\leq 2^{45}\\\
p(j)\geq\frac{1}{n}\end{subarray}}\sqrt{p(j)}$ $\displaystyle\geq$
$\displaystyle\frac{1}{90\sqrt{n}}\max_{\begin{subarray}{c}j\leq 2^{45}\\\
np(j)\geq 20\log\left(j+1\right)\end{subarray}}\sqrt{p(j)\log(j+1)}.$

Finally, we combine (17) and (18) to obtain

$\displaystyle\sqrt{n}\Delta_{n}(p)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sqrt{n}\Delta_{n}(p)+\frac{1}{2}\sqrt{n}\Delta_{n}(p)$
$\displaystyle\geq$
$\displaystyle\frac{1}{180}\max_{\begin{subarray}{c}j>2^{45}\\\ np(j)\geq
20\log\left(j+1\right)\end{subarray}}\sqrt{p(j)\log{(j+1)}}+\frac{1}{180}\max_{\begin{subarray}{c}j\leq
2^{45}\\\ np(j)\geq 20\log\left(j+1\right)\end{subarray}}\sqrt{p(j)\log(j+1)}$
$\displaystyle\geq$
$\displaystyle\frac{1}{180}\max_{\begin{subarray}{c}np(j)\geq
20\log\left(j+1\right)\end{subarray}}\sqrt{p(j)\log(j+1)}$

for $n\geq 2$. Taking limits yields (15), with $c=1/180$.

∎

###  4.5 Proof of Theorem 4

For $p,q\in(0,1)$, we define the Kullback-Leibler and $\chi^{2}$ divergences,
respectively, between the distributions $\operatorname{Bernoulli}(p)$ and
$\operatorname{Bernoulli}(q)$:

$\displaystyle D(p\parallel q)$ $\displaystyle=$ $\displaystyle
p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q},$ $\displaystyle\chi^{2}(p\parallel
q)$ $\displaystyle=$ $\displaystyle\frac{(p-q)^{2}}{q}+\frac{(p-q)^{2}}{1-q}.$

######  Lemma 6.

For $p\in(0,1/2]$ and $\varepsilon\in[0,1-p]$, we have

$\displaystyle D(\varepsilon+p\parallel p)$ $\displaystyle\leq$ $\displaystyle
2\min\left(\varepsilon\log(1/p),\frac{\varepsilon^{2}}{p}\right).$ (19)

###### Proof.

Gibbs and Su (2002, Theorem 5) states that $D(p\parallel
q)\leq\log(1+\chi^{2}(p\parallel q))$. Thus,

$\displaystyle D(p+\varepsilon\parallel p)$ $\displaystyle\leq$
$\displaystyle\log\left(1+\chi^{2}(p+\varepsilon\parallel p)\right)$
$\displaystyle=$
$\displaystyle\log\left(1+\frac{\varepsilon^{2}}{1-p}+\frac{\varepsilon^{2}}{p}\right)$
$\displaystyle\leq$
$\displaystyle\frac{\varepsilon^{2}}{1-p}+\frac{\varepsilon^{2}}{p}$
$\displaystyle=$ $\displaystyle\frac{\varepsilon^{2}}{p(1-p)},$
$\displaystyle\leq$ $\displaystyle\frac{2\varepsilon^{2}}{p}.$

The second inequality, $2\varepsilon\log(1/p)-D(p+\varepsilon\parallel p)\geq
0$, holds for endpoints $x=0$ and $x=1-p$ and

$\displaystyle\frac{\mathrm{d}^{2}}{\mathrm{d}x^{2}}\left[2\varepsilon\log(1/p)-D(p+\varepsilon\parallel
p)\right]=-\frac{1}{(1-p-x)(p+x)}\leq 0$

for $0<x<1-p$, such that $2\varepsilon\log(1/p)-D(p+\varepsilon\parallel p)$
is concave and hence non-negative in the claimed range. ∎

We will also make use of a result of Zhang and Zhou (2020, Theorem 9):

######  Lemma 7.

For any $\beta>1$ there exist constants $c_{\beta},C_{\beta}>0$, depending
only on $\beta$, such that whenever $0\leq\varepsilon\leq\frac{1-p}{\beta}$
and $\varepsilon+p\geq\frac{1}{n}$, we have

$\displaystyle\mathop{\mathbb{P}}\left(\hat{p}_{n}-p\geq\varepsilon\right)$
$\displaystyle\geq$ $\displaystyle
c_{\beta}\exp\left(-C_{\beta}nD(\varepsilon+p\parallel p)\right).$

###### Proof of Theorem 4.

For $k,l\in\mathbb{N}$, define

$\displaystyle\varepsilon(k,l)$ $\displaystyle:=$
$\displaystyle\max\left\\{\frac{\log(k+1)}{n\log(1/p(l))},\sqrt{\frac{p(l)\log(k+1)}{n}}\right\\},$
$\displaystyle\varepsilon(k)$ $\displaystyle:=$
$\displaystyle\varepsilon(k,k).$

Invoking Lemma 6 and Lemma 7 with $\beta=2$, we have that for each
$j\in\mathbb{N}$ verifying $\frac{1}{n}\leq\varepsilon(j)\leq\frac{1}{4}$,

$\displaystyle\mathop{\mathbb{P}}\left(\hat{p}_{n}(j)-p(j)\geq\varepsilon(j)\right)$
$\displaystyle\geq$ $\displaystyle
c_{2}\exp\left(-C_{2}nD(p(j)+\varepsilon(j)\parallel p(j))\right)$
$\displaystyle\geq$ $\displaystyle
c_{2}\exp\left(-2C_{2}n\min\left(\varepsilon\log(1/p(j)),\frac{\varepsilon(j)^{2}}{p(j)}\right)\right)$
$\displaystyle\geq$ $\displaystyle c_{2}\exp\left(-2C_{2}\log(j+1)\right)$
$\displaystyle=$ $\displaystyle\frac{c_{2}}{(j+1)^{2C_{2}}}.$

Since the $\hat{p}_{n}(j)$ are assumed to be independent, for all natural
$k\leq l$ we have

$\displaystyle\mathop{\mathbb{P}}\left(\max_{j\in[k,l]}\hat{p}_{n}(j)-p(j)\leq\varepsilon(k,l)\right)$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{P}}\left(\bigwedge_{j\in[k,l]}\hat{p}_{n}(j)-p(j)\leq\varepsilon(k,j)\right)$
(20) $\displaystyle\leq$
$\displaystyle\left(1-\frac{c_{2}}{(k+1)^{2C_{2}}}\right)^{l-k+1},$

whenever $\varepsilon(k)\leq\frac{1}{4}$ and
$\varepsilon(k,l)\geq\frac{1}{n}$. For $k\in\mathbb{N}$, define

$J(k):=\left\\{2^{(2C_{2})^{k-1}}-1,2^{(2C_{2})^{k-1}},2^{(2C_{2})^{k-1}}+1,2^{(2C_{2})^{k-1}}+2,\ldots,2^{(2C_{2})^{k}}\right\\}.$

where we assume without loss of generality $2C_{2}\in\mathbb{N}$. For
$k\in\mathbb{N}$, define

$\displaystyle\eta(k):=\varepsilon\left(2^{(2C_{2})^{k-1}}-1,2^{(2C_{2})^{k}}\right).$

A repeated application of (20) yields, for $k\in\mathbb{N}$ such that
$\eta(k)\geq\frac{1}{n}$ and
$\varepsilon\left(2^{(2C_{2})^{k-1}}-1\right)\leq\frac{1}{4}$,

$\displaystyle\mathop{\mathbb{P}}\left(\max_{j\in
J(k)}\hat{p}_{n}(j)-p(j)\leq\eta(k)\right)$ $\displaystyle\leq$
$\displaystyle\left(1-\frac{c_{2}}{(2^{(2C_{2})^{k-1}})^{2C_{2}}}\right)^{2^{(2C_{2})^{k}}-2^{(2C_{2})^{k-1}}}$
$\displaystyle=$
$\displaystyle\left(1-\frac{c_{2}}{2^{(2C_{2})^{k}}}\right)^{2^{(2C_{2})^{k}}-2^{(2C_{2})^{k-1}}}$
$\displaystyle\leq$
$\displaystyle\left(\exp\left(-\frac{c_{2}}{2^{(2C_{2})^{k}}}\right)\right)^{2^{(2C_{2})^{k}}-2^{(2C_{2})^{k-1}}}$
$\displaystyle=$
$\displaystyle\exp\left(-\frac{c_{2}}{2^{(2C_{2})^{k}}}\left(2^{(2C_{2})^{k}}-2^{(2C_{2})^{k-1}}\right)\right)$
$\displaystyle=$
$\displaystyle\exp\left(-c_{2}+c_{2}2^{(2C_{2})^{k-1}-2^{(2C_{2})^{k}}}\right)$
$\displaystyle<$ $\displaystyle\mathrm{e}^{-c_{2}}.$

It follows that

$\displaystyle\Delta_{n}(p)$ $\displaystyle\geq$
$\displaystyle\sup_{k\in\mathbb{N}}\mathop{\mathbb{E}}\max_{j\in
J(k)}\hat{p}_{n}(j)-p(j)$ (21) $\displaystyle\geq$
$\displaystyle\left(1-\mathrm{e}^{-c_{2}}\right)\sup_{k\in A}\eta(k)$
$\displaystyle=$ $\displaystyle\left(1-\mathrm{e}^{-c_{2}}\right)\sup_{k\in
A}\max\left\\{\frac{\log(2^{(2C_{2})^{k-1}})}{n\log(1/p(2^{(2C_{2})^{k}}))},\sqrt{\frac{p(2^{(2C_{2})^{k}})\log(2^{(2C_{2})^{k-1}})}{n}}\right\\}$
$\displaystyle\geq$
$\displaystyle\frac{1-\mathrm{e}^{-c_{2}}}{4C_{2}^{2}}\sup_{k\in A}\max_{j\in
J(k+1)}\max\left\\{\frac{\log(j+1)}{n\log(1/p(2^{(2C_{2})^{k}}))},\sqrt{\frac{p(2^{(2C_{2})^{k}})\log(j+1)}{n}}\right\\}$
$\displaystyle\geq$
$\displaystyle\frac{1-\mathrm{e}^{-c_{2}}}{4C_{2}^{2}}\sup_{k\in A}\max_{j\in
J(k+1)}\max\left\\{\frac{\log(j+1)}{n\log(1/p(j)))},\sqrt{\frac{p(j)\log(j+1)}{n}}\right\\}$
$\displaystyle\geq$
$\displaystyle\frac{1-\mathrm{e}^{-c_{2}}}{4C_{2}^{2}}\sup_{\begin{subarray}{c}j>2^{2C_{2}}\\\
{4C_{2}^{2}}\leq
n\varepsilon(j)\leq\frac{n}{16C_{2}^{2}}\end{subarray}}\varepsilon(j),$

where
$A:=\left\\{k\in\mathbb{N}:\varepsilon\left(2^{(2C_{2})^{k-1}}-1\right)\leq\frac{1}{4}\text{
and }\eta(k)\geq\frac{1}{n}\right\\}$.

It remains to handle the initial segment $J(1)$:

$\displaystyle\Delta_{n}(p)$ $\displaystyle\geq$ $\displaystyle\max_{j\in
J(1)}\mathop{\mathbb{E}}\hat{p}_{n}(j)-p(j)$ (22) $\displaystyle\geq$
$\displaystyle\max_{\begin{subarray}{c}j\in J(1)\\\
\frac{1}{n}\leq\varepsilon(j)\leq\frac{1}{4}\end{subarray}}\frac{c_{2}}{(j+1)^{2C_{2}}}\varepsilon(j)$
$\displaystyle\geq$
$\displaystyle\frac{c_{2}}{\left(2^{(2C_{2})}+1\right)^{2C_{2}}}\max_{\begin{subarray}{c}j\in
J(1)\\\
\frac{1}{n}\leq\varepsilon(j)\leq\frac{1}{4}\end{subarray}}\varepsilon(j).$

Combining (21) and (22) yields

$\displaystyle\Delta_{n}(p)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\Delta_{n}(p)+\frac{1}{2}\Delta_{n}(p)$
$\displaystyle\geq$
$\displaystyle\frac{1-\mathrm{e}^{-c_{2}}}{8C_{2}^{2}}\sup_{\begin{subarray}{c}j>2^{2C_{2}}\\\
\frac{4C_{2}^{2}}{n}\leq\varepsilon(j)\leq\frac{1}{16C_{2}^{2}}\end{subarray}}\varepsilon(j)+\frac{c_{2}}{2\left(2^{(2C_{2})}+1\right)^{2C_{2}}}\max_{\begin{subarray}{c}j\in
J(1)\\\
\frac{1}{n}\leq\varepsilon(j)\leq\frac{1}{4}\end{subarray}}\varepsilon(j)$
$\displaystyle\geq$
$\displaystyle\min\left\\{\frac{c_{2}}{2\left(2^{(2C_{2})}+1\right)^{2C_{2}}},\frac{1-\mathrm{e}^{-c_{2}}}{8C_{2}^{2}}\right\\}\sup_{\begin{subarray}{c}j\in\mathbb{N}\\\
{4C_{2}^{2}}\leq
n\varepsilon(j)\leq\frac{n}{16C_{2}^{2}}\end{subarray}}\varepsilon(j).$

Since for every fixed $j\in\mathbb{N}$, the condition ${4C_{2}^{2}}\leq
n\varepsilon(j)\leq\frac{n}{16C_{2}^{2}}$ is eventually satisfied as
$n\to\infty$, the claim is proved. ∎

###  4.6 Proof of Theorem 5

We start by, conditionally on $\tilde{X}_{i}$, defining the class
$F=\left\\{f_{j}:j\in\mathbb{N}\right\\}$ over
$\Omega=\left\\{0,1\right\\}^{\mathbb{N}}$, where
$f_{j}(x)=(1-a(j))x(j)+a(j)(1-x(j))$ and observing that

$\displaystyle\Delta_{n}(\mu)$ $\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}\sup_{f\in
F}\left|n^{-1}\sum_{i=1}^{n}f(X_{i})-\mathop{\mathbb{E}}f(X_{i})\right|.$

Combining with Wainwright (2019, Proposition 4.11) — a standard symmetrization
argument — we get

$\displaystyle\Delta_{n}(\mu)\leq 2R_{n}(F),$ (23)

where

$\displaystyle\hat{R}_{n}(F;X):=\mathop{\mathbb{E}}_{\varepsilon}\sup_{f\in
F}\left|n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\right|$ $\displaystyle
R_{n}(F):=\mathop{\mathbb{E}}_{X}\hat{R}_{n}(F;X)=\mathop{\mathbb{E}}_{\varepsilon,X}\sup_{f\in
F}\left|n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\right|$

are the (empirical and expected, respectively) _Rademacher complexities_ ; the
$\varepsilon_{i},i\in[n]$ are independent Rademacher random variables defined
by $\mathbb{P}(\varepsilon_{i}=1)=\mathbb{P}(\varepsilon_{i}=-1)=1/2$. Since
$\hat{R}_{n}(F;X)$ has $2/n$-bounded differences as a function of
$X_{1},X_{2},...X_{n}$, we can invoke McDiarmid’s inequality (Boucheron et
al., 2013, Theorem 6.2) to obtain, for all $\delta\geq 0$,

$\displaystyle\mathop{\mathbb{P}}\left(\Delta_{n}(\mu)\leq
2\hat{R}_{n}(F;X)+2\sqrt{\frac{2}{n}\log\frac{1}{\delta}}\right)$
$\displaystyle\geq\mathop{\mathbb{P}}\left(R_{n}(F)\leq
2\hat{R}_{n}(F;X)+2\sqrt{\frac{2}{n}\log\frac{1}{\delta}}\right)$ [by (23)]
$\displaystyle\geq 1-\delta.$ (24)

We now turn to bounding $\hat{R}_{n}(F;X)$, by bounding the moment-generating
function (conditional on $X_{i}$) of each
$n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f_{j}(X_{i})$ for $j\in\mathbb{N}$ via
Hoeffding’s lemma. Evidently, for $\lambda\geq 0$, we have

$\displaystyle\mathop{\mathbb{E}}_{\varepsilon}\exp\left(\lambda\left(n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f_{j}(X_{i})\right)\right)$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\mathop{\mathbb{E}}_{\varepsilon_{i}}\exp\left(\lambda\left(n^{-1}\varepsilon_{i}f_{j}(X_{i})\right)\right)$
$\displaystyle\leq$
$\displaystyle\prod_{i=1}^{n}\exp\left(\lambda^{2}\frac{(1-a(j))X_{i}(j)+a(j)(1-X_{i}(j))}{2n^{2}}\right)$
$\displaystyle=$
$\displaystyle\exp\left(\lambda^{2}\sum_{i=1}^{n}\frac{1-a(j))X_{i}(j)+a(j)(1-X_{i}(j))}{2n^{2}}\right)$
$\displaystyle=$
$\displaystyle\exp\left(\lambda^{2}\frac{1}{2n}\tilde{p}_{n}(j)\right).$

By the Cramér-Chernoff method,

$\displaystyle\mathop{\mathbb{P}}_{\varepsilon}\left(n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f_{j}(X_{i})\geq
t\right)$ $\displaystyle\leq$ $\displaystyle\inf_{\lambda\geq
0}\frac{\exp\left(\lambda^{2}\frac{1}{2n}\tilde{p}_{n}(j)\right)}{\mathrm{e}^{t\lambda}}=\exp\left(-\frac{nt^{2}}{2\tilde{p}_{n}(j)}\right).$

Conditional on $X_{1},X_{2},...,X_{n}$, we apply Lemma 8 with
$Y_{j}=n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f_{j}(X_{i})$,
$\sigma^{2}_{j}=\frac{\tilde{p}_{n}(j)}{n}$ and arrive with a bound for
$\hat{R}_{n}(F;X)$;

$\displaystyle\hat{R}_{n}(F;X)$
$\displaystyle:=\mathop{\mathbb{E}}_{\varepsilon}\sup_{f\in
F}\left|n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\right|$
$\displaystyle\leq\mathop{\mathbb{E}}_{\varepsilon}\sup_{f\in
F}\left[n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}+\mathop{\mathbb{E}}_{\varepsilon}\sup_{f\in
F}\left[n^{-1}\sum_{i=1}^{n}-\varepsilon_{i}f(X_{i})\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$
$\displaystyle=2\mathop{\mathbb{E}}_{\varepsilon}\sup_{f\in
F}\left[n^{-1}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ (symmetry of $\varepsilon_{i}$)
$\displaystyle\leq
8\frac{1}{\sqrt{n}}\sup_{j\in\mathbb{N}}\sqrt{{\tilde{p}_{n}}^{\downarrow}(j)\log(j+1)}$
(reindexing)
$\displaystyle=\frac{8}{\sqrt{n}}\sqrt{S({\tilde{p}_{n}}^{\downarrow}(j))}.$

Substituting into (24) yields

$\displaystyle\mathop{\mathbb{P}}_{X}\left(\Delta_{n}(\mu)\leq\frac{16}{\sqrt{n}}\sqrt{S({\tilde{p}_{n}}^{\downarrow})}+\sqrt{\frac{8}{n}\log\frac{1}{\delta}}\right)$
$\displaystyle\geq 1-\delta,$ (25)

for all $\delta>0$. Taking $\mathop{\mathbb{E}}_{\tilde{X}}[\cdot]$ on both
sized completes the proof. ∎

##  5 Auxiliary results

###  5.1 VC bounds

If $\Omega$ is a set and $F\subset\\{0,1\\}^{\Omega}$, we say that $F$
shatters an $A\subseteq\Omega$ if $F(A)=\\{0,1\\}^{A}$, where
$F(A)=\left.F\right|_{A}$ is the restriction of $F$ to $A$. The Vapnik-
Chervonenkis (VC) dimension of $F$ is the maximal size of any shattered set
(possibly, $\infty$), and is denoted $\operatorname{vc}(F)$. We refer the
reader to Anthony and Bartlett (1999) for background on this central learning-
theoretic quantity, including its role in the upper and lower generalization
error bounds.

Let us consider the specific function class relevant to this paper and analyze
its VC-dimension.

######  Proposition 1.

Consider $F=\left\\{f_{j}:j\in[d]\right\\}$ over
$\Omega=\left\\{0,1\right\\}^{d}$, where $f_{j}(x)=x(j)$. Then
$\operatorname{vc}(F)=\left\lfloor\log_{2}d\right\rfloor$.

###### Proof.

The upper bound $\operatorname{vc}(F)\leq\left\lfloor\log_{2}d\right\rfloor$
is trivial since
$\operatorname{vc}(F)\leq\left\lfloor\log_{2}|F|\right\rfloor$ always holds.
For the lower bound, there is no loss of generality in assuming $d=2^{k}$ for
some $k\in\mathbb{N}$; it remains to exhibit a shattered
$A\subset\left\\{0,1\right\\}^{2^{k}}$ of size $k$. To this end, we will
define a $k\times 2^{k}$ matrix, whose $k$ rows will correspond to the
shattered set $A$, as follows. Define the $i$th column of $A$ to be the
integer $i-1\in[2^{k}-1]$ in binary representation. Thus, for example, for
$k=3$, we get
$A=\left\\{x_{1}=00001111,x_{2}=00110011,x_{3}=01010101\right\\}$. It is
straightforward to verify that $F$ indeed shatters $A$. ∎

######  Corollary 1.

There is an absolute constant $c>0$ such that for any estimator mapping
$(x_{1},\ldots,x_{n})\in\left(\left\\{0,1\right\\}^{d}\right)^{n}$ to
$\tilde{p}_{n}\in[0,1]^{d}$ there is a distribution $\mu$ on
$\left\\{0,1\right\\}^{d}$ such that

$\displaystyle\mathop{\mathbb{E}}\left\|\tilde{p}_{n}-p\right\|_{\infty}$
$\displaystyle\geq$ $\displaystyle 1\wedge c\sqrt{\frac{\log d}{n}}.$ (26)

###### Proof.

Whenever $|\Omega|=k$ and $F=\left\\{0,1\right\\}^{\Omega}$, there is a
natural one-to-one correspondence between $A\subseteq\Omega$ and its indicator
$f_{A}:\Omega\to\left\\{0,1\right\\}$. Therefore, for any two distributions
$\mu,\nu$ on $\Omega$, we have

$\displaystyle\left\|\mu-\nu\right\|_{\textup{\tiny{TV}}}:=\max_{A\subset\Omega}|\mu(A)-\nu(A)|=\max_{f\in
F}\left|\mathop{\mathbb{E}}_{X\sim\mu}f(X)-\mathop{\mathbb{E}}_{X\sim\nu}f(X)\right|.$
(27)

For any distribution $\mu$ on $\Omega$ and $F=\left\\{0,1\right\\}^{\Omega}$,
define $\bar{\varphi}\in[0,1]^{F}$ by
$\bar{\varphi}(f)=\mathop{\mathbb{E}}_{X\sim\mu}f(X)$. It follows that
estimating $\bar{\varphi}$ under $\left\|\cdot\right\|_{\infty}$ up to
additive error $\varepsilon$ is equivalent to estimating $\mu$ under
$\left\|\cdot\right\|_{\textup{\tiny{TV}}}$ up to additive error
$\varepsilon$. But the latter problem is well-known to have a worst-case
sample complexity of $\Theta(k/\varepsilon^{2})$ (Anthony and Bartlett, 1999;
Kamath et al., 2015; Kontorovich and Pinelis, 2019). Adapting this to the
collection of $2^{k}$ functions that shatter the set $A$ constructed in
Proposition 1 yields (26). ∎

###  5.2 Maximal inequalities

######  Lemma 8 (Maximal inequality for inhomogeneous sub-Gaussians).

Let $Y_{1},Y_{2},...$ be random variables and $\sigma_{1},\sigma_{2},...$
positive real numbers such that

$\displaystyle\mathop{\mathbb{P}}\left(Y_{i}\geq t\right)\leq
e^{-t^{2}/2\sigma_{i}^{2}},\qquad i\in\mathbb{N},~{}t\geq 0.$

Let

$\displaystyle T$ $\displaystyle:=$
$\displaystyle\sup_{i\in\mathbb{N}}\sigma_{i}^{2}\log(i+1).$

Then

$\displaystyle\mathop{\mathbb{E}}\sup_{i\in\mathbb{N}}\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$ $\displaystyle\leq$ $\displaystyle
4\sqrt{T}.$

###### Proof.

By the union bound, for $t^{2}>2T$ we have

$\displaystyle\mathop{\mathbb{P}}\left(\sup_{i\in\mathbb{N}}\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}\geq t\right)$
$\displaystyle\leq\sum_{i=1}^{\infty}\mathop{\mathbb{P}}\left(\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}\geq t\right)$
$\displaystyle=\sum_{i=1}^{\infty}\mathop{\mathbb{P}}\left(Y_{i}\geq t\right)$
$\displaystyle\leq\sum_{i=1}^{\infty}\mathrm{e}^{-t^{2}/2\sigma_{i}^{2}}$
$\displaystyle\leq\sum_{i=1}^{\infty}\mathrm{e}^{-t^{2}\log(i+1)/2T}$
$\displaystyle=\sum_{i=2}^{\infty}i^{-t^{2}/2T}$
$\displaystyle\leq\int_{1}^{\infty}u^{-t^{2}/2T}\mathrm{d}u$
$\displaystyle=\frac{2T}{t^{2}-2T}.$

Integrating,

$\displaystyle\mathop{\mathbb{E}}\sup_{i\in\mathbb{N}}\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}$
$\displaystyle\leq\int_{0}^{\infty}\mathop{\mathbb{P}}\left(\sup_{i\in\mathbb{N}}\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}\geq t\right)\mathrm{d}t$ $\displaystyle\leq
2\sqrt{T}+\int_{2\sqrt{T}}^{\infty}\frac{2T}{t^{2}-2T}\mathrm{d}t$
$\displaystyle=2\sqrt{T}+\sqrt{T}\frac{-\log\left(3-2\sqrt{2}\right)}{\sqrt{2}}$
$\displaystyle\leq 4\sqrt{T}.$

∎

######  Lemma 9 (Maximal inequality for inhomogeneous sub-gammas).

Let $Y_{i\in I\subseteq\mathbb{N}}$ random variables such that, for each $i\in
I$, there are $v_{i}>0$ and $a_{i}\geq 0$ satisfying either of the conditions

  1. (a)

For all $0<t<\frac{1}{a_{i}}$ (or all $0<t$ if $a_{i}=0$),

$\displaystyle\mathop{\mathbb{E}}[\exp(tY_{i})]$ $\displaystyle\leq$
$\displaystyle\exp\left(\frac{v_{i}t^{2}}{2[1-a_{i}t]}\right).$

  2. (b)

For all $\varepsilon\geq 0$,

$\displaystyle\mathop{\mathbb{P}}\left(Y_{i}\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\varepsilon^{2}}{2(v_{i}+a_{i}\varepsilon)}\right).$

Then

$\displaystyle\mathop{\mathbb{E}}{\sup_{i\in
I}\left[Y_{i}\right]_{\scalebox{0.5}{ \\!\\!\\!\\!\\! $\boldsymbol{+}$}}}$
$\displaystyle\leq$ $\displaystyle 12\sup_{i\in
I}\sqrt{v_{i}\log(i+1)}+16\sup_{i\in I}a_{i}\log(i+1).$ (28)

Remark: It is instructive to compare this to Boucheron et al. (2013, Corollary
2.6), which estimates $\mathop{\mathbb{E}}\sup_{i\in
I}Y_{i}\lesssim\sqrt{v\log d}+a\log d$ in the finite, homogeneous special case
$v_{i}\equiv v$, $a_{i}\equiv a$, and $|I|=d$.

###### Proof.

To streamline the proof we only consider the case where $a_{i}>0$ for all
$i\in I$; the argument is analogous if some of them are zero. By Cramér-
Chernoff’s method, any $Y_{i}$ satisfying (a) also satisfies (b):

$\displaystyle\mathop{\mathbb{P}}\left(Y_{i}\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\inf_{0<t<\frac{1}{a}}\frac{\exp\left(\frac{v_{i}t^{2}}{2[1-a_{i}t]}\right)}{\mathrm{e}^{t\varepsilon}}$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\varepsilon^{2}}{2(v_{i}+a_{i}\varepsilon)}\right).$

Hence, for each $i\in I$ and all $\delta>0$,

$\displaystyle\mathop{\mathbb{P}}\left(\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}\geq\sqrt{2v_{i}\log\frac{1}{\delta}}+2a_{i}\log\frac{1}{\delta}\right)$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{P}}\left(Y_{i}\geq\sqrt{2v_{i}\log\frac{1}{\delta}+\left(a_{i}\log\frac{1}{\delta}\right)^{2}}+a_{i}\log\frac{1}{\delta}\right)$
(29) $\displaystyle\leq$ $\displaystyle\delta$

where we used the subadditivity of $\sqrt{\cdot}$. Applying the union bound to
the family of inequalities in (29),

$\displaystyle\mathop{\mathbb{P}}\left(\sup_{i\in
I}\left[Y_{i}\right]_{\scalebox{0.5}{ \\!\\!\\!\\!\\!
$\boldsymbol{+}$}}\geq\sup_{i\in
I}\sqrt{2v_{i}\log\frac{i(i+1)}{\delta}}+2a_{i}\log\frac{i(i+1)}{\delta}\right)$
$\displaystyle\leq\sum_{i\in I}$
$\displaystyle\mathop{\mathbb{P}}\left(\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\! $\boldsymbol{+}$}}\geq\sup_{i\in
I}\sqrt{2v_{i}\log\frac{i(i+1)}{\delta}}+2a_{i}\log\frac{i(i+1)}{\delta}\right)$
$\displaystyle\leq\sum_{i\in I}$
$\displaystyle\mathop{\mathbb{P}}\left(\left[Y_{i}\right]_{\scalebox{0.5}{
\\!\\!\\!\\!\\!
$\boldsymbol{+}$}}\geq\sqrt{2v_{i}\log\frac{i(i+1)}{\delta}}+2a_{i}\log\frac{i(i+1)}{\delta}\right)$
$\displaystyle\leq\sum_{i\in I}$
$\displaystyle\frac{\delta}{i(i+1)}\leq\sum_{i\in
I}\frac{\delta}{i(i+1)}=\delta.$

Let $Y:=\sup_{i\in I}\left[Y_{i}\right]_{\scalebox{0.5}{ \\!\\!\\!\\!\\!
$\boldsymbol{+}$}},\ a_{i}^{*}:=\sup_{i\in I}a_{i},\ v_{i}^{*}:=\sup_{i\in
I}v_{i}^{*}$ and note that the above bound implies

$\displaystyle\mathop{\mathbb{P}}\left(Y-\sup_{i\in I}\left(\sqrt{2v_{i}\log
i(i+1)}+2a_{i}\log
i(i+1)\right)\geq\max\left(\sqrt{8v_{i}^{*}\log\frac{1}{\delta}},4a_{i}^{*}\log\frac{1}{\delta}\right)\right)$
$\displaystyle\leq$ $\displaystyle\delta.$

Let $Z:=Y-\sup_{i\in I}\left(\sqrt{2v_{i}\log i(i+1)}+2a_{i}\log
i(i+1)\right)$. By a change of variable,

$\displaystyle\mathop{\mathbb{P}}\left(Z\geq\varepsilon\right)$
$\displaystyle\leq$
$\displaystyle\exp{\left(-\frac{\varepsilon^{2}}{8v_{i}^{*}}\right)}\vee\exp{\left(-\frac{\varepsilon}{4a_{i}^{*}}\right)}$
$\displaystyle\leq$
$\displaystyle\exp{\left(-\frac{\varepsilon^{2}}{8v_{i}^{*}}\right)}+\exp{\left(-\frac{\varepsilon}{4a_{i}^{*}}\right)}.$

Integrating,

$\displaystyle\mathop{\mathbb{E}}{Z}$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\mathop{\mathbb{P}}\left(Z\geq\varepsilon\right)\mathrm{d}\varepsilon$
$\displaystyle\leq$
$\displaystyle\int_{0}^{\infty}\exp{\left(-\frac{\varepsilon^{2}}{8v_{i}^{*}}\right)}+\exp{\left(-\frac{\varepsilon}{4a_{i}^{*}}\right)}\mathrm{d}\varepsilon$
$\displaystyle=$ $\displaystyle\sqrt{2\pi v_{i}^{*}}+4a_{i}^{*};$

this proves (28). ∎

#### Acknowledgements.

We thank Daniel Berend and Steve Hanneke for the numerous helpful discussions.

## References

  * Anthony and Bartlett [1999] Martin Anthony and Peter L. Bartlett.  _Neural Network Learning: Theoretical Foundations_.  Cambridge University Press, Cambridge, 1999.  ISBN 0-521-57353-X.  doi: 10.1017/CBO9780511624216.  URL http://dx.doi.org/10.1017/CBO9780511624216.
  * Berend [2022] Daniel Berend.  Private communication, 2022.
  * Berend and Kontorovich [2013a] Daniel Berend and Aryeh Kontorovich.  A sharp estimate of the binomial mean absolute deviation with applications.  _Statistics & Probability Letters_, 83(4):1254–1259, 2013a.
  * Berend and Kontorovich [2013b] Daniel Berend and Aryeh Kontorovich.  On the concentration of the missing mass.  _Electron. Commun. Probab._ , 18:no. 3, 1–7, 2013b.  ISSN 1083-589X.  doi: 10.1214/ECP.v18-2359.  URL http://ecp.ejpecp.org/article/view/2359.
  * Boucheron et al. [2013] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration inequalities_.  Oxford University Press, Oxford, 2013.  ISBN 978-0-19-953525-5.  doi: 10.1093/acprof:oso/9780199535255.001.0001.  URL http://dx.doi.org/10.1093/acprof:oso/9780199535255.001.0001.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * Buldygin and Moskvichova [2013] V. V. Buldygin and K. K. Moskvichova.  The sub-gaussian norm of a binary random variable.  _Theory of Probability and Mathematical Statistics_ , 86:33–49, August 2013.  doi: 10.1090/s0094-9000-2013-00887-4.  URL https://doi.org/10.1090/s0094-9000-2013-00887-4.
  * Cherapanamjeri et al. [2019] Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett.  Fast mean estimation with sub-gaussian rates.  In Alina Beygelzimer and Daniel Hsu, editors, _Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA_ , volume 99 of _Proceedings of Machine Learning Research_ , pages 786–806. PMLR, 2019\.  URL http://proceedings.mlr.press/v99/cherapanamjeri19b.html.
  * Cherapanamjeri et al. [2020] Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter L. Bartlett, and Michael I. Jordan.  Optimal mean estimation without a variance.  _CoRR_ , abs/2011.12433, 2020.  URL https://arxiv.org/abs/2011.12433.
  * Devroye et al. [2016] Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira.  Sub-Gaussian mean estimators.  _The Annals of Statistics_ , 44(6):2695 – 2725, 2016.  doi: 10.1214/16-AOS1440.  URL https://doi.org/10.1214/16-AOS1440.
  * Diaconis and Zabell [1991] Persi Diaconis and Sandy Zabell.  Closed form summation for classical distributions: variations on a theme of de Moivre.  _Statist. Sci._ , 6(3):284–302, 1991.
  * Gibbs and Su [2002] Alison L. Gibbs and Francis E. Su.  On choosing and bounding probability metrics.  _International Statistical Review_ , 70(3):419–435, 2002.
  * Kallenberg [2002] Olav Kallenberg.  _Foundations of modern probability. Second edition. Probability and its Applications_.  Springer-Verlag, 2002.
  * Kamath et al. [2015] Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh.  On learning distributions from their samples.  In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, _Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015_ , volume 40 of _JMLR Workshop and Conference Proceedings_ , pages 1066–1100. JMLR.org, 2015.  URL http://proceedings.mlr.press/v40/Kamath15.html.
  * Kearns and Saul [1998] Michael J. Kearns and Lawrence K. Saul.  Large deviation methods for approximate probabilistic inference.  In _UAI_ , 1998.
  * Klein and Young [2015] Philip Klein and Neal E. Young.  On the number of iterations for dantzig–wolfe optimization and packing-covering approximation algorithms.  _SIAM Journal on Computing_ , 44(4):1154–1172, 2015.  doi: 10.1137/12087222X.  URL https://doi.org/10.1137/12087222X.
  * Kontorovich and Pinelis [2019] Aryeh Kontorovich and Iosif Pinelis.  Exact lower bounds for the agnostic probably-approximately-correct (pac) machine learning model.  _Ann. Statist._ , 47(5):2822–2854, 2019.  ISSN 0090-5364.  doi: 10.1214/18-AOS1766.
  * Lugosi and Mendelson [2019a] Gábor Lugosi and Shahar Mendelson.  Sub-Gaussian estimators of the mean of a random vector.  _The Annals of Statistics_ , 47(2):783 – 794, 2019a.  doi: 10.1214/17-AOS1639.  URL https://doi.org/10.1214/17-AOS1639.
  * Lugosi and Mendelson [2019b] Gábor Lugosi and Shahar Mendelson.  Mean estimation and regression under heavy-tailed distributions: A survey.  _Found. Comput. Math._ , 19(5):1145–1190, 2019b.  doi: 10.1007/s10208-019-09427-x.  URL https://doi.org/10.1007/s10208-019-09427-x.
  * Lugosi and Mendelson [2021] Gábor Lugosi and Shahar Mendelson.  Robust multivariate mean estimation: The optimality of trimmed mean.  _The Annals of Statistics_ , 49(1):393 – 410, 2021.  doi: 10.1214/20-AOS1961.  URL https://doi.org/10.1214/20-AOS1961.
  * Okamoto [1959] Masashi Okamoto.  Some inequalities relating to the partial sum of binomial probabilities.  _Annals of the institute of Statistical Mathematics_ , 10(1):29–35, 1959.
  * Thomas [2018] Thomas.  Is uniform convergence faster for low-entropy distributions?  Theoretical Computer Science Stack Exchange, 2018.  URL https://cstheory.stackexchange.com/q/42009.  URL:https://cstheory.stackexchange.com/q/42009 (version: 2018-12-10).
  * Van Handel [2014] Ramon Van Handel.  Probability in high dimension.  Technical report, PRINCETON UNIV NJ, 2014.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Zhang and Zhou [2020] Anru R. Zhang and Yuchen Zhou.  On the non-asymptotic and sharp lower tail bounds of random variables.  _Stat_ , 9(1):e314, 2020.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/sta4.314.