%\centerline{\bf TAIL-DISTRIBUTION ESTIMATES FOR MULTIPLE}
%\vskip2pt
%\centerline{\bf RANDOM INTEGRALS AND $U$-STATISTICS}
%
\centerline{\bf ON THE ESTIMATION OF MULTIPLE RANDOM INTEGRALS}
\vskip2pt
\centerline{\bf AND $U$-STATISTICS}

\smallskip
\centerline{\it P\'eter Major}
\centerline{\it Alfr\'ed R\'enyi Mathematical Institute of the
Hungarian Academy of Sciences}

\beginsection 1. Introduction.

First I briefly describe the main subject of this work.
Fix a positive integer $n$, consider $n$ independent and identically
distributed random variables $\xi_1,\dots,\xi_n$ on a measurable
space $(X,\Cal X)$ with some distribution $\mu$ and take their
empirical distribution $\mu_n$ together with its normalization
$\sqrt n(\mu_n-\mu)$. Beside this, take a function $f(x_1,\dots,x_k)$
of $k$ variables on the $k$-fold product $(X^k,\Cal X^k)$ of the space
$(X,\Cal X)$, introduce the $k$-th power of the normalized
empirical measure $\sqrt n(\mu_n-\mu)$ on $(X^k,\Cal X^k)$, and
define the integral of the function $f$ with respect to this
signed product measure. This integral is a random variable, and we
want to give a good estimate on its tail distribution. More precisely,
we take the integrals not on the whole space, the diagonals
$x_s=x_{s'}$, $1\le s,s'\le k$, $s\neq s'$, of the space $X^k$ are
omitted from the domain of integration. Such a modification of the
integral seems to be natural.

We shall also be interested in the following generalized version of
the above problem. Let us have a nice class of functions $\Cal F$
of $k$ variables on the product space $(X^k,\Cal X^k)$, and consider
the integrals of all functions in this class with respect to the
$k$-fold direct product of our normalized empirical measure. Give a
good estimate on the tail distribution of the supremum of these
integrals.

It may be asked why the above problems deserve a closer study. I
found them important, because they may help in solving some essential
problems in probability theory and mathematical statistics. I met
such problems when I tried to adapt the method of proof about the
Gaussian limit behaviour of the maximum likelihood estimate to some
similar but more difficult questions. In the original problem the
asymptotic behaviour of the solution of the so-called maximum
likelihood equation has to be investigated. The study of this
problem is hard in its original form. But by applying an appropriate
Taylor expansion of the function that appears in this equation and
throwing away its higher order terms we get an approximation whose
behaviour can be simply understood. So to describe the limit
behaviour of the maximum likelihood estimate it suffices to show
that this approximation causes only a negligible error.

One would try to apply a similar procedure in more difficult
situations. I met some non-parametric maximum likelihood problems,
for instance the description of the limit behaviour of the so-called
Kaplan--Meyer product limit estimate when such an approach could be
applied. But in these problems it was harder to justify that the
simplifying approximation causes only a negligible error. To
show this, the solution of the above mentioned problems was needed.
In the non-parametric maximum likelihood estimate problems I met, the
estimation of multiple (random) integrals played a role similar to
the estimation of the coefficients in the Taylor expansion in the
study of maximum likelihood estimates. Although I could apply
this approach only in some special cases, I believe that it works
in very general situations. But it demands some further work to
show this.

The above formulated problems about random integrals are interesting
and non-trivial even in the special case $k=1$. Their solution
leads to some interesting and non-trivial generalization
of the fundamental theorem of the mathematical statistics about
the difference of the empirical and real distribution of a large
sample.

These problems have a natural counterpart about the behaviour of
so-called $U$-statistics, a fairly popular subject in probability
theory. The investigation of multiple random integrals and
$U$-statistics are closely related, and it turned out that it is
useful to consider them simultaneously.

Let us try to get some feeling about what kind of results can be
expected in these problems. For a large sample size $n$ the
normalized empirical measure $\sqrt n(\mu_n-\mu)$ behaves similarly
to a Gaussian random measure. This suggests that in the problems we
are interested in similar results should hold as in the problems
about multiple Gaussian integrals, called Wiener--It\^o integrals in
the literature. We may expect that the tail behaviour of the
distribution of a $k$-fold random integral with respect to a
normalized empirical measure is similar to that of the $k$-th power
of a Gaussian random variable with expectation zero and an
appropriate variance. Beside this, a similar estimate should hold
for the supremum of multiple random integrals of a class of
functions with respect to a normalized empirical measure or with
respect to a Gaussian random measure under not too restrictive
conditions. We may also hope that the methods of the theory of
multiple Gaussian integrals can be adapted to the investigation
of our problems.

The above consideration supplies a fairly good description of the
situation, but it does not take into account a very essential
difference between the behaviour of multiple Gaussian integrals and
multiple integrals with respect to a normalized empirical measure.
If the variance of a multiple integral with respect to a normalized
empirical measure is very small, what turns out to be equivalent to
a very small $L_2$-norm of the function we are integrating, then the
behaviour of this integral is different from that of a multiple
Gaussian integral with the same kernel function. In this case the
effect of some irregularities of the normalized empirical distribution
turns out to be non-negligible, and no good Gaussian approximation
holds any longer. This case must be better understood, and some
new methods have to be worked out to handle it.

The precise formulation of the results will be given in the
main part of the work. Beside their proof I also tried to explain
the main ideas behind them and the notions introduced in their
investigation. This work contains some new results, and also the
proof of some already rather classical theorems is presented.
The results about Gaussian random variables and their non-linear
functionals, in particular multiple integrals with respect to a
Gaussian field, have a most important role in the study of the
present work. Hence they will be discussed in detail together
with some counterparts about multiple random integrals with
respect to a normalized empirical measure and some results about
$U$-statistics.

The proofs apply results from different parts of the probability
theory. Papers investigating similar results refer to works dealing
with quite different subjects, and this makes their reading rather
hard. To overcome this difficulty I tried to work out the details
and to present a self-contained discussion even at the price of a
longer text. Thus I wrote down (in the main text or in the Appendix)
the proof of many interesting and basic results, like results about
Vapnik--\v{C}ervonenkis classes, about $U$-statistics and their
decomposition to sums of so-called degenerate $U$-statistics, about
so-called decoupled $U$-statistics and their relation to ordinary
$U$-statistics, the diagram formula about the product of 
Wiener--It\^o integrals, their counterpart about the product of 
degenerate $U$-statistics, etc. I tried to give such an exposition 
where different parts of the problem are explained independently of 
each other, and they can be understood in themselves.

An earlier version of this work was explained at the probability
seminar of the University Debrecen (Hungary).

\beginsection 2. Motivation of the investigation. Discussion of
some problems.

Here I try to show by means of some examples why the solution of
the problems mentioned in the introduction may be useful in the
study of some important problems of the probability theory. I try
to give a good picture about the main ideas, but I do not work out
all details. Actually, the elaboration of some details omitted
would demand hard work. But as the discussion of this section is
quite independent of the rest of the paper, these omissions cause
no problem in understanding the subsequent part.

I start with a short discussion of the maximum likelihood
estimate in the simplest case. The following problem is considered.
Let us have a class of density functions $f(x,\vartheta)$ on the
real line depending on a parameter $\vartheta\in R^1$, and
observe a sequence of independent random variables
$\xi_1(\omega),\dots,\xi_n(\omega)$ with a density function
$f(x,\vartheta_0)$, where $\vartheta_0$ is an unknown parameter
we want to estimate with the help of the above sequence of random
variables.

The maximum likelihood method suggests the following approach. Choose
that value $\hat\vartheta_n =\hat\vartheta_n(\xi_1,\dots,\xi_n)$ as
the estimate of the parameter $\vartheta_0$ where the density function
of the random vector $(\xi_1,\dots,\xi_n)$, i.e.\ the product
$$
\prod_{k=1}^n f(\xi_k,\vartheta)=\exp\left\{\sum_{k=1}^n\log
f(\xi_k,\vartheta)\right\}
$$
takes its maximum. This point can be found as the solution of the
so-called maximum likelihood equation
$$
\sum_{k=1}^n\frac{\partial}{\partial\vartheta}\log
f(\xi_k,\vartheta)=0. \tag2.1
$$
We are interested in the asymptotic behaviour of the random variable
$\hat\vartheta_n-\vartheta_0$, where $\hat\vartheta_n$ is the
(appropriate) solution of the equation~(2.1).

The direct study of this equation is rather hard, but a Taylor
expansion of the expression at the left-hand side of~(2.1) around
the (unknown) point $\vartheta_0$ yields a good and simple
approximation of $\hat\vartheta_n$, and it enables us to describe
the asymptotic behaviour of $\hat\vartheta_n-\vartheta_0$.

This Taylor expansion yields that
$$ \allowdisplaybreaks
\align
&\sum_{k=1}^n\frac{\partial}{\partial\vartheta}\log
f(\xi_k,\hat\vartheta_n)=
\sum_{k=1}^n\frac{\frac{\partial}{\partial\vartheta}
f(\xi_k,\vartheta_0)}{f(\xi_k,\vartheta_0)}\\
&\qquad\qquad+(\hat\vartheta_n-\vartheta_0)
\(\sum_{k=1}^n\(\frac{\frac{\partial^2}{\partial\vartheta^2}
f(\xi_k,\vartheta_0)}{f(\xi_k,\vartheta_0)}-
\frac{\(\frac{\partial}{\partial\vartheta}
f(\xi_k,\vartheta_0)\)^2}{f^2(\xi_k,\bar\vartheta_0)} \)\)
+O\(n(\hat\vartheta_n-\vartheta_0)^2\) \\
&=\qquad \sum_{k=1}^n\(\eta_k+\zeta_k(\hat\vartheta_n-\vartheta_0)\)
+O\(n(\hat\vartheta_n-\vartheta_0)^2\),  \tag2.2
\endalign
$$
where
$$
\eta_k=\frac{\frac{\partial}{\partial\vartheta}
f(\xi_k,\vartheta_0)}{f(\xi_k,\vartheta_0)}\quad \text{and}\quad
\zeta_k=
\frac{\frac{\partial^2}{\partial\vartheta^2}
f(\xi_k,\vartheta_0)}{f(\xi_k,\vartheta_0)}-
\frac{ \left( \frac{\partial}{\partial\vartheta}
f( \xi_k,\vartheta_0)\right)^2}{f^2(\xi_k,\bar\vartheta_0)}
$$
for $k=1,\dots,n$. We want to understand the asymptotic behaviour
of the (random) expression on the right-hand side of~(2.2). The
relation
$$
E\eta_k=\int\frac{\frac{\partial}{\partial\vartheta}
f(x,\vartheta_0)}{f(x,\vartheta_0)}f(x,\vartheta_0)\,dx
=\frac{\partial}{\partial\vartheta}\int
f(x,\vartheta_0)\,dx=0
$$
holds, since $\int f(x,\vartheta)\,dx=1$ for all $\vartheta$,
and a differentiation of this relation gives the last identity.
Similarly,
$E\eta^2_k=-E\zeta_k=\int\frac{\(\frac{\partial}{\partial\vartheta}
f(x,\vartheta_0)\right)^2}{f(x,\vartheta_0)}\,dx>0$, \
$k=1,\dots,n$. Hence by the central limit theorem
$\chi_n=\frac{1}{\sqrt n}\summ_{k=1}^n\eta_k$
is asymptotically normal with expectation zero and variance
$I^2=\int\frac{\left(\frac{\partial}{\partial\vartheta}
f(x,\vartheta_0)\right)^2}{f(x,\vartheta_0)}\,dx>0$.
In the statistics literature this number $I$ is called the Fisher
information. By the laws of large numbers
$\frac{1}{n}\summ_{k=1}^n\zeta_k\sim -I^2$.

Thus relation (2.2) suggests the approximation $\tilde\vartheta_n=
-\frac{\summ_{k=1}^n\eta_k}{\summ_{k=1}^n\zeta_k}$ of the
maximum-likelihood estimate $\hat\vartheta_n$, and $\sqrt
n(\tilde\vartheta_n-\vartheta_0)$ is asymptotically normal with
expectation zero and variance~$\frac1{I^2}$. The random variable
$\tilde\vartheta_n$ is not a solution of the equation (2.1),
the value of the expression at the left-hand side is of order
$O(n(\tilde\vartheta_n-\vartheta_0)^2)=O(1)$ in this point. On
the other hand, the derivative of the function at the left-hand
side is large in this point, it is greater than $\const n$ with
some $\const>0$. This implies that the maximum-likelihood equation
has a solution $\hat\vartheta_n$ such that
$\hat\vartheta_n-\tilde\vartheta_n=O\(\frac1n\)$. Hence
$\sqrt n(\hat\vartheta_n-\vartheta_0)$ and
$\sqrt n(\tilde\vartheta_n-\vartheta_0)$ have the same asymptotic
limit behaviour.

The previous method can be summarized in the following way:
Take a simpler linearized version of the expression we want to
estimate by means of an appropriate Taylor expansion, describe the
limit distribution of this linearized version and show that the
linearization causes only a negligible error.

We want to show that such a method also works in more difficult
situations. But in some cases it is harder to show that the error
committed by a replacement of the original expression by a simpler
linearized version is negligible, and to show this the solution of
the problems mentioned in the introduction is needed. The discussion
of the following problem, called the Kaplan--Meyer method for the
estimation of the empirical distribution function with the help of
censored data shows such an example.

The following problem is considered. Let $(X_i,Z_i)$, $i=1,\dots,n$,
be a sequence of independent, identically distributed random vectors
such that the components $X_i$ and $Z_i$ are also independent with
some unknown distribution functions $F(x)$ and $G(x)$. We want to
estimate the distribution function $F$ of the random variables $X_i$,
but we cannot observe the variables $X_i$, only the random variables
$Y_i=\min(X_i,Z_i)$ and $\delta_i=I(X_i\leq Z_i)$. In other words, we
want to solve the following problem. There are certain objects whose
lifetime $X_i$ are independent and $F$ distributed. But we cannot
observe this lifetime $X_i$, because after a time $Z_i$  the
observation must be stopped. We also know whether the real lifetime
$X_i$ or the censoring variable $Z_i$ was observed. We make $n$
independent experiments and want to estimate with their help the
distribution function~$F$.

Kaplan and Meyer, on the basis of some maximum-likelihood estimation
type considerations, proposed the following so-called product limit
estimator $S_n(u)$ to estimate the unknown survival function
$S(u)=1-F(u)$:
$$
1-F_n(u)=S_n(u)=\left\{
\alignedat2
&\prod_{i=1}^n\left(\frac{N(Y_i)}{N(Y_i)+1}\right)^{I(Y_i\leq u,
\delta_i=1)} && \text{ if }u\leq\max(Y_1,\dots,Y_n)\\
&0&& \text{ if } u\geq\max(Y_1,\dots,Y_n),\;\delta_n =1,\\
&\text{undefined} &&\text{ if }u\geq\max(Y_1,\dots,Y_n),\;\delta_n
=0, \endalignedat\right. \tag2.3
$$
where
$$
N(t)=\#\{Y_i,\;\;Y_i>t,\;1\le i \le n\}=\sum_{i=1}^n I(Y_i>t).
$$

We want to show that the above estimate (2.3) is really good.
For this goal we shall approximate the random variables $S_n(u)$ by
some appropriate random variables. To do this first we introduce some
notations.

Put
$$
\aligned
H(u) &=P(Y_i\leq u)=1-\bar H(u),\\
\tilde H(u) &=P(Y_i\leq u,\,\delta_i=1),\quad
\tilde{\tilde H}(u)=P(Y_i\leq u,\,\delta_i =0)
\endaligned \tag2.4
$$
and
$$
\aligned
H_n(u) &=\frac{1}{n} \sum_{i=1}^n I( Y_i \leq u)\\
\tilde H_n(u) &=\frac1n \sum_{i=1}^n I(Y_i\leq u,\, \delta_i
=1), \quad \tilde{\tilde H}_n(u)=\frac{1}{n}\sum_{i=1}^n I( Y_i
\leq u, \, \delta_i=0).
\endaligned\tag2.5
$$
Clearly $H(u)=\tilde H(u)+\tilde{\tilde H}(u)$ and
$ H_n(u)=\tilde H_n(u)+\tilde{\tilde H}_n(u)$.
We shall estimate $F_n(u)-F(u)$ for $u\in(-\infty, T]$ if
$$
1-H(T)>\delta \quad \text{with some fixed } \delta>0. \tag2.6
$$
Condition (2.6) implies that there are more than $\frac\delta2n$
sample points $Y_j$ larger than~$T$ with probability almost 1. The
complementary event has only an exponentially small probability.
This observation helps to show in the subsequent calculations that
some events have negligibly small probability.

We introduce the so-called cumulative hazard function and its
empirical version
$$
\Lambda(u)=-\log(1-F(u)), \quad \Lambda_n(u)=-\log(1-F_n(u)). \tag2.7
$$
Since $F_n(u)-F(u)=\exp(-\Lambda(u))\(1-\exp(\Lambda(u)-\Lambda_n(u))\)$
a simple Taylor expansion yields
$$
F_n(u)-F(u)=(1-F(u))\left(\Lambda_n(u)-\Lambda(u)\right)+R_1(u),\tag2.8
$$
and it is easy to see that $R_1(u)=O\(\Lambda(u)-\Lambda_n(u))^2\)$.
It follows from the subsequent estimations that
$\Lambda(u)-\Lambda_n(u)=O(n^{-1/2})$, thus $nR_1(u)=O(1)$. Hence it
is enough to investigate the term $\Lambda_n(u)$. We shall show that
$\Lambda_n(u)$ has an expansion with $\Lambda(u)$ as the main term
plus $n^{-1/2}$ times a term which is a linear functional of an
appropriate normalized empirical distribution function plus an error
term of order $O(n^{-1})$.

From~(2.3) it is obvious that
$$
\Lambda_n(u)=-\sum_{i=1}^n I(Y_i\leq u, \, \delta_i=1)
\log\left(1-\frac{1}{1+N(Y_i)}\right).
$$
It is not difficult to get rid of the unpleasant logarithmic function
in this formula by means of the relation $-\log(1-x)=x+O(x^2)$ for
small~$x$. It yields that
$$
\Lambda_n(u)=\sum_{i=1}^n \frac{I(Y_i\leq u, \,\delta_i=1)}{N(Y_i)}
+R_2(u)=\tilde{\Lambda}_n(u)+R_2(u),  \tag2.9
$$
and the error term $nR_2(u)$ is exponentially small.

The expression $\tilde{\Lambda}_n(u)$ is still inappropriate for our
purposes. Since the denominators $N(Y_i)=\summ_{j=1}^n I(Y_j>Y_i)$
are dependent for different indices~$i$ we cannot see directly the
limit behaviour of $\tilde{\Lambda}_n(u)$.

We try to approximate $\tilde{\Lambda}_n(u)$ by a simpler
expression. A natural approach would be to approximate the terms
$N(Y_i)$ in it by their conditional expectation $(n-1)\bar
H(Y_i)=(n-1)(1-H(Y_i))=E(N(Y_i)|Y_i)$. This is a too rough `first
order' approximation, but the following `second order approximation'
will be sufficient for our goals. Put
$$
N(Y_i)=\sum_{j=1}^n I(Y_j>Y_i)=n\bar H(Y_i) \(1+
\frac{\summ_{j=1}^nI(Y_j>Y_i)-n\bar H(Y_i)}{n\bar H(Y_i)}\)
$$
and express the terms $\frac1{N(Y_i)}$ in the sum defining
$\tilde \Lambda_n$ by means of the relation
$\frac1{1+z}=\summ_{k=0}^\infty (-1)^kz^k=1-z+\e(z)$ with the choice
$z=\frac{\summ_{j=1}^nI(Y_j>Y_i)-n\bar H(Y_i)}{n\bar H(Y_i)}$. As
$|\e(z)|<2z^2$ for $|z|<\frac{1}{2}$ we get that
$$
\align
\tilde{\Lambda}_n(u)&
=\sum_{i=1}^n\frac{I(Y_i\leq u,\,\delta_i=1)}
{n\bar H(Y_i)}\(1+\sum_{k=1}^\infty\(- \frac{\summ_{j=1}^n
I(Y_j>Y_i)-n\bar H(Y_i)} {n\bar H(Y_i)}\)^k\)\\
&=\sum_{i=1}^n\frac{I(Y_i\leq u,\,\delta_i=1)}
{n\bar H(Y_i)}\(1-\frac{\summ_{j=1}^n I(Y_j>Y_i)-n\bar H(Y_i)}
{n\bar H(Y_i)}\)+R_3(u) \tag2.10 \\
&=2A(u)-B(u)+R_3(u),
\endalign
$$
where
$$
A(u)=A(n,u)=\sum_{i=1}^n\frac{I(Y_i\leq u,\,\delta_i=1)}{n\bar H(Y_i)}
$$
and
$$
B(u)=B(n,u)=\sum_{i=1}^n \sum_{j=1}^n\frac
{I(Y_i\leq u,\,\delta_i=1)I(Y_j>Y_i)}{n^2\bar H^2(Y_i)}.
$$
It can be proved by means of standard methods that $nR_3(u)$ is
exponentially small. Thus relations~(2.9) and~(2.10) yield that
$$
\Lambda_n(u)=2A(u)-B(u)+\text{negligible error.}\tag2.11
$$

This means that to solve our problem the asymptotic behaviour of the
random variables $A(u)$ and $B(u)$ has to be given. We can get a
better insight to this problem by rewriting the sum $A(u)$ as an
integral and the double sum $B(u)$ as a two-fold integral with
respect to empirical measures. Then these integrals can be rewritten
as sums of random integrals with respect to normalized empirical
measures and deterministic measures. Such an approach yields a
representation of $\Lambda_n(u)$ in the form of a sum whose terms
can be well understood.

Let us write
$$
\align
A(u)&=\int_{-\infty}^{+\infty}\frac{I(y\leq u)}{1-H(y)}\,d\tilde
H_n(y),\\
B(u) &=\int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}
\frac{I(y\leq u)I(x>y)}{\(1-H(y)\)^2}\,dH_n(x) d\tilde H_n(y).
\endalign
$$

To rewrite the term $B(u)$ in a form better for our purposes observe
that
$$
\align
H_n(x)\tilde H_n(y)&=H(x)\tilde H(y)+H(x)(\tilde H_n(y)-\tilde H(y))
+(H_n(x)-H(x))\tilde H(y)\\
&\qquad+(H_n(x)-H(x))(\tilde H_n(y)-\tilde H(y)).
\endalign
$$
Hence it can be written in the form
$B(u)=B_1(u)+B_2(u)+B_3(u)+B_4(u)$, where
$$
\align
B_1(u)&=\int_{-\infty}^u\int_{-\infty}^{+\infty}
\frac{I(x>y)}{\(1-H(y)\)^2}\,dH(x)\,d\tilde H(y)\;,\\
B_2(u) &=\frac{1}{\sqrt n}\int_{-\infty}^u\int_{-\infty}^{+\infty}
\frac{I(x>y)}{\(1-H(y)\)^2}\,dH(x)\,d\(\sqrt n
(\tilde H_n(y)-\tilde H(y))\),\\
B_3(u)&=\frac1{\sqrt n}\int_{-\infty}^u
\int_{-\infty}^{+\infty}\frac{I(x>y)}{\(1-H(y)\)^2}
\,d\(\sqrt n\(H_n(x)-H(x)\)\)\,d\tilde H(y)\;,\\
B_4(u)&=\frac 1n \int_{-\infty}^u\int_{-\infty}^{+\infty}
\frac{I(x>y)}{\(1-H(y)\)^2}\,d\(\sqrt n\(H_n(x)-H(x)\)\)\,
d\(\sqrt n(\tilde H_n(y)-\tilde H(y))\).
\endalign
$$
In the above decomposition of $B(u)$ the term $B_1$ is a
deterministic function, $B_2$, $B_3$ are linear functionals of
normalized empirical processes and $B_4$ is a nonlinear functional
of normalized empirical processes. The deterministic term $B_1(u)$
can be calculated explicitly. Indeed,
$$
B_1(u)=\int_{-\infty}^u\int_{-\infty}^{+\infty}
\frac{I(x>y)}{\(1-H(y)\)^2}\,dH(x) d\tilde H(y)=
\int_{-\infty}^u\frac{d\tilde H(y)}{1-H(y)}.
$$
Then the relations
$\tilde H(u)=\int_{-\infty}^u\(1-G(t)\)\,dF(t)$ and
$1-H = (1-F)(1-G)$ imply that
$$
B_1(u)=\int_{-\infty}^u\frac{dF(y)}{1-F(y)}=
-\log(1-F(u))=\Lambda(u).\tag2.12
$$
Observe that
$$
\aligned
A(u) &=\int_{-\infty}^u\frac{d\,\tilde H_n(y)}{1-H(y)}\\
&=\int_{-\infty}^u\frac{d\tilde H(y)}{1-H(y)}+
\frac1{\sqrt n}\int_{-\infty}^u
\frac{d \(\sqrt n (\tilde H_n(y)-\tilde H(y))\)}{1-H(y)}\\
&=B_1(u)+B_2(u).
\endaligned\tag2.13
$$
From relations~(2.11), (2.12) and~(2.13) it follows that
$$
\Lambda_n(u)-\Lambda(u)=B_2(u)-B_3(u)-B_4(u)+\text{negligible error.}
\tag2.14
$$
Integration of $B_2$  and $B_3$ with respect to the variable $x$ and then
integration by parts in the expression $B_2$ yields that
$$
\align
B_2(u)&=\frac1{\sqrt n}\int_{-\infty}^{u}
\frac{d\(\sqrt n(\tilde H_n(y)-\tilde H(y))\)}{1-H(y)}\\
&=\frac{\sqrt n\(\tilde H_n(u)-\tilde H(u)\)}{\sqrt n(1-H(u))}-
\frac1{\sqrt n}\int_{-\infty}^{u}
\frac{\sqrt n(\tilde H_n(y)-\tilde H(y))}{\(1-H(y)\)^2}\,dH(y)\\
B_3(u)&=\frac1{\sqrt n}\int_{-\infty}^u
\frac{\sqrt n\(H(y)-H_n(y)\)}{\(1-H(y)\)^2}\,d\tilde H(y).
\endalign
$$
With the help of the above expressions for $B_2$ and $B_3$,~(2.14)
can be rewritten as
$$
\aligned
\sqrt n\(\Lambda_n(u)-\Lambda(u)\)
&=\frac{\sqrt n\(\tilde H_n(u)-\tilde H(u)\)}{1-H(u)}-\int_{-\infty}^u
\frac{\sqrt n(\tilde H_n(y)-\tilde H(y))}{\(1-H(y)\)^2}\,dH(y)\\
&\qquad+\int_{-\infty}^u\frac{\sqrt n\(H_n(y)-H(y)\)}{\(1-H(y)\)^2}
\,d\tilde H(y)\\
&\qquad-\sqrt n B_4(u)+\text{negligible error.}
\endaligned\tag2.15
$$
Formula (2.15) almost agrees with the statement we wanted to prove.
Here the normalized error $\sqrt n\(\Lambda_n(u)-\Lambda(u)\)$ is
expressed as a sum of linear functionals of normalized empirical
measures plus some negligible error terms plus the error term
$\sqrt nB_4(u)$. So to get a complete proof it
is enough to show that $\sqrt nB_4(u)$ also yields a negligible
error. But $B_4(u)$ is a double integral of a bounded function (here
we apply again formula (2.6)) with respect to a normalized empirical
measure. Hence to bound this term we need a good estimate of
multiple stochastic integrals (with multiplicity~2), and this is just
the problem formulated in the introduction. The estimate we need
here follows from Theorem~8.1 of the present work. Let us remark
that the problem discussed here corresponds to the estimation of the
coefficient of the second term in the Taylor expansion considered
in the study of the maximum likelihood estimation. One may worry a
little bit how to bound $B_4(u)$ with the help of estimations of
double stochastic integrals, since in the definition of $B_4(u)$
integration is taken with respect to different normalized empirical
processes in the two coordinates. But this is a not too difficult
technical problem. It can be simply overcome for instance by
rewriting the integral as a double integral with respect to the
empirical process
$\(\sqrt n\(H_n(x)-H(x)\),\sqrt n\(\tilde H_n(y)-\tilde H(y)\)\)$
in the space $R^2$.

By working out the details of the above calculation we get that
the linear functional $B_2(u)-B_3(u)$ of normalized empirical
processes yields a good estimate on the expression $\sqrt
n(\Lambda_n(u)-\Lambda(u))$ for a fixed parameter~$u$. But we want
to prove somewhat more, we want to get an estimate uniform in the
parameter~$u$, i.e. to show that even the random variable
$\supp_{u\le T}\left|\sqrt n(\Lambda_n(u)-\Lambda(u))-B_2(u)+B_3(u)\right|$
is small. This can be done by making estimates uniform in the
parameter~$u$ in all steps of the above calculation. There appears
only one difficulty when trying to carry out this program. Namely,
we need an estimate on $\supp_u |B_4(u)|$, i.e. we have to bound the
supremum of multiple random integrals with respect to a normalized
random measure for a nice class of kernel functions. This can be
done, but at this point the second problem mentioned in the
introduction appears. This difficulty can be overcome by means of
Theorem~8.2 of this work.

Thus the limit behaviour of the Kaplan--Meyer estimate can be
described by means of an appropriate expansion. The steps of the
calculation leading to such an expansion are fairly standard, the
only hard part is the solution of the problems mentioned in the
introduction. It can be expected that such a method also works in
a much more general situation.

I finish this section with a remark of Richard Gill he made
in a personal conversation after my talk on this subject at a
conference. He told that this approach had given a complete proof
about the limit behaviour of this estimate, but it had exploited the
explicit formula given in the Kaplan--Meyer estimate. He missed the
application of an argument based on the non-parametric maximum
likelihood character of this estimate. This was a completely justified
remark, since if we do not restrict our attention to this problem, but
try to generalize it to general non-parametric maximum likelihood
estimates, then we have to understand how the maximum likelihood
character can be exploited. I believe that this can be done, but it
demands further studies.

\beginsection 3. Some estimates about sums of independent random
variables.

We need some results about the distribution of sums of independent
random variables bounded by a constant with probability one. Later
only the results about sums of independent and identically
distributed variables will be interesting for us. But since they
can be generalized without any effort to sums of not
necessarily identically distributed random variables the condition
about identical distribution of the summands will be dropped.
We are interested in the question when these
estimates give such a good bound as the central limit theorem
suggests, and what can be told otherwise.

More explicitly, the following problem will be considered: Let
$X_1,\dots,X_n$ be independent random variables, $EX_j=0$,
$\Var X_j=\sigma_j^2$, $1\le j\le n$, and take the random sum
$S_n=\summ_{j=1}^nX_j$ and its variance
$\Var S_n=V_n^2=\summ_{j=1}^n\sigma_j^2$. We want to get a good
bound on the probability $P(S_n>u V_n)$. The central limit theorem
suggests that under general conditions an upper bound of the
order $1-\Phi(u)$ should hold for this probability, where $\Phi(u)$
denotes the standard normal distribution function. Since the
standard normal distribution function satisfies the inequality
$\(\frac1u-\frac1{u^3}\)\frac{e^{-u^2/2}}{\sqrt{2\pi}} <1-\Phi(u)<
\frac1u\frac{e^{-u^2/2}}{\sqrt{2\pi}}$ for all $u>0$ it is natural
to ask when the probability $P(S_n >uV_n)$ is comparable with the
value $e^{-u^2/2}$. More generally, we shall call an upper bound of
the form $P(S_n>uV_n)\le e^{-Cu^2}$ with some constant $C>0$ a
Gaussian type estimate.

First I formulate Bernstein's inequality which tells for which values
$u$ the probability $P(S_n>uV_n)$ has a Gaussian type estimate.
It supplies such an estimate if $u\le \const V_n$. On the other hand,
for $u\ge\const V_n$ it yields a much weaker estimate. I also present
an example which shows that in this case only a very weak improvement
of Bernstein's inequality is possible. I also discuss another result,
called Bennett's inequality, which shows that such an improvement is
possible. The main difficulties we meet in this work are closely
related to the weakness of the estimates we have for the probability
of the event $P(S_n>uV_n)$ if $u\gg \const V_n$.

In the usual formulation of Bernstein's inequality a
real number~$M$ is introduced, and it is assumed that the terms in
the sum we investigate are bounded by this number. But since the
problem can be simply reduced to the special case $M=1$ I shall
consider only this special case.

\medskip\noindent
{\bf Theorem 3.1. (Bernstein's inequality).} {\it Let
$X_1,\dots,X_n$ be independent random variables, $P(|X_j|\le1)=1$,
$EX_j=0$, $1\le j\le n$. Put $\sigma_j^2=EX_j^2$, $1\le j\le n$,
$S_n=\summ_{j=1}^n X_j$ and $V_n^2=\Var S_n=\summ_{j=1}^n\sigma_j^2$.
Then
$$
P\(S_n>uV_n\)\le\exp\left\{-\frac{u^2}{2\(1+\frac13\frac
u{V_n}\)} \right\} \quad\text{for all }u>0. \tag3.1
$$
}

\medskip\noindent
{\it Proof of Theorem 3.1.} Let us give a good bound on the
exponential moments $Ee^{tS_n}$ for appropriate parameters
$t>0$. Since $EX_j=0$ and $E|X_j^{k+2}|\le\sigma^2$ for $k\ge0$ we can
write $Ee^{tX_j}=\summ_{k=0}^\infty\frac{t^k}{k!}EX_j^k
\le 1+\frac{t^2\sigma_j^2}2\(1+\summ_{k=1}^\infty
\frac {2t^{k}}{(k+2)!}\) \le 1+\frac{t^2\sigma_j^2}2
\(1+\summ_{k=1}^\infty 3^{-k}t^{k}\)
= 1+\frac{t^2\sigma_j^2}2\frac1{1-\frac t3}
\le\exp\left\{\frac{t^2\sigma_j^2}2\frac1{1-\frac t3}\right\}$
if $0\le t<3$. Hence $Ee^{tS_n}=\prodd_{j=1}^n Ee^{tX_j}\le
\exp\left\{\frac{t^2V_n^2}2\frac1{1-\frac t3}\right\}$ for $0\le t<3$.

The above relation implies that
$$
P\(S_n>uV_n\)=P(e^{tS_n}>e^{tuV_n})\le
Ee^{tS_n}e^{-tuV_n}\le \exp\left\{\frac{t^2V_n^2}2\frac1{1-\frac
t3}-tuV_n\right\}
$$
if $0\le t<3$. Choose the number $t$ in this inequality as the
solution of the equation $t^2V_n^2\frac1{1-\frac t3}=tuV_n$, i.e.
put $t=\frac u{V_n+\frac u3}$. Then $0\le t<3$, and we get that
$P(S_n>uV_n)\le e^{-tuV_n/2}=
\exp\left\{-\frac{u^2}{2\(1+\frac13\frac u{V_n}\)}\right\}$.

\medskip
If the random variables $X_1,\dots,X_n$ satisfy the conditions of
Bernstein's inequality, then also the random variables
$-X_1,\dots,-X_n$ satisfy them. By applying the above result in both
cases we get that
$P(|S_n|>uV_n)\le2\exp\left\{-\frac{u^2}{2\(1+\frac13\frac u{V_n}\)}
\right\}$ under the conditions of Bernstein's inequality.

\medskip
By Bernstein's inequality for all $\e>0$ there is some  number
$\alpha(\e)>0$ such that in the case $\frac u{V_n}<\alpha(\e)$
$P(S_n>uV_n)\le e^{-(1-\e)u^2/2}$. Beside this, for all fixed
numbers $A>0$ there is some constant $C=C(A)>0$ such that in the
case $\frac u{V_n}<A$ the inequality $P(S_n>uV_n)\le e^{-Cu^2}$
holds. This can be interpreted as a Gaussian type estimate for the
probability $P(S_n>uV_n)$ if $u\le \const V_n$.

On the other hand, if $\frac u{V_n}$ is very large, then Bernstein's
inequality yields a much worse estimate. The question arises whether
in this case Berstein's inequality can be replaced by a better, more
useful result. Next we present Theorem~3.2, the so-called Bennett's
inequality which provides a slight improvement of Bernstein's
inequality. But if $\frac u{V_n}$ is very large, then also
Bennett's inequality provides a much weaker estimate on the
probability $P(S_n>uV_n)$ than the bound suggested by a Gaussian
comparison. On the other hand, we shall give an example that shows
that (without imposing some additional conditions) no real
improvement of this estimate is possible.

\medskip\noindent
{\bf Theorem 3.2. (Bennett's inequality).} {\it Let $X_1,\dots,X_n$ be
independent random variables, $P(|X_j|\le1)=1$,
$EX_j=0$, $1\le j\le n$. Put $\sigma_j^2=EX_j^2$, $1\le j\le n$,
$S_n=\summ_{j=1}^n X_j$ and $V_n^2=\Var S_n=\summ_{j=1}^n\sigma_j^2$.
Then
$$
P(S_n>u)\le\exp\left\{-V^2_n\[\(1+\frac u{V^2_n}\)
\log\(1+\frac u{V^2_n}\)-\frac u{V^2_n}\]\right\}\quad\text{for all
}u>0. \tag3.2
$$
As a consequence, for all $\e>0$ there exists some $B=B(\e)>0$ such
that
$$
P\(S_n>u\)\le\exp\left\{-(1-\e)u\log \frac u{V^2_n}
\right\}\quad\text{if } u>BV_n^2, \tag3.3
$$
and there exists some positive constant $K>0$ such that
$$
P\(S_n>u\)\le\exp\left\{-Ku\log \frac u{V^2_n}
\right\}\quad\text{if }u>2V_n^2. \tag3.4
$$
}

\medskip\noindent
{\it Proof of Theorem 3.2.}\/ We have
$$
Ee^{tX_j}=\summ_{k=0}^\infty\frac{t^k}{k!}EX_j^k\le
1+\sigma_j^2\summ_{k=2}^\infty\frac {t^k}{k!}=1+\sigma_j^2
\(e^t-1-t\)\le e^{\sigma_j^2(e^t-1-t)}, \quad 1\le j\le n,
$$
and $Ee^{tS_n}\le e^{V_n^2(e^t-1-t)}$ for all $t\ge0$. Hence
$P(S_n>u)\le e^{-tu}Ee^{tS_n}\le e^{-tu+V_n^2(e^t-1-t)}$ for all
$t\ge0$. We get relation (3.2) from this inequality with the choice
$t=\log\(1+\frac u{V^2_n}\)$. (This is the place of minimum of the
function $-tu+V_n^2(e^t-1-t)$ for fixed $u$ in the parameter~$t$.)

Relation (3.2) and the observation
$\limm_{v\to\infty}\frac{(v+1)\log(v+1)-v}{v\log v}=1$ with the
choice $v=\frac u{V_n^2}$ imply formula~(3.3). Because of relation
(3.3) to prove formula (3.4) it is enough to check it for $2\le
\frac u{V_n^2}\le B$ with some sufficiently large constant $B>0$.
In this case relation (3.4) follows directly from formula (3.2).
This can be seen for instance by observing that the expression
$\frac{V^2_n\[\(1+\frac u{V^2_n}\)\log\(1+\frac u{V^2_n}\)-\frac
u{V^2_n}\]}{u\log\frac u{V^2_n}}$ is a continuous and positive
function of the variable $\frac u{V_n^2}$ in the interval $2\le
\frac u{V_n^2}\le B$, hence its minimum in this interval is strictly
positive.

\medskip
Let us make a short comparison between Bernstein's and Bennett's
inequality. Both results yield an estimate on the probability
$P(S_n>u)$, and their proofs are very similar. They are based on
an estimate of the moment generating functions $R_j(t)=Ee^{tX_j}$
of the summands~$X_j$, but Bennett's inequality yields a better
estimate. It may be worth mentioning that the estimate given for
$R_j(t)=Ee^{tX_j}$ in the proof of
Bennett's inequality agrees with the moment generating function
$Ee^{t(Y_j-EY_j)}$ of the normalization $Y_j-EY_j$ of a Poissonian
random  variable $Y_j$ with parameter $\Var X_j$. As a consequence,
we get, by using the standard method of estimating tail-distributions
by means of the moment generating functions such an estimate for the
probability $P(S_n>u)$ which is comparable with the probability
$P(T_n-ET_n>u)$, where $T_n$ is a Poissonian random variable with
parameter $V_n=\Var S_n$. It can be told that Bernstein's inequality
yields a Gaussian and Bennett's inequality a Poissonian type estimate
for the sums of independent, bounded random variables.

Next we present Example~3.3 which shows that Bennett's inequality
yields a sharp estimate also in the case $u\gg V_n^2$ when
Bernstein's inequality yields a weak bound. But Bennett's inequality
provides only a small improvement which has only a limited
importance. This may be the reason why Bernstein's inequality
which yields a more transparent estimate is more popular.

\medskip\noindent
{\bf Example 3.3. (Sums of independent random variables with bad
tail distribution for large values).} {\it Let us fix some
positive integer $n$, real numbers $u$ and $\sigma^2$ such that
$0<\sigma^2\le\frac18$, $n>4u\ge6$ and $u>4n\sigma^2$. Let
$\bar\sigma^2$ be that solution of the equation $x^2-x+\sigma^2=0$
which is smaller than~$\frac12$. Take a sequence of independent
and identically distributed random variables
$\bar X_1,\dots,\bar X_n$ such that $P(\bar X_j=1)=\bar\sigma^2$,
$P(\bar X_j=0)=1-\bar\sigma^2$ for all $1\le j\le n$. Put
$X_j=\bar X_j-E\bar X_j=X_j-\bar\sigma^2$, $1\le j\le n$,
$S_n=\sum\limits_{j=1}^n X_j$ and $V_n^2=n\sigma^2$.
Then $P(|X_1|\le1)=1$, $EX_1=0$, $\Var X_1=\sigma^2$, hence
$ES_n=0$, and $\Var S_n=V_n^2$. Beside this
$$
P(S_n\ge u)>\exp\left\{-Bu\log \frac u{V^2_n}\right\}
$$
with some appropriate constant $B>0$ not depending on~$n$,
$\sigma$ and~$u$.}

\medskip\noindent
{\it Proof of Example 3.3.}\/ Simple calculation shows that $EX_j=0$,
$\Var X_j=\bar\sigma^2-\bar\sigma^4=\sigma^2$, $P(|X_j|\le1)=0$, and
also the inequality $\sigma^2\le\bar\sigma^2\le\frac32\sigma^2$ holds.
To see the upper bound in the last inequality observe that
$\bar\sigma^2\le\frac13$, i.e. $1-\bar\sigma^2\ge\frac23$, hence
$\sigma^2=\bar\sigma^2(1-\bar\sigma^2)\ge\frac23\bar\sigma^2$. In
the proof of the inequality of Example~3.3 we can restrict our
attention to the case when $u$ is an integer, because in the
general case we can apply the inequality with $\bar u=[u]+1$
instead of~$u$, where $[u]$ denotes the integer part of~$u$, and
since $u\le\bar u\le 2u$, the application of the result in this
case supplies the desired inequality with a possibly worse
constant~$B>0$.

Put $\bar S_n=\summ_{j=1}^n\bar X_j$. We can write
$P(S_n\ge u)=P(\bar S_n\ge u+n\bar\sigma^2)\ge P(\bar S_n\ge2u)
\ge P(\bar S_n=2u)=\binom n{2u}\bar\sigma^{4u}(1-\bar\sigma^2)^{(n-2u)}
\ge(\frac {n\bar\sigma^2}{2u})^{2u}(1-\bar\sigma^2)^{(n-2u)}$,
since $u\ge n\bar\sigma^2$, and $n\ge2u$. On the other hand
$(1-\bar\sigma^2)^{(n-2u)}\ge e^{-2\bar\sigma^2(n-2u)}
\ge e^{-2n\bar\sigma^2}\ge e^{-u}$, hence
$$
\align
P(S_n\ge u)
&\ge\exp\left\{-2u\log\(\frac u{n\bar\sigma^2}\)-2u\log2-u\right\}\\
&=\exp\left\{-2u\log\(\frac u{n\sigma^2}\)
-2u\log\frac{\bar\sigma^2}{\sigma^2}-2u\log2-u\right\}\\
&\ge\exp\left\{-100u\log\(\frac u{V_n^2}\)\right\}.
\endalign
$$
Example~3.3 is proved.

\medskip
In the case $u>4V_n^2$ Bernstein's inequality yields the estimate
$P(S_n>u)\le e^{-\alpha u}$ with some universal constant $\alpha>0$,
and the above example shows that at most an additional logarithmic
factor $K\log\frac u{V_n^2}$ can be expected in the exponent of
the upper bound in an improvement of this estimate. Bennett's
inequality shows that such an improvement is really possible.

\medskip
 I finish this section with another estimate due to Hoeffding
which will be later useful in some symmetrization arguments.

\medskip\noindent
{\bf Theorem 3.4. (Hoeffding's inequality).} {\it Let $\e_1,\dots,\e_n$
be independent random variables, $P(\e_j=1)=P(\e_j=-1)=\frac12$, $1\le
j\le n$, and let $a_1,\dots,a_n$ be arbitrary real numbers. Put
$V=\summ_{j=1}^na_j\e_j$. Then
$$
P(V>u)\le\exp\left\{-\frac{u^2}{2\sum_{j=1}^na_j^2 }\right\}\quad
\text{for all }u>0. \tag3.5
$$
}

\medskip\noindent
{\it Remark 1:}\/ Clearly $EV=0$ and $\Var V=\summ_{j=1}^n a_j^2$,
hence Hoeffding's inequality yields such an estimate for $P(V>u)$
which the central limit theorem suggests. This estimate holds for
all real numbers $a_1,\dots,a_n$ and $u>0$.

\medskip\noindent
{\it Remark 2:}\/ The Rademacher functions $r_k(x)$, $k=1,2,\dots$,
defined by the formulas $r_k(x)=1$ if $(2j-1)2^{-k}\le x<2j2^{-k}$
and $r_k(x)=-1$ if $2(j-1)2^{-k}\le x<(2j-1)2^{-k}$,
$1\le j\le 2^{k-1}$, for all $k=1,2,\dots$, can be considered as
random variables on the probability space $\Omega=[0,1]$ with the
Borel $\sigma$-algebra and the Lebesgue measure as probability
measure on the interval $[0,1]$. They are independent random
variables with the same distribution as the random variables
$\e_1,\dots,\e_n$ considered in Theorem~3.4. Therefore results
about such sequences of random variables whose distributions agree
with those in~Theorem~3.4 are also called sometimes results about
Rademacher functions in the literature. At some points we will
also apply this terminology.

\medskip\noindent
{\it Proof of Theorem 3.4.} Let us give a good bound on the
exponential moment $Ee^{tV}$ for all $t>0$. The identity
$Ee^{tV}=\prodd_{j=1}^nEe^{ta_j\e_j}=
\prodd_{j=1}^n\frac{\(e^{a_jt}+e^{-a_jt}\)}2$ holds, and
$\frac{\(e^{a_jt}+e^{-a_jt}\)}2=\summ_{k=0}^\infty
\frac{a_{j}^{2k}} {(2k)!}t^{2k}\le \summ_{k=0}^\infty \frac
{(a_jt)^{2k}}{2^{k}k!}=e^{a_j^2t^2/2}$, since $(2k)!\ge 2^k k!$
for all $k\ge0$. This implies that $Ee^{tV}\le
\exp\left\{\frac{t^2}2\summ_{j=1}^n a_j^2\right\}$. Hence
$P(V>u)\le\exp\left\{-tu+\frac{t^2}2\summ_{j=1}^n a_j^2\right\}$,
and we get relation (3.5) with the choice $t=u\(\summ_{j=1}^n
a_j^2\)^{-1}$.

\beginsection 4. On the supremum of a nice class of partial sums.

This section contains an estimate about the supremum of a nice 
class of normalized sums of independent and identically 
distributed random variables together with an analogous result
about the supremum of an appropriate class of random one-fold 
integrals with respect to a normalized empirical measure. The 
second result deals with a one-variate version of the problem 
about the estimation of multiple integrals with respect to a 
normalized empirical measure. Thie problem was mentioned in 
the introduction. Some natural questions related to these 
results will be also discussed. It will be examined how 
restrictive their conditions are. In particular, we are 
interested in the question how the condition about the 
countable cardinality of the class of random variables can be 
weakened. A natural Gaussian counterpart of the supremum 
problems about random one-fold integrals will be also 
considered. Most proofs will be postponed to later sections.

To formulate these results first a notion will be
introduced that plays a most important role in the sequel.

\medskip\noindent
{\bf Definition of $L_p$-dense classes of functions.} {\it Let a
measurable space $(Y,\Cal Y)$ be given together with a set $\Cal G$
of $\Cal Y$ measurable real valued functions on this space. The
class of functions $\Cal G$ is called an $L_p$-dense class of
functions, $1\le p<\infty$, with parameter $D$ and exponent $L$ if
for all numbers $0<\e\le1$ and probability measures $\nu$ on the
space $(Y,\Cal Y)$ there exists a finite $\e$-dense subset
$\Cal G_{\e,\nu}=\{g_1,\dots,g_m\} \subset \Cal G$ in the space
$L_p(Y,\Cal Y,\nu)$ with $m\le D\e^{-L}$ elements, i.e. there exists
such a set $\Cal G_{\e,\nu}\subset \Cal G$ with $m\le D\e^{-L}$
elements for which
$\inff_{g_j\in \Cal G_{\e,\nu}}\int |g-g_j|^p\,d\nu<\e^p$ for all
functions $g\in \Cal G$. (Here the set $\Cal G_{\e,\nu}$ may depend
on the measure $\nu$, but its cardinality is bounded by a number
depending only on $\e$.)}

\medskip
In most results of this work the above defined $L_p$-dense classes
will be considered only for the parameter $p=2$. But at some
points it will be useful to work also with $L_p$-dense classes with
a different parameter~$p$. Hence to avoid some repetitions I
introduced the above definition for a general parameter~$p$.

The following estimate will be proved.

\medskip\noindent
{\bf Theorem 4.1. (Estimate on the supremum of a class of partial
sums).} {\it Let us consider a sequence of independent and
identically distributed random variables $\xi_1,\dots,\xi_n$,
$n\ge2$, with values in a measurable space $(X,\Cal X)$ and with
some distribution~$\mu$. Beside this, let a countable and
$L_2$-dense class of functions $\Cal F$ with some parameter $D\ge1$
and exponent $L\ge1$ be given on the space $(X,\Cal X)$ which
satisfies the conditions
$$
\align
\|f\|_\infty&=\supp_{x\in X}|f(x)|\le 1, \qquad \text{for all }
f\in\Cal F \tag4.1 \\
\|f\|_2^2&=\int f^2(x) \mu(\,dx)\le \sigma^2 \qquad \text{for all }
f\in \Cal F \tag4.2
\endalign
$$
with some constant $0<\sigma\le1$, and
$$
\int f(x)\mu(\,dx)=0 \quad \text{for all } f\in\Cal F. \tag4.3
$$
Define the normalized partial sums $S_n(f)=\frac1{\sqrt n}
\summ_{k=1}^n f(\xi_k)$ for all $f\in \Cal F$.

There exist some universal constants $C>0$, $\alpha>0$ and $M>0$
such that the supremum of the normalized random sums $S_n(f)$,
$f\in \Cal F$, satisfies the inequality
$$
\aligned
P\(\supp_{f\in\Cal F}|S_n(f)|\ge u\)
\le C&\exp\left\{-\alpha\(\frac u{\sigma}\)^2\right\}
\quad \text{ for those numbers } u \\
\text{for which } &\sqrt n\sigma^2\ge
u\ge M\sigma(L^{3/4}\log^{1/2}\tfrac2\sigma +(\log D)^{3/4}),
\endaligned \tag4.4
$$
where the numbers~$D$ and $L$ in formula~(4.4) agree with the
parameter and exponent of the $L_2$-dense class~$\Cal F$.}

\medskip
The condition $\sqrt n\sigma^2\ge u\ge
M\sigma(L^{3/4}\log^{1/2}\frac2\sigma +D^{3/4})$ about the number~$u$
in formula~(4.4) is natural. I discuss this after the formulation of
Theorem~4.2 which can be considered as the Gaussian counterpart of
Theorem~4.1. I also formulate a result in Example~4.3 which can be
considered as part of this discussion.

\medskip
The condition about the countable cardinality of $\Cal F$ can be
weakened with the help of the notion of countable approximability
introduced below. For the sake of later applications I define it
in a more general form than needed in this section.

\medskip\noindent
{\bf Definition of countably approximable classes of random
variables.} {\it Let us have a class of random variables $U(f)$,
$f\in \Cal F$, indexed by a class of functions $f\in\Cal F$
on a measurable space $(Y,\Cal Y)$. This class of random variables
is called countably approximable if there is a countable subset
$\Cal F'\subset \Cal F$ such that for all numbers $u>0$ the sets
$A(u)=\{\oo\colon\;\supp_{f\in \Cal F}|U(f)(\oo)|\ge u\}$ and
$B(u)=\{\oo\colon\;\supp_{f\in \Cal F'} |U(f)(\oo)|\ge u\}$ satisfy
the identity $P(A(u)\setminus B(u))=0$.}

\medskip
Clearly, $B(u)\subset A(u)$. In the above definition it was demanded
that for all $u>0$ the set $B(u)$ should be almost as large as
$A(u)$. The following corollary of Theorem~4.1 holds.

\medskip\noindent
{\bf Corollary of Theorem~4.1.} {\it Let a class of functions
$\Cal F$ satisfy the conditions of Theorem~4.1 with the only
exception that instead of the condition about the countable
cardinality of $\Cal F$ it is assumed that the class of random
variables $S_n(f)$, $f\in\Cal F$, is countably approximable. Then
the random variables $S_n(f)$, $f\in\Cal F$, satisfy
relation~(4.4).}

\medskip
This corollary can be simply proved, only Theorem~4.1 has to be
applied for the class $\Cal F'$. To do this it has to be checked
that if $\Cal F$ is an $L_2$-dense class with some parameter $D$
and exponent $L$, and $\Cal F'\subset \Cal F$, then $\Cal F'$ is
also an $L_2$-dense class with the same exponent $L$, only with a
possibly different parameter~$D'$.

To prove this statement let us choose for all numbers $0<\e\le1$
and probability measures $\nu$ on $(Y,\Cal Y)$ some functions
$f_1,\dots,f_m\in \Cal F$ with $m\le D\(\frac\e2\)^{-L}$ elements,
such that the sets $\Cal D_j=\left\{f\colon\;\int |f-f_j|^2\,d\nu\le
\(\frac\e2\)^2\right\}$ satisfy the relation $\bigcupp_{j=1}^m \Cal
D_j=Y$. For all sets $\Cal D_j$ for which $\Cal D_j\cap \Cal F'$ is
non-empty choose a function $f'_j\in \Cal D_j\cap \Cal F'$. In such
a way we get a collection of functions $f'_j$ from the class
$\Cal F'$ containing at most $2^LD\e^{-L}$ elements which satisfies
the condition imposed for $L_2$-dense classes with exponent $L$ and
parameter $2^LD$ for this number $\e$ and measure $\nu$.

\medskip
Next I formulate in Theorem~$4.1'$ a result about the supremum of
the integral of a class of functions with respect to a normalized
empirical distribution. It can be considered as a simple version
of Theorem~4.1. I formulated this result, because Theorems~4.1
and~$4.1'$ are special cases of their multivariate counterparts
about the supremum of so-called $U$-statistics and multiple
integrals with respect to a normalized empirical distribution
function discussed in Section~8. These results are also closely
related, but the explanation of their relation demands some work.

Given a sequence of independent $\mu$ distributed random variables
$\xi_1,\dots,\xi_n$ taking values in $(X,\Cal X)$ let us introduce
their empirical distribution on $(X,\Cal X)$ as
$$
\mu_n(A)(\oo)=\frac1n \#\left\{j\colon\; 1\le j\le n,\; \xi_j(\oo)\in
A\right\}, \quad A\in \Cal X,      \tag4.5
$$
and define for all measurable and $\mu$~integrable functions~$f$
the (random) integral
$$
J_n(f)=J_{n,1}(f)=\sqrt n\int f(x)(\mu_n(\,dx)-\mu(\,dx)). \tag4.6
$$

Clearly $J_n(f)=\frac1{\sqrt n}\summ_{j=1}^n (f(\xi_j)-Ef(\xi_j))
=S_n(\bar f)$ with $\bar f(x)=f(x)-\int f(x)\mu(\,dx)$. It is not
difficult to see that $\supp_{x\in X}|\bar f(x)|\le2$ if
$\supp_{x\in X}|f(x)|\le1$, $\int \bar f(x)\mu(\,dx)=0$, $\int \bar
f^2(x)\mu(\,dx)\le\int f^2(x)\mu(\,dx)$, and if $\Cal F$ is an
$L_2$-dense class of functions with parameter $D$ and exponent $L$,
then the class of functions $\bar{\Cal F}$ consisting of the functions
$\bar f(x)=f(x)-\int f(x)\mu(\,dx)$, $f\in\Cal F$, is an $L_2$-dense
class of functions with parameter $2^LD$ and exponent $L$, since
$\int(\bar f-\bar g)^2\,d\mu\le\e$ if $f,g\in\Cal F$, and
$\int(f-g)^2\,d\mu\le\(\frac\e2\)^2$. Hence Theorem~4.1 implies the
following result.

\medskip\noindent
{\bf Theorem 4.1$'$. (Estimate on the supremum of random integrals
with respect to a normalized empirical measure).} {\it Let us have
a sequence of independent and identically distributed random
variables $\xi_1,\dots,\xi_n$, $n\ge2$, with distribution~$\mu$ on
a measurable space $(X,\Cal X)$ together with some class of
functions $\Cal F$ on this space which satisfies the conditions of
Theorem~4.1 with the possible exception of condition~(4.3). The
estimate (4.4) remains valid if the random sums $S_n(f)$ are replaced
in it by the random integrals $J_n(f)$ defined in~(4.6). Moreover,
similarly to the corollary of Theorem~4.1, the condition about the
countable cardinality of the set $\Cal F$ can be replaced by the
condition that the class of random variables $J_n(f)$, $f\in\Cal F$,
is countably approximable.}

\medskip
All finite dimensional distributions of the set of random variables
$S_n(f)$, $f\in\Cal F$, considered in Theorem~4.1 converge to those
of a Gaussian random field $Z(f)$, $f\in\Cal F$, with expectation 
$EZ(f)=0$ and correlation $EZ(f)Z(g)=\int f(x)g(x)\mu(\,dx)$, 
$f,g\in\Cal F$ as $n\to\infty$. Here, and in the subsequent part 
of the paper a collection of random variables indexed by some set 
of parameters will be called a Gaussian random field if for all 
finite subsets of these parameters the random variables indexed by 
this finite set are jointly Gaussian. We shall also define 
so-called linear Gaussian random fields. They consist of jointly 
Gaussian random variables $Z(f)$, $f\in\Cal G$, indexed by a linear 
space $f\in\Cal G$ which satisfy the relation $Z(af+bg)=aZ(f)+bZ(g)$ 
for all real numbers $a$ and $b$ and $f,g\in\Cal G$.

Let us consider a linear Gaussian random field $Z(f)$, $f\in\Cal G$,
where the set of  indices~$\Cal G=\Cal G_\mu$ consists of the
functions~$f$ square integrable with respect to a $\sigma$-finite
measure~$\mu$, and take an appropriate restriction of this field to
some parameter set $\Cal F\subset\Cal G$. In the next Theorem~4.2
we shall present a natural Gaussian counterpart of Theorem~4.1 by
means of an appropriate choice of~$\Cal F$. Let me also remark that
in Section~10 multiple Wiener--It\^o integrals of functions of
$k$~variables with respect to a white noise will be defined for all
$k\ge1$. In the special case $k=1$ the Wiener--It\^o integrals for
an appropriate class of functions $f\in\Cal F$ yield a model for
which Theorem~4.2 is applicable. Before formulating this result let
us introduce the following definition which is a version of the
definition of $L_p$-dense functions.

\medskip\noindent
{\bf Definition of $L_p$-dense classes of functions with respect to
a measure~$\mu$.} {\it Let a measurable space $(X,\Cal X)$ be given
together with a measure $\mu$ on the $\sigma$-algebra $\Cal X$ and
a set $\Cal F$ of $\Cal X$ measurable real valued functions on
this space. The set of functions $\Cal F$ is called an $L_p$-dense
class of functions, $1\le p<\infty$, with respect to the
measure~$\mu$ with parameter $D$ and exponent $L$ if for all
numbers $0<\e\le1$ there exists a finite $\e$-dense subset
$\Cal F_\e=\{f_1,\dots,f_m\}\subset\Cal F$ in the space
$L_p(X,\Cal X,\mu)$ with $m\le D\e^{-L}$ elements, i.e.
such a set $\Cal F_\e\subset \Cal F$ with $m\le D\e^{-L}$
elements for which
$\inf\limits_{f_j\in \Cal F_\e}\int |f-f_j|^p\,d\mu<\e^p$ for all
functions $f\in \Cal F$.}

\medskip\noindent
{\bf Theorem 4.2. (Estimate on the supremum of a class of Gaussian
random variables).} {\it Let a probability measure $\mu$ be given
on a measurable space $(X,\Cal X)$ together with a linear Gaussian
random field $Z(f)$, $f\in\Cal G$, such that $EZ(f)=0$, 
$EZ(f)Z(g)=\int f(x)g(x)\mu(\,dx)$, $f,g\in\Cal G$, where $\Cal G$ 
is the space of square integrable functions with respect to this 
measure~$\mu$. Let $\Cal F\subset\Cal G$ be a countable and 
$L_2$-dense class of functions with respect to the measure~$\mu$ 
with some exponent~$L\ge1$ and parameter~$D\ge1$ which also 
satisfies condition~(4.2) with some $0<\sigma\le1$.

Then there exist some universal constants $C>0$ and $M>0$ (for
instance $C=4$ and $M=16$ is a good choice) such that the inequality
$$
P\(\supp_{f\in\Cal F}|Z(f)|\ge u\)\le C(D+1) \exp\left\{-\frac1{256}
\(\frac u{\sigma}\)^2\right\} \quad \text{if }u\ge ML^{1/2}\sigma
\log^{1/2}\frac2\sigma \tag4.7
$$
holds with the parameter $D$ and exponent $L$ introduced in this
theorem.}

\medskip
The exponent at the right-hand side of inequality~(4.7) does not
contain the best possible universal constant. One could choose the
coefficient $\frac{1-\e}2$ with arbitrary small $\e>0$ instead of the
coefficient $\frac1{256}$ in the exponent at the right-hand side
of~(4.7) if the universal constants $C>0$ and $M>0$ are chosen
sufficiently large in this inequality. Actually, later in Theorem~8.6
such an estimate will be proved which can be considered as the
multivariate generalization of Theorem~4.2 with the exponent
$-\frac{(1-\e)u^2}{2\sigma^2}$.

The condition about the countable cardinality of the set $\Cal F$
in Theorem~4.2 could be weakened similarly to Theorem~4.1. But
I omit the discussion of this question, since  Theorem~4.2 was
only introduced for the sake of a comparison between the
Gaussian and non-Gaussian case. An essential difference between
Theorems~4.1 and~4.2 is that the class of functions~$\Cal F$
considered in Theorem~4.1 had to be $L_2$-dense, while in
Theorem~4.2 a weaker version of this property was needed. In
that result it was demanded that there exists a subset of
$\Cal F$ of relatively small cardinality which is dense in the
$L_2(\mu)$ norm. In the $L_2$-density property imposed in
Theorem~4.1 a similar property was demanded for all probability
measures~$\nu$. The appearance of such a property may be unexpected.
But as we shall see, the proof of Theorem~4.1 contains a
conditioning argument where a lot of new conditional measures
appear, and the $L_2$-density property is needed to work with all
of them. One would also like to know some results that enable us
to check when this condition holds. In the next section a notion
popular in probability theory, the Vapnik--\v{C}ervonenkis classes
will be introduced, and it will be shown that a
Vapnik--\v{C}ervonenkis class of functions bounded by~1 is
$L_2$-dense.

Another difference between Theorems~4.1 and~4.2 is that the
conditions of formula~(4.4) contain the upper bound
$\sqrt n\sigma^2>u$, and no such condition was imposed in
formula~(4.7). The appearance of this condition in Theorem~4.1
can be explained by comparing this result with those of Section~3.
As we have seen, we do not loose much information if we restrict
our attention to the case $u\le\const V_n^2=\const n\sigma^2$ in
Bernstein's inequality (if sums of independent and identically
distributed random variables are considered). Theorem~4.1 gives
an almost as good estimate for the supremum of normalized partial
sums under appropriate conditions for the class $\Cal F$ of
functions we consider in this theorem, as Bernstein's inequality
yields for the normalized partial sums of independent and
identically distributed random variables with variance bounded
by~$\sigma^2$. But we could prove the estimate of Theorem~4.1 only
under the condition $\sqrt n\sigma^2>u$. We shall show in 
Example~4.3 discussed below that in the case $\sqrt n\sigma^2>u$ 
only a weaker estimate holds. It has also a natural reason why 
condition~(4.1) about the supremum of the functions $f\in \Cal F$ 
appeared in Theorems 4.1 and~$4.1'$, and no such condition was 
needed in Theorem~4.2.

The lower bounds for the level~$u$ were imposed in formulas~(4.4)
and~(4.7) because of a similar reason. To understand why such a
condition is needed in formula (4.7) let us consider the
following example. Take a Wiener process $W(t)$, $0\le t\le1$,
define for all $0\le s<t\le 1$ the functions $f_{s,t}(\cdot)$ on
the interval $[0,1]$ as $f_{s,t}(u)=1$ if $s\le u\le t$,
$f_{s,t}(u)=0$ if $0\le u<s$ or $t<u\le1$, and introduce for all
$\sigma>0$ the following class of functions $\Cal F_\sigma$.
$\Cal F_\sigma=\{f_{s,t}\colon\; 0\le s<t\le1,\, t-s\le\sigma^2,\,
s\text{ and }t\text{ are rational numbers.}\}$. The integral
$Z(f)=\int_0^1f(x)W(\,dx)$ can be defined for all square
integrable functions~$f$ on the interval~$[0,1]$, and this yields
a linear Gaussian random field on the space of square integrable
functions. In the special case $f=f_{s,t}$ we have
$Z(f_{s,t})=\int f_{s,t}(u)W(\,du)=W(t)-W(s)$. It is not difficult
to see that the Gaussian random field $Z(f)$, $f\in\Cal F_\sigma$,
satisfies the conditions of Theorem~4.2 with the number~$\sigma$
in formula~(4.2). It is natural to expect that
$P\(\supp_{f\in\Cal F_\sigma} Z(f)>u\)\le e^{-\const(u/\sigma)^2}$.
However, this relation does not hold if
$u=u(\sigma)<(1-\e)\sqrt2\sigma\log^{1/2}\frac1\sigma$ with some
$\e>0$. In such cases $P\(\supp_{f\in\Cal F_\sigma}Z(f) >u\)\to1$,
as $\sigma\to0$. This can be proved relatively simply with the help
of the estimate $P(Z(f_{s,t})>u(\sigma))\ge\const \sigma^{1-\e}$ if
$|t-s|=\sigma^2$ and the independence of the random integrals
$Z(f_{s,t})$ if the functions $f_{s,t}$ are indexed by such pairs
$(s,t)$ for which the intervals $(s,t)$ are disjoint. This means
that in this example formula~(4.7) holds only under the condition
$u\ge M\sigma\log^{1/2}\frac1\sigma$ with $M=\sqrt2$.

There is a classical result about the modulus of continuity of
Wiener processes, and actually this result helped us to find the
previous example. It is also worth mentioning that there are some
concentration inequalities, see Ledoux~[28] and Talagrand~[51],
which state that under very general conditions the distribution
of the supremum of a class of partial sums of independent random
variables or of the elements of a Gaussian random field is
strongly concentrated around the expected value of this supremum.
(Talagrand's result in this direction is also formulated in
Theorem~18.1 of this lecture note.) These results imply that the
problems discussed in Theorems~4.1 and~4.2 can be reduced to a
good estimate of the expected value $E\supp_{f\in\Cal F}|S_n(f)|$
and $E\supp_{f\in\Cal F}|Z(f)|$ of the supremum considered in
these results. However, the estimation of the expected value of
these suprema is not much simpler than the original problem.

Theorem~4.2 implies that under its conditions
$E\supp_{f\in\Cal F}|Z(f)|\le\const \sigma\log^{1/2}\frac2\sigma$
with an appropriate multiplying constant depending on the
parameter~$D$ and exponent~$L$ of the class of functions~$\Cal F$.
In the case of Theorem~4.1 a similar estimate holds, but under more
restrictive conditions. We also have to impose that
$\sqrt n\sigma^2\ge\const\sigma\log^{1/2}\frac2\sigma$ with
a sufficiently large constant. This condition is needed to guarantee
that the set of numbers~$u$ satisfying condition~(4.4) is not empty.
If this condition is violated, then Theorem~4.1 supplies a weaker
estimate which we get by replacing $\sigma$ by an
appropriate~$\bar\sigma>\sigma$, and by applying Theorem~4.1 with
this number~$\bar\sigma$.

One may ask whether the above estimate about the expected value of
supremum of normalized partial sums may hold without the condition
$\sqrt n\sigma^2\ge\const\sigma\log^{1/2}\frac2\sigma$. We show an
example which gives a negative answer to this question.
Since here we discuss a rather particular problem which is outside
of our main interest in this work I give a rather sketchy
explanation of this example. I present this example together with
a Poissonian counterpart of it which may help explain why such a
result holds.

\medskip\noindent
{\bf Example 4.3. (Supremum of partial sums with bad tail behaviour).}
{\it Let $\xi_1,\dots,\xi_n$ be a sequence of independent random
variables with uniform distribution in the interval~$[0,1]$. Choose
a sequence of real numbers, $\e_n$, $n=3,4,\dots$, such that
$\e_n\to0$ as $n\to\infty$, and $\frac12\ge\e_n\ge n^{-\delta}$ with a
sufficiently small number $\delta>0$. Put
$\sigma_n=\e_n\sqrt{\frac{\log n}n}$, and define the set of
functions $\bar f_{j,n}(\cdot)$ and $f_{j,n}(\cdot)$
on the interval $[0,1]$ by the formulas
$\bar f_{j,n}(x)=1$ if $(j-1)\sigma^2_n\le x<j\sigma^2_n$,
$\bar f_{j,n}(x)=0$ otherwise, and
$f_{j,n}(x)=\bar f_{j,n}(x)-\sigma^2_n$, $n=3,4,\dots$,
 $1\le j\le\frac1{\sigma^2_n}$. Put
$\Cal F_n=\{f_{j,n}(\cdot)\colon\; 1\le j\le \frac1{\sigma^2_n}\}$,
and $u_n=\frac A{\log\frac1{\e_n}}\frac{\log n}{\sqrt n}$ with a
sufficiently small $A>0$. Then
$$
\lim_{n\to\infty}P\(\sup_{f\in\Cal F_n}S_n(f)>u_n\)=1.
$$
}

\medskip
This example has the following Poissonian counterpart.

\medskip\noindent
{\bf Example 4.3$'$. (A Poissonian counterpart of Example 4.3).}
{\it Let $\bar P_n(x)$ be a Poisson process on the interval~$[0,1]$
with parameter~$n$ and $P_n(x)=\frac1{\sqrt n}[\bar P_n(x)-nx]$,
$0\le x\le 1$. Consider the same sequences of numbers~$\e_n$,
$\sigma_n$ and~$u_n$ as in Example~4.3, and define the random
variables $Z_{n,j}=P_n(j\sigma^2_n)-P_n((j-1)\sigma^2_n)$ for all
$n=3,4,\dots$ and $1\le j\le \frac1{\sigma^2_n}$. Then
$$
\lim_{n\to\infty}P\(\sup_{1\le j\le \frac1{\sigma_n}}
(Z_{n,j}-Z_{n,j-1})>u_n\)=1.
$$
}

\medskip
The classes of functions $\Cal F_n$ in Example~4.3 are $L_2$-dense
classes of functions with some exponent~$L$ and parameter~$D$
not depending on the parameter~$n$ and the choice of the
numbers~$\sigma_n$. It can be seen that even the class of function
$\Cal F=\{f\colon\; f(x)=1,\text{ if }s\le x<t,\; f(x)=0
\text{ otherwise.}\}$ consisting of functions defined on the
interval $[0,1]$ is an $L_2$-dense class with some exponent~$L$
and parameter~$D$. This follows from the results discussed in
the later part of this work (mainly Theorem~5.2), but it can be
proved directly that this statement holds e.g. with $L=1$ and $D=8$.
The classes of functions~$\Cal F_n$ also satisfy conditions~(4.1),
(4.2) and~(4.3) of Theorem~4.1 with
$\sigma^2=\bar\sigma_n^2=\sigma_n^2-\sigma_n^4$,
$\limm_{n\to\infty}\frac{\bar\sigma_n}{\sigma_n}=1$, and the
number~$u_n$ satisfies the second condition
$u_n\ge M\bar\sigma_n(L^{3/4}\bar\sigma_n(\log^{1/2}\frac2{\bar\sigma_n}
+(\log D)^{3/4})$ in~(4.4) for sufficiently large~$n$. But it does
not satisfy the first condition $\sqrt n\bar\sigma_n^2\ge u_n$
of~(4.4), and as a consequence Theorem~4.1 cannot be applied in
this case. On the other hand, some calculation shows that
$u_n\ge(\frac{2}{1+4\delta})^{1/2}
\frac A{\e_n\log\frac1{\e_n}}\sigma_n\log^{1/2}{\frac2\sigma_n}$.
Hence $\liminf\limits_{n\to\infty}\e_n\log\frac1{\e_n}
\cdot\frac1{\bar\sigma_n\log^{1/2}\frac2{\bar\sigma_n}}
E\supp_{f\in\Cal F_n}S_n(f)>0$ in this case. As
$\e_n\log\frac1{\e_n}\to0$ as $n\to\infty$, this means that the
expected value of the supremum of the random sums considered in
Example~4.3 does not satisfy the estimate
$\limsup\limits_{n\to\infty}
\frac1{\bar\sigma_n\log^{1/2}\frac2{\bar\sigma_n}}
E\supp_{f\in\Cal F_n}S_n(f)<\infty$  suggested by Theorem~4.1.
Observe that $\sqrt n\bar\sigma^2_n
\sim\const \e_n\bar\sigma_n\log^{1/2}\frac2{\bar\sigma_n}$
in this case, since
$\sqrt n\bar\sigma^2_n\sim\e_n^2\frac{\log n}{\sqrt n}$, and
$\bar\sigma_n\log^{1/2}\frac2{\bar\sigma_n}
\sim \const\e_n\frac{\log n}{\sqrt n}$.

\medskip\noindent
{\it The proof of Examples~4.3 and~$4.3'$.} First we prove the
statement of Example~$4.3'$. As the random variables $Z_{n,j}$ are
independent for a fixed number~$n$, and their number is less than
$n^{1+3\delta}\le n^{2-\delta}$  if $\delta\le\frac14$, it is
enough to show that $P(Z_{n,j}>u_n)\ge\frac1{n^2}$ if $n\ge n_0$
with some threshold index $n_0=n_0(A,\delta)$. Put
$\bar u_n=[\sqrt nu_n+n\sigma^2_n]+1$, where $[\cdot]$ denotes
integer part. Then $P(Z_{n,j}>u_n)\ge P(\bar P_n(\sigma^2_n)\ge\bar u_n)
\ge P(\bar P_n(\sigma^2_n)=\bar u_n)$. On the other hand,
$\bar u_n\sim (\frac A{\log\frac1{\e_n}}+\e_n^2)\log n
<\frac{2A}{\log\frac1{\e_n}}\log n$, hence
$P(\bar P_n(\sigma^2_n)=\bar u_n)
=\frac{(n\sigma^2_n)^{\bar u_n}}{\bar u_n!}e^{-n\sigma_n^2}
>(\frac{n\sigma_n^2\cdot e}{\bar u_n})^{\bar u_n}e^{-n\sigma_n^2}
\ge\exp\left\{-2\bar u_n\log\frac{\bar u_n}{n\sigma_n^2}\right\}
\ge e^{-3\bar u_n\log \frac1{\e_n}}\ge n^{-2}$.

The statement of Example~4.3 can be deduced from~Example~$4.3'$
by applying Poissonian approximation. Let us apply the result of
Example~$4.3'$ for a Poisson process $\bar P_{n/2}$ with
parameter~$\frac n2$ and with such a number~$\bar\e_{n/2}$
with which the value of $\sigma_{n/2}$ equals the previously
defined~$\sigma_n$. Then $\bar\e_{n/2}\sim\frac{\e_n}{\sqrt 2}$,
and the number of sample points of $\bar P_{n/2}$ is less
than~$n$ with probability almost~1. Attaching additional sample
points to get exactly $n$ sample points we can get the result of
Example~4.3. I omit the details.

\medskip
In formulas~(4.4) and~(4.7) we formulated such a condition for
the validity of Theorem~4.1 and Theorem~4.2 which contains a large
multiplying constant of $\sigma\log^{1/2}\frac2\sigma$ in the lower
bound for the number~$u$ if we deal with such an $L_2$ class of
functions $\Cal F$ which has a large exponent~$L$. At a heuristic
level it is clear that in such a case a large multiplying constant
appears. On the other hand, I did not try to find the best possible
coefficients in the lower bound in relations~(4.4) and~(4.7).

\medskip
In Theorem~4.1 (and in its version 4.1$'$) it was demanded that the
class of functions $\Cal F$ should be countable. Later this condition
was replaced by a weaker one about countable approximability.
By restricting our attention to countable or countably approximable
classes we could avoid some unpleasant measure theoretical problems
which would have arisen if we had worked with the supremum of
non-countable number of random variables which may be non-measurable.
There are some papers where possibly non-measurable models
are also considered with the help of some rather deep results
of the analysis and measure theory. Actually, the problem we met
here is the natural analog of an important problem in the theory
of the stochastic processes about the smoothness property of the
trajectories of an appropriate version of a stochastic process
which we can get by exploiting our freedom to change all random
variables on a set of probability zero.

The study of the problem in this work is simpler in one respect.
Here the set of random variables $S_n(f)(\oo)$ or $J_n(f)(\oo)$,
$f\in\Cal F$, are constructed directly with the help of the
underlying random variables $\xi_1(\oo),\dots,\xi_n(\oo)$ for all
$\oo\in\Cal\Omega$ separately. We are interested in when the sets of
random variables constructed in this way are countably approximable,
i.e.\ we are not looking for a possibly different, better version of
them with the same finite dimensional distributions. The next
simple Lemma~4.4 yields a sufficient condition for countable
approximability. Its condition can be interpreted as a smoothness
type condition for the trajectories of a
stochastic process indexed by the functions $f\in\Cal F$.

\medskip\noindent
{\bf Lemma 4.4.} {\it Let a class of random variables $U(f)$,
$f\in\Cal F$, indexed by some set $\Cal F$ of functions be given
on a space $(Y,\Cal Y)$. If there exists a countable subset
$\Cal F'\subset \Cal F$ of the set $\Cal F$ such that the sets
$A(u)=\{\oo\colon\;\supp_{f\in \Cal F}|U(f)(\oo)|\ge u\}$ and
$B(u)=\{\oo\colon\;\supp_{f\in \Cal F'} |U(f)(\oo)|\ge u\}$ introduced
for all $u>0$ in the definition of countable approximability satisfy
the relation $A(u)\subset B(u-\e)$ for all $u>\e>0$, then the class
of random variables $U(f)$, $f\in\Cal F$, is countably approximable.

The above property holds if for all $f\in\Cal F$, $\e>0$ and
$\oo\in\Omega$ there exists a function $\bar f=\bar f(f,\e,\oo)
\in\Cal F'$ such that $|U(\bar f)(\oo)|\ge|U(f)(\oo)|-\e$.}

\medskip\noindent
{\it Proof of Lemma 4.4.}\/ If $A(u)\subset B(u-\e)$ for
all $\e>0$, then $P^*(A(U)\setminus B(u))\le \limm_{\e\to0}
P(B(u-\e)\setminus B(u))=0$,  where $P^*(X)$ denotes the outer measure
of a not necessarily measurable set $X\subset\Omega$, since
$\bigcapp_{\e\to0}B(u-\e)=B(u)$, and this is what we had to prove.
If $\oo\in A(u)$, then for all $\e>0$ there exists some
$f=f(\oo)\in\Cal F$ such that $|U(f)(\oo)|>u-\frac\e2$. If there
exists some $\bar f=\bar f(f,\frac\e2,\oo)$, $f\in\Cal F'$ such that
$|U(\bar f)(\oo)| \ge |Uf(\oo)|-\frac\e2$, then $|U(\bar f)(\oo)|
>u-\e$, and $\oo\in B(u-\e)$. This means that $A(u)\subset B(u-\e)$.

\medskip
The question about countable approximability also appears in the
case of multiple random integrals with respect to a normalized
empirical measure. To avoid some repetition we prove a result which
also covers such cases. For this goal first we introduce the notion
of multiple integrals with respect to a normalized empirical measure.

Given a measurable function $f(x_1,\dots,x_k)$ on the $k$-fold
product space $(X^k,\Cal X^k)$ and a sequence of independent random
variables $\xi_1,\dots,\xi_n$ with some distribution $\mu$ on the
space $(X,\Cal X)$ we define the integral $J_{n,k}(f)$ of the
function $f$ with respect to the $k$-fold product of the normalized
version of the empirical measure $\mu_n$ introduced in (4.5) by the
formula
$$
\align
J_{n,k}(f)&=\frac{n^{k/2}}{k!} \int'
f(x_1,\dots,x_k)(\mu_n(\,dx_1)-\mu(\,dx_1))\dots
(\mu_n(\,dx_k)-\mu(\,dx_k)),\\
&\qquad\text{where the prime in $\tsize\int'$ means that the
diagonals } x_j=x_l,\; 1\le j<l\le k,\\
&\qquad\text{are omitted from the domain of integration.} \tag4.8
\endalign
$$
In the case $k\ge2$ it will be assumed that the probability
measure $\mu$ has no atoms.

Lemma~4.4 enables us to prove that certain classes of random
integrals $J_{n,k}(f)$, $f\in\Cal F$, defined with the help of
some set of functions $f\in\Cal F$ of $k$ variables are countably
approximable. I present an example of a class of such random
integrals which is important in certain applications.

Let us consider the case when $X=R^s$, the $s$-dimensional Euclidean
space with some $s\ge1$. For two vectors $u=(u^{(1)},\dots,u^{(s)})
\in R^s$, $v=(v^{(1)},\dots,v^{(s)})\in R^s$ such that $u< v$, i.e.\
$u^{(j)}< v^{(j)}$ for all $1\le j\le s$ let $B(u,v)$ denote the
$s$-dimensional rectangle $B(u,v)=\{z\colon\; u< z< v\}$. Let us fix
some function $f(x_1,\dots,x_k)$ of $k$~variables such that
$\sup|f(x_1,\dots,x_k)|\le1$, on
the space $(X^k,\Cal X^k)=(R^{ks},\Cal B^{ks})$, where $\Cal B^t$
denotes the Borel $\sigma$-algebra on the Euclidean space $R^t$,
together with some probability measure $\mu$ on $(R^s,\Cal B^s)$.
For all pairs of vectors $(u_1,\dots,u_k)$, $(v_1,\dots,v_k)$ such
that $u_j,v_j\in R^s$ and $u_j\le v_j$, $1\le j\le k$, let us define
the function $f_{u_1,\dots,u_k,v_1,\dots,v_k}$ which equals the
function~$f$ on the rectangle $(u_1,v_1)\times\cdots\times(u_k,v_k)$,
and it is zero outside of this rectangle. Let us call a class of
functions $\Cal F$ consisting of functions of the form
$f_{u_1,\dots,u_k,v_1,\dots,v_k}$ closed if it has the following
property. If $f_{u_1,\dots,u_k,v_1,\dots,v_k}\in\Cal F$ for some
vectors $(u_1,\dots,u_k)$ and $(v_1,\dots,v_k)$, and
$u_j\le \bar u_j<\bar v_j\le v_j$, $1\le j\le k$, then
$f_{\bar u_1,\dots,\bar u_k,\bar v_1,\dots,\bar v_k}\in \Cal F$.
In Lemma~4.5 it will be proved that the random integrals introduced
in formula~(4.8) of functions from a closed class $\Cal F$ constitute
a countably approximable class.

\medskip\noindent
{\bf Lemma 4.5.} {\it Let us have a function $f$ on the Euclidean
space $R^{ks}$ such that the $|f|\le1$ in all points, and consider a
closed class $\Cal F$ of functions of the form
$f_{u_1,\dots,u_k,v_1,\dots,v_k}\in(R^{sk},\Cal B^{sk})$,
$u_j,v_j\in R^s$, $u_j\le v_j$, $1\le j\le k$, introduced in the
previous paragraph with the help of this function~$f$. Let us take
$n$ independent and identically distributed random variables
$\xi_1,\dots,\xi_n$ with some distribution~$\mu$ and values
in the space $(R^s,\Cal B^s)$. Let $\mu_n$ denote the empirical
distribution of this sequence. Then the class of random integrals
$J_{n,k}(f_{u_1,\dots,u_k,v_1,\dots,v_k})$ defined in formula~(4.8)
with functions $f_{u_1,\dots,u_k,v_1,\dots,v_k}\in\Cal F$ is countably
approximable.}

\medskip\noindent
{\it Proof of Lemma 4.5.}\/ We shall prove that the definition of
countable approximability is satisfied in this model if the class of
functions $\Cal F'$ consists of those functions
$f_{u_1,\dots,u_k,v_1,\dots,v_k}$, $u_j\le v_j$, $1\le j\le k$, for
which all coordinates of the vectors $u_j$ and $v_j$ are rational
numbers.

Given some function $f_{u_1,\dots,u_k,v_1,\dots,v_k}$, a real number
$0<\e<1$ and $\oo\in\Omega$ let us choose a function $f_{\bar u_1,
\dots, \bar u_k,\bar v_1,\dots,\bar v_k}\in \Cal F'$ determined with
some vectors $\bar u_j=\bar u_j(\e,\oo)$, $\bar v_j=\bar v_j(\e,\oo)$
$1\le j\le k$, with rational coordinates $u_j\le\bar u_j<\bar v_j\le v_j$
such that the sets $K_j=B(u_j,v_j)\setminus B(\bar u_j,\bar v_j)$
satisfy the relations $\mu(K_j)\le \e2^{-2k+1} n^{-k/2}$,
and $\xi_l(\oo) \notin K_j$ for all $j=1,\dots,k$ and $l=1,\dots, n$.
Let us show that
$$
|J_{n,k}(f_{\bar u_1,\dots,\bar u_k,\bar v_1,\dots,\bar v_k})(\oo)
-J_{n,k}(f_{u_1,\dots,u_k, v_1,\dots,v_k})(\oo)|\le\e. \tag4.9
$$
Then lemma 4.4 (with the choice $U(f)=J_{n,k}(f)$) and relation (4.9)
imply Lemma~4.5.

Relation (4.9) holds, since the difference of integrals at its
left-hand side can be written as the sum of the $2^k-1$ integrals of
the function $f$ with respect to the
$k$-fold product of the measure $\sqrt n(\mu_n-\mu)$ on the domains
$D_1\times\cdots\times D_k$ with the omission of the diagonals
$x_j=x_{\bar j}$, $1\le j,\bar\jmath\le k$, $j\neq\bar\jmath$,
where $D_j$ is either the set $K_j$ or $B(u_j,v_j)$ and $D_j=K_j$ for
at least one index $j$. It is enough to show that the absolute value of
all these integrals is less than $\e2^{-k}$. This follows from the
observations that $|f(x_1,\dots,x_k)|\le1$, $\sqrt
n(\mu_n-\mu)(K_j)=-\sqrt n\mu(K_j)$, $\mu(K_j)\le \e2^{-2k+1}n^{-k/2}$,
and the total variation of the signed measure $\sqrt n(\mu_n-\mu)$
(restricted to the set $B(u_j,v_j)$) is less than $2\sqrt n$.

\medskip
In Lemma~4.5 we have shown with the help of Lemma~4.4 about an
important class of functions that it is countably approximable. There
are other interesting classes of functions about which it can be
proved with the help of Lemma~4.4 that they are countably
approximable, but here we shall not discuss this problem.

\medskip
Let us discuss the relation of the results in this section to an
important result, the so-called fundamental theorem of the mathematical
statistics. In that problem a sequence of independent random
variables $\xi_1(\oo),\dots,\xi_n(\oo)$ is considered with
distribution function $F(x)$, the empirical distribution function
$F_n(x)=F_n(x,\oo)=\frac1n\#\{j\colon\; 1\le j\le n,\, \xi_j(\oo)<x\}$ is
introduced, and the difference $F_n(x)-F(x)$ is considered. This
result states that $\supp_x|F_n(x)-F(x)|$ tends to zero with
probability one.

Observe that $\supp_x|F_n(x)-F(x)|= n^{-1/2} \supp_{f\in \Cal F}
|J_n(f)|$, where $\Cal F$ consists of the functions $f_x(\cdot)$,
$x\in R^1$, defined by the relation $f_x(u)=1$ if $u<x$, and
$f_x(u)=0$ if $u\ge x$. Theorem 4.1$'$ yields an estimate for the
probabilities $P\(\supp_{f\in \Cal F}|J_n(f)|>u\)$. We have seen that
the above class of functions $\Cal F$ is countably approximable. The
results of the next section imply that this class of functions is
also $L_2$-dense. Otherwise it is not difficult to check this
property directly. Hence we can apply Theorem~$4.1'$ to the above
defined class of functions with $\sigma=1$, and it yields that
$P\(n^{-1/2}\supp_{f\in \Cal F}|J_n(f)|>u\)\le e^{-Cnu^2}$ if
$1\ge u\ge\bar Cn^{-1/2}$ with some universal constants $C>0$ and
$\bar C>0$. (The condition $1\ge u$ can actually be dropped.) The
application of this estimate for the numbers $\e>0$ together with
the Borel--Cantelli lemma imply the fundamental theorem of the
mathematical statistics.

In short, the results of this section yield more information about
the closeness the empirical distribution function $F_n$ and
distribution function $F$ than the fundamental theorem of the
mathematical statistics. Moreover, since these results can also be
applied for other classes of functions, they yield useful information
about the closeness of the probability measure $\mu$ and the empirical
measure~$\mu_n$.

\beginsection 5. Vapnik--\v{C}ervonenkis classes and $L_2$-dense
classes of functions.

In this section the most important notions and results will be
presented about Vapnik--\v{C}ervonenkis classes, and it will be
explained how they help to show in some important cases that
certain classes of functions are $L_2$-dense. The classes of
$L_2$-dense classes played an important role in the study of the
previous section. The results of this section may help to find
interesting classes of functions with this property. Some of the
results formulated in this section will be proved in Appendix~A.

First I recall the following notions.

\medskip\noindent
{\bf Definition of Vapnik-\v{C}ervonenkis classes of sets and
functions.} {\it Let a set $X$ be given, and let us select a class
$\Cal D$ of subsets of this set $X$. We call
$\Cal D$ a Vapnik--\v{C}ervonenkis class if there exist two real
numbers $B$ and $K$ such that for all positive integers $n$ and
subsets $S(n)=\{x_1,\dots,x_n\}\subset X$ of cardinality $n$
of the set $X$ the collection of sets of the form $S(n)\cap D$,
$D\in\Cal D$, contains no more than $Bn^K$ subsets of~$S(n)$.
We shall call $B$ the parameter and $K$ the exponent of this
Vapnik--\v{C}ervonenkis class.

A class of real valued functions $\Cal F$ on a space $(Y,\Cal Y)$
is called a Vapnik--\v{C}ervonenkis class if the collection of
graphs of these functions is a Vapnik--\v{C}ervonenkis class, i.e.\
if the sets $A(f)=\{(y,t)\colon\; y\in Y,\;\min(0,f(y))\le t\le
\max(0,f(y))\}$, $f\in \Cal F$, constitute a
Vapnik--\v{C}er\-vo\-nen\-kis class of subsets of the product space
$X=Y\times R^1$.}

\medskip
The following result which was first proved by Sauer is of fundamental
importance in the theory of Vapnik--\v{C}er\-vo\-nen\-kis classes.
This result provides a relatively simple condition for a class
$\Cal D$ of subsets of a set~$X$ to be a Vapnik--\v{C}ervonenkis class.
Its proof is given in Appendix~A. Before its formulation I introduce
some terminology which seems to be wide spread and generally accepted
in the literature.

\medskip\noindent
{\bf Definition of shattering of a set.} {\it Let a set $S$ and a class
$\Cal E$ of subsets of $S$ be given. A finite set $F\subset S$ is called
shattered by the class $\Cal E$ if all its subsets $H\subset F$ can be
written in the form $H=E\cap F$ with some element $E\in\Cal E$ of the
class of sets of $\Cal E$.}

\medskip\noindent
{\bf  Theorem 5.1. (Sauer's lemma).} {\it Let a finite set $S=S(n)$
consisting of $n$ elements be given together with a class $\Cal E$
of subsets of $S$. If $\Cal E$ shatters no subset of $S$ of
cardinality~$k$, then $\Cal E$ contains at most
$\binom n0+\binom n1+\cdots+\binom n{k-1}$ subsets of $S$.}

\medskip
The estimate of Sauer's lemma is sharp. Indeed, if $\Cal E$ contains
all subsets of $S$ of cardinality less than or equal to $k-1$, then
it shatters no subset of a set $F$ of cardinality $k$ (a set $F$
of cardinality~$k$ cannot be written in the form $E\cap F$,
$E\in \Cal E$), and $\Cal E$ contains
$\binom n0+\binom n1+\cdots+\binom n{k-1}$ subsets of $S$. 
Sauer's lemma states, that this is an extreme case. Any class of 
subsets $\Cal E$ of $S$ with cardinality greater than
$\binom n0+\binom n1+\cdots+\binom n{k-1}$ shatters at least one 
subset of~$S$ with cardinality~$k$.

Let us have a set $X$ and a class of subsets $\Cal D$ of it. One may
be interested in when $\Cal D$ is a Vapnik--\v{C}ervonenkis class.
Sauer's lemma gives a useful condition for it. Namely, it implies
that if there exists  a positive integer $k$ such that the class
$\Cal D$ shatters no subset of $X$ of cardinality~$k$, then $\Cal D$
is a Vapnik--\v{C}ervonenkis class. Indeed, let us take some number
$n\ge k$, fix an arbitrary set $S(n)=\{x_1,\dots,x_n\}\subset X$ of
cardinality~$n$, and introduce the class of subsets
$\Cal E=\Cal E(S(n))=\{S(n)\cap D\colon\; D\subset\Cal D\}$. If 
$\Cal D$ shatters no subset of $X$ of cardinality~$k$, then $\Cal E$ 
shatters no subset of $S(n)$ of cardinality~$k$. Hence by
Sauer's lemma the class $\Cal E$ contains at most 
$\binom n0+\binom n1+\cdots+\binom n{k-1}$ elements. Let me remark 
that it is also proved that
$\binom n0+\binom n1+\cdots+\binom n{k-1}\le1.5\frac{n^{k-1}}{(k-1)!}$
if $n\ge k+1$. This estimate gives a bound on the parameter and exponent
of a Vapnik--\v{C}ervonenkis class which satisfies the above condition.

Moreover, Theorem~5.1 also has the following consequence. Take an
(infinite) set $X$ and a class of its subsets $\Cal D$. There are two
possibilities. Either there is some set $S(n)\subset X$ of cardinality
$n$ for all integers $n$ such that $\Cal E(S(n))$ contains all subsets
of $S(n)$, i.e. $\Cal D$ shatters this set, or
$\supp_{S\colon\;S\subset X,\,|S|=n}|\Cal E(S)|$ tends to infinity at
most in a polynomial order as $n\to\infty$, where $|S|$ and $|\Cal E(S)|$
denote the cardinality of $S$ and $\Cal E(S)$.

\medskip
The following Theorem~5.2, an important result of Richard Dudley,
states that a Vapnik--\v{C}er\-vo\-nen\-kis class of functions
bounded by~1 is an $L_1$-dense class of functions.

\medskip\noindent
{\bf Theorem 5.2. (A relation between the $L_1$-dense class and
Vapnik--\v{C}er\-vo\-nen\-kis class property).} {\it Let $f(y)$,
$f\in \Cal F$,  be a Vapnik--\v{C}ervonenkis class of real valued
functions on some measurable space $(Y,\Cal Y)$ such that
$\supp_{y\in Y}|f(y)|\le1$ for all $f\in\Cal F$. Then $\Cal F$ is an
$L_1$-dense class of functions on $(Y,\Cal Y)$. More explicitly, if
$\Cal F$ is a Vapnik--\v{C}ervonenkis class with parameter $B\ge1$ and
exponent $K>0$, then it is an $L_1$-dense class with exponent $L=2K$
and parameter $D=CB^2 (4K)^{2K}$ with some universal constant $C>0$.}

\medskip\noindent
{\it Proof of Theorem 5.2.}\/ Let us fix some probability measure
$\nu$ on $(Y,\Cal Y)$ and a real number $0<\e\le1$. We are going
to show that any finite set
$\Cal D(\e,\nu)=\{f_1,\dots,f_M\}\subset\Cal F$ such that
$\int|f_j-f_k|\,d\nu\ge\e$ if $j\neq k$, $f_j,f_k\in\Cal D(\e,\nu)$
has cardinality $M\le D\e^{-L}$ with some $D>0$ and $L>0$. This
implies that $\Cal F$ is an $L_1$-dense class with parameter~$D$
and exponent~$L$. Indeed, let us take a maximal subset
$\bar{\Cal D}(\e,\nu)=\{f_1,\dots,f_M\}\subset\Cal F$ such that
the $L_1(\nu)$ distance of any two functions in this subset is at
least~$\e$. Maximality means in this context that no function
$f_{M+1}\in\Cal F$ can be attached to $\bar{\Cal D}(\e,\nu)$
without violating this condition. Thus the inequality
$M\le D\e^{-L}$ means that $\bar{\Cal D}(\e,\nu)$ is an
$\e$-dense subset of~$\Cal F$ in the space $L_1(Y,\Cal Y,\nu)$
with no more than $D\e^{-L}$ elements.

In the estimation of the cardinality $M$ of a (finite) set
$\Cal D(\e,\nu)=\{f_1,\dots,f_M\}$ with the property
$\int|f_j-f_k|\,d\nu\ge\e$ if $j\neq k$ the
Vapnik--\v{C}ervonenkis class property of $\Cal F$ is exploited in
the following way. Let us choose relatively few $p$ points
$(y_l,t_l)$, $y_l\in Y$, $-1\le t_l\le1$, $1\le l\le p$, in the
space $(Y\times [-1,1])$ in such a way that the set
$S_0(p)=\{(y_l,t_l),\,1\le l\le p\}$ and graphs
$A(f_j)=\{(y,t)\colon\; y\in Y,\;\min(0,f_j(y))\le t\le\max(0,f_j(y))\}$,
$f_j\in\Cal D(\e,\nu)\subset\Cal F$ have the property that all
sets $A(f_j)\cap S_0(p)$, $1\le j\le M$, are different. Then the
Vapnik--\v{C}ervonenkis class property of $\Cal F$ implies that
$M\le Bp^K$. Hence if there exists a set $S_0(p)$ with the above
property and with a relatively small number $p$, then this yields a
useful estimate on $M$. Such a set $S_0(p)$ will be given by means of
the following random construction.

Let us choose the $p$ points $(y_l,t_l)$, $1\le l\le p$, of the
(random) set $S_0(p)$ independently of each other in such a way that
the coordinate $y_l$ is chosen with distribution $\nu$ on $(Y,\Cal
Y)$ and the coordinate $t_l$ with uniform distribution on the
interval $[-1,1]$ independently of $y_l$. (The number~$p$ will be
chosen later.) Let us fix some indices $1\le j,k\le M$, and estimate
the probability that the sets $A(f_j)\cap S_0(p)$ and $A(f_k)\cap
S_0(p)$ agree, where $A(f)$ denotes the graph of the function~$f$.
Consider the symmetric difference $A(f_j)\Delta A(f_k)$
of the sets $A(f_j)$ and $A(f_k)$. The sets $A(f_j)\cap S_0(p)$ and
$A(f_k)\cap S_0(p)$ agree if and only if $(y_l,t_l)\notin A(f_j)\Delta
A(f_k)$ for all $(y_l,t_l)\in S_0(p)$. Let us observe that for a fixed
$l$ the estimate $P((y_l,t_l)\in A(f_j)\Delta A(f_k))
=\frac12(\nu\times\lambda)(A(f_j)\Delta A(f_k))
=\frac12\int |f_j-f_k|\,d\nu\ge\frac\e2$ hold, where
$\lambda$ denotes the Lebesgue measure. This implies that the
probability that the (random) sets $A(f_j)\cap S_0(p)$ and
$A(f_k)\cap S_0(p)$ agree can be bounded from above by
$\(1-\frac\e2\)^p\le e^{-p\e/2}$.
Hence the probability that all sets $A(f_j)\cap S_0(p)$ are different
is greater than $1-\binom M2 e^{-p\e/2}\ge1-\frac{M^2}2e^{-p\e/2}$.
Choose $p$ such that $\frac74e^{p\e/2}>e^{(p+1)\e/2}>M^2\ge e^{p\e/2}$.
Then the above probability is greater than $\frac18$, and there exists
some set $S_0(p)$ with the desired property.

The inequalities $M\le Bp^K$ and $M^2\ge e^{p\e/2}$ imply that
$M\ge e^{\e M^{1/K}/4B^{1/K}}$, i.e.\ $\frac{\log M^{1/K}}{M^{1/K}}
\ge \frac\e{4KB^{1/K}}$. As $\frac{\log M^{1/K}}{M^{1/K}}\le CM^{-1/2K}$
for $M\ge1$ with some universal constant $C>0$, this estimate implies
that Theorem 5.2 holds with the exponent $L$ and parameter $D$ given in
its formulation.

\medskip
Let us observe that if $\Cal F$ is an $L_1$-dense class of functions
on a measure space $(Y,\Cal Y)$ with some exponent $L$ and parameter
$D$, and also the inequality $\supp_{y\in Y}|f(y)|\le1$ holds for all
$f\in\Cal F$, then $\Cal F$ is an $L_2$-dense class of functions
with exponent $2L$ and parameter $D2^L$. Indeed, if we fix some
probability measure $\nu$ on $(Y,\Cal Y)$ together with a number
$0<\e\le1$, and $\Cal D(\e,\nu)=\{f_1,\dots, f_M\}$ is an
$\frac{\e^2}2$-dense set of $\Cal F$ in the space $L_1(Y,\Cal Y,\nu)$,
$M\le2^L D \e^{-2L}$, then for all function $f\in \Cal F$ some
function $f_j\in\Cal D(\e,\nu)$ can be chosen in such a way that
$\int(f-f_j)^2\,d\nu\le2\int|f-f_j|\,d\nu\le\e^2$. This implies
that $\Cal F$ is an $L_2$-dense class with the given exponent and
parameter.

It is not easy to check whether a collection of subsets $\Cal D$
of a set $X$ is a Vapnik--\v{C}ervonenkis class even with the help
of Theorem~5.1. Therefore the following Theorem~5.3 which enables
us to construct many non-trivial Vapnik--\v{C}ervonenkis classes
is of special interest. Its proof is given in Appendix~A.

\medskip\noindent
{\bf Theorem 5.3. (A way to construct Vapnik--\v{C}ervonenkis classes).}
{\it Let us consider a $k$-dimensional subspace $\Cal G_k$ of the
linear space of real valued functions defined on a set $X$, and define
the level-set $A(g)=\{x\colon\; x\in X,\,g(x)\ge0\}$ for all functions
$g\in\Cal G_k$. Take the class of subsets
$\Cal D=\{A(g)\colon\; g\in \Cal G_k\}$ of the set $X$ consisting of
the above introduced level sets. No subset $S=S(k+1)\subset X$ of
cardinality $k+1$ is shattered by $\Cal D$. Hence by Theorem~5.1
$\Cal D$ is a Vapnik--\v{C}ervonenkis class of subsets of~$X$.}

\medskip
Theorem~5.3 enables us to construct many interesting
Vapnik--\v{C}ervonenkis classes. Thus for instance the class of
all half-spaces in a Euclidean space, the class of all ellipses in
the plane, or more generally the level sets of $k$-order algebraic
functions with a fixed number $k$ constitute a Vapnik--\v{C}ervonenkis
class. It can be proved that if $\Cal C$ and $\Cal D$ are
Vapnik--\v{C}ervonenkis classes of subsets of a set $S$, then also
their intersection
$\Cal C\cap \Cal D=\{C\cap D\colon\; C\in\Cal C,\,D\in\Cal D\}$, their
union $\Cal C\cup \Cal D=\{C\cup D\colon\; C\in\Cal C,\,D\in\Cal D\}$
and complementary sets $\Cal C^c=\{S\setminus C\colon\; C\in\Cal C\}$
are Vapnik--\v{C}ervonenkis classes. These results are less
important for us, and their proofs will be omitted. We are
interested in Vapnik--\v{C}ervonenkis classes not for their own
sake. We are going to study $L_2$-dense classes of functions, and
Vapnik--\v{C}ervonenkis classes make possible to find some
examples. Indeed, Theorem 5.2 implies that if $\Cal D$ is a
Vapnik--\v{C}ervonenkis class of subsets of a set $S$, then their
indicator functions constitute an  $L_1$-dense, hence also an
$L_2$-dense class of functions. Then the results of Lemma~5.4
formulated below enable us to construct new $L_2$-dense class of
functions.
%The description of $L_2$-dense classes of functions are
%interesting for us, because they appear in the conditions of the
%results in Section~4.

\medskip\noindent
{\bf Lemma 5.4. (Some useful properties of $L_2$-dense classes).}
{\it Let $\Cal G$ be an $L_2$-dense class of functions on some space
$(Y,\Cal Y)$ whose absolute values are bounded by one, and let $f$ be a
function on $(Y,\Cal Y)$ also with absolute value bounded by one. Then
$f\cdot\Cal G=\{f\cdot g\colon\; g\in G\}$ is also an $L_2$-dense class
of functions. Let $\Cal G_1$ and $\Cal G_2$ be two $L_2$-dense classes
of functions on some space $(Y,\Cal Y)$ whose absolute values are
bounded by one. Then the classes of functions
$\Cal G_1+\Cal G_2=\{g_1+g_2\colon\; g_1\in\Cal G_1,\,g_2\in\Cal G_2\}$,
$\Cal G_1\cdot\Cal G_2=\{g_1g_2\colon\; g_1\in\Cal G_1,\,g_2\in\Cal G_2\}$,
$\min(\Cal G_1,\Cal G_2)=\{\min(g_1,g_2)\colon\; g_1\in\Cal G_1,\,g_2\in
\Cal G_2\}$, $\max(\Cal G_1,\Cal G_2)=\{\max(g_1,g_2)\colon\; g_1\in
\Cal G_1,\,g_2\in\Cal G_2\}$ are also $L_2$-dense. If $\Cal G$ is an
$L_2$-dense class of functions, and $\Cal G'\subset G$, then $\Cal G'$
is also an $L_2$-dense class.}

\medskip\noindent
The proof of Lemma 5.4 is rather straightforward. One has to observe
for instance that if $g_1,\bar g_1\in\Cal G_1$,
$g_2,\bar g_2\in\Cal G_2$ then $|\min(g_1,g_2)-\min(\bar g_1,\bar g_2)|
\le |g_1-\bar g_1)|+|g_2-\bar g_2|$, hence if
$g_{1,1},\dots,g_{1,M_1}$ is an $\frac\e2$-dense subset of $\Cal G_1$
and $g_{2,1},\dots,g_{2,M_2}$ is an $\frac\e2$-dense subset of $\Cal
G_2$ in the space $L_2(Y,\Cal Y,\nu)$ with some probability measure
$\nu$, then the functions $\min(g_{1,j},g_{2,k})$, $1\le j\le M_1$,
$1\le k\le M_2$ constitute an $\e$-dense subset of $\min(\Cal G_1,\Cal
G_2)$ in $L_2(Y,\Cal Y,\nu)$. The last statement of Lemma 5.4 was proved
after the Corollary of Theorem~4.1. The details are left to the reader.

\medskip
The above result enable us to construct some $L_2$ dense class of
functions. We give an example for it in the following Example~5.5
which is a consequence of Theorem~5.2 and Lemma~5.4.

\medskip\noindent
{\bf Example 5.5.} {\it Take $m$ measurable functions $f_j(x)$,
$1\le j\le m$, functions on a measurable space $(X,\Cal X)$ which
have the property $\sup\limits_{x\in X}|f_j(x)|\le1$ for all
$1\le j\le m$. Let $\Cal D$ be a Vapnik-\v{C}ervonenkis class
consisting of measurable subsets of the set $X$. Define for all
pairs $f_j$, $1\le j\le m$, and $D\in\Cal D$ the function
$f_{j,D}(\cdot)$ as $f_{j,D}(x)=f_j(x)$ if $x\in D$, and
$f_{j,D}(x)=0$ if $x\notin D$, i.e. $f_{j,D}(\cdot)$ is the
restriction of the function $f_j(\cdot)$ to the set~$D$. The set
of functions $f_{j,D}$, $1\le j\le m$, $D\in\Cal D$, is an
$L_2$-dense class of functions.}

\medskip
Beside this, Theorem~5.3 helps us to construct
Vapnik-\v{C}ervonenkis classes of sets. Let me also remark that it
follows from the result of this section that the random variables
considered in Lemma~4.5 are not only countably approximable, but
the class of functions $f_{u_1,\dots,u_k,v_1,\dots,v_k}$
appearing in their definition is $L_2$-dense.


\beginsection 6. The proof of Theorems 4.1 and 4.2 on the
supremum of random sums.

In this section we prove Theorem~4.2, an estimate about the tail
distribution of the supremum of an appropriate class of Gaussian
random variables with the help of a method, called the chaining
argument. We also investigate the proof of Theorem~4.1 which can
be considered as a version of Theorem~4.2 about the supremum of
partial sums of independent and identically distributed random
variables. The chaining argument is not a strong enough method
to prove Theorem~4.1, but it enables us to prove a weakened form
of it formulated in Proposition~6.1. This result turned out to
be useful in the proof of Theorem~4.1. It enables us to reduce
the proof of Theorem~4.1 to a simpler statement formulated in
Proposition~6.2. In this section we prove Proposition~6.1,
formulate Proposition~6.2, and reduce the proof of Theorem~4.1
with the help of Proposition~6.1 to this result. The proof of
Proposition~6.2 which demands different arguments is postponed
to the next section. Before presenting the proofs of this section
I briefly describe the chaining argument.

Let us consider a countable class of functions $\Cal F$ on a
probabality space $(X,\Cal X,\mu)$ which is $L_2$-dense with
respect to the probability measure~$\mu$. Let us have either a
class of Gaussian random variables $Z(f)$ with zero
expectation such that $EZ(f)Z(g)=\int f(x)g(x)\mu(\,dx)$,
$f,g\in\Cal F$, or a set of normalized partial sums
$S_n(f)=\frac1{\sqrt n}\summ_{j=1}^nf(\xi_j)$, $f\in\Cal F$,
where $\xi_1,\dots,\xi_n$ is a sequence of independent $\mu$
distributed random variables with values in the space
$(X,\Cal X)$, and assume that $Ef(\xi_j)=0$ for all
$f\in\Cal F$. We want to get a good estimate on the
probability $P\(\supp_{f\in\Cal F}Z(f)>u\)$ or
$P\(\supp_{f\in\Cal F}S_n(f)>u\)$ if the class of
functions~$\Cal F$ has some nice properties. The chaining
argument suggests to prove such an estimate in the following way.

Let us try to find an appropriate sequence of subset
$\Cal F_1\subset\Cal F_2\subset\cdots\subset\Cal F$ such that
$\bigcupp_{N=1}^\infty\Cal F_N=\Cal F$, $\Cal F_N$ is such a
set of functions from $\Cal F$ with relatively few elements for
which $\inf\limits_{f\in\Cal F_N}\int (f-\bar f)^2\,d\mu\le\delta_N$ 
with an appropriately chosen number $\delta_N$ for all functions
$\bar f\in\Cal F$, and let us give a good estimate on the
probability $P\(\supp_{f\in\Cal F_N}Z(f)>u_N\)$ or
$P\(\supp_{f\in\Cal F_N}S_n(f)>u_N\)$ for all $N=1,2,\dots$ with
an appropriately chosen monotone increasing sequence $u_N$
such that $\limm_{N\to\infty} u_N=u$.

We can get a relatively good estimate under appropriate conditions
for the class of functions~$\Cal F$ by choosing the classes of
functions $\Cal F_N$ and numbers $\delta_N$ and $u_N$ in an
appropriate way. We try to bound the difference of the probabilities
$$
P\(\sup_{f\in\Cal F_{N+1}}Z(f)>u_{N+1}\)
-P\(\sup_{f\in\Cal F_N}Z(f)>u_N\)
$$
or of the analogous difference if $Z(f)$ is replaced by $S_n(f)$.
For the sake of completeness define this difference also in the
case $N=1$ with the choice $\Cal F_0=\emptyset$, when the
second probability in this difference equals zero.

This probability can be estimated in a natural way by taking for
all functions $f_{j_{N+1}}\in\Cal F_{N+1}$ a function
$f_{j_N}\in\Cal F_N$ which is close to it, more explicitly
$\int (f_{j_{N+1}}-f_{j_N})^2\,d\mu\le\delta_N^2$, and
calculating the probability that the difference of the random
variables corresponding to these two functions is greater than
$u_{N+1}-u_N$. We can estimate these probabilities with the help 
of some results which give a relatively good bound on the tail
distribution of $Z(g)$ or $S_n(g)$ if $\int g^2\,d\mu$ is small.
The sum of all such probabilities gives an upper bound for the 
above considered difference of probabilities. Then we get an 
estimate for the probability
$P\(\sup\limits_{f\in\Cal F_N}Z(f)>u_N\)$ for all $N=1,2,\dots$,
by summing up the above estimate, and we get a bound on the
probability we are interested in by taking the limit
$N\to\infty$. This method is called the chaining argument. It
got this name, because we estimate the contribution of a random
variable corresponding to a function
$f_{j_{N+1}}\in\Cal F_{N+1}$ to the bound of the probability we
investigate by taking the random variable corresponding to a
function $f_{j_N}\in\Cal F_N$ close to it, then we choose
another random variable corresponding to a function
$f_{j_{N-1}}\in\Cal F_{N-1}$ close to this function, and so on
we take a chain of subsequent functions and the random variables
corresponding to them.

First we show how this method supplies the proof of Theorem~4.2.
Then we turn to the investigation of Theorem~4.1. In the study of
this problem the above method does not work well, because if two
functions are very close to each other in the $L_2(\mu)$-norm,
then the Bernstein inequality (or an improvement of it) supplies
a much weaker estimate for the difference of the partial sums
corresponding to these two functions than the bound suggested
by the central limit theorem. On the other hand, we shall prove
a weaker version of Theorem~4.1 in Proposition~6.1 with the help
of the chaining argument. This result will be also useful for us.

\medskip\noindent
{\it Proof of Theorem 4.2.}\/ Let us list the elements of $\Cal F$ as
$\{f_0,f_1,\dots\}=\Cal F$, and choose for all $p=0,1,2,\dots$ a set
of functions $\Cal F_p=\{f_{a(1,p)},\dots,f_{a(m_p,p)}\}\subset\Cal F$
with $m_p\le (D+1)\,2^{2pL}\sigma^{-L}$ elements in such a way that
$\inff_{1\le j\le m_p} \int (f-f_{a(j,p)})^2\,d\mu\le 2^{-4p}\sigma^2$
for all $f\in\Cal F$, and let $f_p\in \Cal F_p$. For all indices
$a(j,p)$ of the functions in $\Cal F_p$, \ $p=1,2,\dots$, define a
predecessor $a(j',p-1)$ from the indices of the set of functions
$\Cal F_{p-1}$ in such a way that the functions $f_{a(j,p)}$ and
$f_{a(j',p-1))}$ satisfy the relation
$\int(f_{(j,p)}-f_{(j',p-1)})^2\,d\mu\le2^{-4(p-1)}\sigma^2$.
With the help of the behaviour of the standard normal distribution
function we can write the estimates
$$
\align
P(A(j,p))&=P\(|Z(f_{a(j,p)})-Z(f_{a(j',p-1)})|\ge 2^{-(1+p)}u\)
\le 2\exp\left\{-\frac{2^{-2(p+1)}u^2}{2\cdot 2^{-4(p-1)}\sigma^2}
\right\}\\
&=2\exp\left\{-\frac{2^{2p}u^2}{128\sigma^2}\right\} \quad 1\le j\le
m_p,\; p=1,2,\dots,
\endalign
$$
and
$$
P(B(j))=P\(|Z(f_{a(j,0)})|\ge \frac u2\)\le
\exp\left\{-\frac {u^2}{8\sigma^2}\right\},
\quad 1\le j\le m_0.
$$
The above estimates together with the relation $\bigcupp_{p=0}^\infty
\Cal F_p=\Cal F$ which implies that \hfill\break
$\{|Z(f)|\ge u\}\subset\bigcupp_{p=1}^\infty\bigcupp_{j=1}^{m_p}A(j,p)
\cup\bigcupp_{s=1}^{m_0}B(s)$ for all $f\in\Cal F$ yield that
$$ \allowdisplaybreaks
\align
&P\(\sup_{f\in\Cal F} |Z(f)|\ge u\)
\le P\(\bigcup_{p=1}^\infty\bigcup_{j=1}^{m_p}A(j,p)
\cup\bigcup_{s=1}^{m_0}B(s)\) \\
&\qquad \le \sum_{p=1}^\infty\sum_{j=1}^{m_p}P(A(j,p))
+\sum_{s=1}^{m_0}P(B(s)) \\
&\qquad \le \sum_{p=1}^{\infty} 2(D+1)2^{2pL}
\sigma^{-L} \exp\left\{-\frac{2^{2p}u^2}{128\sigma^2} \right\}
+2(D+1)\sigma^{-L} \exp\left\{-\frac {u^2}{8\sigma^2}\right\}.
\endalign
$$
If $u\ge ML^{1/2}\sigma\log^{1/2}\frac2\sigma$ with $M\ge16$ (and
$L\ge1$ and $0<\sigma\le1$), then
$$
2^{2pL}\sigma^{-L}\exp\left\{-\frac{2^{2p}u^2}{256\sigma^2}
\right\}\le2^{2pL}\sigma^{-L}\(\frac\sigma
2\)^{2^{2p}M^2L/256}\le 2^{-pL}\le2^{-p}
$$
for all $p=0,1\dots$, hence the previous inequality implies that
$$
P\(\sup_{f\in\Cal F}|Z(f)|\ge u\)\le 2(D+1)\summ_{p=0}^\infty 2^{-p}
\exp\left\{-\frac{2^{2p}u^2}{256\sigma^2} \right\}=4(D+1)
\exp\left\{-\frac{u^2}{256\sigma^2} \right\}.
$$
Theorem 4.2 is proved.

\medskip
With an appropriate choice of the bound of the integrals in the
definition of the sets $\Cal F_p$ in the proof of Theorem~4.2 and
some additional calculation it can be proved that the coefficient
$\frac1{256}$ in the exponent of the right-hand side (4.7) can be
replaced by $\frac{1-\e}2$ with arbitrary small $\e>0$ if the
remaining (universal) constants in this estimate are chosen
sufficiently large.

The proof of Theorem 4.2 was based on a sufficiently good estimate on
the probabilities $P(|Z(f)-Z(g)|>u)$ for pairs of functions
$f,g\in\Cal F$ and numbers $u>0$.  In the case of Theorem~4.1 only a
weaker bound can be given for the corresponding probabilities. There
is no good estimate on the tail distribution of the difference
$S_n(f)-S_n(g)$ if its variance is small. As a consequence, the
chaining argument supplies only a weaker result in this case. This
result, where the tail distribution of the supremum of the normalized
random sums $S_n(f)$ is estimated on a relatively dense subset of the
class of functions  $f\in\Cal F$ in the $L_2(\mu)$ norm will be given
in Proposition~6.1. Another result will be formulated in
Proposition~6.2 whose proof is postponed to the next section. It will
be shown that Theorem~4.1 follows from Propositions~6.1 and~6.2.

Before the formulation of Proposition~6.1 I recall an estimate which
is a simple consequence of Bernstein's inequality. If
$S_n(f)=\frac1{\sqrt n}\summ_{j=1}^n f(\xi_j)$ is the normalized sum of
independent, identically random variables, $P(|f(\xi_1)|\le1)=1$,
$Ef(\xi_1)=0$, $Ef(\xi_1)^2\le\sigma^2$, then there exists some
constant $\alpha>0$ such that
$$
P(|S_n(f)|>u)\le 2e^{-\alpha u^2/\sigma^2}\quad \text{if}\quad 0<u<\sqrt
n\sigma^2. \tag6.1
$$

\medskip\noindent
{\bf Proposition 6.1.} {\it Let us have a countable $L_2$-dense
class of functions $\Cal F$ with parameter $D\ge1$ and
exponent~$L\ge1$ on a measurable space $(X,\Cal X)$ whose elements
satisfy relations~(4.1), (4.2) and~(4.3) with some probability
measure $\mu$ on $(X,\Cal X)$ and real number $0<\sigma\le1$. Take
a sequence of independent, $\mu$-distributed random variables
$\xi_1,\dots,\xi_n$, $n\ge2$, and define the normalized random
sums $S_n(f)=\frac1{\sqrt n}\summ_{l=1}^nf(\xi_l)$, for all
$f\in \Cal F$. Let us fix some number $\bar A\ge1$. There exists
some number $M=M(\bar A)$ such that with these parameters~$\bar A$
and~$M=M(\bar A)\ge1$ the following relations hold.

For all numbers $u>0$ such that $n\sigma^2\ge \(\frac u\sigma\)^2
\ge M(L\log\frac2\sigma+\log D)$ a number $\bar\sigma=\bar\sigma(u)$,
$0\le\bar\sigma\le \sigma\le1$, and a collection of functions
$\Cal F_{\bar\sigma}=\{f_1,\dots,f_m\}\subset \Cal F$ with
$m\le D\bar\sigma^{-L}$ elements can be chosen in such a way that
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$, satisfy the relation
$\bigcupp_{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\(\sup_{f\in\Cal F_{\bar\sigma}} |S_n(f)|\ge\frac u{\bar A}\)
\le 4\exp\left\{-\alpha\(\frac u{10\bar A\sigma}\)^2\right\}
\quad \text{if } n\sigma^2\ge(\tfrac u\sigma)^2
\ge M(L\log\tfrac2\sigma+\log D)
\tag6.2
$$
with the constants $\alpha$ in formula~(6.1) and the exponent $L$
and parameter $D$ of the $L_2$-dense class $\Cal F$, and also the
inequality $\frac1{16}(\frac u{\bar A\bar\sigma})^2\ge n\bar\sigma^2
\ge\frac1{64}\(\frac u{\bar A\sigma}\)^2$ holds with the
number~$\bar\sigma=\bar\sigma(u)$. If the number~$u$ satisfies
also the inequality
$$
n\sigma^2\ge \(\frac u\sigma\)^2\ge M\(L^{3/2}\log\frac2\sigma
+(\log D)^{3/2}\) \tag6.3
$$
with a sufficiently large number $M=M(\bar A)$, then the relation
$n\bar\sigma^2\ge L\log n+\log D$ holds, too.}

\medskip
Proposition~6.1 helps to reduce the proof of Theorem~4.1 to the
case when the $L_2$-norm of the functions in the class $\Cal F$
is bounded by a relatively small number $\bar\sigma$. In more
detail, the proof of Theorem~4.1 can be reduced to a good
estimate on the distribution of the supremum of random variables
$\supp_{f\in D_j}|S_n(f-f_j)|$ for all classes $\Cal D_j$,
$1\le j\le m$, by means of Proposition~6.1. We also have to know
that the number~$m$ of the classes $\Cal D_j$ is not too large.
Beside this, we need some estimates on the number $\bar\sigma$
which is the upper bound of the $L_2$-norm of the functions
$f-f_j$, $f\in\Cal D_j$. To get such bounds for $\bar\sigma$ that
we need in the applications of Proposition~6.1 we introduced a
large parameter~$\bar A$ in the formulation of Proposition~6.1
and imposed a condition with a sufficiently large 
number~$M=M(\bar A)$ in formula~(6.3). This condition reappears
in Theorem~4.1 in the conditions of the estimate~(4.4).

Let me remark that one of the inequalities the number
$\bar\sigma$ introduced in Proposition~6.1 satisfies has the
consequence $u>\const\sqrt n\bar\sigma^2$ with an appropriate
constant, and we want to estimate the probability
$P\(\supp_{f\in\Cal F} S_n(f)|>u\)$ with this number~$u$ and a
class of functions~$\Cal F$ whose $L_2$ norm is bounded
by~$\bar\sigma$. Formula~(6.1), that will be applied in the
proof of Proposition~6.1 holds under the condition
$u<\sqrt n\sigma^2$, which is an inequality in the opposite
direction. Hence to complete the proof of Theorem~4.1 with the
help of Proposition~6.1 we need a result whose proof demands an
essentially different method. Proposition~6.2 formulated below
is such a result. I shall show that Theorem~4.1 is a consequence
of Propositions~6.1 and~6.2. Proposition~6.1 is proved at the
end of this section, while the proof of Proposition~6.2 is
postponed to the next section.

\medskip\noindent
{\bf Proposition 6.2.} {\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, $L_2$-dense class of
functions $f=f(x)$ on $(X,\Cal X)$ with some parameter $D\ge1$ and
exponent $L\ge1$ which satisfies conditions~(4.1), (4.2) and~(4.3)
with some $0<\sigma\le1$ such that the inequality
$n\sigma^2>L\log n+\log D$ holds. Then there exists
a threshold index $A_0\ge5$ such that the normalized random sums
$S_n(f)$, $f\in \Cal F$, introduced in Theorem~4.1 satisfy the
inequality
$$
P\(\sup_{f\in\Cal F}|S_n(f)|\ge A n^{1/2}\sigma^2\)\le
e^{-A^{1/2}n\sigma^2/2}\quad \text{if } A\ge A_0. \tag6.4
$$
%$A_0=2^{10}\cdot10^{16}$ and $\gamma=\frac12$.)
}

\medskip
I did not try to find optimal parameters in formula (6.4). Even the
coefficient $-A^{1/2}$ in the exponent at its right-hand side could
be improved. The result of Proposition~6.2 is similar to that of
Theorem~4.1. Both of them give an estimate on a probability of the
form $P\(\supp_{f\in\Cal F}|S_n(f)|\ge u\)$ with some class of
functions~$\Cal F$. The essential difference
between them is that in Theorem~4.1 this probability is considered
for $u\le n^{1/2}\sigma^2$ while in Proposition~6.2 the case
$u=A n^{1/2}\sigma^2$ with $A\ge A_0$ is taken, where $A_0$ is a
sufficiently large positive number. Let us observe that in this
case no good Gaussian type estimate can be given for the
probabilities $P(S_n(f)\ge u)$, $f\in\Cal F$. In this case
Bernstein's inequality yields the bound
$P(S_n(f)>An^{1/2}\sigma^2)=P\(\summ_{l=1}^nf(\xi_l)>uV_n\)<e^{-\const
An\sigma^2}$ with $u=A\sqrt n\sigma$ and $V_n=\sqrt n\sigma$ for
each single function $f\in\Cal F$ which takes part in the supremum of
formula~(6.4). The estimate~(6.4) yields a slightly weaker
estimate for the supremum of such random variables, since it contains the
coefficient $A^{1/2}$ instead of $A$ in the exponent of the estimate
at the right-hand side. But also such a bound will be sufficient for
us.

In Proposition~6.2 such a situation is considered when the
irregularities of the summands provide a non-negligible contribution
to the probabilities $P(|S_n(f)|\ge u)$, and the chaining argument
applied in the proof of Theorem~4.2 does not give a good estimate on
the probability at the left-hand side of~(6.4). This is the reason
why we separated the proof of Theorem~4.1 to  two different
statements given in Proposition~6.1 and~6.2.

In the proof of Theorem~4.1 Proposition~6.1 will be applied
with a sufficiently large number $\bar A\ge1$ and an appropriate
number $M=M(\bar A)$ appearing in the formulation of this result.
Proposition~6.2 will be applied for the set of functions
$\Cal F=\Cal F_j=\left\{\frac{g-f_j}2\colon\; g\in\Cal D_j\right\}$
and number $\sigma=\bar\sigma$, with the number~$\bar\sigma$,
functions~$f_j$ and sets of functions~$\Cal D_j$ introduced in
Proposition~6.1 and with the parameter~$A_0$ appearing in the
formulation of Proposition~6.2. We can write
$$ \allowdisplaybreaks
\align
P\(\supp_{f\in\Cal F}|S_n(f)|\ge u\)&\le
P\(\sup_{f\in\Cal F_{\bar\sigma}} |S_n(f)|\ge \frac u{\bar A}\) \tag6.5 \\
&\qquad +\sum_{j=1}^m P\(\sup_{g\in\Cal D_j}
\left|S_n\(\frac{f_j-g}2\)\right| \ge\(\frac12-\frac1{2\bar A}\)u\),
\endalign
$$
where $m$ is the cardinality of the set of functions $\Cal
F_{\bar\sigma}$ appearing in Proposition~6.1, which is
bounded by $m\le D\bar\sigma^{-L}$. We want to choose the
number~$\bar A$ in such a way that the inequality
$(\frac12-\frac1{2\bar A})u\ge A_0\sqrt n\bar\sigma^2$ holds,
since this enables us to estimate the second term in~(6.5) by
Proposition~6.2 with the choice $A=A_0$. This inequality is
equivalent to $n\bar\sigma^2
\le(\frac1{2A_0}-\frac1{2A_0\bar A})^2(\frac u{\bar\sigma})^2$.
On the other hand, 
$(\frac u{4\bar A\bar\sigma})^2\ge n\bar\sigma^2$ by Proposition~6.1,
hence the desired inequality holds if 
$\frac1{2A_0}-\frac1{2A_0\bar A}\ge\frac1{4\bar A}$.
Hence with the choice $\bar A=\max(1,\frac{A_0+2}2)$ and a
sufficiently large $M=M(\bar A)$ we can bound both terms at the
right-hand side of~(6.5) with Propositions~(6.1) and~(6.2)
respectively.

With such a choice of~$\bar A$ we can write by Proposition~6.2
$$
\align
P\(\sup_{g\in\Cal D_j}
\left|S_n\(\frac{f_j-g}2\)\right| \ge\(\frac12-\frac1{2\bar A}\)u\)
&\le P\(\sup_{g\in\Cal D_j} \left|S_n\(\frac{f_j-g}2\)\right| \ge
A_0\sqrt n\bar\sigma^2\)\\
&\le e^{-A_0^{1/2}n\bar\sigma^2/2} \quad\text{for all }
1\le j\le m.
\endalign
$$
(Observe that the set of functions $\frac{f_j-g}2$, $g\in\Cal D_j$,
is an $L_2$-dense class with parameter $D$ and exponent $L$.) Hence
Proposition~6.1 together with the bound $m\le D\bar\sigma^{-L}$ and
formula~6.5 imply that
$$
P\(\supp_{f\in\Cal F}|S_n(f)|\ge u\)
\le 4\exp\left\{-\alpha\(\frac u{10\bar A\sigma}\)^{2}\right\}
+D\bar\sigma^{-L} e^{-A_0^{1/2}n\bar\sigma^2/2}. \tag6.6
$$

To get the estimate in Theorem~4.1 from inequality (6.6) we show
that the inequality $n\bar\sigma^2\ge L\log n+\log D$ (with $L\ge1$,
$D\ge1$ and $n\ge2$) which is valid under the conditions of
Proposition~6.1 implies that $D\bar\sigma^{-L}\le e^{n\bar\sigma^2}$.
Indeed, we have to show that
$\log D+L\log\frac1{\bar\sigma}\le n\bar\sigma^2$. But we have
$n\bar\sigma^2\ge L\log n\ge\log n$, hence
$\frac1{\bar\sigma}\le\sqrt{\frac n{\log n}}\le n$, thus
$\log\frac1{\bar\sigma}\le\log n$, and
$\log D+L\log\frac1{\bar\sigma}\log D+L\log n\le n\bar\sigma^2$, as
we claimed.

This inequality together with the inequality $n\bar\sigma^2
\ge\frac1{64}(\frac u{\bar A\sigma})^2$, proved in Proposition~6.1
imply that
$$
D\bar\sigma^{-L} e^{-A_0^{1/2}n\bar\sigma^2/2}
\le \exp\left\{-\(\frac{A_0^{1/2}}2-1\)n\bar\sigma^2\right\}
\le \exp\left\{-\frac{(A_0^{1/2}-2)}{128\bar A^2}\(\frac u\sigma\)^2\right\}.
$$
Hence relation~(6.6) yields that
$$
P\(\supp_{f\in\Cal F}|S_n(f)|\ge u\)\le 4\exp
\left\{-\frac\alpha{100\bar A^2}\(\frac u\sigma\)^2\right\}
+\exp\left\{-\frac{(A_0^{1/2}-2)}{128\bar A^2}
\(\frac u\sigma\)^2\right\},
$$
and because of the relation $A_0\ge5$ this estimate implies
Theorem~4.1. Let me remark that the condition $\sqrt n\sigma^2\ge
u\ge M\sigma(L^{3/4}\log^{1/2}\frac2\sigma +(\log D)^{3/4})$
appears in formula~(4.4) because of condition~(6.3) imposed
in Proposition~6.1. (The parameter~$M$ in formula~(4.4) can be
chosen as the double of the parameter~$M$ in~(6.3).)

\medskip
I finish this section with the proof of Proposition~6.1.

\medskip\noindent
{\it Proof of Proposition 6.1.}\/ Let us list the members of
$\Cal F$, as $f_1,f_2,\dots$, and choose for all $p=0,1,2,\dots$ a
set $\Cal F_p=\{f_{a(1,p)},\dots,f_{a(m_p,p)}\}\subset\Cal F$ with
$m_p\le D\, 2^{2pL}\sigma^{-L}$ elements in such a way that
$\inff_{1\le j\le m_p} \int (f-f_{a(j,p)})^2\,d\mu\le 2^{-4p}\sigma^2$
for all $f\in\Cal F$. For all indices $a(j,p)$, $p=1,2,\dots$,
$1\le j\le m_p$, choose a predecessor $a(j',p-1)$, $j'=j'(j,p)$,
$1\le j'\le m_{p-1}$, in such a way that the functions $f_{a(j,p)}$
and $f_{a(j',p-1)}$ satisfy the relation
$\int|f_{a(j,p)}-f_{a(j',p-1)}|^2\,d\mu
\le \sigma^2 2^{-4(p-1)}$. Then we have
$\int\(\frac{f_{a(j,p)}-f_{a(j',p-1)}}2\)^2\,d\mu\le4
\sigma^2 2^{-4p}$ and $\supp_{x_j\in X,\,1\le j\le k}\left|
\frac{f_{a(j,p)}(x_1,\dots,x_k)-f_{a(j',p-1)}(x_1,\dots,x_k)}2\right|
\le 1$. Relation (6.1) yields that
$$
\align
P(A(j,p))&=P\(\frac12|S_{n}(f_{a(j,p)}-f_{a(j',p-1)})|\ge
\frac{2^{-(1+p)}u}
{2\bar A}\) \le 2 \exp\left\{-\alpha\(\frac{2^pu}{8\bar A
\sigma}\)^2 \right\}\\
&\qquad \text {if}\quad n\sigma^2
\ge 2^{6p}\(\frac u{16\bar A\sigma}\)^2,
\quad 1\le j\le m_p,\quad p=1,2,\dots, \tag6.7
\endalign
$$
and
$$
\aligned
P(B(s))&=P\(|S_n(f_{s,0})|\ge \frac u{2\bar A}\)\le
2\exp\left\{-\alpha\(\frac u{2\bar A\sigma}\)^2\right\},
\quad 1\le s\le m_0,\\
&\qquad\qquad\qquad\text{if} \quad n\sigma^2\ge \(\frac u{2\bar
A\sigma}\)^2.
\endaligned\tag6.8
$$
Choose an integer number $R=R(u)$, $R\ge1$, by the inequality
$2^{6(R+1)}\(\frac{u}{16\bar A\sigma}\)^2>n\sigma^2
\ge2^{6R}\(\frac{u}{16\bar A\sigma}\)^2$, define
$\bar\sigma^2=2^{-4R}\sigma^2$ and $\Cal F_{\bar\sigma}=\Cal F_R$.
(As $n\sigma^2\ge\(\frac u\sigma\)^2$ and $\bar A\ge1$ by our
conditions, there exists such a number $R\ge1$. The number~$R$
was chosen as the largest number~$p$ for which the second
relation of formula~(6.7) holds.) Then the cardinality~$m$ of
the set $\Cal F_{\bar\sigma}$ equals $m_R\le D2^{2RL}\sigma^{-L}
=D\bar\sigma^{-L}$, and the sets $\Cal D_j$ are
$\Cal D_j=\{f\colon\; f\in\Cal F,\int (f_{a(j,R)}-f)^2\,d\mu\le
2^{-4R}\sigma^2\}$, $1\le j\le m_R$, hence $\bigcupp_{j=1}^m \Cal
D_j=\Cal F$. Beside this, with our choice of the number $R$
inequalities (6.7) and (6.8) can be applied for $1\le p\le R$.
Hence the definition of the predecessor of an index $(j,p)$ implies
that
$\left\{\oo\colon\;\supp_{f\in\Cal F_{\bar\sigma}}|S_n(f)(\oo)|\ge
\frac u{\bar A}\right\}\subset
\bigcupp_{p=1}^R\bigcupp_{j=1}^{m_p}A(j,p)
\cup\bigcupp_{s=1}^{m_0}B(s)$, and
$$
\align
&P\(\sup_{f\in\Cal F_{\bar\sigma}} |S_n(f)|\ge \frac u{\bar A}\)
\le P\(\bigcup_{p=1}^R\bigcup_{j=1}^{m_p}A(j,p)
\cup\bigcup_{s=1}^{m_0}B(s)\) \\
&\qquad \le
\sum_{p=1}^R\sum_{j=1}^{m_p}P(A(j,p))+\sum_{s=1}^{m_0}P(B(s))
\le \sum_{p=1}^{\infty} 2D\,2^{2pL}\sigma^{-L}
\exp\left\{-\alpha\(\frac{2^pu}{8\bar A\sigma}\)^2
\right\}\\
&\qquad\qquad +2D\sigma^{-L}\exp\left\{-\alpha\(\frac
u{2\bar A\sigma}\)^2\right\}.
\endalign
$$
If the relation $(\frac u\sigma)^2\ge M(L\log\frac2\sigma+\log D)$
holds with a sufficiently large constant~$M$ (depending on $\bar A$),
and $\sigma\le1$, then the inequalities
$$
D2^{2pL}\sigma^{-L}\exp\left\{-\alpha\(\frac{2^pu}{8\bar A\sigma}\)^2
\right\}\le 2^{-p}\exp\left\{-\alpha\(\frac{2^{p}u}
{10\bar A \sigma}\)^2 \right\}
$$
hold for all $p=1,2,\dots$, and
$$
D\sigma^{-L}\exp\left\{-\alpha\(\frac u{2\bar A\sigma}\)^2\right\}
\le\exp\left\{-\alpha\(\frac u{10\bar A\sigma}\)^2\right\}.
$$
Hence the previous estimate implies that
$$
\align
&P\(\sup_{f\in\Cal F_{\bar\sigma}} |S_n(f)|\ge \frac u{\bar A}\)
\le\sum_{p=1}^{\infty}2\cdot 2^{-p}
\exp\left\{-\alpha\(\frac{2^{p}u}{10\bar A \sigma}\)^2
\right\}\\
&\qquad +2\exp\left\{-\alpha\(\frac u{10\bar A \sigma}\)^2\right\}
\le 4 \exp\left\{-\alpha\(\frac u{10 \bar A\sigma}\)^2\right\},
\endalign
$$
and relation (6.2) holds.

As $\sigma^2=2^{4R}\bar\sigma^2$ the inequality
$$
2^{-4R}\cdot\frac{2^{6R}}{256}\(\frac{u}{\bar A\sigma}\)^2\le
n\bar\sigma^2=2^{-4R} n\sigma^2\le
2^{-4R}\cdot\frac{2^{6(R+1)}}{256}\(\frac{u}{\bar A\sigma}\)^2=
\frac14\cdot 2^{-2R}\(\frac{u}{\bar A\bar \sigma}\)^2
$$
holds, and this implies (together with the relation $R\ge1$) that
$$
\frac1{64}\(\frac u{\bar A\sigma}\)^2\le n\bar\sigma^2
\le\frac1{16}\(\frac{u}{\bar A \bar\sigma}\)^2,
$$
as we have claimed. It remained to show that under the
condition~(6.3) $n\bar\sigma^2\ge L\log n+\log D$.

This inequality clearly holds under the conditions of Proposition~6.1
if $\sigma\le n^{-1/3}$, since in this case $\log\frac2\sigma\ge
\frac{\log n}3$, and
$n\bar\sigma^2\ge\frac1{64}(\frac u {\bar A\sigma})^2
\ge\frac1{64\bar A^2} M(L^{3/2}\log\frac2\sigma+(\log D)^{3/2})\ge
\frac1{192\bar A^2} M(L^{3/2}\log n+(\log D)^{3/2})\ge L\log n+\log D$
if $M\ge M_0(\bar A)$ with a sufficiently large number $M_0(\bar A)$.

If $\sigma\ge n^{-1/3}$, we can exploit that the inequality
$2^{6R}\(\frac u{\bar A\sigma}\)^2 \le256n\sigma^2$ holds because
of the definition of the number~$R$. It can be rewritten as
$2^{-4R}\ge 2^{-16/3}\[\dfrac{\(\frac u{\bar A\sigma}\)^2}
{n\sigma^2}\]^{2/3}$.  Hence
$n\bar\sigma^2=2^{-4R}n\sigma^2\ge\frac{2^{-16/3}}{\bar A^{4/3}}
(n\sigma^2)^{1/3}\(\frac u\sigma\)^{4/3}$. As
$\log\frac2\sigma\ge\log2>\frac12$ the inequalities
$n\sigma^2\ge n^{1/3}$ and $(\frac u\sigma)^2\ge
M(L^{3/2}\log\frac2\sigma+(\log D)^{3/2})
\ge\frac M2(L^{3/2}+(\log D)^{3/2})$ hold. They yield that
$$
\align
n\bar\sigma^2&\ge\frac{\bar A^{-4/3}}{50} (n\sigma^2)^{1/3}\(\frac
u\sigma\)^{4/3}\ge\frac{\bar A^{-4/3}}{50}n^{1/9}\(\frac M2\)^{2/3}
(L^{3/2}+(\log D)^{3/2})^{2/3}\\
&\ge\frac{M^{2/3}n^{1/9}(L+\log D)}{100\bar A^{4/3}}\ge L\log n+\log D
\endalign
$$
if $M=M(\bar A)$ is chosen sufficiently large.

\beginsection 7. The completion of the proof of Theorem 4.1.

This section contains the proof of Proposition 6.2 with the help of
a symmetrization argument which completes the proof of Theorem~4.1.
By symmetrization argument I mean the reduction of the investigation
of sums of the form $\sum f(\xi_j)$ to sums of the form
$\sum\e_jf(x_j)$, where $\e_j$ are independent random variables,
independent also of the random variables $\xi_j$, and
$P(\e_j=1)=P(\e_j=-1)=\frac12$.
%This means to replace the terms $f(\xi_j)$ by
%their `symmetrizations' $\e_jf(\xi_j)$ in the sums we are studying.
First a symmetrization lemma is proved, and then with the help of
this result and a conditioning argument the proof of Proposition~6.2
is reduced to the estimation of a probability which can be bounded by
means of the Hoeff\-ding inequality formulated in Theorem 3.4. Such
an approach makes possible to prove Proposition~6.2.

First I formulate the symmetrization lemma we shall apply.

\medskip\noindent
{\bf Lemma 7.1. (Symmetrization Lemma).} {\it Let $Z_n$ and $\bar
Z_n$, $n=1,2,\dots$, be two sequences of random variables
independent of each other, and let the random variables $\bar Z_n$,
$n=1,2,\dots$, satisfy the inequality
$$
P(|\bar Z_n|\le\alpha)\ge\beta\quad \text{for all } n=1,2,\dots \tag7.1
$$
with some numbers $\alpha\ge0$ and $\beta\ge0$. Then
$$
P\(\sup_{1\le n<\infty}|Z_n|>u+\alpha\)\le\frac1\beta P\(\supp_{1\le
n<\infty}|Z_n-\bar Z_n|>u\)\quad \text{for all } u>0.
$$
}

\medskip\noindent
{\it Proof of Lemma 7.1.}\/ Put $\tau=\min\{n\colon\; |Z_n|>u+\alpha\}$ if
there exists such an index $n$, and $\tau=0$ otherwise. Then the
event $\{\tau=n\}$ is independent of the sequence of random variables
$\bar Z_1,\bar Z_2,\dots$ for all $n=1,2,\dots$, and because of this
independence
$$
P(\{\tau=n\})\le\frac1\beta P(\{\tau=n\}\cap\{|\bar Z_n|\le\alpha\})
\le \frac1\beta P(\{\tau=n\}\cap\{|Z_n-\bar Z_n|>u\})
$$
for all $n=1,2,\dots$. Hence
$$
\align
&P\(\sup_{1\le n<\infty}|Z_n|>u+\alpha\)=\sum_{l=1}^\infty P(\tau=l)
\le \frac1\beta \sum_{l=1}^\infty P(\{\tau=l\}\cap\{|Z_l-\bar Z_l|>u\}) \\
&\qquad  \le \frac1\beta \sum_{l=1}^\infty
P(\{\tau=l\}\cap\sup_{1\le n<\infty}|Z_n-\bar Z_n|>u\})
\le\frac1\beta P\(\supp_{1\le n<\infty}|Z_n-\bar Z_n|>u\).
\endalign
$$
Lemma 7.1 is proved.

\medskip
We shall apply the following consequence Lemma~7.2 of the
symmetrization lemma.

\medskip\noindent
{\bf Lemma 7.2.} {\it Let us fix a countable class of functions
$\Cal F$ on a measurable space $(X,\Cal X)$ together with a real
number $0<\sigma<1$. Consider a sequence of independent and identically
distributed random variables $\xi_1,\dots,\xi_n$ with values in the
space $(X,\Cal X)$ such
that $Ef(\xi_1)=0$, $Ef^2(\xi_1)\le\sigma^2$ for all $f\in\Cal F$
together with another sequence $\e_1,\dots,\e_n$ of independent
random variables with distribution $P(\e_j=1)=P(\e_j=-1)=\frac12$,
$1\le j\le n$, independent also of the random sequence
$\xi_1,\dots,\xi_n$. Then
$$
\aligned
&P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
f(\xi_j)\right| \ge A
n^{1/2}\sigma^{2}\) \\
&\qquad \le 4P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge \frac A3 n^{1/2}\sigma^{2}\) \quad\text{if }
A\ge \frac{3\sqrt2}{\sqrt n\sigma}.
\endaligned \tag7.2
$$
}

\medskip\noindent
{\it Proof of Lemma 7.2.}\/ Let us construct an independent copy
$\bar\xi_1,\dots,\bar\xi_n$ of the sequence $\xi_1,\dots,\xi_n$ in
such a way that all three sequences $\xi_1,\dots,\xi_n$, \
$\bar\xi_1,\dots,\bar\xi_n$ and $\e_1,\dots,\e_n$ are independent.
Define the random variables $S_n(f)=\frac1{\sqrt n}\summ_{j=1}^n
f(\xi_j)$ and $\bar S_n(f)=\frac1{\sqrt n}\summ_{j=1}^n f(\bar\xi_j)$
for all $f\in\Cal F$. The inequality
$$
P\(\sup_{f\in\Cal F}|S_n(f)|> A\sqrt n\sigma^2\)\le
2P\(\sup_{f\in\Cal F}|S_n(f)-\bar S_n(f)|> \frac23 A\sqrt
n\sigma^2\). \tag7.3
$$
follows from Lemma~7.1 if it is applied for the countable set of
random variables $Z_n(f)=S_n(f)$ and $\bar Z_n(f)=\bar S_n(f)$,
$f\in\Cal F$, and the numbers $u=\frac23 A\sqrt n\sigma^2$ and
$\alpha=\frac13A\sqrt n\sigma^2$, since the random fields $S_n(f)$
and $\bar S_n(f)$ are independent, and
$P(|\bar S_n(f)|\le\alpha)>\frac12$ for all $f\in\Cal F$. Indeed,
$\alpha=\frac13 A\sqrt n\sigma^2\ge\sqrt2\sigma$, $E\bar S_n(f)^2
\le\sigma^2$, thus Chebishev's inequality implies that
$P(|\bar S_n(f)|\le\alpha)\ge P(|\bar S_n(f)|\le\sqrt2\sigma)
\ge\frac12$ for all $f\in\Cal F$.

Let us observe that the random field
$$
S_n(f)-\bar S_n(f)=\frac1{\sqrt n}\sum_{j=1}^n \(f(\xi_j)
-f(\bar\xi_j)\), \quad f\in \Cal F,  \tag7.4
$$
and its randomization
$$
\frac1{\sqrt n}\sum_{j=1}^n \e_j \(f(\xi_j)
-f(\bar\xi_j)\), \quad f\in \Cal F,  \tag$7.4'$
$$
have the same distribution. Indeed, even the conditional distribution
of ($7.4'$) under the condition that the values of the $\e_j$-s are
prescribed agrees with the distribution of (7.4) for all possible
values of the $\e_j$-s. This follows from the observation that the
distribution of the random field~(7.4) does not change if we exchange
the random variables $\xi_j$ and $\bar\xi_j$ for those indices $j$
for which $\e_j=-1$ and do not change them for those indices~$j$ for
which $\e_j=1$. On the other hand, the distribution of the random
field obtained in such a way agrees with the conditional distribution
of the random field defined in ($7.4'$) under the condition that the
values of the random variables $\e_j$ are prescribed.

The above relation together with formula (7.3) imply that
$$ \allowdisplaybreaks
\align
&P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
f(\xi_j)\right|  \ge A n^{1/2}\sigma^{2}\)\\
&\qquad \le 2P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
\e_j\[f(\xi_j)-\bar f(\xi_j)\]\right| \ge\frac23 A
n^{1/2}\sigma^{2}\) \\
&\qquad\le 2P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge\frac A3 n^{1/2}\sigma^{2}\) \\
&\qquad\qquad+ 2P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|
\summ_{j=1}^n \e_jf(\bar\xi_j)\right|
\ge\frac A3n^{1/2}\sigma^{2}\) \\
&\qquad=4P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge\frac A3n^{1/2}\sigma^{2}\).
\endalign
$$
Lemma~7.2 is proved.

\medskip
Let me briefly explain the method of proof of Proposition~6.2.
A probability of the form
$P\(n^{-1/2}\supp_{f\in\Cal F}\left|\summ_{j=1}^nf(\xi_j)\right|>u\)$
has to be estimated. Lemma~7.2 enables us to replace this problem
by the estimation of the probability
$P\(n^{-1/2}\supp_{f\in\Cal F}\left| \summ_{j=1}^n
\e_jf(\xi_j)\right|>\frac u3\)$ with some independent random
variables $\e_j$, $P(\e_j=1)=P(\e_j=-1)=\frac12$, $j=1,\dots,n$,
which are also independent of the random variables $\xi_j$. We
shall bound the conditional probability of the event appearing in
this modified problem under the condition that the values of the
random variables $\xi_j$ have prescribed values. This can be done
with the help of Hoeffding's inequality formulated in Theorem~3.4
and the $L_2$-density property of the class of functions $\Cal F$
we consider. We hope to get a sharp estimate in such a way which
is similar to the result we got in the study of the Gaussian
counterpart of this problem, because Hoeffding's inequality yields
always a Gaussian type upper bound for the tail distribution of
the random sum we are studying.

Nevertheless, there appears a problem when we try to apply such an
approach. To get a good estimate on the conditional tail distribution
of the supremum of the random sums we are studying with the help of
Hoeffding's inequality we need a good estimate on the conditional
variances of the random sums we are studying, i.e. on the tail
distribution of $\supp_{f\in\Cal F}\frac1n\summ_{j=1}^n f^2(\xi_j)$.
This problem is similar to the original one, and it is not simpler.

But a more detailed study shows that our approach to get a good
estimate with the help of Hoeffding's inequality works. In
comparing our original problem with the new, complementary problem
we have to understand at which level we need a good estimate on the
tail distribution of the supremum in the complementary problem to
get a good tail distribution estimate at level~$u$ in the original
problem. A detailed study shows that to bound the probability in
the original problem with parameter~$u$ we have to estimate the
probability $P\(n^{-1/2}\supp_{f\in\Cal F'}\left|\summ_{j=1}^n
f(\xi_j)\right|>u^{1+\alpha}\)$ with some new nice, appropriately
defined $L_2$-dense class of bounded functions $\Cal F'$  and some
number $\alpha>0$. We shall exploit that the  number~$u$ is
replaced by a larger number $u^{1+\alpha}$ in the new problem. Let
us also observe that if the sum of bounded random variables is
considered, then for very large values~$u$ the probability we
investigate equals zero. On the basis of these observations an
appropriate backward induction procedure can be worked out. In its
$n$-th step we give a good upper bound on the probability
$P\(n^{-1/2}\supp_{f\in\Cal F}\left|\summ_{j=1}^nf(\xi_j)\right|>u\)$
if $u\ge T_n$ with an appropriately chosen number~$T_n$, and try 
to diminish the number~$T_n$ in each step of this induction 
procedure. We can prove Proposition~6.2 as a consequence of the 
result we get by means of this backward induction procedure. To 
work out the details we introduce the following notion.

\medskip\noindent
{\bf Definition of good tail behaviour for a class of normalized
random sums.}
{\it Let us have some measurable space $(X,\Cal X)$ and a
probability measure $\mu$ on it together with some integer $n\ge2$
and real number $\sigma>0$. Consider some class $\Cal F$ of
functions $f(x)$ on the space $(X,\Cal X)$, and take a sequence of
independent and $\mu$ distributed random variables $\xi_1,\dots,\xi_n$
with values in the space $(X,\Cal X)$. Define the normalized random
sums $S_n(f)=\frac1{\sqrt n}\sum\limits_{j=1}^nf(\xi_j)$, $f\in \Cal F$.
Given some real number $T>0$ we say that the set of normalized
random sums $S_n(f)$, $f\in\Cal F$,
has a good tail behaviour at level~$T$ (with parameters $n$ and
$\sigma^2$ which will be fixed in the sequel) if the inequality
$$
P\(\sup_{f\in\Cal F}|S_n(f)|\ge A \sqrt n\sigma^2\) \le
\exp\left\{-A^{1/2}n\sigma^2 \right\} \tag7.5
$$
holds for all numbers $A>T$.}

\medskip
Now I formulate Proposition 7.3 and show that Proposition 6.2
follows from it.

\medskip\noindent
{\bf Proposition 7.3.} {\it Let us fix a positive integer~$n\ge2$,
a real number $0<\sigma\le1$ and a probability measure $\mu$ on a
measurable space $(X,\Cal X)$ together with some numbers $L\ge1$
and $D\ge1$ such that $n\sigma^2\ge L\log n+\log D$. Let us
consider those countable $L_2$-dense classes $\Cal F$ of functions
$f=f(x)$ on the space $(X,\Cal X)$ with exponent~$L$ and
parameter~$D$ for which all functions $f\in\Cal F$ satisfy the
conditions $\supp_{x\in X}|f(x)|\le\frac14$, $\int f(x)\mu(\,dx)=0$
and $\int f^2(x)\mu(\,dx)\le\sigma^2$.

Let a number $T>1$ be such that for all classes of functions
$\Cal F$ which satisfy the above conditions the set of normalized
random sums $S_n(f)=\frac1{\sqrt n}\summ_{j=1}^n f(\xi_j)$,
$f\in\Cal F$, defined with the help of a sequence of independent
$\mu$ distributed random variables $\xi_1,\dots,\xi_n$ have a good
tail behaviour at level~$T^{4/3}$. There is a universal
constant~$\bar A_0$ such that if $T\ge\bar A_0$, then the set of the
above defined normalized sums, $S_n(f)$, $f\in\Cal F$, have a good
tail behaviour for all such classes of functions $\Cal F$ not only at
level $T^{4/3}$ but also at level~$T$.}

\medskip
Proposition~6.2 simply follows from Proposition~7.3. To show this
let us first observe that a class of normalized random sums
$S_n(f)$, $f\in\Cal F$, has a good tail behaviour at level
$T_0=\frac1{4\sigma^2}$ if this class of functions $\Cal F$
satisfies the conditions of Proposition~7.3. Indeed, in this
case $P\(\supp_{f\in\Cal F}|S_n(f)|\ge A\sqrt n\sigma^2\)
\le P\(\supp_{f\in\Cal F}|S_n(f)|>\frac{\sqrt n}4\)=0$ for all
$A>T_0$. Then the repetitive application of Proposition~7.3 yields
that a class of random sums $S_n(f)$, $f\in\Cal F$, has a good tail
behaviour at all  levels $T\ge T_0^{(3/4)^j}$ with an index~$j$ such
that $T_0^{(3/4)^j}\ge\bar A_0$ if the class of functions $\Cal F$
satisfies the conditions of Proposition~7.3. Hence it has a good
tail behaviour for $T=\bar A_0^{4/3}$. If a class of functions
$f\in\Cal F$ satisfies the conditions of Proposition~6.2, then
the class of functions $\bar{\Cal F}=\left\{\bar f=\frac f4\colon\;
f\in\Cal F\right\}$ satisfies the conditions of Proposition~7.3,
with the same parameters~$\sigma$, $L$ and~$D$. (Actually some of
the inequalities that must hold for the elements of a class of
functions~$\Cal F$ satisfying the conditions of Proposition~7.3
are valid with smaller parameters. But we did not change these
parameters to satisfy also the condition
$n\sigma^2\ge L\log n+\log D$.) Hence the class of functions
$S_n(\bar f)$, $\bar f\in \bar{\Cal F}$, has a good tail
behaviour at level $T=\bar A_0^{4/3}$. This implies that the
original class of functions $\Cal F$ satisfies formula~(6.4) in
Proposition~6.2, and this is what we had to show.

\medskip\noindent
{\it Proof of Proposition 7.3.}\/ Fix a class of functions
$\Cal F$ which satisfies the conditions of Proposition~7.3 together
with two independent sequences $\xi_1,\dots,\xi_n$ and
$\e_1,\dots,\e_n$ of independent random variables, where $\xi_j$ is
$\mu$-distributed,
$P(\e_j=1)=P(\e_j=-1)=\frac12$, $1\le j\le n$, and investigate the
conditional probability
$$
P(f,A|\xi_1,\dots,\xi_n)=P\(\left.\frac1{\sqrt n}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge
\frac A6\sqrt n\sigma^2\right|\xi_1,\dots,\xi_n\)
$$
for all functions $f\in\Cal F$, $A> T$ and values
$(\xi_1,\dots,\xi_n)$ in the condition. By the Hoeffding inequality
formulated in Theorem~3.4
$$
P(f,A|\xi_1,\dots,\xi_n)\le 2\exp\left\{-\frac{\frac 1{36}
A^2 n\sigma^4}{2\bar S^2(f,\xi_1,\dots,\xi_n)}\right\} \tag7.6
$$
with
$$
\bar S^2(f,x_1,\dots,x_n)=\frac1n\sum_{j=1}^n f^2(x_j), \quad f\in \Cal
F.
$$
Let us introduce the set
$$
H=H(A)=\left\{(x_1,\dots,x_n)\colon\; \sup_{f\in\Cal F}
\bar S^2(f,x_1,\dots,x_n)\ge \(1+A^{4/3}\)\sigma^2\right\}. \tag7.7
$$
I claim that
$$
P((\xi_1,\dots,\xi_n)\in H)\le e^{-A^{2/3} n\sigma^2}\quad\text{ if }
A>T. \tag7.8
$$
(The set $H$ plays the role of the small exceptional set, where we
cannot provide a good estimate for $P(f,A|\xi_1,\dots,\xi_n)$ for some
$f\in\Cal F$.)

To prove relation (7.8) let us consider the functions $\bar f=\bar
f(f)$, $\bar f(x)=f^2(x)-\int f^2(x)\mu(\,dx)$, and introduce the
class of functions $\bar{\Cal F}=\{\bar f(f)\colon\; f\in\Cal F\}$.
Let us show that the class of functions $\bar{\Cal F}$ satisfies the
conditions of Proposition~7.3, hence the estimate (7.5) holds for
the class of functions $\bar{\Cal F}$ if $A> T^{4/3}$.

The relation $\int \bar f(x)\mu(\,dx)=0$ clearly holds. The condition
$\sup| \bar f(x)|\le\frac 18<\frac14$ also holds if $\sup |f(x)|\le
\frac14$, and $\int \bar f^2(x)\mu(\,dx)\le \int f^4(x)\mu(\,dx)\le
\frac 1{16}\int f^2(x)\,\mu(\,dx)\le\frac{\sigma^2}{16}<\sigma^2$
if $f\in\Cal F$. It remained to show that $\bar{\Cal F}$ is an
$L_2$-dense class with exponent $L$ and parameter $D$. For this goal
we need a good estimate on $\int(\bar f(x)-\bar g(x))^2\rho(\,dx)$,
where $\bar f,\,\bar g\in\bar{\Cal F}$, and $\rho$ is an arbitrary
probability measure.

Observe that $\int (\bar f(x)-\bar g(x))^2\rho(\,dx)\le
2\int(f^2(x)-g^2(x))^2\rho(\,dx)+
2\int(f^2(x)-g^2(x))^2\mu(\,dx)\le2 (\supp (|f(x)|+|g(x)|)^2
\(\int (f(x)-g(x))^2(\rho(\,dx)+\mu(\,dx)\)\le  \int
(f(x)-g(x))^2\bar\rho(\,dx)$ for all $f, g\in\Cal F$, $\bar f=\bar
f(f)$, $\bar g=\bar g(g)$ and probability measure $\rho$, where
$\bar\rho=\frac{\rho+\mu}2$. This means that if $\{f_1,\dots,f_m\}$
is an $\e$-dense subset of $\Cal F$ in the space $L_2(X,\Cal
X,\bar\rho)$, then $\{\bar f_1,\dots,\bar f_m\}$ is an $\e$-dense
subset of $\bar{\Cal F}$ in the space $L_2(X,\Cal X,\rho)$, and
not only $\Cal F$, but also $\bar{\Cal F}$ is an $L_2$-dense class
with exponent $L$ and parameter $D$.

An application of the conditions of Proposition 7.3 for the
number $A^{4/3}> T^{4/3}$ and the class of functions
$\bar{\Cal F}$ yields that
$$
\align
P((\xi_1,\dots,\xi_n)\in H)&=P\(\sup_{f\in\Cal F} \(\frac1n \sum_{j=1}^n
\bar f(f)(\xi_j) +\frac1n \sum_{j=1}^n E f^2(\xi_j)\)
\ge \(1+A^{4/3}\)\sigma^2\)\\
&\le P\(\sup_{\bar f\in\bar {\Cal F}} \frac1{\sqrt n} \sum_{j=1}^n
\bar f(\xi_j) \ge A^{4/3}n^{1/2}\sigma^2\) \le e^{-A^{2/3} n\sigma^2},
\endalign
$$
i.e. relation (7.8) holds.

By formula (7.6) and the definition of the set $H$ given in (7.7)
the estimate
$$
P(f,A|\xi_1,\dots,\xi_n)\le 2e^{- A^{2/3} n\sigma^2/144} \quad
\text{if }(\xi_1,\dots,\xi_n)\notin H
\tag7.9
$$
holds for all $f\in \Cal F$ and $A>T\ge1$. (Here we used the
estimate $1+A^{4/3}\le2A^{4/3}$.) Let us introduce the conditional
probability
$$
P(\Cal F,A|\xi_1,\dots,\xi_n)=
P\(\left.\sup_{f\in \Cal F} \frac1{\sqrt n}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge \frac
A3\sqrt n\sigma^2\right|\xi_1,\dots,\xi_n\)
$$
for all $(\xi_1,\dots,\xi_n)$ and $A>T$. We shall
estimate this conditional probability with the help of relation~(7.9)
if $(\xi_1,\dots,\xi_n) \notin H$.

Given a vector $x^{(n)}=(x_1,\dots,x_n)\in X^n$, let us introduce
the measure $\nu=\nu(x_1,\dots,x_n)=\nu(x^{(n)})$ on $(X,\Cal X)$
which is concentrated in the coordinates of the vector
$x^{(n)}=(x_1,\dots,x_n)$, and $\nu(\{x_j\})=\frac1n$ for all
points~$x_j$, $j=1,\dots,n$. If $\int f^2(u)\nu(\,du)\le\delta^2$
for a function $f$, then
$\left|\frac1{\sqrt n}\summ_{j=1}^n\e_jf(x_j)\right|
\le n^{1/2}\int|f(u)|\nu(\,du)\le n^{1/2}\delta$. As a
consequence, we can write that
$$
\left|\frac1{\sqrt n}\summ_{j=1}^n\e_jf(x_j)-
\frac1{\sqrt n}\summ_{j=1}^n \e_jg(x_j)\right|
\le\frac A6 \sqrt n\sigma^2 \quad\text{if }
\int (f(u)-g(u))^2\,d\nu(u)\le\(\frac {A\sigma^2}6\)^2. \tag7.10
$$

Let us list the elements of the (countable) set $\Cal F$ as
$\Cal F=\{f_1,f_2,\dots\}$, fix a number $\delta=\frac{A\sigma^2}6$,
and choose for all vectors $x^{(n)}=(x_1,\dots,x_n)\in X^n$ a
sequence of indices $p_1(x^{(n)}),\dots,p_m(x^{(n)})$ taking
positive integer values with
$m=\max(1, D\delta^{-L})=\max(1,D(\frac6{A\sigma^2})^L)$
elements in such a way that $\inf\limits_{1\le l\le m}
\int(f(u)-f_{p_l(x^{(n)})}(u))^2\,d\nu(x^{(n)})(u)\le\delta^2$
for all $f\in\Cal F$ and $x^{(n)}\in X^n$ with the above defined 
measure $\nu(x^{(n)})$ on the space $(X,\Cal X)$. This is possible 
because of the $L_2$-dense property of the class of 
functions~$\Cal F$. (This is the point where the $L_2$-dense 
property of the class of functions $\Cal F$ is exploited in its 
full strength.) In a complete proof of Theorem~7.3 we still have 
to show that we can choose the indices $p_j(x^{(n)})$, 
$1\le j\le m$, as measurable functions of their argument~$x^{(n)}$ 
on the space $(X^n,\Cal X^n)$. We shall show this in Lemma~7.4 at 
the end of the proof.

Put $\xi^{(n)}(\oo)=(\xi_1(\oo),\dots,\xi_n(\oo))$. Because of
relation~(7.10), the choice of the number $\delta$ and the property
of the functions $f_{p_l(x^{(n)})}(\cdot)$ we have
$$
\align
&\left\{\oo\colon\;\sup_{f\in\Cal F}
\frac1{\sqrt n}\left|\summ_{j=1}^n \e_j(\oo)f(\xi_j(\oo))\right|
\ge\frac A3\sqrt n\sigma^2\right\} \\
&\qquad \subset\bigcup_{l=1}^m\left\{\oo\colon\;\frac1{\sqrt n}
\left|\summ_{j=1}^n \e_j(\oo)f_{p_l(\xi^{(n)}(\oo))}
(\xi_j(\oo))\right|\ge\frac A6\sqrt n\sigma^2\right\}.
\endalign
$$
This relation together with inequality~(7.9) yield that
$$
\align
P(\Cal F,A|\xi_1,\dots,\xi_n)&
\le\summ_{l=1}^m P(f_{p_l(\xi^{(n)})},A|\xi_1,\dots,\xi_n)\\
&\le 2\max\(1,D\(\frac 6{A\sigma^2}\)^L\)
e^{-A^{2/3} n\sigma^2/144} \\
&\qquad \text{if }(\xi_1,\dots,\xi_n)\notin H \text{ and } A> T.
\endalign
$$
If $A\ge\bar A_0$ with a sufficiently large constant~$\bar A_0$,
then this inequality together with Lemma~7.2 and the estimate~(7.8)
imply that
$$
\aligned
&P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
f(\xi_j)\right| \ge A n^{1/2}\sigma^{2}\)
\le 4P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
\e_jf(\xi_j)\right| \ge \frac A3 n^{1/2}\sigma^{2}\)\\
&\qquad \le\max\(4, 8D\(\frac6{A\sigma^2}\)^L\)e^{-A^{2/3}n\sigma^2/144}
+4e^{-A^{2/3}n\sigma^2} \quad \text{if } A>T.
\endaligned \tag7.11
$$
By the conditions of Proposition~7.3 the inequalities
$n\sigma^2\ge L\log n +\log D$ hold with some $L\ge1$, $D\ge1$ 
and $n\ge2$. This implies that $n\sigma^2\ge L\log2\ge\frac12$,
$(\frac6{A\sigma^2})^L\le(\frac n{2n\sigma^2})^L\le n^L=e^{L\log n}
\le e^{n\sigma^2}$ if $A\ge\bar A_0$ with some sufficiently large
constant $\bar A_0>0$, and $2D=e^{\log2+\log D}\le e^{3n\sigma^2}$.
Hence the first term at the right-hand side of (7.11) can be
bounded by
$$
\max\(4,8D\(\frac6{A\sigma^2}\)^L\)e^{-A^{2/3}n\sigma^2/144}
\le e^{-A^{2/3}n\sigma^2/144}\cdot 4e^{4n\sigma^2}
\le \frac12e^{-A^{1/2}n\sigma^2}
$$
if $A\ge\bar A_0$ with a sufficiently large~$\bar A_0$. The
second term at the right-hand side of~(7.11) can also be bounded
as $4e^{-A^{2/3}n\sigma^2}\le \frac12e^{-A^{1/2}n\sigma^2}$
with an appropriate choice of the number~$\bar A_0$.

By the above calculation formula (7.11) yields the inequality
$$
P\(\frac1{\sqrt n}\supp_{f\in\Cal F}\left|\summ_{j=1}^n
f(\xi_j)\right| \ge An^{1/2}\sigma^{2}\) \le e^{-A^{1/2}n\sigma^2}
$$
if $A>T$, and the constant~$\bar A_0$ is chosen sufficiently large.

\medskip
To complete the proof of Proposition~7.3 we still prove the 
following Lemma~7.4 together with some of its generalizations 
needed in the proof of Propositions~15.3 and~15.4. The latter
results are those multivariate versions of Proposition~7.3 that
we need in the proof of the multivariate version of Proposition~6.2.
We formulated them not in their most general possible form, 
but in the way as we need them in this work.

\medskip\noindent
{\bf Lemma~7.4.} {\it Let $\Cal F=\{f_1,f_2,\dots\}$ be a countable
and $L_2$-dense class of functions with some exponent $L>0$ and
parameter~$D\ge1$ on a measurable space $(X,\Cal X)$. Fix some
positive integer~$n$, and define for all
$x^{(n)}=(x_1,\dots,x_n)\in X^n$ the probability measure
$\nu(x^{(n)})=\nu(x_1,\dots,x_n)$ on the space $(X,\Cal X)$ by 
the formula $\nu(x^{(n)})(x_j)=\frac1n$, $1\le j\le n$. For a 
number $0\le\e\le 1$ put $m=m(\e)=[D\e^{-L}]$, where $[\cdot]$ 
denotes integer part. For all $0\le\e\le 1$ there exists $m=m(\e)$ 
measurable functions $p_l(x^{(n)})$, $1\le l\le m$, on the 
measurable space $(X^n,\Cal X^n)$ with positive integer values in 
such a way that $\inf\limits_{1\le l\le m}
\int(f(u)-f_{p_l(x^{(n)})}(u))^2\nu(x^{(n)})(\,du)\le\e^2$ for all
$x^{(n)}\in X^n$ and $f\in\Cal F$.

In the proof of Proposition~15.3 we need the following result.
Let $\Cal F=\{f_1,f_2,\dots\}$ be a countable and $L_2$-dense class
of functions with some exponent $L>0$ and parameter~$D\ge1$ on the
$k$-fold product $(X^k,\Cal X^k)$ of a measurable space $(X,\Cal X)$
with some $k\ge1$. Fix some positive integer~$n$, and define for all
vectors $x^{(n)}=(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)\in X^{kn}$,
where $x^{(j)}_l\in X$ for all $j$ and $l$ the probability measure
$\rho(x^{(n)})$ on the space $(X^k,\Cal X^k)$ by the formula
$\rho(x^{(n)})(x_{l_j}^{(j)},\,1\le j\le k,\,1\le l_j\le n)
=\frac1{n^k}$ for all sequences
$(x_{l_1}^{(1)},\dots,x_{l_k}^{(k)})$ , $1\le j\le k$, $1\le l_j\le n$,
with coordinates of the elements of the vector
$x^{(n)}=(x_l^{(j)},1\le l\le n,\,1\le j\le k)$. For all $0\le\e\le 1$
there exist $m=m(\e)=[D\e^{-L}]$ measurable functions $p_r(x^{(n)})$,
$1\le r\le m$, on the measurable space $(X^{kn},\Cal X^{kn})$ with
positive integer values in such a way that $\inf\limits_{1\le r\le m}
\int(f(u)-f_{p_r(x^{(n)})}(u))^2\rho(x^{(n)})(\,du)\le\e^2$ for all
$x^{(n)}\in X^{kn}$ and $f\in\Cal F$.

In the proof of Proposition~15.4 we need the following result.
Let $\Cal F=\{f_1,f_2,\dots\}$ be a countable and $L_2$-dense class
of functions with some exponent $L>0$ and parameter~$D\ge1$ on the
product space $(X^k\times Y,\Cal X^k\times\Cal Y)$ with some
measurable spaces $(X,\Cal X)$ and $(Y,\Cal Y)$ and integer~$k\ge1$.
Fix some positive integer~$n$, and define for all vectors
$x^{(n)}=(x_l^{(j,1)},x_l^{(j,-1)},\,1\le l\le n,\,1\le j\le k)\in X^{2kn}$,
where $x^{(j,\pm1)}_l\in X$ for all $j$ and $l$ a probability measure
$\alpha(x^{(n)})$ in the space $(X^k\times Y,\Cal X^k\times\Cal Y)$  
in the following way. Fix some probability measure
$\rho$ on the space $(Y,\Cal Y)$ and two $\pm1$ sequences
$\e^{(k)}_1=(\e_{1,1},\dots,\e_{k,1})$ and
$\e^{(k)}_2=(\e_{1,2},\dots,\e_{k,2})$ of length~$k$. Define with
their help first the following probability measures
$\alpha_1(x^{(n)})=\alpha_1(x^{(n)},\e^{(k)}_1,\e^{(k)}_2,\rho)$
and $\alpha_2(x^{(n)})=\alpha_2(x^{(n)},\e^{(k)}_1,\e^{(k)}_2,\rho)$
on $(X^k\times Y,\Cal X^k\times\Cal Y)$ for all
$x^{(n)}\in\Cal X^{2kn}$. Let
$\alpha_1(x^{(n)})(\{x_{l_1}^{(1,\e_{1,1})}\}\times\cdots\times
\{x_{l_k}^{(k,\e_{k,1})}\}\times B)=\frac{\rho(B)}{n^k}$ and
$\alpha_2(x^{(n)})(\{x_{l_1}^{(1,\e_{1,2})}\}\times\cdots\times
\{x_{l_k}^{(k,\e_{k,2})}\}\times B)=\frac{\rho(B)}{n^k}$ with
$1\le l_j\le n$ for all $1\le j\le k$ and $B\in\Cal Y$ if
$x_{l_j}^{(j,\e_{j,1})}$ and $x_{l_j}^{(j,\e_{j,2})}$
are the appropriate coordinates of the vector $x^{(n)}\in X^{2kn}$.
Put $\alpha(x^{(n)})=\frac{\alpha_1(x^{(n)})+\alpha_2(x^{(n)})}2$.
For all $0\le\e\le 1$ there exist $m=m(\e)=[D\e^{-L}]$ measurable
functions $p_r(x^{(n)})$, $1\le r\le m$, on the measurable space
$(X^{2kn},\Cal X^{2kn})$ with positive integer values in such a way
that $\inf\limits_{1\le r\le m}\int(f(u)-f_{p_r(x^{(n)})}(u))^2
\alpha(x^{(n)})(\,du)\le\e^2$
for all $x^{(n)}\in X^{2kn}$ and $f\in\Cal F$.}

\medskip\noindent
{\it Proof of Lemma 7.4.}\/ Fix some $0<\e\le 1$, put the number
$m=m(\e)$ introduced in the lemma, and let us list the set of all
vectors $(j_1,\dots,j_m)$ of length~$m$ with positive integer
coordinates in some way. Define for all of these vectors
$(j_1,\dots,j_m)$ the set $B(j_1,\dots,j_m)\subset X^n$ in the
following way. We have $x^{(n)}=(x_1,\dots,x_n)\in B(j_1,\dots,j_m)$
if and only if $\inf\limits_{1\le r\le m}
\int (f(u)-f_{j_r}(u))^2\,d\nu(x^{(n)})(u)\le\e^2$ for all
$f\in\Cal F$. Then all sets $B(j_1,\dots,j_m)$ are measurable, and
$\bigcupp_{(j_1,\dots,j_m)}B(j_1,\dots,j_m)=X^n$ because $\Cal F$
is an $L_2$-dense class of functions with exponent~$L$ and
parameter~$D$. Given a point $x^{(n)}=(x_1,\dots,x_n)$ let us choose
the first vector $(j_1,\dots,j_m)=(j_1(x^{(n)}),\dots,j_m(x^{(n)}))$
in our list of vectors for which $x^{(n)}\in B(j_1,\dots,j_m)$, and
define $p_l(x^{(n)})=j_l(x^{(n)})$ for all $1\le l\le m$ with this 
vector $(j_1,\dots,j_m)$. Then the functions $p_l(x^{(n)})$ are 
measurable, and the functions $f_{p_l(x^{(n)})}$, $1\le l\le m$, 
defined with their help together with the probability measures
$\nu(x^{(n)})$ satisfy the inequality demanded in the first 
statement of Lemma~7.4.

The proof of the remaining two statements is almost the same. We
only have to modify the definition of the sets $B(j_1,\dots,j_m)$
in a natural way. The space of arguments $x^{(n)}$ are the spaces
$X^{kn}$ and $X^{2kn}$ in these two cases, and we have to integrate
with respect to the measures $\rho(x^{(n)})$ in the space $X^k$ and
with respect to the measures $\alpha(x^{(n)})$ in the space
$X^k\times Y$ respectively. The sets $B(j_1,\dots,j_m)$ are
measurable also in these cases, and the rest of the proof can be
applied without any change.
