# The suprema of selector processes with the application to positive
infinitely divisible processes111The authors were supported by National
Science Centre, Poland grants 2019/35/B/ST1/04292 (W. Bednorz) and
2021/40/C/ST1/00330 (R. Meller).

Witold Bednorz222Institute of Mathematics, University of Warsaw, Banacha 2,
02-097 Warsaw, Poland., Rafał Martynek333University of Luxembourg, Maison du
Nombre, 6, Avenue de la Fonte, Esch-sur-Alzette, Luxembourg. and Rafał
Meller444Institute of Mathematics, Polish Academy of Sciences, Śniadeckich 8,
00-656 Warsaw, Poland.

###### Abstract

We provide an alternative proof of the recent result by Park and Pham (2022)
on the expected suprema of positive selector and empirical processes. We
extend it to positive infinitely divisible processes.
Keywords:  expected suprema, positive processes, $p$-smallness.
AMS MSC 2010:  60G15, 60G17.

##  1 Introduction

The recent results (see [8], [2]) show that the size of expected suprema of
empirical processes processes as well as of infinitely divisible processes can
be explained by decomposing the initial index set into a sum of two new index
sets. The size of the process defined on one of them is characterized with
Talagrand’s gamma numbers while the process defined on the other index set is
a positive process. The understanding of the size of positive processes was
missing and some conjectures were posed by Talagrand. Recently, some of them
were discussed and proved in [4].
The general idea is to relate the size of the stochastic process with the
geometry of the index set. This gives a rise to the very efficient method of
chaining and in turn the characterization in terms of gamma functionals. The
best known result in this area is the Majorizing Measure Theorem (see e.g. [8,
Theorem 2.10.1]) concerning Gaussian processes. One of the geometric
consequences of this result is that the construction of the partition provides
also in some sense ”witnesses” of the size of the supremum. Let us briefly
explain this concept (cf. discussion after Theorem 2.12.2 and Section 13.2 in
[8]). Let $(G_{t})_{t\in T}$ be a Gaussian process on some index set $T$. By
the Majorizing Measure Theorem one can find a jointly Gaussian sequence
$(u_{k})_{k\geqslant 1}$ such that for some universal constant $L>0$ it holds
that

$\left\\{\sup_{t\in T}|G_{t}|\geqslant L\mathbf{E}\sup_{t\in
T}|G_{t}|\right\\}\subset\left\\{u_{k}\geqslant 1\right\\}$

and

$\sum_{k\geqslant 1}\mathbf{P}(u_{k}\geqslant 1)\leqslant\frac{1}{2}.$

Let us emphasize that the above statement is weaker than the Majorizing
Measure Theorem in the sense that it follows relatively easy from it however
the other direction is not clear at all. Now, since chaining seems out of
reach in the case when in the considered random series of functions we have no
cancellations i.e. in the case of positive processes, the goal is to provide a
characterization in the spirit of the above display.

##  2 Results

Our first aim is to present a new proof of the result in [4] concerning a
positive selector process. Consider a sequence $(\delta_{i})_{i=1}^{n}$ of
independent Bernoulli random variables with

$\mathbf{P}(\delta_{i}=1)=p=1-\mathbf{P}(\delta_{i}=0)$

for some $p\in(0,1)$ and a set $T$ of sequences $t=(t_{i})_{i=1}^{n}$ with
$t_{i}\geqslant 0$. We assume that $T$ is finite. Let

$\delta(T):=\mathbf{E}\sup_{t\in T}\sum_{i=1}^{n}t_{i}\delta_{i}.$

We use the notation $[n]=\\{1,2,\dots,n\\}$. In order to describe the size of
$\delta(T)$ we want to construct ”explicit witnesses” of the event

$\left\\{\sup_{t\in T}\sum_{i=1}^{n}t_{i}\delta_{i}\geqslant
L\delta(T)\right\\}$

whose measure is small. To formalize this goal let us recall the notions of
up-sets and $p$-smallness. Let $S\subseteq[n]$. Then the up-set generated by
$S$ is defined as

$\langle S\rangle=\left\\{T\subseteq[n]:T\supseteq S\right\\}$

and we say that the collection ${\cal F}$ of subsets of $[n]$ is $p$-small if
there exists a collection ${\cal G}$ of subsets of $[n]$ such that

${\cal F}\subseteq\langle{\cal G}\rangle:=\bigcup_{S\in{\cal G}}\langle
S\rangle$

and

$\sum_{S\in{\cal G}}p^{|S|}\leqslant\frac{1}{2}.$

We refer to ${\cal G}$ as the cover of ${\cal F}$. We prove the following
result describing the size of $\delta(T)$.

######  Theorem 2.1.

The family

$\left\\{I\subset[n]:\sup_{t\in T}\sum_{i\in I}^{n}t_{i}\geqslant
L\delta(T)\right\\}$ (1)

is $p$-small. One may take $L=221$.

######  Remark 2.2.

Clearly $\sup_{t\in T}\sum_{i=1}^{n}t_{i}\delta_{i}\leq\sup_{t\in
T}\sum_{i=1}^{n}t_{i}\leq\frac{1}{p}\delta(T)$. Thus the family in (1) is
empty for $L>\frac{1}{p}$. This shows that Theorem 2.1 is interesting only
when $p$ is small.

The main consequence that we deduce from the above theorem is analogue result
for positive infinitely divisible processes (see [8, Definition 12.3.4]).
Notice that following [8, Chapter 12] we take Rosiński’s series representation
of infinitely divisible processes as their definition which uses a Poisson
point process (see e.g. [8, Section 12.1]).
Consider some finite set $T$. In fact, one can think of more complicated sets
$T$ however one should be careful here since it may cause technical problems.
Let $\nu$ be a $\sigma$-finite measure on ${\mathbb{R}}^{T}$ with $\nu(0)=0$.
Assume that for any $t\in T$

$\int_{{\mathbb{R}}^{T}}|x(t)|\wedge 1d\nu(x)<\infty.$

The main additional assumption we make about the measure $\nu$ is that it has
no atoms. Consider a Poisson point process $(Y_{i})_{i\geqslant 1}$ on
${\mathbb{R}}^{T}$ with intensity measure $\nu$. Then we define a positive
infinitely divisible process with Lévy measure $\nu$ as

$|X|_{t}:=\sum_{i\geqslant 1}|Y_{i}(t)|.$

The integrability condition guarantees that the series converges almost
surely. The standard simplification is to look at $T$ as a space of functions
on ${\mathbb{R}}^{T}$ by associating the element $t\in T$ to the function
$x\mapsto x(t)$ on ${\mathbb{R}}^{T}$ so we can write $t(Y_{i})$ instead of
$Y_{i}(t)$. Now, let

$S:=\mathbf{E}\sup_{t\in T}|X|_{t}=\mathbf{E}\sup_{t\in T}\sum_{i\geqslant
1}|t(Y_{i})|$

######  Theorem 2.3.

Suppose that $\nu$ has no atoms. Then there exists a family ${\cal F}$ of
pairs $(g,u)$ where each $g:{\mathbb{R}}^{T}\rightarrow{\mathbb{R}}_{+}$ is
$\nu$-measurable and $u\geqslant 0$ such that

$\left\\{\sup_{t\in T}|X|_{t}\geqslant K\mathbf{E}\sup_{t\in
T}|X|_{t}\right\\}\subset\bigcup_{(g,u)\in{\cal F}}\\{|X|_{g}\geqslant u\\}$
(2)

and

$\sum_{(g,u)\in{\cal F}}\mathbf{P}(|X|_{g}\geqslant u)\leqslant\frac{1}{2}.$
(3)

Obviously, by the Markov inequality the probability of the event described in
(2) is smaller than $1/K$. Our goal is to prove the existence of the family
witnessing the smallness of the event

$\left\\{\sup_{t\in T}|X|_{t}\geqslant K\mathbf{E}\sup_{t\in
T}|X|_{t}\right\\}.$

The third settting we work with is the one of positive empirical processes.
The main novelty of our approach compared to [4] is that we don’t use
multisets which, as we believe, makes the application of the result on the
selectors more transparent.

######  Theorem 2.4.

