\magnification=\magstep1
\hsize=16truecm
 
\input amstex
\TagsOnRight
\parindent=20pt
%\parskip=2pt plus 1.2pt
\parskip=2.5pt plus 1.2pt
%\parskip=3pt plus 1pt

\centerline{ \bf Sharp tail distribution estimates for the supremum}
\centerline{\bf of a class of sums of i.i.d. random variables}

\medskip
\centerline{\it P\'eter Major}

\centerline{\it Alfr\'ed R\'enyi Institute of Mathematics,
Hungarian Academy of Sciences}

\medskip\noindent
{\bf Summary.} 
{\it We take a class of functions ${\Cal F}$ with polynomially 
increasing covering numbers on a measurable space 
$(X,{\Cal X})$ together with a sequence of i.i.d. 
$X$-valued random variables $\xi_1,\dots,\xi_n$, and 
give a good estimate on the tail behaviour of 
$\sup\limits_{f\in{\Cal F}}\sum\limits_{j=1}^nf(\xi_j)$ if the
relations $\sup\limits_{x\in X}|f(x)|\le1$, $Ef(\xi_1)=0$
and $Ef(\xi_1)^2<\sigma^2$ hold with some $0\le\sigma\le1$ for 
all $f\in{\Cal F}$. Roughly speaking this estimate states that 
under some natural conditions the above supremum is not  
much larger than the largest element taking part in it. 
The proof heavily depends on the main result of paper~[6]. 
We also present an example that shows that our results are 
sharp, and compare them with results of earlier papers.}


%\begin{keyword}
%Classes of functions with polynomially increasing covering numbers,
%chaining argument, symmetrization argument, uniform central limit
%theorem, Gaussian and Poissonian coupling
%\MSC[2010] 60F10, 60G50, 60G60
%\end{keyword}

\beginsection Introduction.

The main result of this paper is an estimate about the 
tail-distribution of the supremum of sums of i.i.d. random 
variables presented in Theorem~1 together with an 
extension of it that provides an estimate for this 
tail-distribution in some cases not covered in Theorem~1. 
At first glance these results may look rather complicated, 
but as I try to explain in Section~2 they yield sharp 
estimates under natural conditions. They express such a 
fact that under some natural conditions we can get an 
almost as good bound for the supremum of an appropriately 
defined class of random sums as for one term taking part 
in this supremum. Before presenting these results I recall 
the definition of uniform covering numbers and classes of 
functions with polynomially increasing covering numbers, 
since they appear in the formulation of our results. Here 
I define the notion of uniform covering numbers, unlike 
to~[6], with respect to all $L_p$-norms, $p\ge1$, because 
in some arguments I shall apply it for $p=2$ and not for $p=1$.

\medskip\noindent
{\bf Definition of uniform covering numbers with respect
to $L_p$-norms.} Let a measurable space $(X,{{\Cal X}})$ 
be given together with a class of measurable, real valued 
functions ${\Cal F}$ on this space. The uniform covering 
number of this class of functions at level~$\varepsilon$, 
$\varepsilon>0$, with respect to the $L_p$-norm, 
$1\le p<\infty$, is 
$\sup\limits_\nu {\Cal N}(\varepsilon,{\Cal F},L_p(\nu))$, 
where the supremum is taken for all probability 
measures~$\nu$ on the space $(X,{\Cal X})$, and 
${\Cal N}(\varepsilon,{\Cal F},L_p(\nu))$ is the smallest 
integer $m$ for which there exist some functions 
$f_j\in{\Cal F}$, $1\le j\le m$, such that 
$\min\limits_{1\le j\le m}\int|f-f_j|^p\,d\nu\le\varepsilon^p$ 
for all $f\in{\Cal F}$.

\medskip\noindent
{\bf Definition of a class of functions with polynomially
increasing covering numbers.} We say that a class of 
functions ${\Cal F}$ has polynomially increasing 
covering numbers with parameter~$D$ and exponent $L$ 
if the inequality
$$
\sup_\nu {\Cal N}(\varepsilon,{\Cal F},L_1(\nu))\le D\varepsilon^{-L} 
\tag1.1
$$
holds for all $0<\varepsilon\le 1$ with the number 
$\sup\limits_\nu {\Cal N}(\varepsilon,{\Cal F},L_1(\nu))$ 
introduced in the previous definition with parameter $p=1$.
 
\medskip
Theorem 1 yields the following estimate.

\medskip\noindent
{\bf Theorem 1.} {\it Let a sequence of independent, 
identically distributed random variables $\xi_1,\dots,\xi_n$, 
$n\ge2$, be given with values in a measurable space $(X,{\Cal X})$ 
with some distribution~$\mu$ together with a countable 
class of functions ${\Cal F}$ on the same space $(X,{\Cal X})$ 
which has polynomially increasing covering numbers with
parameter $D\ge1$ and exponent $L\ge1$. Let the class of 
functions ${\Cal F}$ satisfy also the relations
$\sup\limits_{x\in X}|f(x)|\le 1$, $\int f(x)\mu(\,dx)=0$, and 
$\int f^2(x)\mu(\,dx)\le\sigma^2$ with some number 
$0\le\sigma^2\le1$ for all $f\in{\Cal F}$. Define the 
normalized random sums  
$S_n(f)=\frac1{\sqrt n}\sum\limits_{j=1}^n f(\xi_j)$ for all 
$f\in{\Cal F}$. There are some universal constants $C_j>0$,  
$1\le j\le 5$, (such that also the inequality $C_2<1$ holds), 
for which the inequality
$$
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right)\le 
C_1 e^{-C_2\sqrt n v\log(v/\sqrt n\sigma^2)}
\quad \text{for all } v\ge u(\sigma) \tag1.2
$$
holds if one of the following conditions is satisfied.

\medskip
\item{(a)} $\sigma^2\le\frac1{n^{400}}$, and  
$u(\sigma)=\frac{C_3}{\sqrt n}(L+\frac{\log D}{\log n})$,
\item{(b)} $\frac1{n^{400}}<\sigma^2\le\frac {\log n}{8n}$, 
and $u(\sigma)=\frac{C_4}{\sqrt n}
\left(L\frac{\log n}{\log(\frac{\log n}{n\sigma^2})}+\log D\right)$,
\item{(c)} $\frac{\log n}{8n}<\sigma^2\le1$, and
$u(\sigma)=\frac{C_5}{\sqrt n}(n\sigma^2+L\log n+\log D)$. 
}


\medskip
I complete the result of Theorem~1 with an extension which 
almost agrees with Theorem~4.1 in~[5]. It yields an estimate 
for $P\left(\sup\limits_{f\in{\Cal F}}|S_n(f)|\ge v\right)$
in cases not covered in Theorem~1. In case~(c) it enlarges 
the set of levels~$v$ for which a good estimate can be
given for the probability at the left-hand side of~(1.2). 
I discuss this result to give a more complete solution of the 
problem discussed in Theorem~1. Besides, it may be 
interesting to understand what kind of tools are
applied in its proof.

\medskip\noindent
{\bf Extension of Theorem 1.} {\it Let us consider, similarly
to Theorem~1, a sequence of independent, identically 
distributed random variables $\xi_1,\dots,\xi_n$, $n\ge2$, 
with values in a measurable space $(X,{\Cal X})$ with some 
distribution $\mu$ together with a countable class of 
functions ${\Cal F}$ on the same space $(X,{\Cal X})$, which 
has polynomially increasing covering numbers with 
parameter $D\ge1$ and exponent $L\ge1$, and such that 
$\sup\limits_{x\in X}|f(x)|\le 1$, $\int f(x)\mu(\,dx)=0$, and 
$\int f^2(x)\mu(\,dx)\le\sigma^2$ with some number 
$0\le\sigma^2\le1$ for all $f\in{\Cal F}$. The supremum 
of the normalized sums $S_n(f)$, $f\in{\Cal F}$, 
introduced in Theorem~1 satisfies the inequality 
$$
P\left(\sup_{f\in{{\Cal F}}}|S_n(f)|\ge v\right)
\le C\exp\left\{-\alpha\frac {v^2}{\sigma^2}\right\} \tag1.3
$$
with appropriate (universal) constants $\alpha>0$, $C>0$ 
and $C_6>0$ if $\frac{\log n}{8n}<\sigma^2\le1$, and
$\sqrt n\sigma^2\ge v\ge\bar u(\sigma)$, where 
$\bar u(\sigma)$ is defined as 
$$
\bar u(\sigma)
=C_6\sigma\left(L^{3/4}\log^{1/2}\frac2\sigma +(\log D)^{1/2}\right).
$$
}

%\medskip
The value $\frac{\log n}{8n}$ determining the boundary between 
cases~(b) and~(c) in Theorem~1 could be replaced by 
$\alpha\frac{\log n}n$ with an arbitrary number $0<\alpha<1$. 
To see this one has to check that the formula defining 
$u(\sigma)$ in cases~(b) and~(c) give a value of the same order 
if $\sigma^2\sim \alpha\frac{\log n}n$ with $0<\alpha<1$. I chose
the parameter $\alpha=\frac18$ because some calculations were
simpler with such a choice. Let me remark that a similar 
statement holds for the value of boundary $n^{-200}$ between
cases~(a) and~(b). This could have been replaced by 
$n^{-\beta}$ with any $\beta>1$.

\medskip
In Section~2 I try to explain why the above results are natural.
I present an example which shows that Theorem~1 and its Extension
are sharp. There are models satisfying the conditions of these
results for which these results would not hold any longer if
we replaced the functions $u(\sigma)=u(\sigma,n)$ or 
$\bar u(\sigma)$ by a much smaller function. More explicitly,
they would become invalid if we replaced the function 
$u(\sigma,n)$ by a function $v(\sigma,n)$ such that 
$\lim\limits_{n\to\infty}\frac{v(n,\sigma)}{u(n,\sigma)}=0$, 
or $\bar u(\sigma)$ by a function $\bar v(\sigma)$ such that
$\lim\limits_{\sigma\to0}\frac{\bar v(\sigma)}{\bar u(\sigma)}=0$.
(Because of the condition $\bar u(\sigma)\le v\le\sqrt n\sigma^2$
in the Extension of Theorem~1 the value of $\bar u(\sigma)$ 
for small values $\sigma$ is interesting only in the case 
of large sample size~$n$.) In Section~3 I present the proof of
Theorem~1 and its Extension. In Section~4 I discuss the content
of these results in more detail. I explain the main problems and
ideas behind them, and I also make a comparison with the results
of earlier works. 

%\beginsection 2. Discussion on the conditions of these results.
\medskip\noindent
{\bf 2. Discussion on the conditions of these results.}

\medskip\noindent
We defined with the help of a sequence of i.i.d. random
variables $\xi_1,\dots,\xi_n$ on a measurable space $(X,{\Cal X})$ 
and a class of functions ${\Cal F}$ with polynomially increasing
covering numbers on the same space $(X,{\Cal X})$ the random 
sums $S_n(f)$ for all $f\in{\Cal F}$, and wanted to give a 
good estimate on the tail distribution 
$P_n(v)=P\left(\sup\limits_{f\in{\Cal F}}|S_n(f)|>v\right)$ 
of the supremum of these random sums at all levels $v>0$ if 
the conditions $\sup\limits_{x\in X}|f(x)|\le1$, $Ef(\xi_1)=0$ 
and $Ef^2(\xi_1)\le\sigma^2$  hold with some number 
$0\le\sigma\le1$ for all functions $f\in{\Cal F}$. In particular, 
we were interested in the dependence of this estimate on the 
number~$\sigma$. In this section I discuss the sharpness
of our results, and present an example that indicates that 
the estimates given in Theorem~1 and in its Extension are
sharp. 