Let $(E,\rho)$ be some metric space and $d>0$ fixed integer. Let $\mu$ be a
probability measure on $E$ with no atoms. Let $X_{1},\dots,X_{d}$ be
independent random variables distributed according to $\mu$. Let $T$ be a
class of nonnegative Borel measurable functions on $E$. Then there exists a
family ${\cal F}$ of pairs $(g,u)$ where each $g:E\rightarrow{\mathbb{R}}_{+}$
is $\mu$-measurable and $u\geqslant 0$ such that

$\left\\{\sup_{t\in T}\sum_{i=1}^{d}t(X_{i})\geqslant K\mathbf{E}\sup_{t\in
T}\sum_{i=1}^{d}t(X_{i})\right\\}\subset\bigcup_{(g,u)\in{\cal
F}}\left\\{\frac{1}{d}\sum_{i=1}^{d}g(X_{i})\geqslant u\right\\}$ (4)

and

$\sum_{(g,u)\in{\cal
F}}\mathbf{P}\left(\frac{1}{d}\sum_{i=1}^{d}g(X_{i})\geqslant
u\right)\leqslant\frac{1}{2}.$ (5)

##  3 Positive selector process

Theorem 2.1 can be reformulated as follows (see Theorem 5.3, cf. proofs after
[7, Conjecture 6.8] or [4, Appendix A]).

######  Theorem 3.1.

Let ${\cal F}$ be a family of subsets of $[n]$ which is not $p$-small. Suppose
that for each $I\in{\cal F}$ we are given coefficients $(\mu_{I}(i))_{i\in I}$
with $\mu_{I}(i)\geqslant 0$ and

$\mu_{I}(I):=\sum_{i\in I}\mu_{I}(i)=1.$

Then

$\mathbf{E}\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}\geqslant\frac{1}{220}.$

Theorem 3.1 is obvious when $p>\frac{1}{C}$ for a constant $C>1$ (cf. Remark
2.2).

######  Remark 3.2.

Since ${\cal F}\subseteq\bigcup_{i\leq n}\langle\\{i\\}\rangle$ Theorem 3.1 is
trivial when $np<1/2$ (in this case any family ${\cal F}$ is $p$-small). Thus
with no loss in generality we may assume that $np\geq 1/2$.

Our goal now is to prove Theorem 3.1. To this end, we introduce the pivotal
definition. We say that a set $X\subseteq[n]$ is $c$-bad ($c>0$) if

$\sup_{I\in{\cal F}}\mu_{I}(X\cap I)<c.$ (6)

By saying that $X\subseteq[n]$ is random we mean that

$X=\\{i\in[n]:\delta_{i}^{\prime}=1\\},$ (7)

where $(\delta_{i}^{\prime})_{i\leqslant n}$ are independent Bernoulli
variables with arbitrary probability of success. Notice that the distribution
of $X$ conditioned on its cardinality is uniform over $2^{[n]}$. We deduce
Theorem 3.1 from the following.

######  Lemma 3.3 (Key Lemma).

Let ${\cal F}$ be a family of subsets of $[n]$ which is not $p$-small. For any
$m\leq n$ we have

$\mathbf{P}(X\textrm{ is
1/2-bad}\;\big{|}\;|X|=m)\leq\sum_{t=1}^{n}\left(4\frac{np}{m}\right)^{t},$

where bad set is defined in (6) .

###### Proof of Theorem 3.1.

By Remark 3.2 we can assume that $pn\geqslant 1/2$. Thus we may further assume
that $Cpn$ is an integer and $9\leqslant C\leq 11$. Observe that for each $i$
we can represent $\delta_{i}=\delta_{i}^{\prime}\delta_{i}^{\prime\prime}$,
where $(\delta_{i}^{\prime})_{i=1}^{n},(\delta_{i}^{\prime\prime})_{i=1}^{n}$
are independent Bernoulli random variables with
$\mathbf{P}(\delta_{i}^{\prime\prime}=1)=Cp,\mathbf{P}(\delta_{i}^{\prime\prime}=1)=\frac{1}{C}$.
By Jensen’s inequality

$\displaystyle\mathbf{E}\sup_{I\in{\cal F}}\sum_{i\in I}\mu_{I}(i)\delta_{i}$
$\displaystyle=\mathbf{E}\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}^{\prime}\delta_{i}^{\prime\prime}$
$\displaystyle\geq\mathbf{E}\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}^{\prime}\mathbf{E}\delta_{i}^{\prime\prime}=\frac{1}{11}\mathbf{E}\sup_{I\in{\cal
F}}\sum_{i\in I}\mu_{I}(i)\delta_{i}^{\prime}.$ (8)

Lemma 3.3 applied for $m\geqslant Cpn$ gives

$\displaystyle\mathbf{E}\left(\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}^{\prime}\mid\sum_{i=1}^{n}\delta_{i}^{\prime}=m\right)$
$\displaystyle\geq\frac{1}{2}\mathbf{P}\left(X\;\textit{is not
1/2-bad}\mid\sum_{i=1}^{n}\delta_{i}^{\prime}=m\right)\geq\frac{1}{2}\left(1-\sum_{t=1}^{n}\left(4\frac{np}{m}\right)^{t}\right)$
$\displaystyle\geq\frac{1}{2}\left(1-\frac{np}{m}\frac{4}{1-\frac{4np}{m}}\right)\geq\frac{1}{2}\left(1-\frac{4}{C-4}\right)\geq\frac{1}{10}.$
(9)

So, by conditioning

$\displaystyle\mathbf{E}\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}^{\prime}$ $\displaystyle\geq\sum_{m\geqslant
Cpn}\mathbf{E}\left(\sup_{I\in{\cal F}}\sum_{i\in
I}\mu_{I}(i)\delta_{i}^{\prime}\mid\sum_{i=1}^{n}\delta_{i}^{\prime}=m\right)\mathbf{P}\left(\sum_{i=1}^{n}\delta_{i}^{\prime}=m\right)$
$\displaystyle\geq\frac{1}{10}\mathbf{P}\left(\sum_{i=1}^{n}\delta_{i}^{\prime}\geq
Cpn\right)\geq\frac{1}{20},$ (10)

where in the last inequality we used [3] (we recall that $Cnp$ is an integer).
The assertion follows by (8) and (10). ∎

######  Remark 3.4.

Let us observe that Theorem 2.1 implies that the event

$\left\\{\sup_{t\in T}\sum_{i=1}^{n}t_{i}\delta_{i}\geq
221C\delta(T)\right\\}$

is $Cp$-small. To see this let $\delta_{i}^{\prime},\delta_{i}^{\prime\prime}$
be as in the proof of Theorem 3.1. Denote
$\delta^{\prime}(T):=\mathbf{E}\sup_{t\in T}\sum_{i}t_{i}\delta_{i}^{\prime}$.
By Theorem 2.1 the event

$\left\\{\sup_{t\in T}\sum_{i=1}^{n}t_{i}\delta^{\prime}_{i}\geq
221\delta^{\prime}(T)\right\\}$

is $Cp$-small and trivially

$\left\\{\sup_{t\in T}\sum_{i}t_{i}\delta^{\prime}_{i}\geq
221\delta^{\prime}(T)\right\\}\supset\left\\{\sup_{t\in
T}\sum_{i}t_{i}\delta_{i}\geq 221\delta^{\prime}(T)\right\\}.$

The inequality (8) implies that $\delta^{\prime}(T)\leq C\delta(T)$. Thus, we
obtain

$\left\\{\sup_{t\in T}\sum_{i}t_{i}\delta_{i}\geq
221C\delta(T)\right\\}\supset\left\\{\sup_{t\in
T}\sum_{i}t_{i}\delta^{\prime}_{i}\geq 221\delta^{\prime}(T)\right\\}$

and the result follows.

###  3.1 Proof of the Key Lemma

The overall strategy for the proof is to construct the cover of ${\cal F}$
based on the class of bad sets with fixed cardinality and show that its
measure is appropriately small. To achieve this goal we need sets closely
related to so-called fragments (cf. [4, Definition 2.3] or [5], [6] for more
context on the idea of the fragment). We introduce it after the next result.
Let $I_{j}$ be the subset of $I$ consiting of $j$ elements with the highest
values of coefficients i.e.