Although I gave an estimate for the supremum of a class of
random sums defined with the help of a class of functions
${\Cal F}$ which has polynomially increasing covering numbers
with arbitrary exponent $L$ and parameter $D$, I was
mainly interested in the special case when these parameters
$L$ and $D$ are bounded, more precisely when they have a 
bound not depending on the parameter~$\sigma$. In this
case the functions $u(\sigma)$ and $\bar u(\sigma)$ in 
Theorem~1 and in its Extension have a simpler form.
Namely, we can choose $u(\sigma)=\frac {C_3}{\sqrt n}$ in 
case~(a), 
$u(\sigma)=\frac{C_4}{\sqrt n}\frac{\log n}{\log\frac{\log n}{n\sigma^2}}$
in case~(b), $u(\sigma)=C_5\sqrt n\sigma^2$ in case~(c), 
and $\bar u(\sigma)=C_6\sigma\log^{1/2}\frac2\sigma$. In this
section I present an example that indicates that our results 
are sharp in this case. I shall call the estimates in these 
results sharp, because only the value of the universal 
constants appearing in them can be improved. I do not try 
to find the optimal value of these constants, but I want 
to present such an example where these estimates cannot be 
improved in any other respect. In particular, I shall 
show that the estimates in this example do not hold any 
longer if we replace the coefficients $C_j$ in the definition 
of the quantities $u(\sigma)$ and $\bar u(\sigma)$ with very 
small positive constant, because after such a replacement 
the probabilities $P_n(v)$ would be very close to one  
at level $v=u(\sigma)$ or $v=\bar u(\sigma)$ at large 
sample size~$n$. I shall consider the following example.

\medskip\noindent
{\bf Example.} Take a sequence of independent, uniformly 
distributed random variables $\xi_1,\dots,\xi_n$ on the unit 
interval~$[0,1]$, fix a number $0\le\sigma^2\le 1$, and 
define a class of functions ${\Cal F}_\sigma$ and 
$\bar {{\Cal F}_\sigma}$ with functions defined on the unit interval 
$[0,1]$ in the following way. ${\Cal F}_\sigma=\{f_1,\dots,f_k\}$, 
and $\bar{{\Cal F}}=\{\bar f_1,\dots,\bar f_k\}$ with 
$k=k(\sigma)=[\frac1{\sigma^2}]$, where $[\cdot]$ denotes 
integer part, and $\bar f_j(x)=\bar f_j(x|\sigma)=1$  if 
$x\in[(j-1)\sigma^2,j\sigma^2)$, $\bar f_j(x)=\bar f_j(x|\sigma)=0$ 
if  $x\notin[(j-1)\sigma^2,j\sigma^2)$, $1\le j\le k$, and 
$f_j(x)=f_j(x|\sigma)=\bar f_j(x)-\sigma^2$, $1\le j\le n$.

\medskip 
It can be seen that ${\Cal F}_\sigma$ satisfies the conditions 
of Theorem~1 with $Ef(\xi_j)\le \sigma^2$ for all 
$f\in{\Cal F}_\sigma$. In particular, it has polynomially 
increasing covering numbers with such a parameter~$D$ and 
exponent~$L$ that can be bounded by numbers not depending 
on~$\sigma^2$. This can be seen directly, but it is also 
a consequence of some classical results by which the 
indicator functions of a Vapnik--\v{C}ervonenkis class of 
sets constitute a class of functions with polynomially 
increasing covering numbers. (See e.g. Theorem~5.2 in~[5]). 
I shall show that the sequence of random variables 
$\xi_1,\dots,\xi_n$ and class of functions ${\Cal F}$ in 
the above example have the following property.

\medskip\noindent
{\bf An estimate on the function $P_n(v)$ in the models 
of the above Example.} {\it A number $\bar C>0$ can be 
chosen in such a way that for all $\delta>0$ there is an 
index $n_0(\delta)$ such that for all sample sizes 
$n\ge n_0(\delta)$ and numbers $0\le\sigma\le1$ the inequality 
$$
P_n(\hat u(\sigma))=P\left(\sup_{f\in{{\Cal F}_\sigma}}|S_n(f)|
\ge\hat u(\sigma)\right)\ge1-\delta, \tag2.1
$$
holds with $\hat u(\sigma)=\frac{\bar C}{\sqrt n}$ in case~(a), 
i.e. if $\sigma^2\le n^{-400}$,
$\hat u(\sigma)=\frac{\bar C}{\sqrt n}\frac{\log n}
{\log(\frac{\log n}{n\sigma^2})}$ in case~(b), i.e. if
$n^{-400}<\sigma^2\le\frac{\log n}{8n}$, and
$\hat u(\sigma)=\bar C\sigma\log^{1/2}\frac2\sigma$ in case~(c)
i.e. if $\frac{\log n}{8n}\le\sigma^2\le1$.}

\medskip
In Theorem~1 and in its Extension we gave a good estimate for
$P_n(v)$ if $v\ge u(\sigma)$ in cases (a) and (b), and 
$v\ge\bar u(\sigma)$ in case~(c), while in formula~(2.1)
I claimed that there are such models satisfying the conditions
of these results for which no good estimate holds for 
$P_n(\hat u(\sigma))$, if we define the function 
$\hat u(\sigma)$ by replacing the coefficients $C_j$ by a 
sufficiently small constant $\bar C$ in their definition. Let 
me recall that here we restricted our attention to the case 
when the exponent~$L$ and parameter~$D$ of the polynomially 
increasing covering numbers of the class of functions 
${{\Cal F}}_\sigma$ we considered are bounded by a constant 
not depending on the parameter~$\sigma$. Actually, in the 
case~(c) we have to explain the estimate on $P_n(v)$ in more 
detail. In this case we have to compare the estimates given 
by Theorem~1 and its Extension.

It may happen that $\sqrt n\sigma^2\ge\bar u(\sigma)$, and
in this case the estimate~(1.3) of the Extension of Theorem~1 
is an empty statement. I claim that in this case we can 
replace the condition $v\ge u(\sigma)$ by the condition 
$v\ge\bar u(\sigma)$ in case~(c) of Theorem~1 with an 
appropriate constant $C_6$ in the definition of 
$\bar u(\sigma)$, and Theorem~1 remains valid after such a 
modification. To show this it is enough to check that 
$u(\sigma)$ and $\bar u(\sigma)$ have the same order of 
magnitude in this case, i.e. there are universal 
constants $C'>0$ and $C''>0$ such that 
$C'\bar u(\sigma)\le u(\sigma)\le C''\bar u(\sigma)$.

We have $\bar u(\sigma)\le\sqrt n\sigma^2=\frac1{C_5}u(\sigma)$
in this case, which implies the first inequality. On the
other hand, $\sigma^2\ge\frac{\log n}{8n}$ in case~(c), hence as
some calculation shows
$\bar u(\sigma)=C_6\sigma\log^{1/2}\frac2\sigma\ge\text{const.}\,
\sqrt n\sigma^2$. This implies the second inequality. 

If $\sqrt n\sigma^2\ge\bar u(\sigma)$, and the estimate~(1.3)
is not an empty statement, then we can give a good estimate 
for $P_n(v)$ for all $v\ge\bar u(\sigma)$, i.e. also if
$u(\sigma)\ge v\ge \sqrt n\sigma^2$, in a case which was  
covered neither in Theorem~1 nor in its Extension. In this case we
have $C_6\sqrt n\sigma^2\ge v$, and we can write the following
inequality by means of relation~(1.3) with the choice 
$v=\sqrt n\sigma^2$.
$$
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right)\le 
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge \sqrt n\sigma^2\right)\le 
Ce^{-\alpha n\sigma^2}\le Ce^{-\bar\alpha v^2/\sigma^2},
$$ 
with some $\bar\alpha>0$, i.e. relation~(1.3) holds (with 
a possible different parameter $\bar\alpha>0$) for all 
$u(\sigma)\ge v\ge \bar u(\sigma)$.

To understand the content of Theorem~1 and its Extension
together with the estimate on the function $P_n(v)$ in 
the models of the Example formulated above it may be 
useful to recall a result called the concentration 
inequality for the supremum of sums of i.i.d. random 
variables. (See e.g.~[11]). It states that there is a 
concentration point of the tail distribution of the 
supremum of sums of i.i.d. random variables. This
concentration point has the property that the supremum 
is strongly concentrated in a small neighbourhood of it. 
I do not formulate this result in a more precise and 
detailed form, because we need it here only for the sake 
of some orientation. The problem with its application is 
that this result determines the concentration point only 
in an implicit way, as the expected value of the supremum 
we are investigating, and we cannot calculate it explicitly 
in the general case. On the other hand, the concentration 
inequality implies that we can get a good, non-trivial 
estimate for the tail distribution of the supremum of 
sums of i.i.d. random variables only at levels higher than 
their concentration point. (Otherwise we cannot give a 
better estimate for the tail distribution than the trivial 
upper bound~1.) The number $u(\sigma)$ defined in Theorem~1 
is an upper bound for the concentration point in cases~(a) 
and~(b), while the number $\bar u(\sigma)$ defined the 
Extension of Theorem~1 is an upper bound for it in the 
case~(c). On the other hand, the number $\hat u(\sigma)$ 
introduced in formula~(2.1) is a lower bound for the 
concentration point in the models introduced in the Example. 
So in this case we have determined the concentration point 
up to a (universal) multiplying constant.

Thus the functions $u(\sigma)$ and $\bar u(\sigma)$ can
be considered as good upper bounds on the concentration
point of the supremum of the random sums $S_n(f)$, 
$f\in{\Cal F}$, if the conditions of Theorem~1 and its
Extension are satisfied. In formulas~(1.2) and~(1.3) we
also gave an estimate on the function $P_n(v)$, i.e. on 
the tail distribution of the supremum we are investigating 
for $v\ge u(\sigma)$ or $v\ge\bar u(\sigma)$. We can say 
that this estimate is also sharp, we cannot get a better 
bound (if we disregard the value of the universal 
constants $C_1$, $C_2)$ in formula~(1.2) and $C$ and 
$\alpha$ in formula~(1.3) even if we took a single 
normalized sum $S_n(f)$ whose terms $f(\xi_j)$ have
variance $Ef(\xi_j)^2=\sigma^2$.

Indeed, if we disregard the value of the universal 
constants appearing in our estimates, then we can say 
that formula~(1.2) yields such an estimate for the tail 
distribution $P_n(v)$ as Bennett's inequality yields 
for the tail distribution of a single term $S_n(f)$ 
if the terms in this normalized sum have 
variance~$\sigma^2$. At least this is the case if we 
consider the estimate of Bennett's inequality at level
$v\ge 2\sqrt n\sigma^2$. (This follows e.g. from 
formula~(3.3) in this paper. Here we recalled Bennett's 
inequality, and formula~(3.3) is a part of it.) On the 
other hand, we considered in Theorem~1 only such 
levels~$v$ where this condition is satisfied, since 
$u(\sigma)\ge2\sqrt n\sigma$ in all cases of Theorem~1. 
Moreover, there are examples that show that 
inequality~(3.3) is sharp, we cannot get a better 
estimate without some additional restrictions. (See 
Example~3.3 in~[5]). In inequality~(1.3) we gave a 
Gaussian type upper bound, and this is also a sharp
estimate if we disregard the value of the absolute
constants in it.