$I_{j}=\\{i_{l}\in I,\;1\leqslant l\leqslant
j:\;\;\mu_{I}(i_{1})\geqslant\mu_{I}(i_{2})\geqslant\dots\geqslant\mu_{I}(i_{j})\\},$

where we set the convention that $I_{0}=\emptyset$ and for $j\geqslant|I|$ we
have $I_{j}=I$. Also, $I_{j}^{c}=I\setminus I_{j}$.

######  Lemma 3.5.

Let $X\subseteq[n]$ be $c$-bad for some $c>0$ Then, for any $I\in{\cal F}$
there exists a number $j(I,X)$ such that

$|I_{j(I,X)}\cap X|<c|I_{j(I,X)}|.$ (11)

Proof. Assume that $X$ is non-empty, otherwise there is nothing to prove. Fix
$I\in{\cal F}$. For $\varepsilon\in[0,1]$ consider a mapping

$\varepsilon\mapsto\sum_{i\in I\cap X}\mu_{I}(i)\wedge\varepsilon-c\sum_{i\in
I}\mu_{I}(i)\wedge\varepsilon$

and observe that it is continous. Moreover, for $\varepsilon=1$ we have by (6)
that

$\sum_{i\in I\cap X}\mu_{I}(i)-c\sum_{i\in I}\mu_{I}(i)<c-c\mu_{I}(I)=c-c=0$

and obviously $\varepsilon=0$ is mapped to $0$. This means that there exists
the highest value $\varepsilon(I,X)\in[0,1)$ such that

$\sum_{i\in I\cap X}\mu_{I}(i)\wedge\varepsilon(I,X)\geqslant c\sum_{i\in
I}\mu_{I}(i)\wedge\varepsilon(I,X)$ (12)

and for $\varepsilon>\varepsilon(I,X)$ the opposite inequality holds. Now,
observe that for sufficiently small $\delta>0$ we can write

$\sum_{i\in I\cap X}\mu_{I}(i)\wedge(\varepsilon(I,X)+\delta)=\sum_{i\in I\cap
X}\mu_{I}(i)\wedge\varepsilon(I,X)+\delta\sum_{i\in I\cap
X}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}}$

and

$\sum_{i\in I}\mu_{I}(i)\wedge(\varepsilon(I,X)+\delta)=\sum_{i\in
I}\mu_{I}(i)\wedge\varepsilon(I,X)+\delta\sum_{i\in
I}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}}.$

We combine the last two inequalities to get that

$\sum_{i\in I\cap X}\mu_{I}(i)\wedge\varepsilon(I,X)+\delta\sum_{i\in I\cap
X}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}}<c\sum_{i\in
I}\mu_{I}(i)\wedge\varepsilon(I,X)+c\delta\sum_{i\in
I}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}},$

but because of (12) it follows that

$\sum_{i\in I\cap
X}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}}<c\sum_{i\in
I}{\mathbbm{1}}_{\\{\mu_{I}(i)>\varepsilon(I,X)\\}}.$

Let

$\tilde{I}:=\\{i\in
I:\;\mu_{I}(i)>\varepsilon(I,X)\\}\;\;\mbox{and}\;\;j(I,X):=|\tilde{I}|.$ (13)

Obviously,

$I_{j(I,X)}=\tilde{I}$ (14)

so the result follows.

$\blacksquare$

######  Definition 3.6 (Witness).

Fix a $c$-bad set $X\subset[n]$. To each $I\in{\cal F}$ we associate the
number $j(I,X)$ obtained from Lemma 3.5. Now, fix $I\in{\cal F}$. Consider
sets $I^{\prime}\in{\cal F}$ such that

$I^{\prime}_{j(I^{\prime},X)}\setminus X\subset I\setminus X.$ (15)

Among all $I^{\prime}$ for which (15) holds we consider the ones for which
$j(I^{\prime},X)$ is the smallest possible. Among the latter we pick any
$I^{\prime}$ such that $I^{\prime}_{j(I^{\prime},X)}\setminus X$ has minimal
number of elements. We define a $(I,X)$-witness as

$W(I,X):=I^{\prime}_{j(I^{\prime},X)}.$

Now, if we denote $j=j(I^{\prime},X)$ and $t=|I^{\prime}_{j}\setminus X|$ then
it is easy to see that by Lemma 3.5 we have

$j\geqslant t\geq(1-c)j.$ (16)

The aforementioned cover of ${\cal F}$ we are interested in is given for a
fixed $c$-bad $X$ by

${\cal G}(X)=\\{(W(I,X)\setminus X:I\in{\cal F}\\}.$ (17)

######  Remark 3.7.

Indeed, this is a cover of ${\cal F}$ since $W(I,X)\setminus X\subseteq I$ for
every $I\in{\cal F}$ (cf. [4, definition on p. 8]). Let us note that sets
$W(I,X)\setminus X$ are analogues of fragments in [4]. However the notion of
the witness is more suitable for our proof.

Since ${\cal F}$ is not $p$-small we have

$\frac{1}{2}\mathbf{P}(X\textrm{ is
1/2-bad}\mid|X|=m)\binom{n}{m}\leq\sum_{\begin{subarray}{c}X\textrm{ is
1/2-bad}\\\ |X|=m\end{subarray}}\sum_{G\in{\cal G}(X)}p^{|G|}.$ (18)

In order to bound the above double sum we need to control from above the
number of repetitions of the witnesses. It is deduced in Corollary 3.11 from
the next two results.

######  Lemma 3.8.

Take any $c$-bad sets $X,Y$ and $I,J\in{\cal F}$. Denote $I^{\prime}=W(I,X)$
and $J^{\prime}=W(J,Y)$. Assume that

  1. 1.

$j:=j(I^{\prime},X)=j(J^{\prime},Y)$,

  2. 2.

$Z:=I^{\prime}_{j}\cup X=J^{\prime}_{j}\cup Y$,

  3. 3.

$t:=|I^{\prime}_{j}\setminus X|=|J^{\prime}_{j}\setminus Y|$.

Then

$\sum_{i\in I^{\prime}\cap
Y}\mu_{I^{\prime}}(i)\wedge\varepsilon(I^{\prime},X)\geq c\sum_{i\in
I^{\prime}}\mu_{I^{\prime}}(i)\wedge\varepsilon(I^{\prime},X),$

where $\varepsilon(I^{\prime},X)$ is defined as in (12).

######  Remark 3.9.

Observe that, by the definition, $\varepsilon(I^{\prime},Y)$ is the greatest
number for which the above inequality is satisfied. This means that
$\varepsilon(I^{\prime},Y)\geq\varepsilon(I^{\prime},X)$. This is the key
consequence of Lemma 3.8.

Proof. By the definition of $I^{\prime}_{j}$ and since $Y\subset Z$ we have

$\displaystyle\sum_{i\in I^{\prime}\cap
Y}\mu_{I^{\prime}}(i)\wedge\varepsilon(I^{\prime},X)$
$\displaystyle\overset{\eqref{wspol}}{=}\sum_{i\in(I^{\prime}_{j})^{c}\cap
Y}\mu_{I^{\prime}}(i)+\sum_{i\in I^{\prime}_{j}\cap
Y}\varepsilon(I^{\prime},X)$ $\displaystyle=\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)-\sum_{i\in(I^{\prime}_{j})^{c}\cap(Z\setminus
Y)}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)|I^{\prime}_{j}\cap Y|$
$\displaystyle=\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)-\sum_{i\in(I^{\prime}_{j})^{c}\cap(J^{\prime}_{j}\setminus
Y)}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)\left(|I^{\prime}_{j}\cap
Z|-|I^{\prime}_{j}\cap(Z\setminus Y)|\right)$
$\displaystyle=\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)-\sum_{i\in(I^{\prime}_{j})^{c}\cap((J^{\prime}_{j}\setminus
I^{\prime}_{j})\setminus
Y)}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)\left(j-|I^{\prime}_{j}\cap(J^{\prime}_{j}\setminus
Y)|\right)$

where in the last two equalities we used the assumption 2. By the assumption
3. the last line is equal to