To complete this section we still have to show that 
the model introduced in the Example satisfies 
formula~(2.1). This will be done in the following proof.

\medskip\noindent
{\it The  proof of the estimate on the function $P_n(v)$ 
formulated about the models in the Example of this 
Section.} In the proof of relation~(2.1) we introduce 
the following notation. Define the empirical distribution 
function $F_n(x)$ of the random variables 
$\xi_1,\dots,\xi_n$, i.e. put
$$
F_n(x)=\frac1n\{\text{the number of indices }j,\; 1\le j\le n,
\text{ such that } \xi_j< x\}
$$ 
for all $0<x\le 1$, and take its normalization 
$G_n(x)=\sqrt n(F_n(x)-x)$, $0<x\le 1$. Observe that
$$
\left\{\sup_{f\in{{\Cal F}_\sigma}}|S_n(f)|\ge\hat u(\sigma)\right\}
=\left\{\max_{1\le j\le k(\sigma)}|G_n(j\sigma^2)-G_n((j-1)\sigma^2)|
\ge\hat u(\sigma)\right\}. \tag2.2
$$
By a classical results of probability theory, the normalized
empirical distribution functions converge weakly to the Brownian
bridge as $n\to\infty$. In our next considerations it will be 
also interesting that the modulus of continuity of a Brownian 
bridge, (which actually agrees with the modulus of continuity 
of a Wiener process) can be also calculated, (see~e.g.~[8]). 
By a similar, but simpler calculation we can estimate the 
probability of the event we get by replacing the normalized 
empirical distribution function $G_n(\cdot)$ by a Brownian bridge 
in the right-hand side expression of~(2.2). This is actually done 
with the choice $\hat u(\sigma)=\bar C\sigma\log^{1/2}\frac2\sigma$ 
in the fourth chapter of~[5] (page~27), and it is shown 
that this probability is almost one for large parameters~$n$
for all $\sigma>0$ if the coefficient $\bar C$ of $\hat u(\sigma)$ 
is chosen sufficiently small. (Actually we have to choose
$\bar C<\sqrt 2$.) Let us call this estimate the Gaussian version
of formula~(2.1). At a heuristic level this result together 
with formula~(2.2) and the weak convergence of the normalized 
empirical processes $G_n(\cdot)$ to a Brownian bridge suggests
that formula~(2.1) should hold with 
$\hat u(\sigma)=\bar C\sigma\log^{1/2}\frac2\sigma$  and a small 
coefficient $\bar C>0$. 

This heuristic argument is nevertheless misleading, since the
weak convergence of the empirical processes $G_n(\cdot)$ to
the Brownian bridge in itself does not allow to carry out a 
limiting procedure that leads to formula~(2.1). On the other 
hand, a stronger version of the weak convergence of the 
normalized empirical processes (see~[4]) yields a useful result 
in this direction. This result states that a normalized empirical 
process~$G_n(x)$ and a Brownian bridge $B(x)$, $0\le x\le1$, 
can be constructed in such a way that 
$\sup\limits_{0\le x\le 1}|B(x)-G_n(x)|\le K\frac{\log n}{\sqrt n}$ 
for all $n\ge2$ and sufficiently large $K>0$ with probability 
almost~1. This result together with the Gaussian version of 
formula~(2.1) imply the validity of formula~(2.1) if 
$\sigma^2\ge B\frac{\log n}{2n}$ with a sufficiently 
large $B>0$. Indeed, in this case 
$\hat u(\sigma)\ge2K\frac{\log n}{\sqrt n}$, hence the
Gaussian version of formula of~(2.1) together with the 
result of~[4] imply that
$$
P\left(\max_{1\le j\le k(\sigma)}|G_n(j\sigma^2)-G_n((j-1)\sigma^2)|
\ge\frac{\hat u(\sigma)}2\right)\ge1-\delta
$$ 
if 
$\sigma^2\ge B\frac{\log n}n$, and $n\ge n_0(\delta)$, hence 
inequality~(2.1) holds in this case if we choose $\bar C>0$ 
sufficiently small in the definition of~$\hat u(\sigma)$. 
Moreover, this relation also holds for all 
$\sigma^2\ge\frac{\log n}{8n}$, i.e. in the case~(c) if we 
choose $\hat u(\sigma)=\bar C\sigma\log^{1/2}\frac2\sigma$ 
with a sufficiently small $\hat C>0$. To see this it is 
enough to observe that if
$\max\limits_{1\le j\le k(\sigma)}|G_n(j\sigma^2)-G_n((j-1)\sigma^2)|
\le\hat u(\sigma)$, then for any positive integers~$A$ we have
$\max\limits_{1\le j\le k(\sqrt A\sigma)}
|G_n(j(A\sigma))-G_n((j-1)(A\sigma))|\le A\hat u(\sigma)$, 
and that the corresponding result holds if 
$\sigma^2\ge B\frac{\log n}{8n}$.

In cases (a) and (b) the above Gaussian approximation argument
does not work. Moreover, inequality~(2.1) holds only with a
different function $\hat u(\sigma)$ in these cases. In case~(b) 
we shall prove formula~(2.1) by means of a Poissonian 
approximation method described below. It can be considered 
as a more detailed elaboration of the argument in Example~4.3 
of~[5].

In this argument first we consider the following problem. Take 
a Poisson process $Z_n(t)$, $0\le t\le 1$, with parameter $n$, 
(i.e. let $EZ_n(t)=nt$ for all $0\le t\le 1$) in the interval 
$[0,1]$. Fix some number $0\le\sigma^2\le\frac17\frac{\log n}n$, 
and define with its help the number
$\hat u(\sigma)=\hat u(\sigma,n)=\frac3{4\sqrt n}\frac{\log n}
{\log(\frac{\log n}{n\sigma^2})}$ and the random variables 
$\bar V_j=\bar V_j^{(n)}(\sigma)=Z_n(j\sigma^2)-Z_n((j-1)\sigma^2)$ 
for $1\le j\le k$ with $k=k(\sigma)=[\frac1{\sigma^2}]$. 
(Here we 
defined $\hat u(\sigma)$ similarly to the quantity introduced with the 
same notation at the formulation of 
inequality~(2.1) in the case~(b). 
We only made small modifications. Namely, we considered $\sigma^2$ 
in the interval $[0,\frac{\log n}{7n}]$ instead of the interval 
$[\frac1{n^{200}},\frac{\log n}{8n}]$, and we fixed the value
$\bar C=\frac34$ in the definition of $\hat u(\sigma)$.)
We shall
show that for all $\delta>0$ there is some threshold index 
$n_0(\delta)$ such that the inequality
$$
P\left(\max_{1\le j\le k(\sigma)}\bar V_j^{(n)}(\sigma)\ge
\sqrt n\hat u(\sigma,n)\right)\ge 1-\delta
\quad \text{if } n\ge n_0(\delta) \tag2.3
$$
holds for all $0\le\sigma^2\le\frac17\frac{\log n}n$.

To prove this inequality let us first observe that
$$
\align
P\left(\max_{1\le j\le k(\sigma)}\bar V_j^{(n)}(\sigma)\ge
\sqrt n\hat u(\sigma,n)\right)  
&\ge P(\bar V_j^{(n)}(\sigma)=
\sqrt n\hat u(\sigma,n)\text{ for some }1\le j\le k) \\
&=1-P(\bar V_1^{(n)}(\sigma)\neq \sqrt n\hat u(\sigma,n))^k,
\endalign
$$
and
$$
\align
&P(\bar V_1^{(n)}(\sigma)\neq\sqrt n\hat u(\sigma,n))
=1-P(\bar V_1^{(n)}(\sigma)=\sqrt n\hat u(\sigma,n)) \\
&\qquad =1-\frac{(n\sigma^2)^{\sqrt n\hat u(\sigma,n)}}
{(\sqrt n\hat u(\sigma,n))!}e^{-n\sigma^2}
\le1-\left(\frac{n\sigma^2}
{\sqrt n\hat u(\sigma,n)}\right)^{\sqrt n\hat u(n,\sigma)}
e^{-n\sigma^2}.
\endalign
$$
Since we have $k=[\frac 1{\sigma^2}]$ we can bound the 
left-hand side of~(2.3) from below as
$$
\align
&P\left(\max_{1\le j\le k(\sigma)}\bar V_j^{(n)}(\sigma)
\sqrt n\hat u(\sigma,n)\right) \\
&\qquad\ge1-\left[1-\left(\frac{n\sigma^2}{\sqrt n\hat u(\sigma,n)}\right)
^{\sqrt n\hat u(n,\sigma)}e^{-n\sigma^2}\right]^{1/\sigma^2} 
\ge1-e^{-T}
\endalign
$$
with $T=\frac1{\sigma^2}
\left(\frac{n\sigma^2}{\sqrt n\hat u(\sigma,n)}\right)
^{\sqrt n\hat u(n,\sigma)}e^{-n\sigma^2}$. Hence to prove~(2.3) it 
is enough to show that
$$
\left(\frac{n\sigma^2}{\sqrt n\hat u(\sigma,n)}\right)
^{\sqrt n\hat u(n,\sigma)}\ge\sigma^2e^{n\sigma^2}\log\frac1\delta 
\quad \text{if }n\ge n_0(\delta).
\tag2.4)
$$

The right-hand side of~(2.4) can be bounded from above as
$$
\sigma^2e^{n\sigma^2}\log\frac1\delta 
=\frac{\log\frac1\delta}n (n\sigma^2)e^{n\sigma^2}
\le\frac{\log\frac1\delta}n \left(\frac17\log n\right)
e^{(\log n)/7}\le n^{-5/6}
$$
if $n\ge n_0(\delta)$, since $n\sigma^2\le\frac17\log n$, and 
$\log\frac1\delta\le n^{1/100}$ for $n\ge n_0(\delta)$. Hence
we prove~(2.4) if we show that
$$
\frac{\sqrt n\hat u(n,\sigma)}{n\sigma^2}
\log\left(\frac{\sqrt n\hat u(\sigma,n)}{n\sigma^2}\right)
\le\frac56\frac{\log n}{n\sigma^2}.
$$
By applying the definition of $\hat u(n,\sigma)$ and introducing
the quantity $z=\frac34\frac{\log n}{n\sigma^2}$ we can rewrite the
last inequality as 
$\frac z{\log (\frac{4z}3)}\log(\frac z{\log (\frac{4z}3)})\le\frac{10}9z$,
or since $z\ge\frac{21}4$ in the case we are investigating it can be 
rewritten as 
$\frac19\log\frac{4z}3\ge -\log\log\frac{4z}3-\log\frac43$ if 
$z\ge\frac{21}4$, and this relation clearly holds. Thus we 
proved~(2.3).

We shall prove relation~(2.1) in the case~(b) by means of 
formula~(2.3) for a Poisson process with parameter 
$\frac{99}{100}n$ 
instead of~$n$ and a simple coupling argument between an empirical 
process and a Poisson process. Namely, we make the following 
coupling. Let us consider a sequence of independent random variables 
$\xi_1,\xi_2\dots$ with uniform distribution on the unit interval
$[0,1]$ together with a Poissonian random variable $\eta=\eta_n$ 
with parameter $\frac{99}{100}n$ independent of the random
variables $\xi_j$, $j=1,2,\dots$, and take the first $\eta_n$ 
terms of the random variables $\xi_j$, i.e. the sequence
$\xi_1,\xi_2,\dots,\xi_{\eta_n}$ with the random stopping index 
$\eta_n$. In such a way we constructed a Poisson process with 
parameter $\frac{99}{100}n$, which is smaller than the 
(non-normalized) empirical distribution of the sequence 
$\xi_1,\dots,\xi_n$ in the following sense. For large 
parameter~$n$ with probability almost~1 all intervals 
$[a,b]\subset[0,1]$ contain more points from the sequence 
$\xi_1,\dots,\xi_n$ than from the above constructed
Poisson process. This is a simple consequence of the fact that
$P(\eta_n>n)\to0$ as $n\to\infty$.

The above coupling construction and formula~(2.3) 
(with a Poisson process with parameter $\frac{99}{100}$) imply that
$$
P\left(\sup_{\bar f\in\bar{{\Cal F}}_\sigma}\sqrt nS_n(\bar f)\ge
\sqrt{\frac{99}{100} n}
\hat u\left(\sigma,\frac{99}{100}n\right)\right)\ge 1-\delta
\quad \text{if } n\ge n_0(\delta) 
$$
with the class of functions $\bar{{\Cal F}}_\sigma$ introduced before
the formulation~(2.1) and the function $\hat u(\sigma,n)$ defined 
in the estimate about the models of the Example in case~(b). To 
complete the proof of~(2.1) in the case~(b) it is enough to check 
that the above relation remains valid if the class of functions 
$\bar{\Cal F}_\sigma$ is replaced by the class of functions 
${\Cal F}_\sigma$ and the term
$\sqrt{\frac{99}{100} n}\hat u(\sigma,\frac{99}{100}n)$ is 
replaced by $\hat u(\sigma,n)=\frac{\bar C}{\sqrt n}\frac{\log n}
{\log(\frac{\log n}{n\sigma^2})}$ with some appropriate $\bar C>0$.
Since the functions $f\in{\Cal F}$ are of the form 
$f(x)=\bar f(x)-\sigma^2$ with some $\bar f\in{\Cal F}$, the 
identity $\sqrt nS_n(f)=\sqrt nS_n(\bar f)-n\sigma^2$ holds, 
and to prove the desired relation it is enough to check that 
$$
\sqrt{\frac{99}{100} }\frac34\frac{\log n}
{\log(\frac{\log n}{\frac{99}{100}n\sigma^2})}-n\sigma^2\ge 
\sqrt{\frac{99}{100} }\frac34\frac{\log n}
{\log(\frac{\log n}{n\sigma^2})}-n\sigma^2\ge 
\bar C \frac{\log n}{\log(\frac{\log n}{n\sigma^2})}
$$
with some appropriate $\bar C>0$ if $8n\sigma^2\le\log n$. The 
first inequality clearly holds, and the second inequality is 
equivalent to the relation
$$
\sqrt{\frac{99}{100} }\frac34\frac{\frac{\log n}{n\sigma^2}}
{\log(\frac{\log n}{n\sigma^2})}\ge \alpha
$$
with some $\alpha>1$. But this relation clearly holds if 
$8n\sigma^2\le\log n$. Thus we have proved~(2.1) also in case~(b).

In the case~(a) the proof of~(2.1) is very simple. It is enough
to observe that the sample points $\xi_j$ fall into one of the 
intervals $[(j-1)\sigma^2,j\sigma^2)$, $1\le j\le k$, (we disregard
the event that they fall into the last interval $[k\sigma^2,1)$ which
has negligibly small probability), hence
$$
P\left(\sup_{\bar f\in\bar{{\Cal F}}_\sigma}\sqrt nS_n(\bar f)\ge1\right)
\ge 1-\delta \quad \text{if } n\ge n_0(\delta), 
$$
and since $\sigma^2$ is very small for large $n$ relation~(2.1)
holds in case~(a) with $\bar C=1-\varepsilon$ for any $\varepsilon>0$.
%\hfill$\qed$

\medskip
I finish this section with some remarks on the paper~[2],
about whose existence I learned only after finishing this work.
Theorem~4 in Section~2 of that paper contains an almost sure
limit theorem on the appropriately normalized supremum of 
the increase of the empirical distribution functions $F_n$,
$n=1,2,\dots$, of a sequence of i.i.d. random variables in 
small intervals if these i.i.d. random variables are 
uniformly distributed in the interval~$[0,1]$. Here we take 
the supremum of $F_n$  for all subintervals of~$[0,1]$ 
whose length is smaller than a prescribed number~$a_n$. 
Actually paper~[2] contains a more general result, but its 
application about the growth of the empirical distribution 
functions in small intervals seems to be its most 
interesting application. I do not give a precise 
formulation of Theorem~4 in~[2], I omit its rather 
technical conditions. In particular, I do not describe what
kind of conditions the number $a_n$ must satisfy in this
theorem. I only want to make some comments about its 
relation to the result about the model in our Example.

If we look carefully at the result of~[2], then we can understand
that it gives an improved version of the statement about the
properties of the model discussed in the Example of this section
in case~(b). It enables us to define such a function $\hat u(\sigma)$
in this case for which even the relation
$$
P\left( (1-\varepsilon)\hat u(\sigma)\le\sup_{f\in{{\Cal F}_\sigma}}|S_n(f)|
\le(1+\varepsilon)\hat u(\sigma)\right)\to1
$$
holds for all $\varepsilon>0$ if $n\to\infty$, and $\sigma=\sigma(n)$
satisfies the relation $n^{-400}\le\sigma^2\le\frac{\log n}{8n}$.
This means that in this case we can determine the value
of the concentration point precisely and not only  up to a 
multiplicative constant. Actually a precise explanation of 
this statement demands the elaboration of some technical 
details, but I omit this.

Finally I remark that our approach to the problem studied in
this section is essentially different from that of~[2]. In that 
paper the results are proved by means of some deep inequalities 
contained in earlier results, while here I tried to explain that 
they can be proved by means of a good Poissonian 
coupling. This may explain the situation better, and this 
approach seems to be appropriate also for the proof of the 
results in~[2].

\beginsection 3. Proof of Theorem 1 and its extension.

\noindent
{\it Proof of Theorem 1.}\/ In the case (a) inequality~(1.2) 
is a simple consequence of Theorem~1 in~[6]. We can apply 
this result by writing $\sigma$ instead of $\rho$ in its 
formulation, since 
$\left(\int |f(x)|\mu(\,dx)\right)^2\le \int f^2(x)\mu(\,dx)\le\sigma^2$ 
by the Cauchy--Schwarz inequality. Hence under the conditions 
of Theorem~1 the inequality $\int|f(x)|\mu(\,dx)\le\rho$ 
holds for all $f\in{{\Cal F}}$ with $\rho=\sigma$, and by
Theorem~1 of~[6]
$$
P\left(\sup_{f\in{{\Cal F}}}|S_n(f)|\ge v\right)
\le De^{-\frac1{25} \sqrt nv\log(\sigma^{-2})}
\quad\text{if } v\ge\frac{\bar C}{\sqrt n}L \text{ and }
\sigma^2\le\frac1{n^{400}} \tag3.1
$$
with an appropriate $\bar C>0$. (Here we apply a division 
by $\sqrt n$ in the definition of $S_n(f)$, which was not 
done in~[6], and this causes some difference in the formulas.)

I claim that we can drop the coefficient $D$ at the right-hand 
side of~(3.1) if we replace the coefficient $\frac1{25}$ by
$\frac1{50}$ in the exponent, we choose such a constant $\bar C$
in~(3.1) for which $\bar C\ge\frac18$, and exploit that by 
condition~(a)  
$v\ge u(\sigma)\ge\frac{\bar C}{\sqrt n}(L+\frac{\log D}{\log n})$. 
To show this it is enough to check that 
$D\le e^{\sqrt nv\log(\sigma^{-2})/50}$
in this case. This relation holds, since 
$\frac{\log D}{\log n}\le 8\sqrt nv$, and 
$\log(\sigma^{-2})\ge 400\log n$, thus
$D=\exp\{\frac1{400}(\frac{\log D}{\log n})(400\log n)\}
\le\exp\{\frac1{50}\sqrt nv\log(\sigma^{-2})\}$, as I claimed.

Next I show that formula~(3.1) or its previous 
modification remains valid if we replace $\log(\sigma^{-2})$ by 
$\log(\frac v{\sqrt n\sigma^2})$ in the exponent of its 
right-hand side. In the proof of this statement we can 
restrict our attention to the case $v\le\sqrt n$, since 
otherwise the probability at the left-hand side of~(3.1)
equals zero. In this case the inequality 
$\sigma^{-2}\ge\frac v{\sqrt n\sigma^2}$ holds, and this 
allows the above replacement. The above modifications of 
formula~(3.1) imply inequality~(1.2) in case~(a).

\medskip\noindent
{\it Remark.}\/ If we are not interested in the value of the 
(universal) constants in~(1.2), then in the case~(a) this 
inequality has the same strength if we replace the term 
$\log (v/\sqrt n\sigma^2)$ by $\log(\sigma^{-2})$ in it. To 
see this, observe that beside the inequality 
$\sigma^{-2}\ge\frac v{\sqrt n\sigma^2}$ (if $v\le\sqrt n$), 
the inequality $\frac v{\sqrt n\sigma^2}\ge\frac1{n\sigma^2}
\ge\sigma^{-2+1/200}$ also holds in case~(a) because 
of the inequalities $v\ge u(\sigma)\ge n^{-1/2}$ and 
$n^{-200}\ge\sigma^2$. The original form of~(1.2) has the 
advantage that it simultaneously holds in all cases~(a), (b) 
and~(c).

\medskip\noindent
{\it The proof of Theorem~1 in cases~(b) and~(c)}.\/
We exploit that the class of functions ${\Cal F}$ 
satisfies~(1.1). We use this relation with the 
choice $\varepsilon=n^{-400}$ and the measure 
$\mu$ instead of $\sup\limits_\nu$.  We may find in such a way
$m\le Dn^{400L}$ functions $f_j\in{\Cal F}$, $1\le j\le m$, such that
$\min\limits_{1\le j\le m}\int |f_j(x)-f(x)|\mu(\,dx)\le n^{-400}$
for all $f\in{\Cal F}$. This means that 
${\Cal F}=\bigcup\limits_{j=1}^n{\Cal D}_j$
with 
$$
{\Cal D}_j=\left\{f\colon\; f\in{\Cal F},\,\int|f_j(x)-f(x)|\mu(\,dx)
\le n^{-400}\right\},
$$
and as a consequence
$$
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right) 
\le \sum_{j=1}^m P\left(|S_n(f_j)|\ge\frac v2\right)
+\sum_{j=1}^m P\left(\sup_{f\in{\Cal D}_j}|S_n(f-f_j)|\ge\frac v2\right) 
\tag3.2
$$
for all $v>0$. We shall estimate both terms at the right-hand side 
of~(3.2) if $v\ge u(\sigma)$, the first term by means of Bennett's 
inequality, more precisely by a consequence of it formulated below,
and the second term by means of the already proved case~(a) of 
Theorem~1. We shall apply the following version of Bennett's 
inequality, see~[5].