$\displaystyle\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)-\sum_{i\in(I^{\prime}_{j})^{c}\cap((J^{\prime}_{j}\setminus
I^{\prime}_{j})\setminus
Y)}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)\left(j-t+|(J^{\prime}_{j}\setminus
I^{\prime}_{j})\setminus Y|\right)$
$\displaystyle\geq\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)(j-t).$

The last inequality holds, because if $i\in(I^{\prime}_{j})^{c}$ then by the
definition (14) of $I^{\prime}_{j}$ we have that
$\mu_{I^{\prime}}(i)<\varepsilon(I^{\prime},X)$. Now, using the assumption 3.
one more time,

$\displaystyle\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)(j-t)$
$\displaystyle=\sum_{i\in(I^{\prime}_{j})^{c}\cap
Z}\mu_{I^{\prime}}(i)+\varepsilon(I^{\prime},X)|I^{\prime}_{j}\cap
X|=\sum_{i\in I^{\prime}\cap
X}\mu_{I^{\prime}}(i)\wedge\varepsilon(I^{\prime},X)$ $\displaystyle\geq
c\sum_{i\in I^{\prime}}\mu_{I^{\prime}}(i)\wedge\varepsilon(I^{\prime},X).$

The last inequality follows again from the definition (12) of
$\varepsilon(I^{\prime},X)$.

$\blacksquare$

######  Lemma 3.10.

Under the assumptions of Lemma 3.8 it is true that $I^{\prime}_{j}\setminus
Y=J_{j}^{\prime}\setminus Y$.

Proof. By the construction of the witness and the assumption 2. we have that

$J\setminus Y\supset J^{\prime}_{j}\setminus Y=(J^{\prime}_{j}\cup Y)\setminus
Y=(I^{\prime}_{j}\cup X)\setminus Y\supset I^{\prime}_{j}\setminus Y.\ $ (19)

Thus we must have that

$j_{0}:=j(I^{\prime},Y)\geq j,$ (20)

otherwise we would had

$I^{\prime}_{j_{0}}\setminus Y\subset I^{\prime}_{j}\setminus Y\subset
J\setminus Y,$

and contradict the optimality of $j=j(J^{\prime},Y)$. Recall (14) and suppose
that $j_{0}=j(I^{\prime},Y)>j$. The larger cardinality obviously indicates the
lower threshold, therefore we have
$\varepsilon(I^{\prime},Y)<\varepsilon(I^{\prime},X)$. This however
condtradicts Lemma 3.8 (see Remark 3.9) and thus we must have $j_{0}=j$. This
implies that $|I_{j}^{\prime}\setminus Y|=|J^{\prime}_{j}\setminus Y|$ by the
construction of the witness. Since these two sets have the same cardinality
and one is a subset of the other from (19) it must be that in fact
$I^{\prime}_{j}\setminus Y=J^{\prime}_{j}\setminus Y$.

$\blacksquare$

######  Corollary 3.11.

Fix $m,t$ and $Z\subset[n]$ such that $|Z|=m+t$. Then for any $t\leq j\leq n$
there are at most ${j\choose t}$ witnesses $W(I,X)$ for which the following
conditions are satisfied

  1. 1.

$X$ is $c$-bad,

  2. 2.

$|X|=m$,

  3. 3.

$j(W(I,X),X)=j$,

  4. 4.

$Z=W(I,X)\cup X$,

  5. 5.

$|W(I,X)|=t$,

where the numbers $j(\cdot,\cdot)$ are defined as in (13).

Proof. Fix any $X,I$ satisfying $1-5$. Take any other pair $Y,J$ which also
satisfies the same conditions. By Lemma 3.10 $W(Y,J)\subset I^{\prime}_{j}$,
so there are at most ${j\choose t}$ choices for $W(Y,J)$.

$\blacksquare$

We are in the position to bound the expression in (18) and prove the Key
Lemma.

###### Proof of Lemma 3.3.

Recall the construction of the cover (17), the control of cardinality of the
fragment (16). Corollary 3.11 implies that

$\displaystyle\sum_{\begin{subarray}{c}X\textrm{ is 1/2-bad}\\\
|X|=m\end{subarray}}\sum_{G\in{\cal G}(X)}p^{|G|}$ $\displaystyle=\sum_{j\geq
1}\sum_{j/2\leq t\leq j}\sum_{|Z|=m+t}p^{t}|\\{W(I,X):Z=I^{\prime}_{j}\cup X,\
|I^{\prime}_{j}\setminus X|=t\\}|$ $\displaystyle\leq\sum_{j\geq
1}\sum_{j/2\leq t\leq
j}\sum_{|Z|=m+t}p^{t}\binom{j}{t}=\sum_{t=1}^{n}\sum_{j=t}^{2t}\binom{j}{t}\binom{n}{m+t}p^{t}.$
(21)

Clearly

$\sum_{j=t}^{2t}\binom{j}{t}=\binom{2t+1}{t+1}\leq\frac{1}{2}2^{2t+1}=4^{t}$

and

$\frac{\binom{n}{m+t}}{\binom{n}{m}}\leq\left(\frac{n}{m}\right)^{t}.$

Those two inequalities applied to (21) give

$\displaystyle\sum_{\begin{subarray}{c}X\textrm{ is 1/2-bad}\\\
|X|=m\end{subarray}}\sum_{G\in{\cal G}(X)}p^{|G|}$
$\displaystyle\leq\binom{n}{m}\sum_{t=1}^{n}\left(4\frac{np}{m}\right)^{t}$

The above together with (18) imply the assertion.

∎

##  4 Positive infinitely divisible processes

The following definition is an analog of $p$-smallness for an event in
${\mathbb{R}}^{T}$.

######  Definition 4.1.

We say that the event $A$ is $\delta$-small if there exists a family ${\cal
F}$ of pairs $(g,u)$ where $g:{\mathbb{R}}^{T}\rightarrow{\mathbb{R}}_{+}$ is
$\nu$-measurable and $u\geqslant 0$ such that

$A\subset\bigcup_{(g,u)\in{\cal F}}\\{|X|_{g}\geqslant u\\}$

and

$\sum_{(g,u)\in{\cal F}}\mathbf{P}(|X|_{g}\geqslant u)\leqslant\delta.$

In other words Theorem 2.3 states that the event $\left\\{\sup_{t\in
T}|X|_{t}\geqslant K\mathbf{E}\sup_{t\in T}|X|_{t}\right\\}$ is $1/2$-small.

###### Proof of Theorem 2.3.

The problem is difficult only when $S=\mathbf{E}\ \sup_{t\in
T}|X|_{t}<\infty$. Therefore, we may assume that

$\mathbf{E}|X|_{t}=\mathbf{E}\sum_{i\geqslant
1}|t(Y_{i})|=\int_{{\mathbb{R}}^{T}}|t(x)|\nu(dx)<\infty.$ (22)

The proof is based on consecutive simplifications which finally allow us to
apply Theorem 2.1.
Step 1. First we split the process into two parts

$|X|_{t}=|X|^{(1)}_{t}+|X|^{(2)}_{t}=\sum_{i\geq
1}|t(Y_{i})|{\mathbbm{1}}_{\\{|t(Y_{i})|\geq 2^{-N}\\}}+\sum_{i\geq
1}|t(Y_{i})|{\mathbbm{1}}_{\\{|t(Y_{i})|<2^{-N}\\}},$

where $N$ is some large fixed integer. Consider
$f:{\mathbb{R}}\to{\mathbb{R}}$ given by
$f(s)=|s|{\mathbbm{1}}_{\\{|s|<2^{-N}\\}}$ so we can write
$|X|^{(2)}_{t}=|X|_{f(t)}$. Thus,

$\displaystyle\\{\sup_{t\in T}|X|_{t}\geqslant KS\\}$
$\displaystyle\subset\\{\sup_{t\in T}|X|^{(1)}_{t}\geqslant
KS\\}\cup\bigcup_{t\in T}\\{|X|^{(2)}_{t}\geqslant KS\\}$
$\displaystyle=\\{\sup_{t\in T}|X|^{(1)}_{t}\geqslant KS\\}\cup\bigcup_{t\in
T}\\{|X|_{f(t)}\geqslant KS\\}.$

Markov’s inequality implies that