\medskip\noindent
{\bf Bennett's inequality.} {\it Let $X_1,\dots,X_n$ 
be independent and identically distributed random variables such
that $P(|X_1|\le1)=1$, $EX_1=0$ and $EX_1^2\le\sigma^2$ with
some $0\le\sigma\le 1$. Put 
$S_n=\frac1{\sqrt n}\sum\limits_{j=1}^n X_j$. Then
$$
P(S_n>v)\le\exp\left\{-n\sigma^2\left[\left(1+\frac v{\sqrt n\sigma^2}\right)
\log\left(1+\frac v{\sqrt n\sigma^2}\right)
-\frac v{\sqrt n\sigma^2}\right]\right\}
$$
for all $ v>0$. As a consequence, for all $\varepsilon>0$ 
there exists some $B=B(\varepsilon)>0$ such that
$$
P\left(S_n>v\right)\le\exp\left\{-(1-\varepsilon)\sqrt nv
\log \frac v{\sqrt n\sigma^2}
\right\}\quad\text{if } v>B\sqrt n\sigma^2, 
$$
and there exists some positive constant $K>0$ such that
$$
P\left(S_n>v\right)\le\exp\left\{-K\sqrt nv\log \frac v{\sqrt n\sigma^2}
\right\}\quad\text{if }v>2\sqrt n\sigma^2. \tag3.3
$$
}

\medskip
The above result is a special case of Theorem~3.2 in~[5] in 
the case when we restrict our attention to sums of independent 
and identically distributed random variables. It has a slightly 
different form, because in the definition of $S_n$ we considered 
normalized sums (with a multiplication by $n^{-1/2}$). Here we 
need only the inequality formulated in~(3.3) which helps to 
estimate the probabilities appearing in the first sum at the 
right-hand side of~(3.2). To apply~(3.3) in 
the estimation of these terms we have to show that  if the 
constants $C_4$ and $C_5$ are chosen sufficiently large in 
Theorem~1, then $u(\sigma)>2\sqrt n\sigma^2$ in cases~(b) and~(c).

In case~(b) it is enough to show that $\sqrt nu(\sigma)\ge 
C_4\frac{\log n}{\log(\frac{\log n}{n\sigma^2})}\ge2n\sigma^2$,
and even
$C_4\frac{\log n}{\log(\frac{\log n}{n\sigma^2})}\ge 20n\sigma^2$,
or in an equivalent form $\frac{C_4}{20}\frac{\log n}{n\sigma^2}
\ge\log(\frac{\log n}{n\sigma^2})$. (Observe that
$\frac{\log n}{n\sigma^2}\ge8$, hence 
$\log(\frac{\log n}{n\sigma^2})>0$ in case~(b).)
This statement holds, since $z=\frac{\log n}{n\sigma^2}\ge8$ 
in case~(b), and $\frac{C_4}{20}z\ge\log z$ if $z\ge8$, and 
$C_4$ is sufficiently large.

In case~(c), clearly $u(\sigma)\ge\frac{C_5}{\sqrt n}n\sigma^2
\ge20\sqrt n\sigma^2$ for sufficiently large constant $C_5$. 
These relations together with formula~(3.3) imply that in 
cases (b) and (c)
$$
P\left(|S_n(f_j)|\ge\frac v2\right)\le 
2\exp\left\{-K\sqrt nv\log \frac v{\sqrt n\sigma^2}\right\} 
\quad\text{if }v\ge u(\sigma) \tag3.4
$$
with an appropriate $K>0$ for all $1\le j\le m$. (In 
formula~(3.4)
we have exploited that $\log(\frac{\frac v2}{\sqrt n\sigma^2})\ge
\frac12\log(\frac v{\sqrt n\sigma^2})$ since 
$\frac v{\sqrt n\sigma^2}\ge20$, and as a consequence 
$\log(\frac v{\sqrt n\sigma^2})\ge 2\log 2$.)

Let us define, with the help of the class of functions 
${\Cal D}_j$ the class of functions 
${\Cal D}_j'=\{h\colon\; h=\frac{f-f_j}2,\;f\in{\Cal D}_j\}$ for
all $1\le j\le m$. It is not difficult to see that 
$\sup\limits_{x\in X}|h(x)|\le1$, 
$\int h^2(x)\mu(\,dx)\le\int |h(x)|\mu(\,dx)\le n^{-400}$ for 
all $h\in{\Cal D}'_j$, and ${\Cal D}_j'$ is a class of functions 
which has polynomially increasing covering numbers with 
parameter $D$ and exponent $L$, $1\le j\le m$. I claim that
$$
\align
P\left(\sup_{f\in{\Cal D}_j}|S_n(f-f_j)|\ge\frac v2\right) 
&=P\left(\sup_{h\in{\Cal D}'_j}|S_n(h_j)|\ge\frac v4\right) \\
&\le e^{-C_2\sqrt nv\log(vn^{195})} \quad \text{if }v\ge u(\sigma)
\tag3.5
\endalign
$$
for all $1\le j\le n$ in both cases~(b) and~(c). We shall get 
this estimate by applying Theorem~1 in the already proved 
case~(a) with the choice of parameter $\sigma^2=n^{-400}$. To 
apply this result we have to check that 
$\frac v4\ge\frac{u(\sigma)}4\ge u(n^{-200})
=\frac{C_3}{\sqrt n}(L+\frac{\log D}{\log n})$
if the constants $C_4$ and $C_5$ are sufficiently large. These 
statements hold, since in case~(b) 
$\frac{\log n}{\log \frac{\log n}{n\sigma^2}}
\ge\frac{\log n}{\log (n^{399}\log n)}\ge\frac1{400}$, hence 
$u(\sigma)\ge \frac{C_4}{\sqrt n}(\frac{L}{200}+\log D)
\ge4u(n^{-200})$ if $C_4$ is chosen sufficiently large,
and an analogous but simpler argument supplies this relation
in case~(c) if $C_5$ is chosen sufficiently large.

It is not difficult to see that the right-hand side both 
of~(3.4) and~(3.5) can be bounded from above by 
$C_1e^{-\bar C_2 \sqrt nv\log(v/\sqrt n\sigma^2)}$
with some appropriate constants $C_1>0$ and $\bar C_2>0$. Hence 
relations (3.2), (3.4) and (3.5) together 
with the inequality $m\le Dn^{400L}$ imply that
$$
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right)\le C_1 Dn^{400L}
e^{-\bar C_2 \sqrt nv\log(v/\sqrt n\sigma^2)} 
\quad\text{if }v\ge u(\sigma) 
\tag3.6
$$
in both cases (b) and (c). Hence to complete the proof of Theorem~1
(with the choice $C_2=\frac{\bar C_2}2$) it is enough to show that
$$
e^{-\frac{\bar C_2}2 \sqrt nv\log (v/\sqrt n\sigma^2)}\le 
e^{-\frac{\bar C_2}2 \sqrt nu(\sigma)\log(u(\sigma)/\sqrt n\sigma^2)} 
\le D^{-1}n^{-400L} \quad\text{if }v\ge u(\sigma) \tag3.7
$$
in cases~(b) and~(c) if the constants $C_4$ and $C_5$ are chosen
sufficiently large.

It is enough to prove the second inequality in formula~(3.7),
since its proof also implies that the expressions in the 
exponent of this formula have negative value, and they 
are decreasing functions for $v\ge u(\sigma)$. The second
inequality in~(3.7) clearly holds in case~(c), since 
$\frac{\bar C_2}2\sqrt nu(\sigma)\ge400L\log n+\log D$,
and $\log\frac{u(\sigma)}{\sqrt n\sigma^2}\ge1$ in this case. 
In case~(b) relation~(3.7) can be reduced to the inequalities
$\bar C_2 \sqrt nu(\sigma)\log(\frac{u(\sigma)}{\sqrt n\sigma^2})
\ge800L\log n$, and
$\bar C_2 \sqrt nu(\sigma)\log(\frac{\sqrt n(\sigma)}{n\sigma^2})
\ge4\log D$. To prove the second inequality observe that
in case~(b) 
$$
\bar C_2\sqrt nu(\sigma)\ge C_4\bar C_2\log D\ge4\log D, 
\quad \text{and} 
\quad\log\left(\frac{\sqrt nu(\sigma)}{n\sigma^2}\right)\ge1.
$$
The second of these inequalities follows from the relation
$$
\frac{\sqrt nu(\sigma)}{n\sigma^2}\ge C_4
\frac{\frac{\log n}{n\sigma^2}}{\log(\frac{\log n}{n\sigma^2})}\ge3,
$$
which holds because of the relation $\frac{\log n}{n\sigma^2}\ge8$
in case~(b).

The remaining inequality can be rewritten as
$\bar C_2 \frac{\sqrt nu(\sigma)}{n\sigma^2}\log(\frac{\sqrt nu(\sigma)}
{n\sigma^2})\ge800L\frac{\log n}{n\sigma^2}$. To prove it observe 
that because of the definition of the function $u(\sigma)$ in 
case~(b) we can write
$\bar C_2\frac{\sqrt nu(\sigma)}{n\sigma^2}\ge1600L\frac{\log n}{n\sigma^2}
\frac1{\log(\frac{\log n}{n\sigma^2})}$.
%\ge1600L\frac{\log n}{n\sigma^2}$,
%since $\log(\frac{\log n}{n\sigma^2})\ge\log8\ge1$. 
I also claim that $\log(\frac{\sqrt nu(\sigma)}{n\sigma^2})
\ge\frac12(\frac{\log n}{n\sigma^2})$. By multiplying the last two
inequalities we get the desired inequality, and this completes the 
proof of Theorem~1.

To prove the above formulated inequality introduce the notation 
$z=\frac{\log n}{n\sigma^2}$ and $\hat u(\sigma)=\frac1{\sqrt n}
\frac{\log n}{\log(\frac{\log n}{n\sigma^2})}$. By exploiting 
the definition of $u(\sigma)$ in case~(b) we can write with the 
help of this notation that
$\log(\frac{\sqrt nu(\sigma)}{n\sigma^2})
\ge\log(\frac{\sqrt n\hat u(\sigma)}{n\sigma^2})=\log z-\log\log z
\ge\frac12\log z=\frac12(\frac{\log n}{n\sigma^2})$. In this 
calculation we have exploited that in case~(b) $z\ge8$, 
hence $\log z-\log\log z\ge\frac12\log z$. Theorem~1 is proved.

\medskip
The extension of Theorem~1 is a slight generalization of 
Theorem~4.1 in~[5], and its proof is based on the same ideas. 
The original proof in~[5] is made by means of two results, 
formulated in Propositions~6.1 and~6.2 of that work. 
Here I present a slightly improved version of Proposition~6.2 
in Theorem~3.1, which is, as I show, a simple consequence of 
Theorem~1. Then I formulate Theorem~3.2 which is a 
(simplified) version of Proposition~6.1 in~[5]. I show that 
the Extension of Theorem~1 can be proved with the help of 
these results by slightly modifying (and simplifying) the 
proof of Theorem~4.1 in~[5]. In Section~4 I shall 
discuss the role of Theorems~3.1 and~3.2 together
with the idea behind them in more detail.

First I formulate Theorem 3.1.

\medskip\noindent
{\bf Theorem~3.1.} {\it Let us have a probability measure 
$\mu$ on a measurable space $(X,{{\Cal X}})$ together with a 
sequence of independent and $\mu$ distributed random 
variables $\xi_1,\dots,\xi_n$, $n\ge2$, and a countable 
class ${\Cal F}$ of functions $f=f(x)$ on $(X,{{\Cal X}})$ which
has polynomially increasing covering numbers
with some parameter $D\ge1$ and exponent $L\ge1$. Let this
class of functions ${\Cal F}$ also satisfy the relations
$\sup\limits_{x\in X}|f(x)|\le 1$, $\int f(x)\mu(\,dx)=0$ and 
$\int f^2(x) \mu(\,dx)\le \sigma^2$ for all $f\in{\Cal F}$ with 
some $0<\sigma\le1$ that satisfies the inequality 
$n\sigma^2>L\log n+\log D$. Then there exists a threshold 
index $A_0$ such that the normalized random sums
$S_n(f)$, $f\in {{\Cal F}}$, introduced in Theorem~1 satisfy 
the inequality
$$
P\left(\sup_{f\in{{\Cal F}}}|S_n(f)|\ge A n^{1/2}\sigma^2\right)\le
e^{-An\sigma^2}\quad \text{if } A\ge A_0. \tag3.8
$$
}

\medskip
I show that the estimate~(3.8) in Theorem~3.1 is a weakened
version of formula~(1.2) of Theorem~1. First I show that the
probability at the left-hand side of~(3.8) can be estimated 
by means of Theorem~1 in case~(c) with the choice 
$v=An^{1/2}\sigma^2$ if $A\ge A_0$ with a sufficiently large 
threshold index $A_0>0$. We have to check that 
$n\sigma^2\ge\frac18\log n$, and $v\ge u(\sigma)$ (with the 
function $u(\sigma)$ defined in case~(c) of Theorem~1) if 
$A_0$ is chosen sufficiently large. These inequalities hold, 
since under the conditions of Theorem~3.1 
$n\sigma^2\ge L\log n\ge\frac18\log n$, and for
$v\ge A_0n^{1/2}\sigma^2$ we can write 
$v\ge\frac{A_0}{\sqrt n}n\sigma^2\ge\frac{A_0}{2\sqrt n}n\sigma^2
+\frac{A_0}{2\sqrt n}(L\log n+\log D)
\ge\frac{C_5}{\sqrt n}(n\sigma^2+L\log n+\log D)=u(\sigma)$. 

Thus we can apply formula~(1.2) with $v=An^{1/2}\sigma^2$ 
to estimate the left-hand side of~(3.8), and we get the 
upper bound 
$$
C_1e^{-C_2\sqrt nv\log(v/\sqrt n\sigma^2)}=
C_1e^{-C_2 An\sigma^2\log A}\le e^{-An\sigma^2}
$$ 
for $A\ge A_0$
if the (universal) constant~$A_0$ is chosen sufficiently 
large.  Thus we proved Theorem~3.1 which provides a slightly
better estimate than Proposition~6.2 in~[5]. 

In the proof of the Extension of Theorem~1 I shall
also apply following Theorem~3.2 which is a simple
modified version of Proposition~6.1 in~[5].

\medskip\noindent
{\bf Theorem~3.2.} {\it Let us have a sequence of i.i.d. 
random variables $\xi_1,\dots,\xi_n$, $n\ge2$, on a 
measurable space $(X,{{\Cal X}})$ with some distribution
$\mu$ and a class of functions ${\Cal F}$ on the space
$(X,{\Cal X})$ that satisfies the inequality 
${\Cal N}(\varepsilon,{\Cal F},L_2(\mu))\le \bar D \varepsilon^{-L}$ 
with some numbers $\bar D\ge1$ and $L\ge1$ for all 
$0<\varepsilon\le1$. Let us also assume that this class 
of functions ${\Cal F}$ also has the properties 
$\sup\limits_{x\in X}|f(x)|\le1$, 
$\int f(x)\mu(\,dx)=0$ and $\int f^2(x)\mu(\,dx)\le\sigma^2$
with a prescribed number $0<\sigma\le 1$ for all $f\in{\Cal F}$.
Take the normalized sums 
$S_n(f)=\frac1{\sqrt n}\sum\limits_{l=1}^nf(\xi_l)$ for all
$f\in {{\Cal F}}$, and let us fix a number $\bar A\ge1$. 

There exists a number $M=M(\bar A)>0$ such that with 
these parameters~$\bar A$ and~$M=M(\bar A)\ge1$ the 
following relations hold. For all numbers $v>0$ such that
$n\sigma^2\ge \left(\frac v\sigma\right)^2
\ge M(L\log\frac2\sigma+\log \bar D)$ define the number
$\bar\sigma_0=\bar\sigma_0(v)=\frac1{8\sqrt n}\frac v{\bar A\sigma}$. 
Then for all numbers $\bar\sigma_0\le\bar\sigma\le\sigma$ a 
collection of functions
${{\Cal F}}_{\bar\sigma}=\{f_1,\dots,f_m\}\subset{{\Cal F}}$ with
$m\le \bar D2^{2L}\bar\sigma^{-L}$ elements can be chosen 
in such a way that the union of the  sets
 ${{\Cal D}}_j=\{f\colon\, f\in {{\Cal F}},\int|f-f_j|^2\,d\mu
\le\bar\sigma^2\}$, $1\le j\le m$, cover the set of functions 
${{\Cal F}}$, i.e. $\bigcup\limits_{j=1}^m{{\Cal D}}_j={{\Cal F}}$, and 
the normalized random sums $S_n(f)$, $f\in{{\Cal F}}_{\bar\sigma}$, 
$n\ge2$, satisfy the inequality
$$
P\left(\sup_{f\in{{\Cal F}}_{\bar\sigma}} |S_n(f)|\ge\frac v{\bar A}\right)
\le 4\exp\left\{-\alpha\left(\frac v{10\bar A\sigma}\right)^2\right\}
\tag3.9
$$
with an appropriate constant $\alpha$ and with the previously
chosen parameter $\bar A$. (In formula~(3.9) we have assumed 
that the number $v$ appearing in it satisfies the condition
$n\sigma^2\ge(\frac v\sigma)^2\ge M(L\log\frac2\sigma+\log \bar D)$.)}

\medskip\noindent
{\it Remark.} Theorem~3.2 is an empty statement if the inequality
$n\sigma^2\ge(\frac v\sigma)^2\ge M(L\log\frac2\sigma+\log \bar D)$
has no solution. This result can be considered as a consequence 
of Proposition~6.1 in~[5], although it contains some statements 
which are proved but not explicitly stated in~[5]. In that
work inequality~(3.9) is proved in the special case when 
$\bar\sigma=4^k\sigma$ with some non-negative integer~$k$, and
$\bar\sigma\ge\bar\sigma_0$, and in that case the set 
${\Cal F}_{\bar\sigma}$ can be chosen with smaller cardinality 
$m\le \bar D\bar\sigma^{-L}$. It is not difficult to deduce
Theorem~3.2 from this result. Actually Theorem~3.2 contains the 
result one can prove with the help of the classical chaining
method under the conditions of the Extension of Theorem~1.
It is a classical method which works in `regular Gaussian' or
`almost Gaussian' models, see~[5].

\medskip
In the proof of the Extension of Theorem~1 let us first check
that under its conditions also the conditions of Theorem~3.2
hold with $\bar D=D2^{L}$. In particular, all numbers $v$
satisfying the conditions of the Extension of Theorem~1
satisfy also the condition 
$n\sigma^2\ge \left(\frac v\sigma\right)^2
\ge M(L\log\frac2\sigma+\log \bar D)$ 
of Theorem~3.2 if we choose the constant~$C_6$ in the 
definition of $\bar u(\sigma)$ (in dependence of the 
value $M(\bar A)$) sufficiently large. The inequality 
${\Cal N}(\varepsilon,{\Cal F},L_2(\mu))
\le\bar D \varepsilon^{-L}$ with $\bar D=2^LD$
under the conditions of this Extension follows from the
inequality
${\Cal N}(\varepsilon,{\Cal F},L_2(\mu))
\le{\Cal N}(\frac\varepsilon2,{\Cal F},L_1(\mu))$
if ${\Cal F}$ consists of functions whose absolute value is
bounded by~1. This relation is a consequence of the observation
that $\int|f-g|^2\,d\mu\le2\int|f-g|\,d\mu$ if $\sup|f(x)|\le1$
and $\sup|g(x)|\le1$.

We still have to check that
$n\sigma^2\ge \left(\frac v\sigma\right)^2
\ge M(L\log\frac2\sigma+\log \bar D)$ under the conditions
$\bar u(\sigma)\le v\le\sqrt n\sigma^2$. But this is a simple
consequence of the definition of $\bar u(\sigma)$ if the 
constant~$C_6$ is chosen sufficiently large in it. Actually
at this point we could replace the number $L^{3/4}$ by $L^{1/2}$
in the definition of~$\bar u(\sigma)$.

We shall prove the Extension of Theorem~1 with the help of
Theorem~3.2 with the choice of $\bar\sigma^2=\frac v{\bar A\sqrt n}$,
where $\bar A=\max(2,A_0)$ and Theorem~3.1 with $\sigma=\bar\sigma$.
First we have to check that this number $\bar\sigma$ satisfies
the conditions 
$\bar\sigma_0=\frac1{8\sqrt n}\frac v{A\sigma}\le\bar\sigma\le\sigma$ 
(to apply Theorem~3.2) and  $n\bar\sigma^2\ge L\log n+\log D$ 
(to apply Theorem~3.1) (if the number $M(\bar A)$ is sufficiently
big). We shall also show that 
$n\bar\sigma^2\ge L\log\frac1{\bar\sigma}+\log(2^{3L}D)$.

The inequality $\bar\sigma_0\le\bar\sigma\le\sigma$ can be
rewritten as $\frac{v^2}{64\sqrt n\bar A\sigma^2}
=\bar A\sqrt n\bar\sigma_0^2\le v\le\bar A\sqrt n\sigma^2$.
Both of these inequalities hold if $v\le\bar A\sqrt n\sigma^2$,
or in an equivalent form $(\frac v\sigma)^2\le \bar A^2n\sigma^2$.
This inequality holds under the conditions of Theorem~3.2, since
we chose a number $\bar A\ge1$.

To prove the second inequality let us observe that 
$n\bar\sigma^2\ge n\bar\sigma_0^2=\frac1{64}\frac{v^2}{\bar A^2\sigma^2}
\ge\frac M{64\bar A^2}(L\log\frac2\sigma+\log (2^LD))$. This calculation
implies the desired inequality in the case $\sigma\le n^{-1/3}$
if the constant $M=M(\bar A)$ is chosen sufficiently large, since
in this case $\log\frac2\sigma\ge\frac13\log n$. In the case
$n^{-1/3}\le\sigma\le1$ we exploit that in the Extension of
Theorem~1 we restricted our attention to the case when the number
$u$ satisfies the more restrictive condition $v\ge\bar u(\sigma)
=C_6\sigma(L^{3/4}\log^{1/2}\frac2\sigma +(\log D)^{1/2})$. In
this case we can write 
$n\bar\sigma^2=\frac {\sqrt nv}A\ge\frac{\sqrt n\bar u(\bar\sigma)}A
\ge\frac{C_6\sqrt n\sigma L^{3/4}\log^{1/2}\frac2\sigma}A
\ge L^{3/4}n^{1/6}$
if the constant $C_6$ is sufficiently large, and
$n\bar\sigma^2\ge n\bar\sigma_0^2=\frac1{64}\frac{v^2}{\bar A^2\sigma^2}
\ge\frac1{64}\frac{\bar u(\sigma)^2}{\bar A^2\sigma^2}
\ge C_6L^{3/2}\log\frac2\sigma\ge C_6 L^{3/2}$. The last two 
inequalities imply that in the case $n^{-1/3}\sigma\le1$ we have
$n\bar\sigma^2=(n\bar\sigma^2)^{2/3}(n\bar\sigma^2)^{1/3}
\ge C^{1/3}_6 L n^{1/9}\ge2L\log n$. On the other hand,
the former results imply that $n\bar\sigma^2\ge2\log D$, and
as a consequence the desired inequality holds also in the
case $n^{-1/3}\le\sigma\le1$. The remaining inequality
$n\bar\sigma^2\ge L\log\frac1{\bar\sigma}+\log(2^{3L}D)$
follows from the first estimate we proved about $n\bar\sigma^2$.

To prove the Extension of Theorem~1 let us choose with the
help of Theorem~3.2 a sequence of functions 
${\Cal F}_{\bar\sigma}=\{f_1,\dots,f_m\}\subset{{\Cal F}}$ and sets
${{\Cal D}}_j=\{f\colon\, f\in {{\Cal F}},\int|f-f_j|^2\,d\mu
\le\bar\sigma^2\}$, $1\le j\le m$, with
$m\le \bar D2^{2L}\bar\sigma^{-L}$ elements such that
$\bigcup\limits_{j=1}^m{{\Cal D}}_j={\Cal F}$.

Since we chose a number $A\ge2$ with the above notation 
we can write up the inequality
$$
%\align
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right) 
\le P\left(\sup_{f\in{{\Cal F}}_{\bar\sigma}} |S_n(f)|
\ge\frac vA\right)+\sum_{j=1}^m
P\left(\sup_{f\in{{\Cal D}}_j} |S_n(f-f_j)|\ge\frac v2\right)
%\endalign
$$
if $\bar u(\sigma)\le v\le\sqrt n\sigma^2$, and the two
terms at the right-hand side of this inequality can be
estimated by means of Theorems~3.1 and~3.2.