$\displaystyle\sum_{t\in T}\mathbf{P}(|X|_{f(t)}\geqslant KS)\leq\sum_{t\in
T}\frac{\mathbf{E}|X|_{f(t)}}{KS}=\sum_{t\in
T}\frac{\int_{{\mathbb{R}}^{T}}|t(x)|{\mathbbm{1}}_{|t(x)|<2^{-N}}d\nu(x)}{KS}.$

Since $T$ is finite and (22) we have that for large enough $N$, $\sum_{t\in
T}\mathbf{P}(|X|_{f(t)}\geqslant KS)<\frac{1}{16}$. So we need to show that
$\\{\sup_{t\in T}|X|^{(1)}_{t}\geqslant KS\\}$ is $7/16$ small. Redefine
$f(s)=|s|{\mathbbm{1}}_{\\{|s|\geq 2^{-N}\\}}$. Then
$|X|^{(1)}_{t}=|X|_{f(t)}$ and $\mathbf{E}\sup_{t\in
T}|X|_{t}\geq\mathbf{E}\sup_{t\in T}|X|_{f(t)}$. Hence, without loss of
generality we may assume that for any $t\in T$ we have $|t|\geq 2^{-N}$. In
particular, this implies

$\nu(|t|\leq M)\leq 2^{N}\int_{R^{T}}|t(x)|d\nu(x)\leq 2^{N}S$ (23)

Step 2. The second step is to replace measurable functions
$t:{\mathbb{R}}^{T}\rightarrow{\mathbb{R}}$ by step functions. Consider sets

$A^{N}_{(k(t))_{t\in T}}=\bigcap_{t\in
T}\\{x\in{\mathbb{R}}^{T}:\;\frac{k(t)}{4^{N}}\leqslant|t(x)|<\frac{k(t)+1}{4^{N}}\\}$
(24)

indexed by $N$ and $(k(t))_{t\in T}$ which is a collection of any integers
such that for each $t\in T$ we have $1\leqslant k(t)\leqslant M4^{N}-1$ for
suitably large $M$. Since $T$ is finite we can enumerate its elements and
distinguish two sequences of levels $(k(t))_{t\in T}$ if the levels are
different for any element $t\in T$. In this sense, for fixed $N$ the sets
$A^{N}_{(k(t))_{t\in T}}$ are disjoint. We denote by ${\cal A}_{N}$ the
collection of such disjoint sets $A^{N}_{(k(t))_{t\in T}}$ for which
$\nu(A^{N}_{(k(t))_{t\in T}})>0$. Observe that for any $N$ (since we recall
that for any $t\in T$, $\\{|t|<2^{-N}\\}=\emptyset$)

$\displaystyle{\cal N}\cup\bigcup_{A\in{\cal A}_{N}}A=\bigcap_{t\in
T}\\{x\in{\mathbb{R}}^{T}:|t(x)|<M\\},\textrm{ and }\nu({\cal N})=0.$ (25)

Moreover, for any $t\in T$, $A\in{\cal A}_{N}$ let $k(A,t)$ be the unique
integer such that the number $t(A):=k(A,t)/4^{N},$ fullfils

$t(A)-1/4^{N}<t(x)\leqslant t(A),\ \textrm{ for any }x\in A.$ (26)

Let also

$Y(A):=\sum_{i\geqslant 1}{\mathbbm{1}}_{\\{Y_{i}\in A\\}}.$ (27)

Note that (25) implies

${\mathbb{R}}^{T}=\left(\bigcup_{A\in{\cal
A}_{N}}A\right)\cup\left(\bigcup_{t\in T}\\{x\in{\mathbb{R}}^{T}:\;|t(x)|\geq
M\\}\right)\cup{\cal N},\textrm{ and }\nu({\cal N})=0.$

Thus, if we denote $B_{M}(t)=\\{x\in{\mathbb{R}}^{T}:\;|t(x)|\geq M\\}$ and
take $g_{M,t}(x)={\mathbbm{1}}_{B_{M}(t)}(x)$ the above display readily
implies that

$\\{\sup_{t\in T}|X|_{t}>KS\\}\subset\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}t(A)Y(A)\geqslant KS\\}\cup\bigcup_{t\in T}\\{|X|_{g_{M,t}}\geqslant
1\\}\cup{\cal N}.$

Now,

$\mathbf{P}(|X|_{g_{M,t}}\geqslant
1)\leqslant\mathbf{E}|X|_{g_{M,t}}=\nu(B_{M}(t))=\nu(x\in{\mathbb{R}}^{T}:\;|t(x)|>M).$

Since, for every $t\in T$, $\int_{{\mathbb{R}}^{T}}|t(x)|\nu(dx)<\infty$
(recall (22)) and $T$ is finite we have for $M$ large enough that

$\sum_{t\in T}\mathbf{P}(|X|_{g_{M,t}}\geqslant 1)\leqslant\sum_{t\in
T}\nu(B_{M}(t))\leqslant\frac{1}{16}.$

Henceforth, we need to show that $\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}t(A)Y(A)\geqslant KS\\}$ is $3/8$-small.

Step 3. The next step is to choose suitably small $p$ and divide each
$A\in{\cal A}_{N}$ into subsets of $\nu$\- measure equal to $p$. More
precisely, let $m(A)=\lfloor\nu(A)/p\rfloor$. Since $\nu(A)$ is atomless there
exist $\nu$-measurable disjoint sets $A_{1},A_{2},\ldots A_{m(A)}\subset A$
such that $\nu(A_{k})=p$. We define

${\cal B}_{N}=\\{A_{k}\mid\ A\in{\cal A}_{N},k\leq m(A)\\}.$

Let also $A_{\ast}=A\backslash\bigcup^{m(A)}_{k=1}A_{k}$ for $A\in{\cal
A}_{N}$. Obviously $\nu(A_{\ast})<p$. Let us choose $p$ sufficiently small so
that each $m(A)\geqslant 16\cdot 2^{N}S$. Similarly to the previous step we
show that set $\bigcup_{A\in{\cal A}_{N}}A_{\ast}$ can be ignored. We simply
put $g_{A_{\ast}}(x)={\mathbbm{1}}_{A_{\ast}}(x)$ and note that

$\displaystyle\left\\{\sup_{t\in T}\sum_{A\in{\cal A}_{N}}t(A)Y(A)\geqslant
KS\right\\}\subset\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B)Y(B)\geqslant KS\right\\}\cup\bigcup_{A\in{\cal
A}_{N}}\\{|X|_{g_{A_{\ast}}}\geqslant 1\\}.$

In the above display $t(B)$ is equal to $t(A)$ where $A$ is the unique set
such that $B\subset A\in{\cal A}_{N}$. This ensures that (cf. (35))

$t(B)-\frac{1}{4^{N}}<t(x)\leq t(B),\ \textrm{ for any }x\in B.$ (28)

Since sets in the class ${\cal A}_{N}$ are disjoint and using (25) and (23)

$\displaystyle\sum_{A\in{\cal A}_{N}}\mathbf{P}(|X|_{g_{A_{\ast}}}\geqslant
1)\leqslant\sum_{A\in{\cal A}_{N}}\mathbf{E}|X|_{g_{A_{\ast}}}=\sum_{A\in{\cal
A}_{N}}\nu(A_{\ast})\leq\sum_{A\in{\cal A}_{N}}\frac{\nu(A)}{16\cdot
2^{N}S}\leq\frac{\nu(\cap_{t\in T}\\{|t|\leq M\\})}{16\cdot
2^{N}S}\leq\frac{1}{16}.$ (29)

Thus the problem reduces further to showing that the event

$\left\\{\sup_{t\in T}\sum_{B\in{\cal B}_{N}}t(B)Y(B)\geqslant KS\right\\}$

is $5/16$ small.
Step 4. Let

$S^{\prime}=\mathbf{E}\sup_{t\in T}\sum_{B\in{\cal B}_{N}}t(B)Y(B).$

By the construction of sets $B\in{\cal B}_{N}$ and coefficients $t(B)$ and
from (23)