We can write
$$
P\left(\sup_{f\in{{\Cal F}}_{\bar\sigma}} |S_n(f)|
\ge\frac v{\bar A}\right)\le 
4e^{-\alpha v^2/100\bar A^2\sigma^2}
$$
by Theorem~3.2, and
$$
\sum_{j=1}^m P\left(\sup_{f\in{{\Cal D}}_j}|S_n(f-f_j)|\ge\frac v2\right)
\le me^{-nA\bar\sigma^2}
$$
by Theorem~3.1.

On the other hand,
$$
me^{-nA\bar\sigma^2}
\le D2^{3L}\bar\sigma^{-L}e^{-nA\bar\sigma^2}
\le e^{-nA\bar\sigma^2/2}\le e^{-nA\bar\sigma_0^2/2}=
e^{-Av^2/64\bar A\sigma^2}\le
e^{-v^2/64\sigma^2},
$$
since 
$$
D2^{3L}\bar\sigma^{-L}e^{-nA\bar\sigma^2/2}
\le D2^{3L}\bar\sigma^{-L}e^{-n\bar\sigma^2}\le1
$$
by the inequality $n\bar\sigma^2\ge L\log \frac1{\bar\sigma}
+\log(D2^{3L})$. The above inequalities imply that
$$
P\left(\sup_{f\in{\Cal F}}|S_n(f)|\ge v\right)\le 
4e^{-\alpha v^2/100\bar A^2\sigma^2}+
e^{-v^2/64\sigma^2}
$$
if $\bar u(\sigma)\le v\le\sqrt n\sigma^2$. Thus formula~(1.3)
and the Extension of Theorem~1 is proved.

\medskip
I finish this paper with a discussion about its methods and
results.

\beginsection 4. A discussion about the methods and results 
of this paper.

The problem of this paper, the estimation of the tail-distribution
of the supremum $\sup\limits_{f\in{\Cal F}}S_n(f)$ of the normalized
sums $S_n(f)=\frac1{\sqrt n}\sum\limits_{k=1}^n f(\xi_k)$ for a
sequence of i.i.d. random variables $\xi_1,\dots,\xi_n$ and a
class of functions ${\Cal F}$ with some nice properties has a long
history. Such a problem arises in a natural way in the study of
the uniform central limit theorem for a class of normalized
sums $S_n(f)$, $f\in{\Cal F}$, with a nice class of functions
${\Cal F}$, see~[3]. An important part of such a study is to prove
the `tightness' of the class of functions $S_n(f)$, $f\in{\Cal F}$,
by showing first that for a subclass ${\Cal F}'\subset{\Cal F}$
such that $E(f-g)^2\le\delta$ with a small number $\delta$ for 
any pairs $f,g\in{\Cal F}'$ the supremum 
$\sup\limits_{f\in {\Cal F}'}S_n(f-g)$ with a fixed $g\in{\Cal F}$ 
is small with probability almost~1. There are some results 
that give a bound on the 
tail-distribution of such a supremum if $\delta=\delta_n$,
and $\delta_n\to0$ as $n\to\infty$. But the estimates I 
know about in this direction do not provide a sharp estimate 
if $\delta_n\to0$ very fast. My goal in this paper was to give
a good estimate also in such cases, and to give a good bound
on the tail distribution of $\sup\limits_{f\in{\Cal F}'}S_n(f-g)$ 
in the general case $\delta=\delta_n$.

Let us remark that for large indices $n$ the random variables 
$S_n(f)$ are asymptotically Gaussian. Hence it is natural to 
study first the natural Gaussian counterpart of the above 
problem to understand what kind of estimates hold in this 
modified problem, what kind of methods are useful in their 
study, and how they can be adapted to our original problem. 
The following problem can be considered as this natural 
Gaussian counterpart. Take a class of (jointly) Gaussian 
random variables $\eta_t$, $E\eta_t=0$, $t\in T$, with a 
(countable) parameter set~$T$, and give a good estimate on 
the tail distribution of $\sup\limits_{t\in T}\eta_t$ with 
the help of the (pseudo) metric~$\rho(s,t)$, 
$\rho^2(s,t)=E(\eta_s-\eta_t)^2$, $s,t\in T$. There is a 
good solution of this problem with the help of the so-called 
chaining argument. This is worked out in detail in~[12], and 
this book contains the sharpest results in this direction. 
We get a good estimate if for all $\varepsilon>0$ we can find 
a set $\{t_1,\dots,t_M\}\subset T$ with relatively few 
$M=M(\varepsilon)$ elements, whose $\varepsilon$-neighbourhood 
with respect to the metric~$\rho$ covers the whole space~$T$. 
The estimate depends on this function $M(\varepsilon)$. In 
particular, if $M(\varepsilon)\le D\varepsilon^{-L}$ with some 
constants $D>1$ and $L>1$, and $E\eta_t^2\le\sigma^2\le 1$ 
for all $t\in T$ and $\varepsilon>0$, then the estimate 
$P\left(\sup\limits_{t\in T}\eta_t>u\right)
\le De^{-(u-u(\sigma))^2/2\sigma^2}$ holds for all $u\ge u(\sigma)$ 
with $u(\sigma)=CL^{1/2}\sigma\log^{1/2}\frac2\sigma$, where 
$C>0$ is a universal constant. The book~[12] contains a sharper
result which provides a good estimate in the general case.
It is also mentioned in this book that a similar estimate
holds for an arbitrary set of random variables $\zeta_t$, 
$t\in T$, if they satisfy the `Gaussian type estimate'
$P(|\zeta_t-\zeta_s|>u)\le C e^{-\alpha u^2/\rho^2(s,t)}$ with some fixed 
numbers $C>0$ and $\alpha>0$ for all $s,t\in T$ and $u>0$. 
The question arises whether such an estimate holds also in 
our original problem about the supremum of normalized random 
sums $S_n(f)$, $f\in{\Cal F}$, if they are defined with the 
help of a nice class of functions~${\Cal F}$.

Let us assume that $\sup|f(x)|\le1$, and $ES_n(f)=0$ for all 
$f\in{\Cal F}$ in the class of functions ${\Cal F}$ we consider. 
Then we may try to apply the above indicated result with 
$T={\Cal F}$ and an appropriate metric $\rho$ on it. Observe that 
$E[S_n(f)-S_n(g)]^2=\int (f-g)^2\,d\mu$ for all $f,g\in{\Cal F}$, 
where $\mu$ denotes the distribution of the random variables 
$\xi_j$. This means that we have to work with the metric 
$\rho(f,g)$ defined as $\rho^2(f,g)=\int(f-g)^2\,d\mu$ in this 
case. The question arises whether the above formulated `Gaussian 
type estimate' which provides a good estimate on the
tail distribution of the supremum we are interested in 
holds in this case.

I discussed this problem in detail in the third chapter
of my book~[5]. The main point is that there are some
classical results, like the Bernstein or Bennett inequality
that give good  estimates for the tail distribution of sums 
of bounded i.i.d. random variables, but they provide so
 good `Gaussian type estimates' that we need only at not 
too high levels~$u$. There are also examples that show 
that in certain cases we cannot get good `Gaussian type 
estimates' at high  levels~$u$. This has the consequence 
that the chaining argument worked out to handle the 
Gaussian counterpart of our problem is not good enough to 
solve our problem. It enables us to reduce it to the special 
case, when the distance $\rho(f,g)$ is very small for all 
$f,g\in{\Cal F}$, but it does not give more help. (How small 
this distance must be that depends on the sample size~$n$.)
The study of this reduced problem demands new ideas.
Moreover, to get good estimates we have to introduce
some new conditions about the behaviour of the 
class~${\Cal F}$, it is not enough to have good control on 
the metric $\rho(f,g)$, $f,g\in{\Cal F}$, introduced above.

There are two main approaches to introduce appropriate
new conditions which enable us to prove good estimates
in the problem we are interested in. The first one can
be found in the book of Talagrand~[12]. He introduced a
condition by which for all $\varepsilon>0$ the class of 
functions ${\Cal F}$ must have an $\varepsilon$-dense 
subset with relatively few elements not only with respect 
to the metric $\rho$ but also with respect to the supremum norm. 
Theorems~1.2.7 and~2.7.2 in~[12] are results in this spirit.
Talagrand also proved some interesting and deep consequences of 
these results in Chapter~3 of~[12]. There are however 
important problems where such an approach does not work. 
Such problems are e.g. the behaviour of the models 
considered in the Example of Section~2 or the problems
considered in Section~2 of~[6]. More generally such a 
problem appears if ${\Cal F}$ consists of the indicator 
functions $\chi_A$ of different sets or if we consider 
their normalized versions  $f_A(x)=\chi_A(x)-\mu(A)$. 
(We may apply such a normalization to get functions 
whose integral with respect to the measure $\mu$ equals 
zero.) In such cases all functions of ${\Cal F}$ are far 
from each other in the supremum norm, and as a consequence 
of it ${\Cal F}$ has no dense subset with respect to the 
supremum norm with relatively few elements. To overcome
this difficulty a different additional condition was 
introduced. This new condition demands that ${\Cal F}$ must 
be a class of functions with polynomially increasing 
covering numbers. This approach proved to be useful in 
several interesting cases when the method of~[12] does 
not work. There are some works, see e.g.~[3], 
[10], [14]
where it is shown that there are many classes of functions
${\Cal F}$ with polynomially increasing covering numbers.
The proof about their existence is closely related to the 
theory of Vapnik--\v{C}ervonenkis classes.

The original technique for proving good estimates on the
tail distribution of the supremum of the random sums
$S_n(f)$, $f\in{\Cal F}$, under the condition that the
class of functions ${\Cal F}$ has polynomially increasing 
covering numbers was the application of the so-called 
symmetrization argument. This technique is applied in 
several works, see e.g.~[3], [5], [7], 
[9], [10], [13], 
and it works in several models when the method of~[12] 
is not applicable. I do not describe this method, I only 
remark that I compared it with that of Talagrand in 
Chapter~18 of~[5] at pp.~235--237. Here I also made a 
comparison between the applicability of these two
methods.

Nevertheless, the symmetrization argument does not provide 
a sharp estimate if the bound 
$\sigma^2\ge \sup\limits_{f\in{\Cal F}}Ef^2(\xi_j)$ is too 
small. The main goal of the present paper to give a sharp 
estimate also in this case. To understand our results
better let us compare them with the results of some 
previous papers in the case when the class of functions 
${\Cal F}$ contains functions bounded by~1, and it has 
polynomially increasing covering numbers with bounded 
exponent~$L$ and parameter~$D$, i.e. these numbers have 
a bound not depending on $\sigma$. Paper~[14] gives the 
following upper bound for the value of the concentration 
point of the distribution of $\sup\limits_{f\in{\Cal F}}S_n(f)$
in this case.
$$
E^*\sup_{f\in{\Cal F}} S_n(f)\le C J(\sigma,{\Cal F},L_2)
\left(1+\frac{J(\sigma,{\Cal F},L_2)}{\sigma^2\sqrt n}\right)
$$
with a universal coefficient $C$, where 
$$
J(\sigma,{\Cal F},L_2)=\sup\limits_\nu\int_0^\sigma 
\sqrt{1+\log {\Cal N}(\varepsilon,{\Cal F},L_2(\nu))}\,d\varepsilon
$$
with the uniform covering number 
$\sup\limits_\nu{\Cal N}(\cdot,\cdot,\cdot)$
with respect to $L_2$-norms. (Here the notation $E^*$ 
is applied, since the choice of a non-countable class 
of functions ${\Cal F}$ is also allowed, and in this 
case the outer expectation $E^*$ is applied.)

Some calculation shows that in this case
$J(\sigma,{\Cal F},L_2)\asymp\sigma\sqrt{\log\frac2\sigma}$,
hence we get the upper bound $\text{const.}\left(\sigma \sqrt
{\log \frac2\sigma}+\frac{\log\frac2\sigma}{\sqrt n}\right)$
for the value of the concentration point in this case. This 
yields the upper bound $C\sigma\sqrt{\log\frac2\sigma}$ if 
$\sigma^2\ge\text{const.}\frac{\log n}n$ and 
$C\frac{\log\frac2\sigma}{\sqrt n}$ if
$\sigma^2\le\text{const.}\frac{\log n}n$ for the value of 
the concentration point. This result is sharp in the first 
case, (see Theorem~1 and its Extension together with the 
Example in Section~2). But it is not sharp in the second
case. Moreover, it can be improved in the following
trivial way. If $\sigma^2\le\sigma_0^2=\frac{\log n}n$, then 
we can apply the above estimate for $\sigma^2_0$ instead of 
$\sigma^2$, and this yields the upper bound $\frac{\log n}{\sqrt n}$
instead of the estimate $\frac{\log \frac2\sigma}{\sqrt n}$
for the value of the concentration point. This means that the 
result of~[14] could not yield a better estimate if 
$\sigma^2\ll\sigma^2_0$ than in the case $\sigma^2=\sigma_0^2$.

Massart's paper~[7] contains another result about the tail
distribution of the supremum of $S_n(f)$, $f\in{\Cal F}$. The 
proof in that paper is based on a modified version of the 
symmetrization argument. The result of~[7] is rather 
complicated, but one can get an estimate for the value of
the concentration point with its help. Here I shall consider 
the version of this result presented in Theorem~2.14.16 of 
the book~[13]. We can get the bound for the value of the 
concentration point by calculating when the bound given 
for the tail distribution of the supremum given in this
result becomes smaller than~1. Some calculation that I
would omit would provide the right bound
$C\sigma\sqrt{\log\frac2\sigma}$ if 
$\sigma^2\ge\text{const.}n^{-1/4}$ and a much weaker
bound $Cn^{-1/4}\log^{1/2}\frac2\sigma$ for the value of
the concentration point in the other case. It is also
worth considering the estimate that Alexander's
method worked out in~[1] supplies. It is based on the
chaining argument, and it yields a good estimate, 
similarly to~[14] if
$\sigma^2\ge\sigma_0^2=\frac{\log n}n$, and a weak one
in the other case. 

Actually the proof of the result in~[5] corresponding
to the Extension of the Theorem~1 is based on 
Alexander's idea in~[1], and it yields a good estimate
only for $\sigma\ge\sigma_0$. The starting point in
the present investigation was an attempt to find a 
refinement of this method which supplies a good 
estimate for the tail distribution of the supremum
we are investigating if the number $\sigma^2$
satisfying the inequality 
$\sigma^2\ge\sup\limits_{f\in{\Cal F}}Ef^2(\xi_j)$ can
be chosen in an arbitrary way. The original result was 
proved by means of an appropriate inductive hypothesis. 
To get an improved version of it we have to find a 
good reformulation of this inductive hypothesis that 
takes into account that in the case of small parameter 
$\sigma^2$ we have a better estimate. This lead me to the 
investigation of the problem in paper~[6]. Then 
it turned out that a direct application of the results 
in~[6] enables us to work out a different method 
that yields a more general result with less effort. It 
may be interesting to compare this method with some 
standard techniques applied in the study of other 
probabilistic problems.

In the proof of limit theorems for sums of independent
random variables or in the study of some similar problems 
a standard method is the application of the so-called
truncation. The truncated random terms show nice `regular'
behaviour, since they are bounded. This enables 
us to study them with the help of classical methods. 
The contributions omitted by truncation contain the 
`irregular' part of the random variables, and they 
cannot be handled by standard methods. But in nice 
cases it can be proved that they are negligible, 
hence we can prove the desired results. 

Here we applied a similar approach to prove our estimates 
with the help of the result in~[6]. We took some 
appropriately chosen functions $f_j\in{\Cal F}$, considered 
their small neighbourhoods with respect to the metric 
$\rho$ defined in this section, and estimated the 
increase of $S_n(f)$ in these neighbourhoods. More
explicitly, we chose some appropriate functions 
$f_j\in{\Cal F}$ and an appropriate small number 
$\sigma>0$, and we estimated the tail distribution of 
$\sup\limits_{f\in{\Cal F},\,\rho(f,f_j)\le\sigma}S_n(f-f_j)$.
The tail distribution of these terms could be well 
estimated by means of the result in~[6]. They 
played a role similar to that part of random sums which 
were omitted at truncation in some analogous problems
because of their large value. These terms are small by the 
results of~[6]. On the other hand, they enable us to 
restrict our attention to such problems where we can make 
good estimations by means of some standard methods, like the 
application of classical estimates on the tail distribution 
of the single terms $S_n(f)$ or the chaining argument. In 
the proof of Theorem~1 and its Extension actually such an
approach was followed.

If we look carefully how we could work with the help of 
the result of~[6] and how the symmetrization argument was 
applied in other works, then we can see that they played
a similar role. It seems to me that the result of~[6] can 
replace the symmetrization argument in most applications, 
moreover it supplies a more powerful tool.

\medskip\noindent
{\bf References.}

\medskip
\item{[1]} K. S. Alexander, Probability inequalities for empirical
processes and a law of the iterated logarithm. Annals of 
Probability {\bf 15} no. 4 1041--1067 (1984) 
\item{[2]} P. Deheuvels, J. H. J. Einmahl, D. M. Mason, 
F. H. Ruymgaart, The almost sure behavior of maximal and minimal 
multivariate $k_n$-spacings. J. Multivariate Anal. {\bf24}, 
155--176 (1988)
\item{[3]} R. M. Dudley, {\it Uniform Central Limit Theorems.
Second Edition.} Cambridge University Press, Cambridge (2014)
\item{[4]}J. Koml\'os, P. Major, G. Tusn\'ady, An approximation
of partial sums of independent rv.'s and the sample DF. I.
Z. Wahrscheinlichkeitstheorie verw. Gebiete 32, 111--131 (1975)
\item{[5]} P. Major, On the estimation of multiple random integrals
and $U$-statistics {\it Lecture Notes in Mathematics} vol 2079
(Springer) Heidelberg New York Dordrecht London (2013)
\item{[6]}P. Major, Sharp estimate on the supremum of a class
of partial sums of small i.i.d. random variables, 
Stochastic Processes and their Applications (2015), \hfill\break
http://dx.doi.org/10.1016/j.spa.2015.07.016
\item{[7]} P. Massart, Rates of convergence in the central
limit theorem for empirical processes. Annales Institut Henri 
Poincar\'e {\bf22}, 381--423 (1986)
\item{[8]} H. P. McKean Jr., {\it Stochastic integrals.}
Academic Press New York London (1969)
\item{[9]} D. Pollard, A central limit theorem for empirical
processes. Austral Math. Soc. (Series A). 235--248 {\bf33}, (1982)
\item{[10]} D. Pollard, {\it Convergence of Stochastic Processes.}
(Springer, New York, (1984)
\item{[11]} M. Talagrand, New concentration inequalities in
product spaces. {\it Invent. Math.} {\bf 126}, 505--563 (1996) 
\item{[12]} M. Talagrand, {\it The generic chaining.} Springer 
Monographs in Mathematics. \hfill\break 
Springer--Verlag, Berlin Heidelberg New York (2005) 
\item{[13]} A. W. van der Vaart,  J. A. Wellner, {\it Weak 
Convergence and Empirical Processes.} Springer, New York (1996)
\item{[14]} A. W. van der Wart, J. A. Wellner, A local maximal
inequality under uniform entropy. Electronic Journal of Statistics
{\bf5}, 192--203  (2011)

\bye