$\displaystyle S$ $\displaystyle=\mathbf{E}\sup_{t\in T}\sum_{i\geqslant
1}|t(Y_{i})|\geqslant\mathbf{E}\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}(t(B)-\frac{1}{4^{N}})Y(B)=S^{\prime}-\sum_{B\in{\cal
B}_{N}}\frac{1}{4^{N}}\mathbf{E}Y(B)$ $\displaystyle\geq
S^{\prime}-\frac{1}{4^{N}}\sum_{A\in{\cal
A}_{N}}\nu(A)=S^{\prime}-\frac{\nu(\cap_{t\in T}\\{|t|\leq M\\})}{4^{N}}\geq
S^{\prime}-\frac{S}{2^{N}}\geq\frac{S^{\prime}}{2}$

for $N$ large enough. So, it is enough to prove that the event

$\\{\sup_{t\in T}\sum_{B\in{\cal B}_{N}}t(B)Y(B)\geqslant KS^{\prime}\\}$

is $5/16$ small (we replaced $S$ by $S^{\prime}$).

Step 5. This step shows that the random variables $Y(B)$ can be replaced by
the independent Bernoulli variables. Let $n:=|{\cal B}_{N}|$. Note that
$np\leq\sum_{B\in{\cal B}_{N}}\nu(B)<\infty$ and $p$ can be arbitrary small,
thus we may assume that $np^{2}<1/16$. Let now
$g_{B}(x)={\mathbbm{1}}_{B}(x)$. Clearly,

$\\{Y(B)>1\\}=\\{|X|_{g_{B}}\geq 2\\}.$

So, we immediately obtain that

$\left\\{\sup_{t\in T}\sum_{B\in{\cal B}_{N}}t(B)Y(B)\geq
KS^{\prime}\right\\}\subset\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geq
KS^{\prime}\right\\}\cup\bigcup_{B\in{\cal B}_{N}}\\{|X|_{g_{B}}\geq 2\\}.$

Observe that since $(Y_{i})_{i\geq 1}$ is the Poisson point process the random
variables $Y(A_{k})$ are independent (we will need this property later) and
Poisson with parameter $\nu(B)=p$. Thus,

$\displaystyle\sum_{B\in{\cal B}_{N}}\mathbf{P}(|X|_{g_{B}}\geq 2)$
$\displaystyle=\sum_{B\in{\cal B}_{N}}\mathbf{P}(Y(B)>1)=n(1-e^{-p}(1+p))\leq
np^{2}<\frac{1}{16},$

So, we reduced our problem to the task of proving that the event

$\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geqslant KS^{\prime}\\}$

is $1/4$\- small.

Final Step. Clearly,

$\bar{S}:=\mathbf{E}\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}t(A){\mathbbm{1}}_{\\{Y(A_{k})>0\\}}\leq S^{\prime}.$

We recall that the random variables $Y(B)$ are independent (and identically
distributed as we mentioned in Step 4). Hence, Theorem 2.1 ensures that the
event

$\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geqslant KS^{\prime}\right\\}$

is $(1-e^{-p})$-small and since $(2ep)\geqslant 1-e^{-p}$ by Remark 3.4 we can
argue that for sufficiently large constant $K$ it is $(2ep)$-small. This means
that there exists family ${\cal F}$ of subsets of set ${\cal B}_{N}$ such that

$\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geqslant
KS^{\prime}\right\\}\subset\bigcup_{F\in{\cal F}}\bigcap_{B\in F}\\{Y(B)>0\\}$

and

$\sum_{F\in{\cal F}}(2ep)^{|F|}\leqslant\frac{1}{2}.$

Now, take

$g_{F}(x):={\mathbbm{1}}_{\bigcup_{B\in F}B}(x).$

Note that

$\bigcap_{B\in F}\\{Y(B)>0\\}\subset\\{\sum_{B\in
F}Y(B)\geqslant|F|\\}=\\{|X|_{g_{F}}\geqslant|F|\\},$

thus

$\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geqslant
KS^{\prime}\right\\}\subset\bigcup_{F\in{\cal
F}}\left\\{|X|_{g_{F}}\geqslant|F|\right\\}.$

Since $\sum_{B\in F}Y(B)\sim Poiss(p|F|)$ Chernoff’s inequality implies that

$\displaystyle\mathbf{P}(|X|_{g_{F}}\geqslant|F|)$
$\displaystyle=\mathbf{P}\left(\sum_{B\in F}Y(B)\geqslant|F|\right)\leqslant
e^{|F|\ln p}\mathbf{E}e^{-\ln p\sum_{B\in F}Y(B)}$ $\displaystyle=e^{|F|\ln
p}e^{p|F|(\frac{1}{p}-1)}\leqslant(ep)^{|F|}.$

Therefore,

$\sum_{F\in{\cal F}}\mathbf{P}(|X|_{g_{F}}\geqslant|F|)\leq\sum_{F\in{\cal
F}}(ep)^{|F|}\leq\frac{1}{4}$

so we found the witness that the event

$\left\\{\sup_{t\in T}\sum_{B\in{\cal
B}_{N}}t(B){\mathbbm{1}}_{\\{Y(B)>0\\}}\geqslant KS^{\prime}\right\\}$

is $1/4$-small. ∎

##  5 Positive empirical processes

The overall strategy is as in the previous section. We want to partition $E$
into a sequence of appropriately small sets with respect to the measure $\mu$,
argue that it is enough to investigate only one representative of each of the
partition sets and therefore reduce the problem to the selector case. The main
difference is that the analogues of indicators from Step $5$ are now not
independent. To deal with this fact we first prove a version of Theorem 2.1.
Let us use the notation $\binom{[n]}{m}$ for a class of all $m$-element
subsets of $[n]$. Suppose that $Y\in\binom{[n]}{m}$ is chosen uniformly. By
$\mathbf{P}_{Y}$ and $\mathbf{E}_{Y}$ we denote the probability and the
expectation with respect to $Y$. We aim to prove the following conditional
version of Theorem 3.1.

######  Theorem 5.1.

Let ${\cal F}$ be a family of subsets of $[n]$ which is not $p$-small. Suppose
that for each $I\in{\cal F}$ we are given coefficients $(\mu_{I}(i))_{i\in I}$
with $\mu_{I}(i)\geqslant 0$ and

$\mu_{I}(i)=\sum_{i\in I}\mu_{I}(i)\geqslant 1.$

Let $Y$ be uniformly distirbuted on $\binom{[n]}{m}$ where $m\geq 9pn$. Then

$\mathbf{E}_{Y}\sup_{I\in{\cal F}}\sum_{i\in I\cap
Y}\mu_{I}(i)\geqslant\frac{1}{10}.$

###### Proof.

Let $X$ be given by (7). Then $X$ condidionally on $\\{|X|=m\\}$ has the same
distirbution as $Y$ (uniform). So by Lemma 3.3

$\mathbf{P}(Y\textit{is 1/2-bad})\leq\frac{4}{5}.$

Thus

$\mathbf{E}_{Y}\sup_{I\in{\cal F}}\sum_{i\in I\cap
Y}\mu_{I}(i)\geqslant\frac{1}{2}\mathbf{P}(Y\textit{ is not
1/2-bad})\geq\frac{1}{2}\left(1-\frac{4}{5}\right).$

∎

######  Remark 5.2.

Theorems 2.1 and 5.1 are in the sense exposition of the same result from two
perspectives. Theorem 5.1 emphasizes the necessary relation between $m$ and
$n$ for providing a $p$-small cover which we need in the application for
empirical processes.

######  Theorem 5.3.

For $L>10$, the family

${\cal F}=\left\\{I\in\binom{[n]}{m}:\sup_{t\in T}\sum_{i\in I}t_{i}\geqslant
L\mathbf{E}_{Y}\sup_{t\in T}\sum_{i\in Y}t_{i}\right\\}$

is $\frac{m}{9n}$-small.

###### Proof.

Assume for contradiction that ${\cal F}$ is not $\frac{m}{Cn}$-small. Let
$S=\mathbf{E}_{Y}\sup_{t\in T}\sum_{i\in Y}t_{i}$. For any $I\in{\cal F}$ we
can find $t\in T$ such that for $\mu_{I}(i):=\frac{t_{i}}{LS}$we have
$\sum_{i\in I}\mu_{I}(i)\geqslant 1$, so for $L>10$ we have

$\mathbf{E}_{Y}\sup_{I\in{\cal F}}\sum_{i\in I\cap
Y}\mu_{I}(i)\leqslant\mathbf{E}_{Y}\sup_{t\in T}\sum_{i\in
Y}\frac{t_{i}}{LS}=\frac{1}{L}<\frac{1}{10},$

which contradicts Theorem 5.1. ∎

######  Lemma 5.4.

Let $Y$ and $Y^{\prime}$ be uniformly distributed over $\binom{[n]}{m}$ and
$\binom{[n]}{km}$ respectively, where $k$ is a natural number. Then

$\mathbf{E}_{Y^{\prime}}\sup_{t\in T}\sum_{i\in Y^{\prime}}t_{i}\leq
k\mathbf{E}_{Y}\sup_{t\in T}\sum_{i\in Y}t_{i}.$

###### Proof.

Let $\pi$ be a random permutation uniformly distributed over all permutation
of the set $[km]$. Let $y_{1}<y_{2}<\ldots<y_{km}$ be the elements of
$Y^{\prime}$. Then

$\displaystyle S^{\prime}=\mathbf{E}_{\pi,Y^{\prime}}\sup_{t\in
T}\sum_{i=1}^{km}t_{y_{\pi(i)}}\leq\sum_{l=0}^{k-1}\mathbf{E}_{\pi,Y}\sup_{t\in
T}\sum_{i=lm+1}^{(l+1)m}t_{y_{\pi(i)}}=kS.$

∎

######  Proposition 5.5.

Let $Y$ be uniformly distributed over $\binom{[n]}{m}$ and
$S=\mathbf{E}\sup_{t\in T}\sum_{i\in Y}t_{i}$. Then the following family is
$\frac{Cm}{n}$-small

${\cal F}=\left\\{I\in\binom{[n]}{m}:\sup_{t\in T}\sum_{i\in
I}t_{i}\geq(90C+1)S\right\\}.$

###### Proof.

For any $I\in\binom{[n]}{m}$ we pick $t^{I}\in T$ such that

$\sup_{t\in T}\sum_{i\in I}t_{i}=\sum_{i\in I}t^{I}_{i}.$

Then

${\cal F}=\left\\{I\in\binom{[n]}{m}:\sum_{i\in
I}t^{I}_{i}\geq(90C+1)S\right\\}.$

Assume that ${\cal F}$ is not $\frac{Cm}{n}$-small. Let $k=\lceil 9C\rceil$
and take $Y^{\prime}$ uniformly distributed over $\binom{[n]}{km}$. By Theorem
(5.1)

$\mathbf{E}_{Y^{\prime}}\sup_{I\in{\cal F}}\sum_{i\in Y^{\prime}}t^{I}_{i}\geq
10CS.$ (30)

On the other hand from Lemma (5.4)

$\mathbf{E}_{Y^{\prime}}\sup_{I\in{\cal F}}\sum_{i\in
Y^{\prime}}t^{I}_{i}\leq\mathbf{E}_{Y^{\prime}}\sup_{t\in T}\sum_{i\in
Y^{\prime}}t_{i}\leq kS.$ (31)

Trivially (30) and (31) gives contradiction and as a result ${\cal F}$ is
$\frac{Cm}{n}$-small.

∎

###### Proof of Theorem 2.4.

We proceed as in the case of infinitely divisible processes gradually
simplifying the functions $t\in T$. There are only a few technical
differences. For instance Step 1 in the proof of Theorem 2.3 is now
superfluous. Throughout the proof we use the analogous notion of
$\delta$-smallness from Definition 4.1, where we replace $|X|_{g}$ with
$\frac{1}{d}\sum_{i\leq d}g(X_{i})$.

Let $S=\mathbf{E}\sup_{t\in T}\sum_{i=1}^{d}t(X_{i})$. There is nothing to
prove unless

$\sup_{t\in T}\int_{E}t(x)\mu(dx)=\sup_{t\in T}\mathbf{E}t(X_{i})\leq
S<\infty.$ (32)

The above implies that there exists $M>0$ so that

$\sum_{t\in T}\mu(\\{|t|\geq M\\})\leq\frac{1}{16d}.$ (33)

Step 1. Fix large $N$. By repeating the argument from Step 2 in the proof of
Theorem 2.3 we construct a family of disjoint sets ${\cal A}_{N}$, together
with coefficients $(t(A))_{t\in T,A\in{\cal A}_{N}}$ such that

$\displaystyle{\cal N}\cup\bigcup_{A\in{\cal A}_{N}}A=\bigcap_{t\in T}\\{x\in
E^{T}:|t(x)|\leq M\\},\textrm{ where }\mu({\cal N})=0,$ (34) $\displaystyle
t(A)-4^{-N}\leq t(x)\leq t(A),\textrm{ for any }A\in{\cal A}_{N},\ x\in A.$
(35)

Let $X(A)=\sum_{i=1}^{d}{\mathbbm{1}}_{\\{X_{i}\in A\\}}$. Thus if we consider
$g_{M,t}(x)=1$ if $t(x)\geq M$ and $0$ otherwise we readilly obtain (by using
(34) and (35)) that

$\left\\{\sup_{t\in
T}\sum_{i=1}^{d}t(X_{i})>KS\right\\}\subset\left\\{\sup_{t\in
T}\sum_{A\in{\cal A}_{N}}t(A)X(A)>KS\right\\}\cup\bigcup_{t\in
T}\left\\{\sum_{i=1}^{d}g_{M,t}(X_{i})\geq 1\right\\}\cup{\cal N}.$

By the Bernoulli inequality and (33)

$\sum_{t\in T}\mathbf{P}\left(\left\\{\sum_{i=1}^{d}g_{M,t}(X_{i})\geq
1\right\\}\right)=\sum_{t\in T}1-\mu(\\{|t|\leq M\\})^{d}\leq d\sum_{t\in
T}\mu(\\{|t|>M\\})\leq\frac{1}{16}.$

Thus it is enough to show that the set $\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}t(A)X(A)>KS\\}$ is $7/16$-small.

Step 2. Fix small $p>0$. We divide each $A\in{\cal A}_{N}$ into sets
$A_{1},\ldots,A_{m(A)},A_{*}$, where $m(A)=\lfloor\mu(A)/p\rfloor$,
$\mu(A_{1})=\ldots=\mu(A_{m(A)})=p$ and $\mu(A_{*})<p$. We can pick so small
$p$ that $m(A)\geq 16d$. We do the same as in the Step 3 (including the
notation) in the proof of Theorem 2.3. The calculations in (29) are now of the
form

$\sum_{A\in{\cal A}_{N}}\mathbf{P}(\sum_{i=1}^{d}g_{A_{*}}(X_{i})\geq 1)\leq
d\sum_{A\in{\cal A}_{N}}\mu(A_{*})\leq d\sum_{A\in{\cal
A}_{N}}\frac{\mu(A)}{16d}\leq\frac{1}{16},$ (36)

where in the last inequality we used (34) and that $\mu$ is a probabilistic
measure. Observe that the event that any of $X_{i}$’s belongs to $A_{*}$
constitutes the final cover that we are constructing. Thus, it is enough to
show that the event

$\left\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{n}}\sum_{k=1}^{m(A)}t(A)X(A_{k})\geqslant KS\right\\}$ (37)

is $5/16$-small.
Step 3. Let $S^{\prime}=\mathbf{E}\sup_{t\in T}\sum_{A\in{\cal
A}_{n}}\sum_{k=1}^{m(A)}t(A)X(A_{k})$. Formulas (34) and (35) imply that
$S^{\prime}\leq 2S$ for large enough $N$ (the calculactions are the same as in
Step 4 in the proof of Theorem 2.3.) Thus, we can replace $S$ by $S^{\prime}$
in (37).

Step 4. In this step we replace the variables $X(A_{k})$ by $0-1$ variables
(however not independent ones). Again, let $n=\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}1$. By our construction $np\leq\sum_{A\in{\cal
A}_{N}}\mu(A)\leq 1$. Thus, ($d$ is fixed) we can pick $p$ so small that
$np^{2}d^{2}\leq 1/16$. For any $A\in{\cal A}_{N}$ and $k\leq m(A)$ let
$g_{A_{k}}(x)={\mathbbm{1}}_{A_{k}}(x)$. We have that

$\\{X(A_{k})>1\\}=\left\\{\sum_{i=1}^{d}g_{A_{k}}(X_{i})\geq 2\right\\},$

so (as before) for

${\cal E}:=\left\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}t(A)X(A_{k})\geq
KS^{\prime}\right\\}\cap\bigcap_{A\in{\cal A}_{N},1\leqslant k\leqslant
m(A)}\\{X(A_{k})\in\\{0,1\\}\\}$

we have

$\left\\{\sup_{t\in T}\sum_{A\in{\cal A}_{N}}\sum_{k=1}^{m(A)}t(A)X(A_{k})\geq
KS^{\prime}\right\\}\subset{\cal
E}\cup\left\\{\sum_{i=1}^{d}g_{A_{k}}(X_{i})\geq 2\right\\}.$

Since $(1-p)^{d}\geqslant 1-pd$, we have

$\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}\mathbf{P}\left(\sum_{i=1}^{d}g_{A_{k}}(X_{i})\geq
2\right)=n(1-(1-p)^{d}-dp(1-p)^{d-1})\leqslant np^{2}d^{2}\leq\frac{1}{16}.$
(38)

Since trivially

$\bar{S}=\mathbf{E}\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}t(A)X(A_{k})\prod_{A\in{\cal
A}_{N}}\prod_{k=1}^{m(A)}{\mathbbm{1}}_{\\{{X(A_{k})\in\\{0,1\\}\\}}}\leqslant
S^{\prime},$

it is enough to show that the event

${\cal E}^{\prime}:=\left\\{\sup_{t\in T}\sum_{A\in{\cal
A}_{N}}\sum_{k=1}^{m(A)}t(A)X(A_{k})\geq
K\bar{S}\right\\}\cap\bigcap_{A\in{\cal A}_{N},1\leqslant k\leqslant
m(A)}\\{X(A_{k})\in\\{0,1\\}\\}$

is $1/4$-small.

Final Step. Let ${\cal F}=\\{A_{k}:A\in{\cal A}_{N},\;k\leq m(A)\\}$. We
denote by $\binom{{\cal F}}{d}$ a family of $d$ element subsets of ${\cal F}$.
Let $Y$ be uniformly chosen from $\binom{{\cal F}}{d}$. Finally, define for
$A\in{\cal F}$, $Y(A)=1$ if $A\in Y$ and $0$ otherwise. Let $X\in 2^{\cal F}$
be a random set defined as $X=\\{A\in{\cal F}:X(A)\geq 1\\}$. Let us observe
first that

$\frac{8}{7}\mathbf{E}\sup_{t\in T}\sum_{A\in
X}t(A)X(A)\geq\mathbf{E}\sup_{t\in T}\sum_{A\in Y}t(A).$ (39)

If follows since by (36) and (38) we have

$\mathbf{E}\sup_{t\in T}\sum_{A\in
X}t(A)X(A)\geq\frac{7}{8}\mathbf{E}\left(\sup_{t\in T}\sum_{A\in
X}t(A)X(A)\mid|X|=d,\ X(A)\in\\{0,1\\}:A\in{\cal F}\right).$

Now, if we take any $I=\\{A_{1},\ldots,A_{d}\\}\in\binom{{\cal F}}{d}$ and any
other $J\in\binom{{\cal F}}{d}$ we see that

$\mathbf{P}(X=I)=\sum_{\pi\in\mathrm{Sym}_{d}}\mathbf{P}(X_{\pi(1)}\in
A_{1},\ldots,X_{\pi(d)}\in A_{d})=d!p^{d}=\mathbf{P}(X=J).$

Thus $X$ conditioned on $\\{|X|=d,\ X(A)\in\\{0,1\\}:A\in{\cal F}\\}$ has the
same distribution as $Y$ which concludes the argument for (39).
Now, by Proposition 5.5 there exists $\frac{4ed}{n}$-small familly ${\cal G}$
which consists of sets $G=\\{A_{1},A_{2},\ldots,A_{|G|}:A_{i}\in{\cal F}\\}$
such that

$\displaystyle\\{Y\in\binom{{\cal F}}{d}:\sup_{t\in T}\sum_{A\in Y}t(A)\geq
4eL\mathbf{E}\sup_{t\in T}\sum_{A\in X}t(A)X(A)\\}$
$\displaystyle\subset\\{Y\in\binom{{\cal F}}{d}:\sup_{t\in T}\sum_{A\in
Y}t(A)\geq 4eL\mathbf{E}\sup_{t\in T}\sum_{A\in Y}t(A)\\}$
$\displaystyle\subset\bigcup_{G\in{\cal G}}\bigcap_{A\in G}\\{Y(A)=1\\}$

and $\sum_{G\in{\cal G}}\left(\frac{Cd}{n}\right)^{|G|}\leqslant\frac{1}{2}$.
Then clearly

${\cal E}^{\prime}\subset\bigcup_{G\in{\cal G}}\\{X(A)=1,A\in
G\\}\cap\\{X(A)\in\\{0,1\\};A\in{\cal F}\\}.$

We define $f_{G}(x)=\sum_{A\in G}{\mathbbm{1}}_{A}(x)$ and see that

$\\{X(A)=1,A\in G\\}\cap\\{X(A)\in\\{0,1\\};\;A\in{\cal
F}\\}\subset\left\\{\sum_{i=1}^{d}f_{G}(X_{i})\geq|G|\right\\}.$

Thus it is enough to show that

$\sum_{G\in{\cal
G}}\mathbf{P}\left(\sum_{i=1}^{d}f_{G}(X_{i})\geq|G|\right)\leq 1/4.$

The variables $(f_{G}(X_{i}))_{i\leqslant d}$ are independent Bernoulli random
variables with probability of success equal to $|G|p$. So

$\displaystyle\mathbf{P}\left(\sum_{i\leq
d}f_{G}(X_{i})\geq|G|\right)=\sum_{k=|G|}^{d}\binom{d}{k}(p|G|)^{k}(1-p|G|)^{d-k}\leq\frac{1}{1-p}\binom{d}{|G|}(p|G|)^{|G|}.$

The proof is completed the moment we show that

$\frac{1}{1-p}\binom{d}{|G|}(p|G|)^{|G|}\leqslant\frac{1}{2}\left(\frac{4ed}{n}\right)^{|G|}.$

But

$\left(\frac{4ed}{n}\right)^{|G|}=\left(\frac{4ed}{n}\right)^{|G|}\binom{d}{|G|}\frac{(d-|G|)!|G|!}{d!}\geqslant\binom{d}{|G|}\frac{|G|^{|G|}}{d^{|G|}}\left(\frac{4ed}{2en}\right)^{|G|},$

so it is enough to show that

$(2epn)^{|G|}\leqslant\frac{1-p}{2}(4e)^{|G|}.$

The above is obviously true since $pn\leqslant 1$ and $p$ is as small as we
need. ∎

## Acknowledgements

The authors would like to thank the organizers of the ”Workshop in Convexity
and High -Dimensional Probability” held on May 23- 27, 2022 at Georgia
Institute of Technology at which some progress on this paper was done.

## References

  * [1]
  * [2] W. Bednorz, R. Martynek (2022) The suprema of infinitely divisible processes, Ann. Probab., 50(1), 397–417.
  * [3] N. Lord (2010) Binomial averages when the mean is an integer, Math. Gaz., 94, 331-–332.
  * [4] J. Park and H.T. Pham (2022) On a conjecture of Talagrand on selector processes and a consequence on positive empirical process. arXiv:2204.10309.
  * [5] J. Park and H. T. Pham (2022) A proof of the Kahn-Kalai Conjecture. arXiv:2203.17207
  * [6] J. Kahn, B. Narayanan, and J. Park (2021) The threshold for the square of a Hamilton cycle, Proc. Amer. Math. Soc., 149 no. 8, 3201-–3208.
  * [7] M. Talagrand (2010) Are many small sets explicitly small? Proceedings of the 2010 ACM International Symposium on Theory of Computing, 13–35.
  * [8] M. Talagrand (2022) Upper and Lower Bounds for Stochastic Processes. 2nd Edition. A Series of Modern Surveys in Mathematics 60, Springer, Cham.