\beginsection 16. A symmetrization argument.

The proof of Propositions~15.3 and 15.4 applies some ideas similar
to the argument in the proof of Proposition~7.3. But here some
additional technical difficulties have to be overcome. As a first
step, two results formulated in Lemma~16.1A and~16.1B will be proved.
They can be considered as a randomization argument with the help of
Rademacher functions analogous to the application of Lemma~7.2 in
the proof of Propositions~7.3. Lemma~16.1A will be applied in the
proof of Proposition~15.3 and Lemma~16.1B in the proof of
Proposition~15.4. In this section these lemmas will be proved. Their
proofs will be based on some additional lemmas formulated in
Lemmas~16.2A, 16.2B, 16.3A and~16.3B. By exploiting the structure
of Propositions~15.3 and~15.4 we may assume when proving them for
parameter~$k$ that they hold (together with their consequences)
for all parameters $k'<k$.

Lemma~16.1A is a natural multivariate version of Lemma~7.2. Lemma~7.2
enables us to replace the estimation of the distribution
of the supremum of a class of sums of independent random variables
with the estimation of the distribution of the supremum of the
randomized version of these sums. Lemma~16.1A will enable us to
reduce the proof of Proposition~15.3 to the estimation of the
tail-distribution of the supremum of an appropriately defined class
of randomized degenerate $U$-statistics. This supremum will be
estimated by means of the multi-dimensional version of
Hoeff\-ding's inequality given in Theorem~13.3. Lemma~16.B plays
a similar role in the proof of Proposition~15.4. But its application
is more difficult. In this result the probability investigated in
Proposition~15.4 is bounded by the distribution of the supremum of
some random variables $\bar W(f)$, $f\in\Cal F$, which will be
defined in formula~(16.7). The expressions $\bar W(f)$,
$f\in\Cal F$, are rather complicated, and they are worth studying
more closely. This will be done in the proof of Corollary of
Lemma~16.1B which yields a more appropriate bound for the
expression we want to estimate in Proposition~15.4, than
Lemma~16.1B. In the proof of Proposition~15.4 the Corollary
of~16.1B will be applied instead of the original lemma.

The proof of Lemmas~16.1A and~16.1B is similar to that of
Lemma~7.2. First we introduce $k$ additional independent
copies $\bar\xi^{(j)}_1,\dots,\bar\xi^{(j)}_n$ beside the $k$
(independent and identically distributed) copies
$\xi^{(j)}_1,\dots,\xi^{(j)}_n$, $1\le j\le k$, of the sequence
$\xi_1,\dots,\xi_n$ and construct with their help some appropriate
random sums. We shall prove in Lemmas~16.2A and~16.2B that these
random sums have the same distribution as their randomized
versions we shall work with in the proof of Lemmas~16.1A and~16.1B.
These Lemmas formulate a natural multivariate version of an
importantant argument in the proof of Lemma~7.2. In the proof of
this lemma we have exploited that the random sums defined in~(7.4)
have the same joint distribution as their randomized versions
defined in~$(7.4')$. Lemmas~16.2A and~16.2B formulate a
multivariate version of this statement. They enable us (similarly
to the corresponding argument in the proof of Lemma~7.2) to reduce
the proof of Propositions~16.1A and~16.1B to the study of some
simpler questions. This will be done with the help of Lemmas~16.3A
and~16.3B. In Lemma~16.3A the supremum of some conditional
variances is estimated under appropriate conditions. This lemma
plays a similar role in the proof of Lemma~16.1A as condition~(7.1)
plays in the proof of Lemma~7.1. Its result together with
the generalized form of the symmetrization Lemma, Lemma~15.2,
enable us to prove Lemma~16.1A. Lemma~16.1B can be proved
similarly, but here the conditional distribution of a more
complicated expression has to be estimated. This can be done with
the help of Lemma~16.3B. In Lemma~16.3B the supremum of the
conditional expectation of some appropriate expressions is
bounded.

The main results of this section are the following two lemmas.

\medskip\noindent
{\bf Lemma 16.1A. (Randomization argument in the proof of
Proposition~15.3).} {\it Let $\Cal F$ be a class of functions on
the space $(X^k,\Cal X^k)$ which satisfies the conditions of
Proposition~15.3 with some probability measure $\mu$. Let us have $k$
independent copies $\xi_1^{(j)},\dots,\xi_n^{(j)}$, $1\le j\le k$, of
a sequence of independent $\mu$ distributed random variables
$\xi_1,\dots,\xi_n$, and a sequence of independent random variables
$\e=(\e_1,\dots,\e_n)$, $P(\e_l=1)=P(\e_l=-1)=\frac12$, $1\le l\le n$,
which is independent also of the random sequences
$\xi_1^{(j)},\dots,\xi_n^{(j)}$, $1\le j\le k$. Consider the
decoupled $U$-statistics $\bar I_{n,k}(f)$, $f\in\Cal F$, defined
with the help of these random variables by formula~(14.11) together
with their randomized version $\bar I_{n,k}^\e(f)$ defined in
formula~(14.12).

There exists some constants $A_0=A_0(k)>0$ and $\gamma=\gamma_k>0$
such that the inequality
$$
\aligned
P\(\sup_{f\in\Cal F} n^{-k/2}\left|\bar
I_{n,k}(f)\right|>An^{k/2}\sigma^{k+1}\)&<
2^{k+1}P\(\sup_{f\in\Cal F} \left|\bar I_{n,k}^{\e}(f)\right|
>2^{-(k+1)}A n^k\sigma^{k+1}\)\\
&\qquad+2^kn^{k-1}e^{-\gamma_k A^{1/(2k-1)} n\sigma^2/k}
\endaligned \tag16.1
$$
holds for all $A\ge A_0$.}

\medskip
It may be worth remarking that the second term at the right-hand side
of formula~(16.1) yields a small contribution to the upper bound in
this relation because of the condition $n\sigma^2\ge L\log n+\log D$.

To formulate Lemma~16.1B first some new quantities have to be
introduced. Some of them will be used somewhat later. The quantities
$\bar I_{n,k}^V(f,y)$ introduced in the subsequent formula~(16.2)
depend on the sets $V\subset\{1,\dots,k\}$, and they are the
natural modifications of the inner sum terms in formula (15.1).
Such expressions are needed in the formulation of the
symmetrization result applied in the proof of Proposition~15.4.
Their randomized versions $\bar I_{n,k}^{(V,\e)}(f,y)$, introduced
in formula (16.5), correspond to the inner sum terms in
formula~(15.2). The integrals of these expressions will be also
introduced in formulas~(16.3) and~(16.6).

Let us consider a class $\Cal F$ of functions
$f(x_1,\dots,x_k,y)\in \Cal F$ on a space $(X^k\times Y, \Cal X^k
\times \Cal Y,\mu^k\times\rho)$ which satisfies the conditions of
Proposition~15.4. Let us take $2k$ independent copies
$\xi_1^{(j)},\dots,\xi_n^{(j)}$,
$\bar\xi_1^{(j)},\dots,\bar\xi_n^{(j)}$, $1\le j\le k$,
of a sequence of independent $\mu$ distributed random variables
$\xi_1,\dots,\xi_k$ together with a sequence of independent random
variables $(\e_1,\dots,\e_n)$, $P(\e_l=1)=P(\e_l=-1)=\frac12$, $1\le
l\le n$, which is also independent of the previous random sequences.
Let us introduce the notation $\xi_l^{(j,1)}=\xi_l^{(j)}$
and $\xi_l^{(j,-1)}=\bar\xi_l^{(j)}$, $1\le l\le n$, $1\le j\le k$.
For all subsets $V\subset\{1,\dots,k\}$ of the set
$\{1,\dots,k\}$ let $|V|$ denote the cardinality of this set,
and define for all functions $f(x_1,\dots,x_k,y)\in \Cal F$ and
$V\subset\{1,\dots,k\}$ the decoupled $U$-statistics
$$
\bar I_{n,k}^V(f,y)=\frac1{k!}\summ\Sb (l_1,\dots,l_k)\colon\;
1\le l_j\le n,\;j=1,\dots,k\\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb
f\(\xi_{l_1}^{(1,\delta_1(V))},\dots,\xi_{l_k}^{(k,\delta_k(V))},y\),
\tag16.2
$$
where $\delta_j(V)=\pm1$, $1\le j\le k$, $\delta_j(V)=1$ if $j\in V$,
and $\delta_j(V)=-1$ if $j\notin V$, together with the random variables
$$
H_{n,k}^V(f)=\int \bar I_{n,k}^V(f,y)^2\rho(\,dy), \quad f\in\Cal F.
\tag16.3
$$
We shall consider $\bar I_{n,k}^V(f,y)$ defined in~(16.2) as a random
variable with values in the space $L_2(Y,\Cal Y,\rho)$.

Put
$$
\bar I_{n,k}(f,y)=\bar I_{n,k}^{\{1,\dots,k\}}(f,y),\quad
H_{n,k}(f)=H_{n,k}^{\{1,\dots,k\}}(f), \tag16.4
$$
i.e. $\bar I_{n,k}(f,y)$ and $H_{n,k}(f)$ are the random
variables $\bar I_{n,k}^V(f,y)$ and $H_{n,k}^V(f)$ with
$V=\{1,\dots,k\}$ which means that these expressions are defined
with the help of the random variables $\xi^{(j)}_l=\xi_l^{(j,1)}$,
$1\le j\le k$, $1\le l\le n$.

Let us also define the `randomized version' of the random variables
$\bar I_{n,k}^V(f,y)$ and $H_{n,k}^V(f)$ as
$$
\bar I_{n,k}^{(V,\e)}(f,y)=\frac1{k!}\summ\Sb (l_1,\dots,l_k)\colon\;
1\le l_j\le n,\;
j=1,\dots, k\\ l_j\neq l_{j'} \text{ if } j\neq j'\endSb \!\!\!\!\!
\e_{l_1}\cdots\e_{l_k}f\(\xi_{l_1}^{(1,\delta_1(V))},\dots,
\xi_{l_k}^{(k,\delta_k(V))},y\),\quad f\in\Cal F, \tag16.5
$$
and
$$
H_{n,k}^{(V,\e)}(f)=\int \bar I_{n,k}^{(V,\e)}(f,y)^2\rho(\,dy)
,\quad f\in\Cal F, \tag16.6
$$
where $\delta_j(V)=1$ if $j\in V$, and $\delta_j(V)=-1$ if
$j\in\{1,\dots,k\}\setminus V$.
Similarly to formula~(16.2), we shall consider
$\bar I_{n,k}^{V,\e}(f,y)$ defined in~(16.5) as a random
variable with values in the space $L_2(Y,\Cal Y,\rho)$.

Let us also introduce the random variables
$$
\bar W(f)=\int\[\sum_{V\subset \{1,\dots,k\}} (-1)^{(k-|V|)}\bar
I_{n,k}^{(V,\e)}(f,y)\]^2\rho(\,dy), \quad f\in\Cal F. \tag16.7
$$
With the help of the above notations Lemma~16.1B can be formulated
in the following way.

\medskip\noindent
{\bf Lemma 16.1B. (Randomization argument in the proof of
Proposition~15.4).} {\it Let $\Cal F$ be a set of functions on
$(X^k\times Y,\Cal X^k\times\Cal Y)$ which satisfies the conditions
of Proposition~15.4 with some probability measure $\mu^k\times\rho$.
Let us have $2k$ independent copies
$\xi_{1}^{(j,\pm1)},\dots,\xi_{n}^{(j,\pm1)}$, $1\le j\le k$, of a
sequence of independent $\mu$ distributed random variables
$\xi_1,\dots,\xi_n$ together with a sequence of independent random
variables $\e_1,\dots,\e_n$, $P(\e_j=1)=P(\e_j=-1)=\frac12$, $1\le
j\le n$, which is independent also of the previously considered
sequences.

Then there exists some constants $A_0=A_0(k)>0$ and
$\gamma=\gamma_k$ such that if the integrals $H_{n,k}(f)$,
$f\in\Cal F$, determined by this class of functions $\Cal F$ have a
good tail behaviour at level $T^{(2k+1)/2k}$ for some $T\ge A_0$,
(this property was defined in Section~15 in the definition of good
tail behaviour for a class of integrals of decoupled $U$-statistics
before the formulation of Propositions~15.3 and~15.4), then the
inequality
$$
\aligned
P\(\sup_{f\in\Cal F} \left|H_{n,k}(f)\right|>A^2n^{2k}\sigma^{2(k+1)}\)
&<2P\(\sup_{f\in\Cal F} \left|\bar W(f)\right|
>\frac{A^2}2 n^{2k}\sigma^{2(k+1)}\)\\
&\qquad+2^{2k+1}n^{k-1}e^{-\gamma_k A^{1/2k} n\sigma^2/k}
\endaligned \tag16.8
$$
holds with the random variables $H_{n,k}(f)$ introduced in the
second identity of relation (16.4) and with $\bar W(f)$ defined in
formula (16.7) if $\gamma_k>0$ is a sufficiently small positive
number for all $A\ge T$ .}

\medskip
A corollary of Lemma~16.1B will be formulated which can be
better applied than the original lemma. Lemma~16.B is a little bit
inconvenient, because the expression at the right-hand side of
formula (16.8) contains a probability depending on
$\supp_{f\in\Cal F}|\bar W(f)|$, and $\bar W(f)$ is a too
complicated expression. Some new formulas~(16.9) and~(16.10) will
be introduced which enable us to rewrite $\bar W(f)$ in a slightly
simpler form. These formulas yield such a corollary of Lemma~16.B
which is more appropriate for our purposes. To work out the details
first some diagrams will be introduced.

Let $\Cal G=\Cal G(k)$ denote the set of all diagrams consisting of
two rows, such that both rows of these diagrams are the set
$\{1,\dots,k\}$, and these diagrams contain some edges
$\{(j_1,j_1')\dots,(j_s,j_s')\}$, $0\le s\le k$, connecting a
point (vertex) of the first row with a point (vertex) of the
second row. The vertices $j_1,\dots,j_s$  which are end points of some
edge in the first row are all different, and the same relation holds
also for the vertices $j_1',\dots,j_s'$ in the second row which are
endpoints of some edge. Given some diagram $G\in\Cal G$ let
$e(G)=\{(j_1,j_1')\dots,(j_s,j_s')\}$ denote the set of its edges,
and let $v_1(G)=\{j_1,\dots,j_s\}$ be the set of those vertices in
the first row and $v_2(G)=\{j_1',\dots,j_s'\}$ the set of those
vertices in the second row of the diagram~$G$ from which an edge
of~$G$ starts.

Given some diagram $G\in \Cal G$ and two sets
$V_1,V_2\subset\{1,\dots,k\}$, we define the following random
variables $H_{n,k}(f|G,V_1,V_2)$ with the help of the random
variables $\xi_{1}^{(j,1)},\dots,\xi_{n}^{(j,1)}$,
$\xi_{1}^{(j,-1)},\dots,\xi_{n}^{(j,-1)}$, $1\le j\le k$, and
$\e=(\e_1,\dots,\e_n)$ taking part in the definition of the random
variables $\bar W(f)$:
$$ \allowdisplaybreaks
\align
H_{n,k}(f|G,V_1,V_2)&=\sum\Sb
(l_1,\dots,l_k,\,l'_1,\dots,l'_k)\colon \\ 1\le l_j\le n,\, l_j\neq l_{j'}
\text{ if }j\neq j',\,1\le j,j'\le k,\\
1\le l'_j\le n,\, l'_j\neq l'_{j'}\text { if }
j\neq j',\,1\le j,j'\le
k,\\ l_j=l'_{j'} \text { if } (j,j')\in e(G),\; l_j\neq l'_{j'} \text
{ if } (j,j')\notin e(G)\endSb
\!\!\!\!\!\!\!\!\!\!\!\! \prod_{j\in\{1,\dots,k\}
\setminus v_1(G)} \!\!\!\!  \e_{l_j}  \prod_{j\in\{1,\dots,k\}
\setminus v_2(G)}  \!\!\!\!   \e_{l'_j} \\
&\qquad\frac1{k!^2} \int
f(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,\xi_{l_k}^{(k,\delta_k(V_1))},y)\\
& \qquad\qquad f(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,
\xi_{l'_k}^{(k,\delta_k(V_2))},y)
\rho(\,dy), \tag16.9
\endalign
$$
where $\delta_j(V_1)=1$ if $j\in V_1$, $\delta_j(V_1)=-1$ if
$j\notin V_1$, and $\delta_j(V_2)=1$ if $j\in V_2$,
$\delta_j(V_2)=-1$ if $j\notin V_2$. (Let us observe that if the
graph $G$ contains $s$ edges, then the product of the $\e$-s in (16.9)
contains $2(k-s)$ terms, and the number of terms in the sum (16.9) is
less than $n^{2k-s}$.) As the Corollary of Lemma~16.1B will indicate,
in the proof of Proposition~15.4 we shall need a good estimate on the
tail distribution of the random variables $H_{n,k}(f|G,V_1,V_2)$
for all $f\in\Cal F$ and $G\in\Cal G$, $V_1,V_2\subset\{1,\dots,k\}$.
Such an estimate can be obtained by means of Theorem 13.3, the
multivariate version of Hoeffding's inequality. But the estimate we
get in such a way will be rewritten in a form more appropriate for our
inductive procedure. This will be done in the next section.

The identity
$$
\bar W(f)=\sum_{G\in \Cal G,\, V_1,V_2\subset\{1,\dots,k\}}
(-1)^{|V_1|+|V_2|} H_{n,k}(f|G,V_1,V_2) \tag16.10
$$
will be proved.

To prove this identity let us write first
$$
\bar W(f)=\sum_{V_1,V_2\subset \{1,\dots,k\}} (-1)^{|V_1|+|V_2|}
\int\bar I_{n,k}^{(V_1,\e)}(f,y)\bar I_{n,k}^{(V_2,\e)}(f,y)\rho(\,dy).
$$
Let us express the products $\bar I_{n,k}^{(V_1,\e)}(f,y)\bar
I_{n,k}^{(V_2,\e)}(f,y)$ by means of formula (16.5). Let us rewrite
this product as a sum of products of the form
$\frac1{k!^2}\prodd_{j=1}^k\e_{l_j}f(\cdots)
\prodd_{j=1}^k\e_{l_j'}f(\cdots)$ and let us define the following
partition of the terms in this sum. The elements of this partition
are indexed by the diagrams $G\in \Cal G$, and if we take a diagram
$G\in\Cal G$ with the set of edges $e(G)=
\{(j_1,j_1'),\dots,(j_s,j_s')\}$, then the term of this sum
determined by the indices $l_1,\dots,l_k,l'_1,\dots,l'_k$
belongs to the element of the partition indexed by this diagram
$G$ if and only if $l_{j_u}=l_{j_u'}'$ for all $1\le u\le s$, and
no more numbers between the indices $l_1,\dots,l_k,l_1'\dots,l'_k$
may agree. Since $\e_{l_{j_u}}\e_{l'_{j_u'}}=1$ for all
$1\le u\le s$ and the set of indices of the remaining random
variables $\e_{l_j}$ is
$\{l_j\colon\;j\in\{1,\dots,k\}\setminus v_1(G)\}$,
the set of indices of the remaining random variables $\e_{l_j'}$
is $\{l'_{j'}\colon\;j\in\{1,\dots,k\}\setminus v_2(G)\}$, we get
by integrating  the product
$\bar I_{n,k}^{(V_1,\e)}(f,y)\bar I_{n,k}^{(V_2,\e)}(f,y)$
with respect to the measure $\rho$ that
$$
\int\bar I_{n,k}^{(V_1,\e)}(f,y)\bar I_{n,k}^{(V_2,\e)}(f,y)\rho(\,dy)
=\sum_{G\in \Cal G} H_{n,k}(f|G,V_1,V_2)
$$
for all $V_1,V_2\in\{1,\dots,k\}$. The last two relations imply
formula (16.10).

Since the number of terms in the sum of formula (16.10) is less than
$2^{4k}k!$, this relation implies that Lemma~16.1B has the following
corollary:

\medskip\noindent
{\bf Corollary of Lemma 16.1B. (A simplified version of the
randomization argument of Lemma~16.1B).} {\it Let a set of
functions $\Cal F$ satisfy the conditions of Proposition~15.4. Then
there exist some constants $A_0=A_0(k)>0$ and $\gamma=\gamma_k>0$
such that if the integrals $H_{n,k}(f)$, $f\in\Cal F$, determined
by this class of functions $\Cal F$ have a good tail behaviour at
level $T^{(2k+1)/2k}$ for some $T\ge A_0$, then the inequality
$$
\aligned
&P\(\sup_{f\in\Cal F} |H_{n,k}(f)|>A^2n^{2k}\sigma^{2(k+1)}\)\\
&\qquad\qquad\le 2\sum_{G\in \Cal G,\, V_1,V_2\subset\{1,\dots,k\}}
P\(\sup_{f\in\Cal F} \left |H_{n,k}(f|G,V_1,V_2)\right|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!} \) \\
&\qquad\qquad\qquad +2^{2k+1}n^{k-1}e^{-\gamma_k A^{1/2k} n\sigma^2/k}
\endaligned \tag16.11
$$
holds with the random variables $H_{n,k}(f)$ and $H_{n,k}(f|G,V_1,V_2)$
defined in formulas (16.4) and (16.9) for all $A\ge T$.}

\medskip\noindent
In the proof of Lemmas 16.1A and 16.1B the result of the
following Lemmas~16.2A and~16.2B will be applied.

\medskip\noindent
{\bf Lemma 16.2A.} {\it Let us take $2k$ independent copies
$$
\xi_1^{(j,1)},\dots,\xi_n^{(j,1)} \quad \text{and} \quad
\xi_1^{(j,-1)},\dots,\xi_n^{(j,-1)}, \quad 1\le j\le k,
$$
of a sequence of independent $\mu$ distributed random variables
$\xi_1,\dots,\xi_n$ together with a sequence of independent random
variables $(\e_1,\dots,\e_n)$, $P(\e_l=1)=P(\e_l=-1)=\frac12$, $1\le
l\le n$, which is also independent of the previous sequences.

Let $\Cal F$ be a class of functions which satisfies the
conditions of Proposition 15.3. Introduce with the help of the above
random variables for all sets $V\subset\{1,\dots,k\}$ and functions
$f\in \Cal F$ the decoupled $U$-statistic
$$
\bar I_{n,k}^V(f)=\frac1{k!}\summ\Sb (l_1,\dots,l_k)\colon \;
1\le l_j\le n,\; j=1,\dots, k,\\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb
f\(\xi_{l_1}^{(1,\delta_1(V))},\dots,\xi_{l_k}^{(k,\delta_k(V))}\) \tag16.12
$$
and its `randomized version'
$$
\bar I_{n,k}^{(V,\e)}(f)=\frac1{k!}\summ\Sb (l_1,\dots,l_k)\colon\;
1\le l_j\le n,\; j=1,\dots, k,\\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb
\e_{l_1}\cdots\e_{l_k}f\(\xi_{l_1}^{(1,\delta_1(V))},\dots,
\xi_{l_k}^{(k,\delta_k(V))}\),  \quad f\in\Cal F, \tag$16.12'$
$$
where $\delta_j(V)=\pm1$, and $\delta_j(V)=1$ if $j\in V$, and
$\delta_j(V)=-1$ if $j\in\{1,\dots,k\}\setminus V$.

Then the sets of random variables
$$
S(f)=\sum_{V\subset \{1,\dots,k\}} (-1)^{(k-|V|)}\bar I_{n,k}^V(f),
\quad f\in\Cal F, \tag16.13
$$
and
$$
\bar S(f)=\sum_{V\subset \{1,\dots,k\}} (-1)^{(k-|V|)}\bar
I_{n,k}^{(V,\e)}(f), \quad f\in\Cal F, \tag$16.13'$
$$
have the same joint distribution.}

\medskip\noindent
{\bf Lemma 16.2B.} {\it Let us take $2k$ independent copies
$$
\xi_1^{(j,1)},\dots,\xi_n^{(j,1)}\quad \text{and} \quad
\xi_1^{(j,-1)},\dots,\xi_n^{(j,-1)}, \quad 1\le j\le k,
$$
of a sequence of independent, $\mu$ distributed random variables
$\xi_1,\dots,\xi_n$ together with a sequence of independent random
variables $(\e_1,\dots,\e_n)$, $P(\e_l=1)=P(\e_l=-1)=\frac12$, $1\le
l\le n$, which is also independent of the previous sequences.

Let us consider a class $\Cal F$ of functions
$f(x_1,\dots,x_k,y)\in \Cal F$ on a space $(X^k\times Y, \Cal X^k
\times \Cal Y,\mu^k\times\rho)$ which satisfies the conditions of
Proposition~15.4. For all functions $f\in \Cal F$
and $V\in\{1,\dots,k\}$ consider the decoupled $U$-statistics
$\bar I_{n,k}^V(f,y)$ defined by formula (16.2) with the help of
the random variables $\xi_1^{(j,1)},\dots,\xi_n^{(j,1)}$  and
$\xi_1^{(j,-1)},\dots,\xi_n^{(j,-1)}$, and define with their help
the random variables
$$
W(f)=\int\[\sum_{V\subset \{1,\dots,k\}} (-1)^{(k-|V|)}\bar
I_{n,k}^V(f,y)\]^2\rho(\,dy), \quad f\in\Cal F. \tag16.14
$$
Then the random vectors $\{W(f)\colon\; f\in \Cal F\}$ defined
in~(16.14) and $\{\bar W(f)\colon\; f\in \Cal F\}$ defined
in~(16.7) have the same distribution.}

\medskip\noindent
{\it Proof of Lemmas 16.2A and 16.2B.} Lemma~16.2A actually agrees
with the already proved Lemma~15.1, only the notation is
different. The proof of Lemma~16.2B is very similar to the proof of
Lemma~15.1. It can be shown that even the following stronger statement
holds. For any $\pm1$ sequence $u=(u_1,\dots,u_n)$ of length~$n$ the
conditional distribution of the random field $\bar W(f)$, $f\in\Cal F$,
under the condition $(\e_1,\dots,\e_n)=u=(u_1,\dots,u_n)$ agrees with
the distribution of the random field $W(f)$, $f\in\Cal F$.

To see this relation let us first observe that the conditional
distribution of the field $\bar W(f)$ under this condition agrees
with the distribution of the random field we get by replacing the
random variables $\e_l$ by $u_l$ for all $1\le l\le n$ in
formulas~(16.5), (16.6) and~(16.7). Beside this, define the vector
$(\xi(u)^{(j,1)}_l,\xi(u)^{(j,-1)}_l)$, $1\le j\le k$, $1\le l\le n$,
by the formula
$(\xi(u)^{(j,1)}_l,\xi(u)^{(j,-1)}_l)=(\xi^{(j,-1)}_l,\xi^{(j,1)}_l)$
for those indices $(j,l)$ for which $u_l=-1$, and
$(\xi(u)^{(j,1)}_l,\xi(u)^{(j,-1)}_l)=(\xi^{(j,1)}_l,\xi^{(j,-1)}_l)$
for which $u_l=1$ (independently of the value of the parameter $j$).
Then the joint distribution of the vectors
$(\xi(u)^{(j,1)}_l,\xi(u)^{(j,-1)}_l)$, $1\le j\le k$, $1\le l\le n$,
and $(\xi^{(j,1)}_l,\xi^{(j,-1)}_l)$, $1\le j\le k$, $1\le l\le n$,
agree. Hence the joint distribution of the random vectors
$\bar I_{n,k}^V(f,y)$, $f\in\Cal F$, $V\subset \{1,\dots,k\}$ defined
in~(16.2) and of the random vectors $W(f)$, $f\in\Cal F$, defined
in~(16.14) do not change if we replace in their definition the random
variables $\xi^{(j,1)}_l$ and $\xi^{(j,-1)}_l$ by $\xi(u)^{(j,1)}_l$
and $\xi(u)^{(j,-1)}_l$. But the set of random variables $W(f)$,
$f\in\Cal F$, obtained in this way agrees with the set of random
variables we introduced to get a set of random variables with the
same distribution as the conditional distribution of $\bar W(f)$,
$f\in \Cal F$ under the condition $(\e_1,\dots,\e_n)=u$. (These
random variables are defined as the square integral of the same sum,
only the terms of this sum are listed in a different order in the
two cases.) These facts imply Lemma~16.2B.

\medskip
In the next step we prove the following Lemma~16.3A.

\medskip\noindent
{\bf Lemma 16.3A.} {\it Let us consider a class of functions $\Cal F$
satisfying the conditions of Proposition 15.3 with parameter~$k$
together with $2k$ independent copies
$\xi^{(j,1)}_1,\dots,\xi^{(j,1)}_n$ and
$\xi^{(j,-1)}_1,\dots,\xi^{(j,-1)}_n$, $1\le j\le k$, of a sequence
of independent, $\mu$-distributed random variables
$\xi_1,\dots,\xi_n$. Take the random variables $\bar I_{n,k}^V(f)$,
$f\in\Cal F$, $V\subset\{1,\dots,k\}$, defined with the help of
these quantities in formula (16.12). Let
$\Cal B=\Cal B(\xi_{1}^{(j,1)},\dots,\xi_{n}^{(j,1)};\;1\le j\le k)$
denote the $\sigma$-algebra generated by the random variables
$\xi_{1}^{(j,1)},\dots,\xi_{n}^{(j,1)}$ , $1\le j\le k$, i.e.\ by
the random variables with upper indices of the form $(j,1)$,
$1\le j\le k$. There exists a number $A_0=A_0(k)>0$ such that
for all $V\subset\{1,\dots,k\}$, $V\neq\{1,\dots,k\}$, the
inequality
$$
P\(\sup_{f\in\Cal F}\left.E\(\bar I_{n,k}^V(f)^2\right|\Cal B\)
> 2^{-(3k+3)}A^2n^{2k}\sigma^{2k+2}\)<
n^{k-1}e^{-\gamma_k A^{1/(2k-1)} n\sigma^2/k}
\tag16.15
$$
holds with a sufficiently small $\gamma_k>0$ if $A\ge A_0$.}

\medskip\noindent
{\it Proof of Lemma 16.3A.}\/ Let us first consider the case
$V=\emptyset$. In this case the estimate $\left.E\(\bar
I_{n,k}^\emptyset(f)^2\right|\Cal B\)=E\(\bar I_{n,k}^\emptyset(f)^2\)
\le\frac{n^k}{k!}\sigma^2\le 2^kn^{2k}\sigma^{2k+2}$ holds for all
$f\in\Cal F$. In the above calculation it was exploited that the
functions $f\in\Cal F$ are canonical, which implies certain
orthogonalities, and beside this the inequality $n\sigma^2\ge\frac12$
holds, because of the relation $n\sigma^2\ge L\log n+\log D$.
The above relations imply that for $V=\emptyset$ the probability at
the left-hand side of (16.15) equals zero if the number $A_0$ is
chosen sufficiently large. Hence inequality~(16.15) holds in this
case.

To avoid some complications in the notation let us first restrict our
attention to sets of the form $V=\{1,\dots,u\}$ with some $1\le u<k$,
and prove relation (16.15) for such sets. For this goal let us
introduce the random variables
$$
\bar I_{n,k}^V(f,l_{u+1},\dots,l_k)=\frac1{k!}\summ\Sb
(l_1,\dots,l_u)\colon \\
1\le l_j\le n,\; j=1,\dots, u,\\ l_j\neq l_{j'} \text{ if } j\neq j'\endSb
f\(\xi_{l_1}^{(1,1)},\dots,\xi_{l_u}^{(u,1)},\xi_{l_{u+1}}^{(u+1,-1)},
\dots, \xi_{l_k}^{(k,-1)}\)
$$
for all $f\in\Cal F$ and sequences $l(u)=(l_{u+1},\dots,l_k)$ with the
properties $1\le l_j\le n$ for all $u+1\le j\le k$ and $l_j\neq l_{j'}$
if $j\neq j'$, i.e. let us fix the last $k-u$ coordinates
$\xi_{l_{u+1}}^{(u+1,-1)}$,\dots, $\xi_{l_k}^{(k,-1)}$  of the
random variable $\bar I_{n,k}^V(f)$ and sum up with respect the first
$u$ coordinates. Then we can write
$$ \allowdisplaybreaks
\align
\left.E\(\bar I_{n,k}^V(f)^2\right|\Cal B\)&=
\left.E\(\(\summ\Sb (l_{u+1},\dots,l_k)\colon\;
1\le l_j\le n\; j=u+1,\dots,k, \\
l_j\neq l_{j'} \text { if } j\neq j'\endSb
\bar I_{n,k}^V(f,l_{u+1},\dots,l_{k})\)^2\right|\Cal B\) \\
&=\summ\Sb (l_{u+1},\dots,l_k)\colon\; 1\le l_j\le n,\;
j=u+1,\dots,k,\\
l_j\neq l_{j'}\text { if } j\neq j'\endSb
\left.E\(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k)^2\right|\Cal B\).
\tag16.16
\endalign
$$
The last relation follows from the identity
$$
\left.E\(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k)
\bar I_{n,k}^V(f,l'_{u+1},\dots,l'_{k})\right|\Cal B\)=0
$$
if $(l_{u+1},\dots,l_k)\neq(l'_{u+1},\dots,l'_k)$, which holds,
since $f$ is a canonical function. We still exploit that the
random variables $\xi_l^{(j,1)}$, $1\le j\le u$ are $\Cal B$
measurable, while the random variables $\xi_{l_j}^{(j,-1)}$,
$u+1\le j\le k$, are independent of the $\sigma$-algebra
$\Cal B$. These facts enable us to calculate the above
conditional expectation in a simple way.

It follows from relation (16.16) that
$$
\aligned
&\left\{\oo\colon\; \sup_{f\in\Cal F}\left. E\(\bar I_{n,k}^V(f)^2\right|
\Cal B\)(\oo) > 2^{-(3k+3)}A^2n^{2k}\sigma^{2k+2}  \right\}\\
&\qquad \subset \bigcup \Sb (l_{u+1},\dots,l_k)\colon \\
1\le l_j\le n,\; j=u+1,\dots,k.\\
l_j\neq l_{j'} \text { if } j\neq j'\endSb
\left\{\oo\colon\; \sup_{f\in\Cal F}\left. E\(\bar
I_{n,k}^V(f,l_{u+1},\dots,l_k)^2\right|\Cal
B\)(\oo) >\frac{A^2n^{2k}\sigma^{2k+2}}{2^{(3k+3)}n^{k-u}} \right\}.
\endaligned
\tag16.17
$$
The probability of the events in the union at the right-hand side
of (16.17) can be estimated with the help of the Corollary of
Proposition~15.4 with parameter $u<k$ instead of $k$. (We may assume
that Proposition~15.4 holds for $u<k$.) We claim that this corollary
yields that
$$
P\(\sup_{f\in\Cal F}\left. E\(\bar
I_{n,k}^V(f,l_{u+1},\dots,l_k)^2\right|\Cal
B\)>\frac {A^2n^{k+u}\sigma^{2k+2}} {2^{(3k+3)}}\)\le
e^{-\gamma_kA^{1/(2u+1)}(n+u-k)\sigma^2} \tag16.18
$$
with an appropriate $\gamma_k>0$ for all sequences
$(l_{u+1},\dots,l_k)$, $1\le l_j\le n$, $u+1\le j\le k$, and such
that $l_j\neq l_{j'}$ if $j\neq j'$.

Let us show that if a class of functions $f\in \Cal F$ satisfies the
conditions of Proposition~15.3 then it also satisfies relation (16.18).
For this goal introduce the space $(Y,\Cal Y,\rho)=(X^{k-u},\Cal
X^{k-u},\mu^{k-u})$, the $k-u$-fold power of the measure space $(X,
\Cal X,\mu)$, and for the sake of simpler notations write $y=(x_{u+1},
\dots,x_k)$ for a point $y\in Y$. Let us also introduce the class of
those function $\bar{\Cal F}$ in the space
$(X^u\times Y,\Cal X^u\times\Cal Y,\mu^u\times\rho)$ consisting of
functions $\bar f$ of the form
$\bar f(x_1,\dots,x_u,y)=f(x_1,\dots,x_k)$ with
$y=(x_{u+1},\dots,x_k)$ and some function $f(x_1,\dots,x_k)\in\Cal F$.
If the class of function $\Cal F$ satisfies the conditions of
Proposition~15.3 (with parameter~$k$), then the class of functions
$\bar{\Cal F}$ satisfies the conditions of Proposition~15.4 with
parameter $u<k$. Hence the Corollary of Proposition~15.4 can be
applied for the class of functions $\bar{\Cal F}$ by our inductive
hypothesis. We shall apply it for decoupled $U$-statistics with the
class of kernel functions $\bar{\Cal F}$ and parameters  $n+k-u$
and $u$ (instead of $n$ and $k$), and with the expressions
$\bar I^{l(u)}_{n+u-k,u}(\bar f)$ and  $H^{l(u)}_{n+u-k,u}(\bar f)$
defined below with the help of the independent random sequences
$\xi_l^{(j,1)}$, $1\le j\le u$,
$l\in\{1,\dots,n\}\setminus\{l_{u+1},\dots,l_k\}$ of independent,
$\mu$-distributed random variables of length~$n+u-k$, where the set
of numbers $\{l_{u+1},\dots,l_k\}$ is the set of indices appearing in
formula~(16.18). It can be seen that with the definition of the random
variables $\bar I^{l(u)}_{n+u-k,u}(\bar f,y)$ and
$H^{l(u)}_{n+u-k,u}(\bar f)$ we shall give below the identity
$$
E\(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k)^2|\Cal B\)
=\(\frac{u!}{k!}\)^2\int\bar I^{l(u)}_{n+u-k,u}(\bar f,y)^2\rho(\,dy)
=\(\frac{u!}{k!}\)^2H^{l(u)}_{n+u-k,u}(\bar f)
\tag16.19
$$
holds. In formula~(16.19) the function $\bar f\in\bar{\Cal F}$ is
defined by the formula $\bar f(x_1,\dots,x_u,y)=f(x_1,\dots,x_k)$ with
$y=(x_{u+1},\dots,x_k)$, and the random variables
$\bar I^{l(u)}_{n+u-k,u}(\bar f,y)$ and
$H^{l(u)}_{n+u-k,u}(\bar f)$ are defined, similarly to~(16.2)--(16.4),
by the formulas
$$
\bar I_{n+u-k,u}^{l(u)}(\bar f,y)=\frac1{u!}\summ\Sb (l_1,\dots,l_u)\colon\;
l_j\in\{1,\dots, n\}\setminus\{l_{u+1},\dots,l_k\},\;j=1,\dots,u\\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb
\bar f\(\xi_{l_1}^{(1,1)},\dots,\xi_{l_u}^{(u,1)},y\)
$$
and
$$
H_{n+u-k,u}^{l(u)}(\bar f)
=\int\bar I_{n+u-k,u}^{l(u)}(\bar f,y)^2\rho(\,dy),
\quad\bar f\in\bar{\Cal F}.
$$
The value of $H_{n+u-k,u}^{l(u)}(\bar f)$ depends on the choice of
the sequence~$l(u)$, but its distribution does not depend on it. We
can give the following estimate by the corollary of Proposition~(15.4)
for $u<k$ and relation~(16.19). Choose a sufficiently small
$\gamma=\gamma_k>0$. We have
$$
\align
&P\(\sup_{\bar f\in\bar{\Cal F}} (n+u-k)^{-u}
H^{l(u)}_{n+u-k,u}(\bar f)\ge \gamma_k^{2/(2u+1)}
A^2(n+u-k)^u\sigma^{2u+2}\) \\
&\qquad =P\(\sup_{\bar f\in\bar{\Cal F}}
E(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k)^2|\Cal B)
\ge \(\frac{k!}{u!}\)^2 \gamma_k^{2/(2u+1)} A^2 (n+u-k)^{2u}\sigma^{2u+2}\) \\
&\qquad\le e^{-\gamma_kA^{1/(2u+1)}(n+k-u)\sigma^2}
\quad \text{for } A>A_0(u)\gamma_k^{-2/(2u+1)}.
\tag16.20
\endalign
$$
It is not difficult to derive formula (16.18) from relation (16.20).
It is enough to check that the level
$\frac{A^2n^{k+u}\sigma^{2k+2}}{2^{(3k+3)}}$ in the
probability at the left-hand side of (16.18) can be replaced by
$\gamma_k^{2/(2u+1)}A^2\(\frac{k!}{u!}\)^2(n+u-k)^{2u}\sigma^{2u+2}$
if $\gamma_k>0$ is chosen sufficiently small. This statement holds,
since
$\gamma_k^{2/(2u+1)}A^2\(\frac{k!}{u!}\)^2(n+u-k)^{2u}\sigma^{2u+2}<
\gamma_k^{2/(2k+1)}A^2\(\frac{k!}{u!}\)^2n^{2u}\sigma^{2u+2}
\le\frac {A^2n^{k+u}\sigma^{2k+2}}{2^{(3k+3)}}$ if the constant
$\gamma_k>0$ is chosen sufficiently small, since
$n\sigma^2>L\log n\le \frac12$ by the conditions of
Proposition~15.3.

Relations (16.17) and (16.18) imply that
$$
P\(\sup_{f\in\Cal F}\left. E\(\bar I_{n,k}^V(f)^2\right|
\Cal B\)(\oo) > 2^{-(3k+3)}A^2n^{2k}\sigma^{2k+2} \)\le
n^{k-u}e^{-\gamma_kA^{1/(2u+1)}(n+u-k)\sigma^2}.
$$
Since $e^{-\gamma_k A^{1/(2u+1)}(n+u-k)\sigma^2}
\le e^{-\gamma_k A^{1/(2k-1)}n\sigma^2/k}$
if $u\le k-1$, $n\ge k$ and $A>A_0$ with a sufficiently large
number~$A_0$, inequality (16.15) holds for all sets $V$ of the form
$V=\{1,\dots,u\}$, $1\le u<k$.

The case of a general set $V\subset\{1,\dots,k\}$, $1\le |V|<k$,
can be handled similarly, only the notation becomes more complicated.
Moreover, the case of general sets $V$ can be reduced to the case of
sets of form we have already considered. Indeed, given some set
$V\subset\{1,\dots,k\}$, $1\le|V|<k$, let us define a new class of
function $\Cal F_V$ we get by applying a rearrangement of the indices
of the arguments $x_1,\dots,x_k$ of the functions $f\in\Cal F$ in such
a way that the arguments indexed by the set $V$ are the first $|V|$
arguments of the functions $f_V\in\Cal F_V$, and put $\bar
V=\{1,\dots,|V|\}$. Then the class of functions $\Cal F_V$ also
satisfies the condition of Proposition~15.3, and we can get relation
(16.15) with the set $V$ by applying it for the set of function $\Cal
F_V$ and set $\bar V$.

\medskip
Now we prove Lemma~16.1A. It will be proved with the help of
Lemma~16.2A, the generalized symmetrization lemma~15.2 and Lemma~16.3A.

\medskip\noindent
{\it Proof of Lemma 16.1A.} First we show with the help of the
generalized symmetrization lemma, i.e. of Lemma 15.2 and Lemma~16.3A that
$$
\aligned
P\(\sup_{f\in\Cal F} n^{-k/2} \left|\bar
I_{n,k}(f)\right|>An^{k/2}\sigma^{k+1}\)&<
2P\(\sup_{f\in\Cal F} |S(f)|>\frac A2n^k\sigma^{k+1}\)\\
&\qquad +2^kn^{k-1}e^{-\gamma_k A^{1/(2k-1)} n\sigma^2/k}
\endaligned \tag16.21
$$
with the function $S(f)$ defined in (16.13). To prove relation (16.21)
introduce the random variables $Z(f)=\bar I_{n,k}^{\{1,\dots,k\}}(f)$
and $\bar Z(f)=-\summ_{V\subset \{1,\dots,k\},\,V\neq\{1,\dots,k\}}
(-1)^{k-|V|}\bar I_{n,k}^V(f)$ for all $f\in\Cal F$, the
$\sigma$-algebra $\Cal B$ considered in Lemma~16.3A and the set
$$
B=\bigcap\Sb V\subset\{1,\dots,k\}\\V\neq\{1,\dots,k\}\endSb
\left\{\oo\colon\; \sup_{f\in\Cal F}\left.E\(\bar I_{n,k}^V(f)^2\right|
\Cal B\)(\oo) \le 2^{-(3k+3)}A^2n^{2k}\sigma^{2k+2}\right\}.
$$

Observe that $S(f)=Z(f)-\bar Z(f)$, $f\in\Cal F$, $B\in\Cal B$, and
by Lemma~16.3A the inequality $1-P(B)\le2^kn^{k-1}e^{-\gamma_k A^{1/(2k-1)}
n\sigma^2/k}$ holds. To prove relation (16.21) apply Lemma~15.2 with
the above introduced random variables $Z(f)$ and $\bar Z(f)$,
$f\in\Cal F$, (both here and in the subsequent proof of Lemma~16.1B
we work with random variables $Z(\cdot)$ and $\bar Z(\cdot)$ indexed
by the countable set of functions $f\in\Cal F$, hence the functions
$f\in\Cal F$ play the role of the parameters~$p$ when Lemma~15.2 is
applied) random set $B$ and $\alpha=\frac A2n^k\sigma^{k+1}$,
$u=\frac A2n^k\sigma^{k+1}$. It is enough to show that
$$
P\(|\bar Z(f)|>\frac A2n^k\sigma^{k+1}|\Cal B\)(\oo)\le\frac12
\quad \text{ for all }f\in\Cal F \quad \text {if } \oo\in\Cal B.
\tag16.22
$$
But $P\(|\bar I_{n,k}^{|V|}(f)|>2^{-(k+1)} An^k\sigma^{k+1}|
\Cal B\)(\oo)\le\frac{2^{2(k+1)}E(\bar I^{|V|}_{n,k}(f)^2|\Cal B)(\oo)}
{A^2n^{2k}\sigma^{2(k+1)}}\le 2^{-(k+1)}$ for all functions
$f\in \Cal F$ and sets
$V\subset\{1,\dots,k\}$, $V\neq\{1,\dots,k\}$, if $\oo\in B$
by the `conditional Chebishev inequality', hence relations (16.22)
and~(16.21) hold.

Lemma 16.1A follows from relation (16.21), Lemma~16.2A and the
observation that the random variables $\bar I_{n,k}^{(V,\e)}(f)$,
$f\in\Cal F$, defined in $(16.12')$ have the same distribution for
all $V\subset\{1,\dots,k\}$ as the random variables
$\bar I_{n,k}^{\e}(f)$, defined in formula~(14.12). Hence Lemma~16.2A,
the definition ($16.13'$) of the random variables $\bar S(f)$, $f\in\Cal F$,
implies the inequality
$$
\align
P\(\sup_{f\in\Cal F} |S(f)|>\frac A2n^k\sigma^{k+1}\)
&=P\(\sup_{f\in\Cal F} |\bar S(f)|>\frac A2n^k\sigma^{k+1}\)\\
&\le 2^kP\(\sup_{f\in\Cal F} \left|\bar I_{n,k}^\e(f)\right|
>2^{-(k+1)}A n^k\sigma^{k+1}\).
\endalign
$$
Lemma 16.1A is proved.

\medskip
Lemma~16.1B will be proved with the help of the following
Lemma~16.3B, which is a version of Lemma~16.3A.

\medskip\noindent
{\bf Lemma 16.3B.} {\it Let us consider a class of functions $\Cal F$
satisfying the conditions of Proposition~15.4 together with $2k$
independent copies $\xi^{(j,1)}_1,\dots,\xi^{(j,1)}_n$ and
$\xi^{(j,-1)}_1$,\dots, $\xi^{(j,-1)}_n$, $1\le j\le k$, of a
sequence of independent, $\mu$-distributed random variables
$\xi_1,\dots,\xi_n$. Take the random variables
$\bar I_{n,k}^V(f,y)$ and $H^V_{n,k}(f)$, $f\in\Cal F$,
$V\subset\{1,\dots,k\}$, defined in formulas~(16.2) and~(16.3) with
the help of these quantities. Let
$\Cal B=\Cal B(\xi_1^{(j,1)},\dots, \xi_n^{(j,1)};\;1\le j\le k)$
denote the $\sigma$-algebra generated by the random variables
$\xi_1^{(j,1)},\dots,\xi_n^{(j,1)}$, $1\le j\le k$, i.e. by those
random variables  which appear in the definition of the random
variables $\bar I_{n,k}^V(f,y)$ and $H_{n,k}^V(f)$ introduced in
formulas (16.2) and (16.3), and have second argument~1 in their
upper index.

\medskip
\item{a)}
There exist some numbers $A_0=A_0(k)>0$ and $\gamma=\gamma_k>0$
such that for all $V\subset\{1,\dots,k\}$, $V\neq\{1,\dots,k\}$,
the inequality
$$
P\(\sup_{f\in\Cal F} E(H^{V}_{n,k}(f)|\Cal B)
>2^{-(4k+4)}A^{(2k-1)/k} n^{2k}\sigma^{2k+2}\)<
n^{k-1}e^{-\gamma_k A^{1/2k} n\sigma^2/k}
\tag16.23
$$
holds if $A\ge A_0$.

\medskip
\item{b)} Given two subsets $V_1,V_2\subset\{1,\dots,k\}$ of the
set $\{1,\dots,k\}$ define the integrals (of random kernel functions)
$$
H_{n,k}^{(V_1,V_2)}(f)=\int |\bar I_{n,k}^{V_1}(f,y)
\bar I_{n,k}^{V_2}(f,y)| \rho(\,dy),
\quad f\in\Cal F, \tag16.24
$$
with the help of the functions $\bar I_{n,k}^V(f,y)$ defined in~(16.2).
There exist some number $A_0=A_0(k)>0$ and $\gamma=\gamma_k$ such that
if the integrals $H_{n,k}(f)$, $f\in\Cal F$, determined by
this class of functions $\Cal F$ have a good tail behaviour at level
$T^{(2k+1)/2k}$ for some $T\ge A_0$, then the inequality
$$
P\(\sup_{f\in\Cal F} E(H^{(V_1,V_2)}_{n,k}(f)|\Cal B)
>2^{-(2k+2)}A^2n^{2k}\sigma^{2k+2}\)
<2n^{k-1}e^{-\gamma_k A^{1/2k}n\sigma^2/k}
\tag16.25
$$
holds for any pairs of subsets $V_1,V_2\subset\{1,\dots,k\}$ with
the property that at least one of them does not equal the set
 $\{1,\dots,k\}$ if the number~$A$ satisfies the condition $A>T$.}

\medskip\noindent
{\it Proof of Lemma 16.3B.}\/ Part a) of Lemma 16.3B can be proved
in almost the same way as Lemma 16.3A. Hence I only briefly
explain the main step of the proof. In the case $V=\emptyset$ the
identity $E(H^{V}_{n,k}(f)|\Cal B)=E(H^{V}_{n,k}(f))$ holds, hence it
is enough to show that $E(H^{V}_{n,k}(f))\le\frac{n^k\sigma^2}{k!}
\le2^k\frac{n^{2k}\sigma^{2k+2}}{k!}$ for all $f\in\Cal F$ under the
conditions of Proposition~15.4. (This relation holds, because
the functions of the class $\Cal F$ are canonical.) The case of a
general set $V$, $V\neq\emptyset$ and $V\neq\{1,\dots,k\}$, can be
reduced to the case $V=\{1,\dots,u\}$ with some $1\le u<k$.

Given a set $V=\{1,\dots,u\}$, $1\le u<k$, let us define for all
$f\in\Cal F$ and sequences $l(u)=(l_{u+1},\dots,l_k)$ with the properties
$1\le l_j\le n$ for all $u+1\le j\le k$ and $l_j\neq l_{j'}$
if $j\neq j'$ the random variable
$$
\bar I_{n,k}^V(f,l_{u+1},\dots,l_k,y)=\frac1{k!} \!\! \summ\Sb
(l_1,\dots,l_u)\colon \\ 1\le l_j\le n,\; j=1,\dots, u,
\\ l_j\neq l_{j'} \text{ if } j\neq j'\endSb \!\!
f\(\xi_{l_1}^{(1,1)},\dots,\xi_{l_u}^{(u,1)},\xi_{l_{u+1}}^{(u+1,-1)},
\dots,\xi_{l_k}^{(k,-1)},y\).
$$
It can be shown, similarly to the proof of relation~(16.16) in
the proof of Proposition~16.3A that because of the canonical
property of the functions $f\in\Cal F$
$$
\left.E\(\bar H_{n,k}^V(f)\right|\Cal B\)
=\summ\Sb (l_{u+1},\dots,l_k)\colon \\ 1\le l_j\le n,\; j=u+1,\dots,k,\\
l_j\neq l_{j'}\text {if } j\neq j'\endSb \int
\left.E\(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k,y)^2\right|\Cal
B\)\rho(\,dy),
$$
and the proof of part a) of Lemma~16.3B can be reduced to the inequality
$$
\align
P&\(\sup_{f\in\Cal F}E\(\left.\int \bar
I_{n,k}^V(f,l_{u+1},\dots,l_k,y)^2\rho(\,dy)\right|\Cal B\)
>\frac {A^{(2k-1)/k}n^{k+u}\sigma^{2k+2}}{2^{(4k+4)}}\)\\
&\qquad \le e^{-\gamma_kA^{(2k-1)/2k(2u+1)}(n+u-k)\sigma^2}
\endalign
$$
with a sufficiently small $\gamma_k>0$. This inequality can be
proved, similarly to relation (16.18) in the proof of Lemma 16.3A
with the help of the Corollary of Proposition~15.4. Only here we
have to work in the space $(X^u\times \bar Y,\Cal
X^u\times\bar{\Cal Y}, \mu^u\times\bar \rho)$ where $\bar
Y=X^{k-u}\times Y$, $\bar{\Cal Y}=\Cal X^{k-u}\times\Cal Y$,
$\bar\rho=\mu^{k-u}\times\rho$ with the class of function
$\bar f\in\bar{\Cal F}$ consisting of the functions~$\bar f$ defined
by the formula $\bar f(x_1,\dots,x_u,\bar y)=f(x_1,\dots,x_k,y)$
with some $f(x_1,\dots,x_k,y)\in \Cal F$, where
$\bar y=(x_{u+1},\dots,x_k,y)$. Here we apply the following version
of formula~(16.19).
$$
E\(\bar I_{n,k}^V(f,l_{u+1},\dots,l_k,y)^2|\Cal B\)
=\(\frac{u!}{k!}\)^2\int \bar I^{l(u)}_{n+u-k,u}
(\bar f,\bar y)^2\bar\rho(\,d\bar y)
=\(\frac{u!}{k!}\)^2H_{n+u-k,u}(\bar f)
$$
with the function $\bar f\in\bar{\Cal F}$ for which the identity
$\bar f(x_1,\dots,x_u,\bar y)=f(x_1,\dots,x_k,y)$ holds with
$\bar y=(x_{u+1},\dots,x_k,y)$ and the and the random variables
$\bar I^{l(u)}_{n+u-k,u}(\bar f,\bar y)$ and $H_{n+u-k,u}(\bar f)$
defined similarly as the corresponding terms after formula~(16.19),
only $y$ is replaced by $\bar y$, the measure $\rho$ by $\bar\rho$,
and the presently defined $\bar f\in\bar{\Cal F}$ are considered in
the present case. I omit the details.

\medskip\noindent
Part b) of Lemma 16.3B will be proved with the help of Part a) and
the inequality
$$
\sup_{f\in\Cal F} E(H^{(V_1,V_2)}_{n,k}(f)|\Cal B) \le
\(\sup_{f\in\Cal F} E(H^{V_1}_{n,k}(f)|\Cal B)\)^{1/2}
\(\sup_{f\in\Cal F} E(H^{V_2}_{n,k}(f)|\Cal B)\)^{1/2}
$$
which follows from the Schwarz inequality applied for integrals with
respect to conditional distributions. Let us assume that
$V_1\neq\{1,\dots,k\}$. The last inequality implies that
$$
\aligned
&P\(\sup_{f\in\Cal F} E(H^{(V_1,V_2)}_{n,k}(f)|\Cal B)
>2^{-(2k+2)}A^2n^{2k}\sigma^{2k+2}\)\\
&\qquad \le P\(\sup_{f\in\Cal F} E(H^{V_1}_{n,k}(f)|\Cal B)
>2^{-(4k+4)}A^{(2k-1)/k} n^{2k}\sigma^{2k+2}\) \\
&\qquad\qquad+P\(\sup_{f\in\Cal F} E(H^{V_2}_{n,k}(f)|\Cal B)
>A^{(2k+1)/k} n^{2k}\sigma^{2k+2}\)
\endaligned
$$
Hence if we know that also the inequality
$$
P\(\sup_{f\in\Cal F} E(H^{V_2}_{n,k}(f)|\Cal B)
>A^{(2k+1)/k} n^{2k}\sigma^{2k+2}\)
\le n^{k-1} e^{-\gamma_k A^{1/2k}n\sigma^2} \tag16.26
$$
holds, then we can deduce relation~(16.25) from the estimate~(16.23)
and the last inequality. Relation~(16.26) follows from Part a) of
Lemma~16.3B if $V_2\neq\{1,\dots,k\}$ and $A\ge1$, since in this
case the level $A^{(2k+1)/k} n^{2k}\sigma^{2k+2}$ can be replaced
by the smaller number $2^{-(4k+2)}A^{(2k-1)/k} n^{2k}\sigma^{2k+2}$
in the probability of formula (16.26). In the case
$V_2=\{1,\dots,k\}$ it follows from the conditions of Part~b) of
Lemma~16.3B if the number $\gamma_k$ is chosen for some
$\gamma_k\le1$. Indeed, since $A^{(2k+1)/2k}>T^{(2k+1)/2k}$, by
the conditions of Proposition~15.4 the estimate~(15.7) holds if
the number $A$ is replaced in it by $A^{(2k+1)/2k}$ (at both side
of the inequality), and this relation implies inequality~(16.26)
in this case.

\medskip
Now we turn to the proof of Lemma~16.1B.

\medskip\noindent
{\it Proof of Lemma 16.1B.}\/ By Lemma~16.2B it is enough to
prove that relation (16.8) holds if the random variables $\bar W(f)$
are replaced in it by the random variables $W(f)$ defined in
formula~(16.14). We shall prove this by applying the generalized
form of the symmetrization lemma, Lemma~15.2, with the choice of
$Z(f)=H_{n,k}^{(\bar V,\bar V)}(f)$, $\bar V=\{1,\dots,k\}$,
$\bar Z(f)=Z(f)-W(f)$, $f\in\Cal F$,
$\Cal B=\Cal B(\xi_1^{(j,1)},\dots,\xi_n^{(j,1)};\;1\le j\le k)$,
$\alpha=\frac{A^2}2n^{2k}\sigma^{2k+2}$,
$u=\frac{A^2}2n^{2k}\sigma^{2k+2}$ and the set
$$
B=\bigcap\Sb (V_1,V_2)\colon\; V_j\in \{1,\dots,k\},\;j=1,2,\\
V_1\neq\{1,\dots,k\} \text { or } V_2\neq\{1,\dots,k\} \endSb
\left\{\oo\colon \sup_{f\in\Cal F} E(H^{(V_1,V_2)}_{n,k}(f)|\Cal B)(\oo)
\le 2^{-(2k+2)} A^{2} n^{2k}\sigma^{2k+2}\right\}.
$$

By part~b) of Lemma 16.3B the inequality $1-P(B)\le2^{2k+1}n^{k-1}
e^{-\gamma_k A^{1/2k}n\sigma^2/k}$ holds. Observe that
$Z(f)=H_{n,k}^{(\bar V,\bar V)}(f)=H_{n,k}(f)$ for all $f\in\Cal F$.
Hence to prove Lemma 16.1B with the
help of Lemma~15.2 it is enough to show that
$$
P\(\left.|\bar Z(f)|>\frac{A^2}2 n^{2k}\sigma^{2k+2}\right|
\Cal B\)(\oo)\le\frac12 \quad \text{for all }f\in\Cal F\text{ if }
\oo\in B. \tag16.27
$$
To prove this relation observe that because of the definition of the
set~$B$
$$
E (|\bar Z(f)| |\Cal B)(\oo)\le \summ \Sb (V_1,V_2)\colon\; V_j\in
\{1,\dots,k\},\;j=1,2,\\
V_1\neq\{1,\dots,k\} \text { or } V_2\neq\{1,\dots,k\} \endSb
E(H^{(V_1,V_2)}_{n,k}(f)|\Cal B)(\oo)\le\frac{A^2}4n^{2k}\sigma^{2k+2}
$$
if $\oo\in B$ for all $f\in \Cal F$. Hence the `conditional Markov
inequality' implies  that
$P\(\left.|\bar Z(f)|>\frac{A^2}2 n^{2k}\sigma^{2(k+1)}\right|
\Cal B\)(\oo)\le\frac
{2E(|\bar Z(f)| |\Cal B)(\oo)}{A^2n^{2k}\sigma^{2k+2}}\le\frac12$
if $\oo\in B$, and inequality~(16.27) holds. Lemma~16.1B is proved.

\beginsection 17. The proof of the main result.

This section contains the proof of Proposition 15.3 together with
Proposition~15.4.  They complete the proof of the main result of this
work, of Theorem~8.4.

\medskip\noindent
{\script A.) The proof of Proposition 15.3.}

\medskip\noindent
The proof of Proposition 15.3 is similar to that of Proposition~7.3.
It applies an induction procedure with respect to the parameter $k$.
In the proof of Proposition~15.3 for parameter~$k$ we may assume that
Propositions~15.3 and~15.4 hold for $u<k$. In the proof we want to
give a good estimate on the expression
$$
P\(\supp_{f\in\Cal F}\left|
\bar I_{n,k}^{\e}(f)\right| >2^{-(k+1)}A n^k\sigma^{k+1}\)
$$
appearing in the estimate (16.1) of Lemma~16.1A. To estimate this
probability we introduce (using the notation of Proposition~15.3)
the functions
$$
S^2_{n,k}(f)(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)=\frac1{k!}\summ\Sb
(l_1,\dots,l_k)\colon\\
1\le l_j\le n,\; j=1,\dots, k,\\ l_j\neq l_{j'} \text{ if } j\neq
j'\endSb f^2\(x_{l_1}^{(1)},\dots,x_{l_k}^{(k)}\),\quad f\in\Cal F,
\tag17.1
$$
with $x_l^{(j)}\in X$, $1\le l\le n$, $1\le j\le k$.
We define with the help of this function the following set
$H=H(A)\subset X^{kn}$ for all $A>T$ similarly to the set defined
in formula~(7.7).
$$
\aligned H=H(A)&=\biggl\{(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)\colon \\
&\qquad \sup_{f\in\Cal F} S^2_{n,k}(f)(x_l^{(j)},\,1\le l\le n,\,
1\le j\le k)>2^kA^{4/3}n^k\sigma^2\biggr\}.
\endaligned \tag17.2
$$
We want to show that
$$
P(\{\oo\colon \; (\xi_l^{(j)}(\oo),\,1\le j\le n,\,1\le j\le k)\in H\})
\le 2^k e^{-A^{2/3k}n\sigma^2} \quad\text{if }A\ge T. \tag17.3
$$

To prove relation (17.3) we take the Hoeffding decomposition of the
$U$-statistics with kernel functions $f^2(x_1,\dots,x_k)$,
$f\in\Cal F$, given in Theorem~9.1, i.e. we write
$$
f^2(x_1,\dots,x_k)=\summ_{V\subset\{1,\dots,k\}} f_V(x_j,j\in V),
\quad f\in\Cal F, \tag17.4
$$
with $f_V(x_j,j\in V)=\prodd_{j\notin V}P_j\prodd_{j\in V}Q_j
f^2(x_1,\dots,x_k)$, where $P_j$ is the projection defined in formula
(9.1) and $Q_j=I-P_j$ agrees with the operator $Q_j$ defined in
 formula~(9.2).

The functions $f_V$ appearing in formula (17.4) are canonical (with
respect to the measure $\mu$), and the identity
$S^2_{n,k}(f)(\xi_l^{(j)}\,1\le l\le n,1\le j \le k)=\bar I_{n,k}(f^2)$
holds for all $f\in \Cal F$ with the expression $\bar I_{n,k}(\cdot)$
defined in~(14.11). By applying the Hoeff\-ding decomposition~(17.4)
for each term $f^2(\xi_{l_1}^{(1)}\dots,\xi_{l_k}^{(k)})$ in the
expression $S^2_{n,k}(f)$ we get that
$$
\aligned
&P\(\sup_{f\in\Cal F}S^2_{n,k}(f)(\xi_l^{(j)},\,1\le l\le n,\,1\le j\le
k) >2^kA^{4/3}n^k\sigma^2\)\\
&\qquad \le\summ_{V\subset\{1,\dots,k\}} P\(\frac{|V|!}{k!}
\sup_{f\in\Cal F} n^{k-|V|}|\bar I_{n,|V|}(f_V)|>A^{4/3}n^k\sigma^2\)
\endaligned \tag17.5
$$
with the functions $f_V$ appearing in formula~(17.4). We want to give
a good estimate for each term in the sum at the right-hand side
in~(17.5). For this goal first we show that the classes of functions
$\{f_V\colon\;f\in \Cal F\}$ in the expansion~(17.4) satisfy the
conditions of Proposition~15.3 for all $V\subset\{1,\dots,k\}$.

The functions $f_V$ are canonical for all $V\subset\{1,\dots,k\}$.
It follows from the conditions of Proposition~15.3 that
$|f^2(x_1,\dots,x_k)|\le 2^{-2(k+1)}$ and
$$
\int f^4(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k)\le
2^{-(k+1)}\sigma^2.
$$
Hence relations (9.4) and $(9.4')$ of Theorem~9.2 imply that
$\left|\supp_{x_j\in X,j\in V}f_V(x_j,j\in V)\right|\le
2^{-(k+2)}\le2^{-(k+1)}$ for all $V\subset\{1,\dots,k\}$ and
$\int f^2_V(x_j,j\in V)\prodd_{j\in V}\mu(\,dx_j)\le 2^{-(k+1)}
\sigma^2\le\sigma^2$ for all $V\subset\{1,\dots,k\}$. Finally, to
check that the class of functions $\Cal F_V=\{f_V\colon\; f\in\Cal F\}$
is $L_2$-dense with exponent $L$ and parameter $D$ observe that for all
probability measures $\rho$ on $(X^k,\Cal X^k)$ and pairs of functions
$f,g\in \Cal F$ $\int(f^2-g^2)^2\,d\rho\le 2^{-2k}\int(f-g)^2\,d\rho$.
This implies that if $\{f_1,\dots,f_m\}$, $m\le D\e^{-L}$, is an
$\e$-dense subset of $\Cal F$ in the space $L_2(X^k,\Cal X^k,\rho)$,
then the set of functions $\{2^kf_1^2,\dots,2^kf_m^2\}$ is an
$\e$-dense subset of the class of functions $\Cal F'=\{2^kf^2\colon\;
f\in \Cal F\}$, hence $\Cal F'$ is also an $L_2$-dense class of functions
with exponent~$L$ and parameter~$D$. Then by Theorem~9.2 the class of
functions $\Cal F_V$ is also $L_2$-dense with exponent $L$ and
parameter~$D$ for all sets $V\subset\{1,\dots,k\}$.

For $V=\emptyset$, the function $f_V$ is constant,
$f_V=\int f^2(x_1,\dots,x_k) \mu(\,dx_1)\dots\mu(\,dx_k)\le\sigma^2$
holds, and $\bar I_{|V|}(f_{|V|})|=f_V\le\sigma^2$. Therefore
the term corresponding to $V=\emptyset$ in the sum of probabilities
at the right-hand side of (17.5) equals zero under the conditions
of Proposition~15.3 with the choice of some $A_0\ge1$. I claim that
the remaining terms in the sum at the right-hand side of~(17.5)
satisfy the inequality
$$ \allowdisplaybreaks
\align
&P\(\frac{|V|!}{k!}n^{k-|V|}\sup_{f\in\Cal F}|\bar I_{n,|V|}(f_V)|
>A^{4/3}n^{k}\sigma^2\)\\
&\qquad \le P\(\sup_{f\in\Cal F}
|\bar I_{n,|V|}(f_V)|>A^{4/3}\frac{k!}{|V|!}n^{|V|}\sigma^{|V|+1}\)
\le e^{-A^{2/3k}n\sigma^2} \quad\text{if } 1\le|V|\le k. \tag17.6
\endalign
$$
The first inequality in (17.6) holds, since $\sigma^{|V|+1}\le\sigma^2$
for $|V|\ge1$, and $n\ge k\ge|V|$. The second inequality follows from
the inductive hypothesis if $|V|<k$, since in this case the middle
expression in~(17.6) can be bounded with the help of Proposition~15.3
by $e^{-(A^{4/3}k!/|V|!)^{1/2|V|}n\sigma^2}\le e^{-A^{2/3k}n\sigma^2}$
if $A_0=A_0(k)$ in Proposition~15.3 is chosen sufficiently large. In
the case $V=\{1,\dots,k\}$ it follows from the inequality $A\ge T$ and
the inductive assumption by which the supremum of decoupled
$U$-statistics determined by such a class of kernel-functions which
satisfies the conditions of Proposition~15.3 has a good
tail behaviour at level $T^{4/3}$. Relations~(17.5) and~(17.6) together
with the estimate in the case $V=\emptyset$ imply formula~(17.3).

By conditioning the probability $P\(\left|\bar I_{n,k}^{\e}(f)
\right|>2^{-(k+2)}A n^{k/2}\sigma^{k+1}\)$ with respect to the
random variables $\xi_l^{(j)}$, $1\le l\le n$, $1\le j\le k$ we get
with the help of the multivariate version of Hoeff\-ding's inequality
(Theorem~13.3) that
$$
\align
&P\(\left.\left|\bar I_{n,k}^{\e}(f)\right|
>2^{-(k+2)}A n^k\sigma^{k+1}\right|\xi_l^{(j)}(\oo)=x_l^{(j)},
1\le l\le n,1\le j\le k\) \\
&\qquad \le C\exp\left\{-\frac12\(\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{2k+4}
S^2_{n,k}(x_l^{(j)},1\le l\le n,\,1\le j\le k)/k!}\)^{1/k}\right\}
\tag17.7 \\
&\qquad \le Ce^{-2^{-4-4/k}A^{2/3k}(k!)^{1/k}n\sigma^2} \quad
\text{for all }f\in\Cal F\quad \text{if } (x_l^{(j)},\,
1\le l\le n,\,1\le j\le k) \notin H
\endalign
$$
with some appropriate constant $C=C(k)>0$.

Define for all $1\le j\le k$ and sets of points $x_l^{(j)}\in X$,
$1\le l\le n$, the probability measures
$\rho_j=\rho_{j,\,(x_l^{(j)},\,
1\le l\le n)}$, $1\le j\le k$, uniformly distributed on the set of
points $\{x_l^{(j)},\; 1\le l\le n\}$, i.e. let
$\rho_j(x_l^{(j)})=\frac1n$ for all $1\le l\le n$. Let us also
define the product $\rho=\rho(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)
=\rho_1\times\cdots\times\rho_k$ of these measures on the space
$(X^k,\Cal X^k)$. If $f$ is a function on $(X^k,\Cal X^k)$ such
that $\int f^2\,d\rho\le\delta^2$ with some $\delta>0$, then
$$
\align
\sup_{\e_1,\dots,\e_n} |\bar I_{n,k}^\e(f)
(x_l^{(j)},\, 1\le l\le n,\,1\le j\le k)|
&\le\frac{n^k}{k!}\int
|f(u_1,\dots,u_k)|\rho(\,du_1,\dots,\,du_k)\\
&\le\frac{n^k}{k!}
\(\int f^2\,d\rho\)^{1/2}\le\frac{n^k}{k!}\delta,
\endalign
$$
$u_j\in R^k$, $1\le j\le k$, and as a consequence
$$
\align
&\sup_{\e_1,\dots,\e_n}|\bar I_{n,k}^\e(f)
(x_l^{(j)},\, 1\le l\le n,\,1\le j\le k)-\bar I_{n,k}^\e(g)
(x_l^{(j)},\, 1\le l\le n,\,1\le j\le k)|\\
&\qquad \le2^{-(k+2)}An^k\sigma^{k+1} \quad\text{if }
\int (f-g)^2\,d\rho\le (2^{-(k+2)}k!A\sigma^{k+1})^2, \tag17.8
\endalign
$$
where $\bar I_{n,k}^\e(f)(x_l^{(j)},\, 1\le l\le n,\,1\le j\le k)$
equals the expression $\bar I_{n,k}^\e(f)$ defined in~(14.12) if
we replace $\xi_{l_j}^{(j)}$ by $x_{l_j}^{(j)}$ for all
$1\le j\le k$, and $1\le l_j\le n$ in it, and $\rho$ is the measure
$\rho=\rho(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)$ defined above.

Let us fix the number $\delta=2^{-(k+2)}k!A\sigma^{k+1}$, and let us
list the elements of the set $\Cal F$ as $\Cal F=\{f_1,f_2,\dots\}$.
Put
$$
m=m(\delta)=\max(1,D\delta^{-L})
=\max(1,D(2^{(k+2)}(k!)^{-1}A^{-(1)}\sigma^{-(k+1)})^L),
$$
and choose for all vectors
$x^{(n)}=(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)\in X^{kn}$, such a
sequence of positive integers $p_1(x^{(n)}),\dots,p_m(x^{(n)}))$
for which
$$
\inf\limits_{1\le l\le m}\int (f(u)-f_{p_l(x^{(n)})}(u))^2
\,d\rho(x^{(n)})\le\delta^2\quad\text{for all } f\in\Cal F.
$$
(Here we apply the notation
$\rho(x^{(n)})=\rho(x_l^{(j)},\,1\le l\le n,\,1\le j\le k)$.)
This is possible, since $\Cal F$ is an $L_2$-dense
class with exponent~$L$ and parameter~$D$, and we can choose
$m=D\delta^{-l}$, if $\delta<1$, Beside this, we can choose $m=1$ if
$\delta=1$, since
$\int |f-g|^2\,d\rho\le \sup|f(x)-g(x)|^2\le2^{-2k}\le1$ for all
$f,g\in\Cal F$. Moreover, it follows from Lemma~7.4 that the
functions $p_l(x^{(n)})$, $1\le l\le m$, can be chosen as measurable
functions of the argument  $x^{(n)}\in X^{kn}$.

Let us introduce the random vector
$\xi^{(n)}(\oo)=(\xi^{(j)}_l(\oo),\,1\le l\le n,\,1\le j\le k)$.
By  arguing similarly as we did in the proof of Proposition~7.3 we
get with the help of relation~(17.8) and the property of the
functions $f_{p_l(x^{(n)})}(\cdot)$ constructed above that
$$
\align
&\left\{\oo\colon\;\sup_{f\in\Cal F}|\bar I_{n,k}^\e(f)(\oo)|
\ge2^{-(k+1)}An^k\sigma^{k+1}\right\} \\
&\qquad \subset\bigcup_{l=1}^m\left\{\oo\colon\;
|\bar I_{n,k}^\e(f_{p_l(\xi^{(n)}(\oo))})(\oo)|
\ge2^{-(k+2)}An^k\sigma^{(k+1)} \right\}.
\endalign
$$

The above relation and formula (17.7) imply that
$$ \allowdisplaybreaks
\align
&P\(\sup_{f\in\Cal F}\left.\left|\bar I_{n,k}^{\e}(f)(\oo)\right|
>2^{-(k+1)}A n^k\sigma^{k+1}\right|\xi_l^{(j)}(\oo)=x_l^{(j)},
1\le l\le n,1\le j\le k\) \\
&\qquad \le \sum_{l=1}^m
P\(\left.\left|\bar I_{n,k}^{\e}(f_{p_l(\xi^{(n)}(\oo))}(\oo)\right|
>\frac{A n^k\sigma^{k+1}}{2^{k+2}}\right|\xi_l^{(j)}(\oo)=x_l^{(j)},
1\le l\le n,1\le j\le k\)    \\
&\qquad \le C m(\delta) e^{-2^{-4-4/k}A^{2/3k}(k!)^{1/k}n\sigma^2} \\
&\qquad \le C (1+D(2^{k+2} A^{-1} (k!)^{-1}\sigma^{-(k+1)})^L)
e^{-2^{-4-4/k}A^{2/3k}(k!)^{1/k}n\sigma^2} \tag17.9 \\
&\qquad\qquad \text{if } \{x_l^{(j)},\, 1\le l\le n,\,1\le j\le k\}\notin H.
\endalign
$$

Relations (17.3) and (17.9) imply that
$$
\aligned
&P\(\sup_{f\in\Cal F}\left|\bar I_{n,k}^{\e}(f)\right|
>2^{-(k+1)}A n^k\sigma^{k+1}\)
\le C (1+D(2^{k+2}A^{-1} (k!)^{-1}\sigma^{-(k+1)})^L)\\
&\qquad\qquad e^{-2^{-4-4/k}A^{2/3k}(k!)^{1/k}n\sigma^2}
+2^k e^{-A^{2/3k}n\sigma^2} \quad\text{if }A> T.
\endaligned \tag17.10
$$
Proposition 15.3 follows from the estimates (16.1), (17.10) and the
condition $n\sigma^2\ge L\log n+\log D$, $L,D\ge 1$, if $A\ge A_0$
with a sufficiently large number~$A_0$. Indeed, in this case
$n\sigma^2\ge\frac12$,
$(2^{k+2}A^{-1} (k!)^{-1}\sigma^{-(k+1)})^L\le
(\frac{n^{(k+1)/2}}{(2n\sigma^2)^{(k+1)/2}})^L\le n^{L(k+1)/2}=
e^{L\log n\cdot (k+1)/2}\le e^{(k+1)n\sigma^2/2}$,
$D=e^{\log D}\le e^{n\sigma^2}$, and
$$
C (1+D(2^{k+2} A^{-1} (k!)^{-1}\sigma^{-(k+1)})^L)
e^{-2^{-4-4/k}A^{2/3k}(k!)^{1/k}n\sigma^2}\le\frac13 e^{-A^{1/2k}n\sigma^2}.
$$
The estimation of the remaining terms in the upper bound of the
estimates~(16.1) and~(17.10) leading to the proof of relation~(15.5)
is simpler. We can exploit that
$e^{-A^{2/3k}n\sigma^2}\ll e^{-A^{1/2k}n\sigma^2}$ and as
$n^{k-1}\le e^{(k-1)n\sigma^2}$
$$
2^kn^{k-1}e^{-\gamma_k A^{1/(2k-1)} n\sigma^2/k}\le
2^ke^{(k-1)n\sigma^2}e^{-\gamma_k A^{1/(2k-1)} n\sigma^2/k}
\ll e^{-A^{1/2k}n\sigma^2}
$$
for a large number~$A$.

Now we turn to the proof of Proposition~15.4.

\medskip\noindent
{\script B.) The proof of Proposition 15.4.}

\medskip\noindent
Because of formula (16.11) in the Corollary of Lemma~16.1B to prove
Proposition 15.4 i.e. inequality (15.7) it is enough to choose a
sufficiently large parameter $A_0$ and to show that with such a choice
the random variables $H_{n,k}(f|G,V_1,V_2)$ defined in formula (16.9)
satisfy the inequality
$$
\aligned
&P\(\sup_{f\in\Cal F} \left |H_{n,k}(f|G,V_1,V_2)\right|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!} \) \le
2^{k+1} e^{-A^{1/2k}n\sigma^2}\\
&\qquad\text{ for all } G\in \Cal G\quad \text{and }
\;V_1,V_2\in\{1,\dots,k\} \quad\text{if } A>T\ge A_0
\endaligned \tag17.11
$$
under the conditions of Proposition~15.4.

Let us first prove formula (17.11) in the case when
$|e(G)|=k$, i.e.\ when all vertices of the diagram $G$ are end-points
of some edge, and the expression $H_{n,k}(f|G,V_1,V_2)$ contains no
`symmetrizing term' $\e_j$. In this case we apply a special argument
to prove relation~(17.11).

It can be seen with the help of the Schwarz inequality that for a
diagram $G$ such that $|e(G)|=k$
$$ \allowdisplaybreaks
\align
|H_{n,k}(f|G,V_1,V_2)|&\le\frac1{k!}
\(\sum\Sb (l_1,\dots,l_k)\colon \\
1\le l_j\le n, \;1\le j\le k,\\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb \int
f^2(\xi_{l_1}^{(1),\delta_1(V_1))},\dots,\xi_{l_k}^{(k,\delta_k(V_1))},y)
\rho(\,dy)\)^{1/2}\\
&\qquad \frac1{k!}\(\sum\Sb (l_1,\dots,l_k)\colon\\
1\le l_j\le n, \;1\le j\le k,\\
l_j\neq l_{j'} \text{ if }j\neq j'\endSb
\int f^2(\xi_{l_1}^{(1,\delta_1(V_2))},\dots,
\xi_{l_k}^{(k,\delta_k(V_2))},y) \rho(\,dy)\)^{1/2} \\
&\tag17.12
\endalign
$$
with $\delta_j(V_1)=1$ if $j\in V_1$, $\delta_j(V_1)=-1$ if
$j\notin V_1$, and $\delta_j(V_2)=1$ if $j\in V_2$,
$\delta_j(V_2)=-1$ if $j\notin V_2$.

Relation (17.12) can be proved for instance by bounding first each
integral in formula (16.9) by means of the Schwarz inequality, and
then by bounding the sum appearing in such a way by means of the
inequality $\sum |a_jb_j|\le \(\sum a_j^2\)^{1/2}\(\sum b_j^2\)^{1/2}$.
Observe that in the case $|(e(G)|=k$ the summation in~(16.9) is
taken for such vectors  $(l_1,\dots,l_k,l_1',\dots,l_k')$ for which
$(l_1',\dots,l_k')$ is a permutation of the sequence $(l_1,\dots,l_k)$
determined by the diagram~$G$. Hence the sum we get after applying the
Schwarz inequality for each integral in~(16.9) has the form
$\sum a_jb_j$ where the set of indices~$j$ in this sum agrees with
the set of vectors $(l_1,\dots,l_k)$ such that $1\le l_p\le n$
for all $1\le p\le k$, and $l_p\neq l_{p'}$ if $p\neq p'$.

By formula (17.12)
$$ \allowdisplaybreaks
\align
&\left\{\oo\colon\;\sup_{f\in\Cal F} \left |H_{n,k}(f|G,V_1,V_2)(\oo)\right|
>\frac{A^2n^{2k}\sigma^{(2(k+1)}}{2^{4k+1}k!} \right\} \\
&\qquad \subset
\biggl\{\oo\colon\; \sup_{f\in\Cal F} \!\!\!\! \sum\Sb
(l_1,\dots,l_k)\colon\\
1\le l_j\le n,\; 1\le j\le k,   \\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb \!\!\!\!\! \int
f^2(\xi_{l_1}^{(1,\delta_1(V_1))}(\oo),\dots,\xi_{l_k}^{(k,\delta_k(V_1))}
(\oo),y) \rho(\,dy) \\
&\hskip9truecm >\frac {A^2n^{2k}\sigma^{2(k+1)}k!}
{2^{4k+1}} \biggr\}\\
&\qquad\qquad \cup \biggl\{\oo\colon\; \sup_{f\in\Cal F} \!\!\!\!
\sum\Sb (l_1,\dots,l_k)\colon\\
1\le l_j\le n, \; 1\le j\le k, \\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb \!\!\!\!\! \int
f^2(\xi_{l_1}^{(1,\delta_1(V_2))}(\oo),\dots,
\xi_{l_k}^{(k,\delta_k(V_2))}
(\oo),y)\rho(\,dy) \\
&\hskip9truecm >\frac{A^2n^{2k}\sigma^{2(k+1)}k!}{2^{4k+1}}\biggr\},
\endalign
$$
hence
$$ \allowdisplaybreaks
\align
&P\(\sup_{f\in\Cal F} \left |H_{n,k}(f|G,V_1,V_2)\right|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!}\) \tag17.13   \\
&\qquad \le 2P\(\sup_{f\in\Cal F}\frac1{k!}
\sum\Sb (l_1,\dots,l_k)\colon\;
1\le l_j\le n,\; 1\le j\le k, \\
l_j\neq l_{j'} \text{ if } j\neq j'\endSb
h_f(\xi_{l_1}^{(1,1)},\dots,\xi_{l_k}^{(k,1)})
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}}\)
\endalign
$$
with  the functions $h_f(x_1,\dots,x_k)=\int
f^2(x_1,\dots,x_k,y)\rho(\,dy)$, $f\in\Cal F$. (In this upper bound
we could get rid of the terms $\delta_j(V_1)$ and $\delta_j(V_2)$,
i.e. on the dependence of the expression $H_{n,k}(f|G,V_1,V_2)$ on
the sets $V_1$ and $V_2$, since the probability of the events in the
previous formula do not depend on them.)

I claim that
$$
P\(\supp_{f\in\Cal F} |\bar I_{n,k}(h_f)|\ge2^k An^k \sigma^2\)\le
2^k e^{-A^{1/2k}n\sigma^2} \quad \text{for }A\ge A_0  \tag17.14
$$
if the constant $A_0=A_0(k)$ is chosen sufficiently large in
Proposition~15.4. Relation (17.14) together with the relation
$A^2\frac{n^{2k}\sigma^{2(k+1)}}{2^{4k+1}}\ge2^kA n^k\sigma^2$ (if
$A>A_0$ with a sufficiently large~$A_0$) imply that the probability
at the right-hand side of (17.13) can be bounded by
$2^{k+1}e^{-A^{1/2k}n\sigma^2}$, and the estimate~(17.11)
holds in the case $|e(G)|=k$.

Relation (17.14) is similar to relation (17.3) (together with the
definition of the random set~$H$ in formula~(17.2)), and a
modification of the proof of the latter estimate yields the proof
also in this case. Indeed, it follows from the conditions of
Proposition~15.4 that
$0\le\int h_f(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k)\le\sigma^2$
for all $f\in\Cal F$, and it is not difficult to check that
$\sup|h_f(x_1,\dots,x_k)|\le2^{-2(k+1)}$, and the class of functions
$\Cal H=\{2^kh_f,\; f\in\Cal F\}$ is an $L_2$-dense class with
exponent $L$ and parameter $D$. Hence by applying the Hoeff\-ding
decomposition of the functions $h_f$, $f\in \Cal F$, similarly to
formula (17.4) we get for all $V\subset \{1,\dots,k\}$ such a set
of functions $\{h_f)_V,\,f\in\Cal F\}$, which satisfies the
conditions of Proposition~15.3. Hence a natural adaptation of the
estimate given for the expression at the right-hand side of (17.5)
(with the help of~(17.6) and the investigation of
$\bar I_{|V|}(f_V)$ for $V=\emptyset$) yields the proof of
formula (17.14). We only have to replace
$S_{n,k}(f)$ by $\bar I_{n,k}(h_f)$, $\bar I_{n,|V|}(f_V)$ by
$\bar I_{n,|V|}((h_f)_V)$ and the levels $2^kA^{4/3}n^k\sigma^2$
and $A^{4/3}n^k\sigma^2$ by $2^kAn^k\sigma^2$ and $An^k\sigma^2$.
Let us observe that each term of the upper bound we get in such
a way can be directly bounded, since during the proof of
Proposition~15.4 for parameter~$k$ we may assume that the result
of Proposition~15.3 holds also for this parameter~$k$.

In the case $e(G)<k$ formula (17.11) will be proved with the help of
the multivariate version of Hoeff\-ding's inequality, Theorem~13.3.
In the proof of this case an expression, analogous to $S^2_{n,k}(f)$
defined in formula~(17.1) will be introduced and estimated for all
sets $V_1,V_2\subset \{1,\dots,k\}$ and diagrams $G\in \Cal G$ such
that $|e(G)|<k$. To define it first some notations will be introduced.

Let us consider the set $J_0(G)=J_0(G,k,n)$,
$$
\align
J_0(G)&=\{(l_1,\dots,l_k,l'_1,\dots,l'_k)\colon\; 1\le l_j,l'_j\le n,
\, 1\le j\le k,\, l_j\neq l_{j'}\text { if } j\neq j', \\
&\qquad l'_j\neq l'_{j'}\text{ if }j\neq j',\;\, l_j=l'_{j'}\text{ if }
(j,j')\in e(G),\; l_j\neq l'_{j'}\text{ if } (j,j')\notin e(G)\}.
\endalign
$$
The set $J_0(G)$ contains those sequences
$(l_1,\dots,l_k,l'_1,\dots,l'_k)$ which appear as indices in the
summation in formula (16.9) for a fixed diagram~$G$. We also
introduce an appropriate partition of it.

For this aim let us first define the sets
$M_1(G)=\{j(1),\dots,j(k-|e(G)|)\}=\{1,\dots,k\}\setminus
v_1(G)$, $j(1)<\cdots<j(k-|e(G)|)$, and
$M_2(G)=\{\bar \jmath(1),\dots,\bar\jmath(k-|e(G|)\}
=\{1,\dots,k\}\setminus v_2(G)$, $\bar  \jmath(1)<\cdots<
\bar\jmath(k-|e(G|)$, the sets of those vertices of the first and
second row of the diagram $G$ in increasing order from which no
edge starts. Let us also introduce the set $V(G)=V(G,n,k)$,
$$
\align
V(G)&=\{(l_{j(1)},\dots,l_{j(k-|e(G)|)},
l'_{\bar\jmath(1)},\dots,l'_{\bar \jmath(k-|e(G)|)})\colon\;
1\le l_{j(p)}, l'_{\bar \jmath(p)}\le n, \\
&\qquad 1\le p\le k-|e(G)|,\, l_{j(p)}\neq l_{j(p')},\,
l'_{\bar\jmath(p)}\neq l'_{\bar\jmath(p')} \text { if }p\neq p',\,
1\le p,p'\le k-|e(G)|, \\
&\qquad\qquad  l_{j(p)}\neq l'_{\bar\jmath(p')},\, 1\le p,p'\le
k-|e(G)| \}.
\endalign
$$
The set $V(G)$ consists of those vectors which can appear as the
restriction of some vector $(l_1,\dots,l_k,l'_1,\dots,l'_k)\in J_0(G)$
to the coordinates indexed by the elements of the set
$M_1(G)\cup M_2(G)$. The elements of $V(G)$ are such vectors whose
coordinates are indexed by the set $M_1(G)\cup M_2(G)$, and they take
different integer values between 1 and $n$. Given a vector $v\in V(G)$
put $v=(v^{(1)},v^{(2)})$ with $v^{(1)}=\{v(r),\,1\le r\le k-|e(G)|\}$,
and $v^{(2)}=\{\bar v(r),\, 1\le r\le k-|e(G)|\}$, where $v^{(1)}$ and
$v^{(2)}$  denote the set of coordinates of $v$ indexed by the elements
of the set $M_1(G)$ and $M_2(G)$ respectively. For all vectors
$v\in V(G)$ define the set
$$
\align
E_G(v)&=\{(l_1,\dots,l_k,l'_1,\dots,l'_k)\colon\; 1\le l_j\le n,
\, 1\le l'_{\bar\jmath}\le n, \text{ for }1\le j,\bar\jmath\le k,\\
&\qquad l_j\neq l_{j'}\text{ if }j\neq j',\,
l'_{\bar \jmath}\neq l'_{\bar\jmath'}\text{ if }\bar \jmath\neq \bar
\jmath',\\
&\qquad l_j=l'_{\bar\jmath}\text{ if } (j,\bar\jmath)\in e(G)\text
{ and } l_j\neq l'_{\bar\jmath} \text{ if } (j,\bar\jmath)
\notin e(G),\\
&\qquad l_{j(r)}=v(r),\, l'_{\bar\jmath(r)}=\bar v(r),\, 1\le r\le
k-|e(G)|\},\quad v\in V(G),
\endalign
$$
where $\{j(1),\dots,j(k-|e(G)|)\}=M_1(G)$, $\{\bar \jmath(1),\dots,
\bar \jmath(k-|e(G)|)\}=M_2(G)$, $v=(v^{(1)},v^{(2)})$ with
$v^{(1)}=(v(1),\dots,v(k-|e(G)|))$ and
$v^{(2)}=(\bar v(1),\dots,\bar v(k-|e(G)|))$ in the last line of
this definition. Beside this, let us define
$$
E^1_G(v)=\{(l_1,\dots,l_k)\colon\;
(l_1,\dots,l_k,l'_1,\dots,l'_k)\in E_G(v)\}
$$
and
$$
E^2_G(v)=\{(l'_1,\dots,l'_k)\colon\;
(l_1\dots,l_k,l'_1,\dots,l'_k)\in E_G(v)\}.
$$

Given a vector $v\in V(G)$, $v=(v^{(1)},v^{(2)})$, the set $E_G(v)$
consists of those vectors
$\ell=(l_1,\dots,l_k,l'_1,\dots,l'_k)\in J_0(G)$ whose restrictions
to $M_1(G)$ and $M_2(G)$ equal $v^{(1)}$ and $v^{(2)}$ respectively.
More explicitly, $\ell\in E_G(v)$, if for $j\in M_1(G)$ its
coordinate~$l_j$ agrees with the corresponding element of
$v^{(1)}$, for $\bar\jmath\in M_2(G)$ its coordinate
$l'_{\bar\jmath}$ agrees with the corresponding element of
$v^{(2)}$, and the remaining coordinates of $\ell$ satisfy the
following properties. The indices of the remaining coordinates of
$\ell$ can be partitioned into pairs $(j_s,\bar\jmath_{s'})$,
$1\le s,s'\le |e(G)|$ in such a way that
$(j_s,\bar\jmath_{s'})\in e(G)$. The identity
$l_{j_s}=l'_{\bar\jmath_{s'}}$ holds for such  pairs
$(j_s,\bar\jmath_{s'})$, and if $(j_s,\bar\jmath_{s'})\notin e(G)$,
then the coordinates $l_{j_s}$ and $l'_{\bar\jmath_{s'}}$ are
different. Otherwise, the coordinates $l_{j_s}$ and
$l'_{\bar\jmath_{s'}}$ can be  freely chosen from the set
$\{1,\dots,n\}\setminus\{v^{(1)},v^{(2)}\}$. The sets
$E^1_G(v)$ and $E^2_G(v)$ consist of the vectors containing
the first~$k$ and the second~$k$ coordinates of the vectors
$\ell\in E_G(v)$.

The sets $E_G(v)$, $v\in V(G)$, constitute a partition of the set
$J_0(G)$, and the random variables $H_{n,k}(f|G,V_1,V_2)$ defined
in (16.9) can be rewritten with their help as
$$
\aligned
&H_{n,k}(f|G,V_1,V_2)(\oo)=\sum_{v=(v^{(1)},v^{(2)})\in V(G)}
\prod_{s=1}^{k-|e(G)|}\e_{l_{j(s)}}(\oo)
\prod_{s=1}^{k-|e(G)|}\e_{l'_{\bar\jmath(s)}}(\oo)\\
&\qquad\sum_{(l_1,\dots,l_k,l_1'\dots,l'_k)\in E_G(v)}
\frac1{k!^2} \int
f(\xi_{l_1}^{(1,\delta_1(V_1))}(\oo),\dots,
\xi_{l_k}^{(k,\delta_k(V_1))}(\oo),y)\\
& \hskip6truecm f(\xi_{l'_1}^{(1,\delta_1(V_2))}(\oo),
\dots,\xi_{l'_k}^{(k,\delta_k(V_2))}(\oo),y) \rho(\,dy),
\endaligned \tag17.15
$$
where $\delta_j(V_1)=1$ if $j\in V_1$, $\delta_j(V_1)=-1$ if
$j\notin V_1$, and $\delta_j(V_2)=1$ if $j\in V_2$,
$\delta_j(V_2)=-1$ if $j\notin V_2$.

Let us fix some $G\in\Cal G$ and $V_1,V_2\subset\{1,\dots,k\}$.
The inequality
$$
P\(S^2(\Cal F|G,V_1,V_2)>2^{2k}A^{8/3}n^{2k}\sigma^4\)\le
2^{k+1}e^{-A^{2/3k}n\sigma^2} \quad\text{if }A\ge A_0\text{ and }
e(G)<k \tag17.16
$$
will be proved for the random variable
$$
\align
S^2(\Cal F|G,V_1,V_2)=\sup_{f\in\Cal F}\frac1{k!^2}&\sum_{v\in V(G)}
\biggl(\sum_{(l_1,\dots,l_k,l'_1,\dots,l'_k)\in E_G(v)}
\int f(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,
\xi_{l_k}^{(k,\delta_k(V_1))},y) \\
&\qquad\qquad f(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,\xi_{l'_k}
^{(k,\delta_k(V_2))},y) \rho(\,dy)\biggr)^2, \tag17.17
\endalign
$$
where $\delta_j(V_1)=1$ if $j\in V_1$, $\delta_j(V_1)=-1$ if
$j\notin V_1$, and $\delta_j(V_2)=1$ if $j\in V_2$,
$\delta_j(V_2)=-1$ if $j\notin V_2$. The random variable
$S^2(\Cal F|G,V_1,V_2)$ defined in (17.17) plays a similar role in
the proof of Proposition~15.4 as the random variable
$\supp_{f\in\Cal F}S^2_{n,k}(f)$ with $S^2_{n,k}(f)$ defined in
formula~(17.1) played in the proof of Proposition~15.3.

To prove formula (17.16) let us first fix some $v\in V(G)$, and let
us observe that the following inequality similar to
relation~(17.12) holds.
$$ \allowdisplaybreaks
\align
&\biggl(\sum_{(l_1,\dots,l_k,l'_1,\dots,l'_k)\in E_G(v)}
\int f(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,\xi_{l_k}^{(k,\delta_k(V_1))},y)\\
&\hskip7truecm f(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,\xi_{l'_k}
^{(k,\delta_k(V_2))},y) \rho(\,dy)\biggr)^2\\
&\qquad\le \(\sum_{(l_1,\dots,l_k)\in E_G^1(v)}
\int f^2(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,
\xi_{l_k}^{(k,\delta_k(V_1))},y) \rho(\,dy)\) \\
&\qquad\qquad \(\sum_{(l'_1,\dots,l'_k)\in E_G^2(v)}
\int f^2(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,
\xi_{l'_k} ^{(k,\delta_k(V_2))},y) \rho(\,dy)\) \tag17.18
\endalign
$$
for all $f\in\Cal F$ and  $v\in V(G)$. Indeed, observe that for a
vector $\bar v=(\bar v_1,\bar v_2)\in E_G(v)$ with
$\bar v_1\in E_G^1(v)$ and $\bar v_2\in E_G^2(v)$, the coordinates
of the vector $\bar v_1$ in the set~$M_1(G)$ and the coordinates
of the vector $\bar v_2$ in the set~$M_2(G)$ are prescribed, while
the coordinates of $\bar v_1$ in the set $v_1(G)$ are given by a
permutation of the coordinates $\bar v_2$ in the set $v_2(G)$.
(The sets $v_1(G)$ and $v_2(G)$ were defined before the introduction
of formula~(16.9) as the sets of those vertices in the first and
second row of the diagram~$G$ respectively from which an edge
of~$G$ starts.) This permutation is determined by the diagram~$G$.
Inequality~(17.18) can be proved on the basis of the above
observation similarly to formula~(17.12).

We shall prove with the help of formula~(17.18) the following
inequality.
$$ \allowdisplaybreaks
\align
&S^2(\Cal F|G,V_1,V_2)\\
&\qquad \le\sup_{f\in\Cal F}\sum_{v\in V(G)}
\frac1{k!}\(\!\sum_{(l_1,\dots,l_k)\in E_G^1(v)}
\int f^2(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,
\xi_{l_k}^{(k,\delta_k(V_1))},y) \rho(\,dy)\) \\
&\qquad\qquad \frac1{k!}\(\sum_{(l'_1,\dots,l'_k)\in E_G^2(v)}
\int f^2(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,
\xi_{l'_k} ^{(k,\delta_k(V_2))},y) \rho(\,dy)\)   \tag17.19   \\
&\qquad \le \supp_{f\in\Cal F}\frac1{k!} \(\sum\Sb (l_1,\dots,l_k)\colon\;
1\le l_j\le n,\, 1\le j\le k,\\ l_j\neq l_{j'}\text{ if }j\neq j'\endSb
\int f^2(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,
\xi_{l_k}^{(k,\delta_k(V_1))},y) \rho(\,dy)\) \\
&\qquad\qquad \supp_{f\in\Cal F}\frac1{k!}\(\sum\Sb
(l_1',\dots,l_k')\colon\;
1\le l_j'\le n,\,1\le j\le k,\\ l'_j\neq l'_{j'}
\text{ if } j\neq j'\endSb \int
f^2(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,\xi_{l'_k}
^{(k,\delta_k(V_2))},y) \rho(\,dy)\).
\endalign
$$
The first inequality of~(17.19) is a simple consequence of
formula~(17.18) and the definition of the random variable
$S^2(\Cal F|G,V_1,V_2)$. To check its second inequality let us
observe that it can be reduced to the simpler relation, where the
expression $\supp_{f\in\Cal F}$ is omitted at each place. The
simplified inequality obtained after the omission of the
expressions $\sup$ can be checked by carrying out the term by
term multiplication between the products of sums appearing
in~(17.19). At both sides of the inequality a sum consisting of
terms of the form
$$
\frac1{k!^2}\int f^2(\xi_{l_1}^{(1,\delta_1(V_1))},\dots,
\xi_{l_k}^{(k,\delta_k(V_1))},y) \rho(\,dy)
\int f^2(\xi_{l'_1}^{(1,\delta_1(V_2))},\dots,\xi_{l'_k}
^{(k,\delta_k(V_2))},y) \rho(\,dy), \tag17.20
$$
appears. It is enough to check that if a term of this form appears
in the middle term of the simplified version formula of (17.19),
then it appears with coefficient~1, and it also appears at the
right-hand side of this formula. To see this, observe that each
term of the form~(17.20) which appears in the sum we get by
carrying out the multiplications in middle term of~(17.19)
determines uniquely the index $v=(v^{(1)},v^{(2)})\in V(G)$ in
the outer sum of the middle term in the inequality~(17.19).
Indeed, if the random variables defining this expression of the
form~(17.20) have indices $\ell=(l_1,\dots,l_k,l_1',\dots,l_k')$,
then this vector $\ell$ uniquely determines the vector
$v=(v^{(1)},v^{(2)})\in V(G)$, since $v^{(1)}$ must agree with
the restriction of the vector $l=(l_1,\dots,l_k)$ to the
coordinates with indices in $M_1(G)$ and $v^{(2)}$ must agree
with the restriction of the vector $l'=(l'_1,\dots,l'_k)$ to
the coordinates with indices in $M_2(G)$. Beside this, by
carrying out the multiplication at the right-hand side of~(17.19)
we get such a sum which contains all such terms of the
form~(17.20) which appeared in the sum expressing the middle term
in inequality~(17.19). The above arguments imply inequality~(17.19).

Relation (17.19) implies that
$$
P(S^2(\Cal F|G,V_1,V_2))>2^{2k}A^{8/3}n^{2k}\sigma^4) \le
2P\(\supp_{f\in\Cal F} \bar I_{n,k}(h_f)>2^kA^{4/3}n^k\sigma^2\)
$$
with $h_f(x_1,\dots,x_k)=\int f^2(x_1,\dots,x_k,y)\rho(\,dy)$.
(Here we exploited that in the last formula $S^2(\Cal F|G,V_1,V_2)$
is bounded by the product of two random variables whose distributions
do not depend on the sets $V_1$ and $V_2$.) Thus to prove inequality
(17.16) it is enough to show that
$$
2P\(\supp_{f\in\Cal F} \bar I_{n,k}(h_f)>2^kA^{4/3}n^k\sigma^2\)\le
2^{k+1}e^{-A^{2/3k}n\sigma^2} \quad \text{if } A\ge A_0. \tag17.21
$$
Actually formula (17.21) follows from the already proven formula
(17.14), only the parameter $A$ has to be replaced by $A^{4/3}$
in it.

With the help of relation (17.16) the proof of Proposition~15.4
can be completed similarly to Proposition~15.3. The following
version of inequality~(17.7) can be proved with the help of the
multivariate version of Hoeff\-ding's inequality, Theorem~13.3, and
the representation of the random variable $H_{n,k}(f|G,V_1,V_2)$ in
the form~(17.15).
$$
\aligned
&P\(\left.|H_{n,k}(f|G,V_1,V_2)|
>\frac{A^2}{2^{4k+2}k!} n^{2k}\sigma^{2(k+1)}
\right| \xi^{j,\pm1}_{l},\,1\le l\le n,\,1\le j\le k\)(\oo)\\
&\qquad \le Ce^{-2^{-(6+2/k)} A^{2/3k}n\sigma^2} \quad
\text{if}\quad S^2(\Cal F|G,V_1,V_2)(\oo)
\le2^{2k} A^{8/3}n^{2k}\sigma^4 \text{ and }A\ge A_0
\endaligned\tag17.22
$$
with an appropriate constant $C=C(k)>0$ for all $f\in\Cal F$ and
$G\in \Cal G$ such that $|e(G)|<k$ and $V_1,V_2\subset\{1,\dots,k\}$.
(Observe that the conditional probability estimated in~(17.22) can
be represented in the following way. In a point $\oo\in\Omega$ fix
the values of $\xi^{(j,\pm1)}_l(\oo)$ for all
indices $1\le l\le n$ and $1\le j\le k$ in the random variable
$H_{n,k}(f|G,V_1,V_k)$, and the conditional probability in this point
$\oo$ equals the probability that the random variable, (depending on
the random variables $\e_l$,  $1\le l\le n$), obtained in such a way is
greater than $\frac{A^2}{2^{4k+2}k!}n^{2k}\sigma^{2(k+1)}$.)

Indeed, in this case the conditional probability considered in (17.22)
can be bounded because of the multivariate version of the Hoeffding
inequality (Theorem~13.3) by
$C\exp\left\{-\frac12\(\frac{A^4n^{4k}\sigma^{4(k+1)}}{2^{8k+4}(k!)^2S^2
(\Cal F|G,V_1,V_2)/(k!)^2}\)^{1/2j}\right\}\le C\exp
\left\{-\frac12\(\frac{A^{4/3}n^{2k}\sigma^{4k}}{2^{10k+4}}\)^{1/2j}
\right\}$ with an appropriate $C=C(k)>0$, where $2j=2k-2|e(G)|$, and
$0\le |e(G)|\le k-1$. Since $j\le k$, $n\sigma^2\ge\frac12$, and also
$\frac{A^{4/3}}{2^{10k+4}}\ge2$ if $A_0$ is  chosen sufficiently
large we can write in the above upper bound for the left-hand side
of~(17.22) $j=k$, and in such a way we get inequality~(17.22).

The next inequality in which we estimate
$\supp_{f\in\Cal F}H_{n,k}(f|G,V_1,V_2)$ is a natural version of
formula~(17.9) in the proof of Proposition~15.3.
$$
\align
&P\(\left.\sup_{f\in\Cal F} |H_{n,k}(f|G,V_1,V_2)|
>\frac{A^2}{2^{4k+1}k!} n^{2k}\sigma^{2(k+1)}
\right| \xi^{(j,\pm1)}_{l},\,1\le l\le n,\,1\le j\le k\)(\oo)\\
&\qquad \le C \(1+D\(\frac{2^{4k+3}k!}{A^2\sigma^{2(k+1)}}\)^L\)
e^{-2^{-(6+2/k)}A^{2/3k}n\sigma^2}  \\
&\qquad \text{if }  S^2(\Cal F|G,V_1,V_2))(\oo)
\le2^{2k} A^{8/3}n^{2k}\sigma^4 \text{ and } A\ge A_0 \tag17.23
\endalign
$$
for all $G\in\Cal G$ such that $|e(G)|<k$ and
$V_1,V_2\subset\{1,\dots,k\}$.

To prove formula (17.23) let us fix two sets
$V_1,V_2\subset\{1,\dots,k\}$ and a diagram $G$ such that $|e(G)|<k$.
Let us 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}$
some probability measure $\alpha(x^{(n)})$ on the space
$X^k\times Y$ (with the space $Y$ which appears in the
formulation of Proposition~15.4) with which we can work similarly
as with the probability measures $\nu(x^{(n)}$ and $\rho(x^{(n)}$
in the proof of Propositions~7.3 and~15.3.

To do this let us consider some vector
$x^{(n)}=(x_l^{(j,1)},x_l^{(j,-1)},\,1\le l\le n,\,1\le j\le k)\in X^{2kn}$,
and define first the probability measures
$\nu_j^{(1)}=\nu_j^{(1)}(x^{(n)},V_1)$ and
$\nu_j^{(2)}=\nu_j^{(2)}(x^{(n)},V_2)$ in the space $(X,\Cal X)$
for all $1\le j\le k$  which are uniformly distributed in the set
of points $x_{l}^{(j,\delta_j(V_1))}$, $1\le l\le n$ and
$x_{l}^{(j,\delta_j(V_2))}$, $1\le l\le n$, respectively. This means
that we define for all $1\le j\le k$ (and sets $V_1$ and $V_2$) the
probability measures
$\nu^{(1)}_j\(\{x_l^{(j,\delta_j(V_1))}\}\)=\frac1n$ and
$\nu^{(2)}_j\(\{x_l^{(j,\delta_j(V_2))}\}\)=\frac1n$, $1\le l\le n$,
where $\delta_j(V_1)=1$ if $j\in V_1$, $\delta_j(V_1)=-1$
if $j\notin V_1$, and similarly $\delta_j(V_2)=1$ if $j\in V_2$ and
$\delta_j(V_2)=-1$ if $j\notin V_2$. Let us consider the product
measures $\alpha_1=\alpha_1(x^{(n)},V_1)
=\nu_1^{(1)}\times\cdots\times\nu_k^{(1)}\times\rho$
and $\alpha_2=\alpha_2(x^{(n)},V_2)
=\nu_1^{(2)}\times\cdots\times\nu_k^{(2)}\times\rho$ on
the product space $(X^k\times Y,\Cal X^k\times\Cal Y)$, where $\rho$
is that probability measure on $(Y,\Cal Y)$ which appears in
Proposition~15.4. With the help of the measures $\alpha_1$ and
$\alpha_2$ define the measure $\alpha=\alpha(x^{(n)})
=\alpha(x^{(n)},V_1,V_2)=\frac{\alpha_1+\alpha_2}2$ in the space
$(X^k\times Y,\Cal X^k,\times\Cal Y)$.
Let us also define the measure
$\tilde\alpha=\tilde\alpha(x^{(n)})=\tilde\alpha(x^{(n)},V_1,V_2)
=\nu^{(1)}_1\times\cdots\nu^{(1)}_k
\times\nu^{(2)}_1\times\cdots\nu^{(2)}_k\times\rho$ in the space
$(X^{2k}\times Y,\Cal X^{2k},\times\Cal Y)$.

Let us define $H_{n,k}(f|G,V_1,V_2)$ as a function in the product
space $(X^{2kn},\Cal X^{2kn})$ (with arguments $x^{(j,1)}_l$ and
$x^{(j,-1)}_l$, $1\le j\le k$, $1\le l\le n$) by means of
formula~(17.15) by replacing the random variables
$\xi_{l_j}^{(j,\delta_j(V_1))}(\oo)$ by
$x_{l_j}^{(j,\delta_j(V_1))}$ and the random variables
$\xi_{l'_j}^{(j,\delta_j(V_2))}(\oo)$ by
$x_{l'_j}^{(j,\delta_j(V_2))}$ in it for all $1\le j\le k$ and
$1\le l_j,l'_j\le n$. With such a notation we can write for any
pairs $f,g\in\Cal F$ and
$x^{(n)}=(x^{j,1)}_l,x^{(j,-1)}_l,\,1\le j\le k,\,1\le l\le n)\in X^{2kn}$,
by exploiting the properties of the above defined measure
 $\tilde\alpha$ the inequality
$$
\aligned
&\sup_{\e_1,\dots,\e_n}
|H_{n,k}(f|G,V_1,V_2)(x^{(n)})-H_{n,k}(f|G,V_1,V_2)(x^{(n)})|\\
&\qquad \le \sum_{v=(v^{(1)},v^{(2)})\in V(G)} \;
\sum_{(l_1,\dots,l_k,l_1'\dots,l'_k)\in E_G(v)} \\
&\qquad\qquad \frac1{k!^2}\int
|f(x_{l_1}^{(1,\delta_1(V_1))},\dots,x_{l_k}^{(k,\delta_k(V_1))},y)
f(x_{l'_1}^{(1,\delta_1(V_2))},\dots,x_{l'_k}^{(k,\delta_k(V_2))},y) \\
&\qquad\qquad\qquad - g(x_{l_1}^{(1,\delta_1(V_1))},\dots,
x_{l_k}^{(k,\delta_k(V_1))},y)
g(x_{l'_1}^{(1,\delta_1(V_2))},
\dots,x_{l'_k}^{(k,\delta_k(V_2))},y)| \rho(\,dy)\\
&\qquad \le n^{2k} \int |f(x_1,\dots,x_k,y)f(x_{k+1},\dots,x_{2k},y)
- g(x_1,\dots,x_k,y)g(x_{k+1},\dots,x_{2k},y)|\\
&\qquad\qquad\qquad\qquad  \tilde\alpha(\,dx_1,\dots,\,dx_{2k},\,dy).
\endaligned \tag17.24
$$
Beside this, since both $\sup |f(x_1,\dots,x_k,y)|\le1$
and $\sup |g(x_1,\dots,x_k,y)|\le1$, we have
$$ \allowdisplaybreaks
\align
|&f(x_1,\dots,x_k,y)f(x_{k+1},\dots,x_{2k},y)
- g(x_1,\dots,x_k,y)g(x_{k+1},\dots,x_{2k},y)|\\
&\qquad \le
|f(x_1,\dots,x_k,y)||f(x_{k+1},\dots,x_{2k},y)-g(x_{k+1},\dots,x_{2k},y)|\\
&\qquad\qquad+
|g(x_{k+1},\dots,x_{2k})||f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|\\
&\qquad \le |f(x_{k+1},\dots,x_{2k},y)-g(x_{k+1},\dots,x_{2k},y)|\\
&\qquad\qquad +|f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|.
\endalign
$$
It follows from this inequality, formula~(17.24) and the definition of
the measures $\tilde\alpha$, $\alpha_1$, $\alpha_2$ and $\alpha$ that
$$ \allowdisplaybreaks
\align
&\sup_{\e_1,\dots,\e_n}
|H_{n,k}(f|G,V_1,V_2)(x^{(n)})-H_{n,k}(f|G,V_1,V_2)(x^{(n)})|\\
&\qquad \le n^{2k}\int
(|f(x_{k+1},\dots,x_{2k},y)-g(x_{k+1},\dots,x_{2k},y)|\\
&\qquad\qquad\qquad +|f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|)
\tilde\alpha(\,dx_1,\dots,\,dx_{2k},\,dy)\\
&\qquad=n^{2k}\int |f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|\\
&\qquad\qquad\qquad\quad (\alpha_1(\,dx_1,\dots,\,dx_k,\,dy)
+\alpha_2(\,dx_1,\dots,\,dx_k,\,dy)) \tag17.25  \\
&\qquad=2n^{2k}\int |f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|
\alpha(\,dx_1,\dots,\,dx_k,\,dy)\\
&\qquad\le2n^{2k}\(\int |f(x_1,\dots,x_k,y)-g(x_1,\dots,x_k,y)|^2
\alpha(\,dx_1,\dots,\,dx_k,\,dy)\)^{1/2}
\endalign
$$
with the previously defined probability measure $\alpha=\alpha(x^{(n)})$.
Put $\delta=\frac {A^2\sigma^{2(k+1)}}{2^{4k+3}k!}$,
list the elements of $\Cal F$ as $\Cal F=\{f_1,f_2,\dots\}$,
and choose a set of indices $p_1(x^{(n)}),\dots,p_m(x^{(n)})$
taking positive integer values with $m=\max(1,D\delta^{-L})$
elements such that
$\supp_{1\le l\le m}\int f(u)-f_{p_l(x^{(n)})}(u))^2
\alpha(x^{(n)})(\,du)\le \delta^2$ for all $f\in\Cal F$. Such a
choice of the indices $p_l(x^{(n)})$, $1\le l\le m$, is possible,
since $\Cal F$ is $L_2$-dense with exponent~$L$ and parameter~$D$.
Moreover, by  Lemma~7.4 we may chose the functions $p_l(x^{(n)})$,
$1\le l\le m$, as measurable functions of their argument
$x^{(n)}\in X^{2kn}$.

Put $\xi^{(n)}(\oo)=(\xi^{(j,\pm1)}_l(\oo),\,1\le l\le n,\,1\le j\le k)$.
By  arguing similarly as we did in the proof of Propositions~7.3
and~(15.3) we get with the help of relation~(17.25) and the
property of the functions $f_{p_l(x^{(n)})}(\cdot)$ constructed
above that
$$
\align
&\left\{\oo\colon\;\sup_{f\in\Cal F}| H_{n,k}(f|G,V_1,V_2)(\oo)|
\ge\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{(4k+1)}k!}\right\} \\
&\qquad \subset\bigcup_{l=1}^m\left\{\oo\colon\;
|H_{n,k}(f_{p_l(\xi^{(n)}(\oo)}|G,V_1,V_2)(\oo)(\oo)|
\ge\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{(4k+2)}k!}\right\}.
\endalign
$$
Hence
$$
\align
&P\(\left.\sup_{f\in\Cal F} |H_{n,k}(f|G,V_1,V_2)|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!}
\right| \xi^{(j,\pm1)}_{l},\,1\le l\le n,\,1\le j\le k\)(\oo)\\
&\qquad\le \sum_{l=1}^m
P\biggl(\left. |H_{n,k}(f_{p_l(\xi^{(n)}(\oo))}|G,V_1,V_2)|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!}\right| \\
&\qquad\qquad\qquad\qquad
\xi^{(j,\pm1)}_{l},\,1\le l\le n,\,1\le j\le k\biggr)(\oo)
\endalign
$$
for almost all~$\oo$. The last inequality together with~(17.22)
and the inequality $m=\max(1,D\delta^{-L})\le 1+D
\(\frac{2^{4k+3}k!}{A^2\sigma^{2(k+1)}}\)^L$ imply relation~(17.23).

It follows from relations (17.16) and (17.23) that
$$
\align
&P\(\sup_{f\in\Cal F}|H_{n,k}(f|G,V_1,V_2)|
>\frac{A^2n^{2k}\sigma^{2(k+1)}}{2^{4k+1}k!}\)\le
2^{k+1}e^{-A^{2/3k}n\sigma^2}\\
&\qquad + C
\(1+D\(\frac{2^{4k+3}k!}{A^2\sigma^{2(k+1)}}\)^L\)
e^{-2^{-(6+2/k)}A^{2/3k}n\sigma^2}
\quad\text{if }A\ge A_0
\endalign
$$
for all $V_1,V_2\subset\{1,\dots,k\}$ and diagram $G\in\Cal G$
such that $|e(G)|\le k-1$. This inequality implies that
relation~(17.11) holds also in the case $|e(G)|\le k-1$ if the
constants $A_0$ is chosen sufficiently large in Proposition~15.4,
and we this completes the proof of Proposition~15.4. To prove
relation~(17.11) in the case $|e(G)|\le k-1$ we still have to
show that
$D(\frac{2^{4k+3}k!}{A^2\sigma^{2(k+1)}})^L\le e^{\const n\sigma^2}$
if $A>A_0$ with a sufficiently large~$A_0$, since this implies that
the second term at the right-hand of our last estimation is not too
large.

This follows from the inequality $n\sigma^2\ge L\log n+\log D$
which implies that
$$
\(\frac{2^{4k+3}k!}{A^2\sigma^{2(k+1)}}\)^L\le
\(\frac{n^{(k+1)}}{(2n\sigma^2)^{(k+1)}}\)^L\le e^{(k+1)L\log n}
\le e^{{(k+1)}n\sigma^2}
$$
if $A_0$ is sufficiently large, and $D=e^{\log D}\le e^{n\sigma^2}$.

\beginsection 18. An overview of the results in this work.

I discuss briefly the problems investigated in this work,
recall some basic results related to them, and also give some
references. I also write about the background of these problems
which may explain the motivation for their study.

I met the main problem considered in this work when I tried to
adapt the method of proof of the central limit theorem for
maximum-likelihood estimates to some more difficult questions about
so-called non-parametric maximum likelihood estimate problems.
The Kaplan--Meyer estimate for the empirical distribution function
with the help of censored data investigated in the second section
is such a problem. It is not a maximum-likelihood estimate in the
classical sense, but it can be considered as a non-parametric
maximum likelihood estimate. In the estimation of the empirical
distribution function with the help of censored data we cannot
apply the classical maximum likelihood method, since in the
solution of this problem we have to choose our estimate from a
too large class of distribution functions. The main problem is
that there is no dominating measure with respect to which all
candidates which may appear as our estimate have a density
function. A natural way to overcome this difficulty is to choose
a smaller class of distribution functions, to compare the
probability of the appearance of the sample we observed with
respect to all distribution functions of this class and to
choose that distribution function as our estimate for which this
probability takes its maximum.

The Kaplan--Meyer estimate can be found on the basis of the above
principle in the following way: Let us estimate the distribution
function $F(x)$ of the censored data simultaneously together with
the distribution function $G(x)$ of the censoring data. (We have a
sample of size $n$ and know which sample elements are censored and
which are censoring data.) Let us consider the class of such pairs
of estimates $(F_n(x),G_n(x))$ of the pair $(F(x),G(x))$ for which
the distribution function $F_n(x)$ is concentrated in the censored
sample points and the distribution function $G_n(x)$ is
concentrated in the censoring sample points; more precisely, let us
also assume that if the largest sample point is a censored point,
then the distribution function $G_n(x)$ of the censoring data takes
still another value which is larger than any sample point, and if
it is a censoring point then the distribution function $F_n(x)$ of
the censored data takes still another value larger than any sample
point. (This modification at the end of the definition is needed,
since if the largest sample points is from the class of censored
data, then the distribution $G(x)$ of the censoring data in this
point must be strictly less than~1, and if it is from the class of
censoring data, then the value of the distribution function $F(x)$
of the censored data must be strictly less than~1 in this point.)
Let us take this class of pairs of distribution functions
$(F_n(x),G_n(x))$, and let us choose that pair of distribution
functions of this class as the (non-parametric maximum likelihood)
estimate with respect to which our observation has the greatest
probability.

The above extremal problem for the pairs of distribution functions
$(F_n(x),G_n(x))$ can be solved explicitly, (see~[25]), and it
yields the estimate of $F_n(x)$ written down in formula~(2.3).
(The function $G_n(x)$ satisfies a similar relation, only the
random variables~$X_j$ and~$Y_j$ and the events $\delta_j=1$ and
$\delta_j=0$ have to be replaced in it.) Then, as I have indicated,
a natural analog of the linearization procedure in the proof of
the central limit theorem for the classical maximum likelihood
estimate works also in this case, and there is only
one really hard part of the proof. We have to show that the
linearization procedure gives a small error. The estimation of
this error led to the problem about a good estimate on the tail
distribution of the integral of an appropriate function of two
variables with respect to the product of a normalized empirical
measure with itself. Moreover, as a more detailed investigation
showed, we actually need the solution of a more general problem
where we have to bound the tail distribution of the supremum of
a class of such integrals. The main subject of this work is to
solve the above problems in a more general setting, to estimate
not only two-fold, but also $k$-fold random integrals and the
supremum of such integrals for an appropriate class of kernel
functions with respect to a normalized empirical distribution
for all~$k\ge1$.

The proof of the limit theorem for the Kaplan--Meyer estimate
explained in this work applied the explicit form of this estimate.
It would be interesting to find such a modification of this proof
which only exploits that the Kaplan--Meyer estimate is the solution
of an appropriate extremal problem. We may expect that such a proof
can be generalized to a general result about the limit behaviour
for a wide class of non-parametric maximum likelihood estimates.
Such a consideration is behind the remark of Richard Gill I quoted
at the end of Section~2.

A detailed proof together with a sharp estimate on the speed of
convergence for the limit behaviour of the Kaplan--Meyer
estimate based on the ideas presented in Section~2 is given
in paper~[38]. Paper~[39] explains more about its background, and
it also discusses the solution of some other non-parametric maximum
likelihood problems. The results about multiple integrals with
respect to a normalized empirical distribution function needed in
these works were proved in~[30]. These results were satisfactory
for the study in~[38], but they also have some drawbacks. They do
not show that if the random integrals we are considering have
small variances, then they satisfy better estimates. Beside this,
if we consider the supremum of random integrals of an appropriate
class of functions, then these results can be applied only in
very special cases. Moreover, the method of proof of~[30] did not
allow a real generalization of these results, hence I had to find
a different approach when tried to generalize them.

I do not know of other works where the distribution of multiple
random integrals with respect to a normalized empirical distribution
is studied. On the other hand, there are some works where the
distribution of (degenerate) $U$-statistics is investigated. The
most important results obtained in this field are contained in the
book of de la Pe\~na and Gin\'e {\it Decoupling, From Dependence to
Independence}\/~[7]. The problems about the behaviour of degenerate
$U$-statistics and multiple integrals with respect to a normalized
empirical distribution function are closely related, but the
explanation of their relation is far from trivial. The main
difference between them is that integration with respect to
$\mu_n-\mu$ instead of the empirical distribution $\mu_n$ means
some sort of normalization, while this normalization is missing
in the definition of $U$-statistics. I return to this question
later.

The main part of this work starts at Section~3. A general overview
of the results without the hard technical details can be found
in~[33].

First the estimation of sums of independent random variables
or one-fold random integrals with respect to a normalized empirical
distribution and the supremum of such expressions is investigated
in Sections~3 and~4. This question has a fairly big literature. I
would mention first of all the books {\it A course on empirical
processes}\/~[11], {\it Real Analysis and Probability}\/~[12] and
{\it Uniform Central Limit Theorems}\/~[13] of R.~M.~Dudley.
These books contain a much more detailed description of the
empirical processes than the present work together with a lot of
interesting results.

Section~3 deals with the tail behaviour of sums of independent and
bounded random variables with expectation zero. The proof of two
already classical results, Bernstein's and Bennett's inequalities
is given there. (Their proofs can be found e.g. in Theorem~1.3.2
of~[13] and~[5]). We are also interested in the question when they
give such an estimate which the central limit theorem suggests.
Actually, as it is explained in Section~3, Bennett's inequality
gives a bound suggested by a Poissonian approximation of partial
sums of independent random variables. Bernstein's inequality
provides an estimate suggested by the central limit theorem if the
variance of the sum we consider is not too small. (The results in
Section~3 explain this statement more explicitly.) If the variance
of the sum is too small, then Bennett's inequality provides a
slight improvement of Bernstein's inequality. Moreover, as
Example~3.3 shows, Bennett's inequality is essentially sharp in
this case.

The estimate on the tail distribution of a sum of independent random
variables is weak if this sum has a small variance. This means that
in this case the probability that the sum is larger than a given
value may be much larger than the (rather small) value suggested by
the central limit theorem. Such a behaviour may occur, because the
contribution of some unpleasant irregularities to this probability
may be non-negligible in the case of a small variance.

In the study of the supremum of sums of independent random variables
a good control is needed on the tail distribution of the (supremum
of) sums of independent random variables even if they have small
variance. The solution of this problem (and of its natural
multivariate version) turned out to be the hardest part of this
work. The results based on the similar behaviour of partial sums
and their Gaussian counterpart is not sufficient in this case,
some new ideas have to be applied. In the proof of sharp estimates
in this case we also use some kind of symmetrization arguments.
The last result of Section~3, Hoeff\-ding's inequality presented
in Theorem~3.4 is an important ingredient of these symmetrization
arguments. It is also a classical result whose proof can be found
for instance in~[23].

Section~4 contains the one-variate version of our main result
about the supremum of the integrals of a class $\Cal F$ of
functions with respect to a normalized empirical measure together
with an equivalent statement about the tail distribution of the
supremum of a class of random sums defined with the help of a
sequence of independent and identically distributed random
variables and a class of functions $\Cal F$ with some nice
properties. These results are given in Theorems~4.1 and~$4.1'$.
Also a Gaussian version of them is presented in Theorem~4.2 about
the distribution of the supremum of a Gaussian random field with
some appropriate properties. The content of these results can be
so interpreted that if we take the supremum of random integrals
or of random sums determined by a nice class of functions $\Cal F$
in the way  described in Section~4, then the tail distribution of
this supremum satisfies an almost as good estimate as the `worst
element' of the random variables taking part in this supremum. I
also discussed a result in Example~4.3 which shows that some rather
technical conditions of Theorem~4.1 cannot be omitted.

The most important condition in Theorem~4.1 was that the class of
functions $\Cal F$ we considered in it is $L_2$-dense. This
property was introduced before the formulation of this result.
One may ask whether we can introduce different classes of
functions in Theorem~4.1 and prove with their help better results.
It is worth mentioning that Talagrand proved results similar to
Theorem~4.1 for different classes of functions~$\Cal F$ in his
book~[52]. These classes of functions are very different of
ours, and Talagrand's results seem to be incomparable with ours.
I return to this question later.

In the above mentioned results we have imposed the condition that
the class of functions~$\Cal F$ or what is equivalent, the set of
random variables whose supremum we estimate is countable. In the
proofs this condition is really exploited. On the other hand, in
some important applications we also need results about the
supremum of a possibly non-countable set of random variables.
To handle such cases I introduced the notion of countably
approximable classes of random variables and proved that in the
results of this work the condition about countability can be
replaced by the weaker condition that the supremum of countably
approximable classes is taken. R.~M.~Dudley worked out a different
method to handle the supremum of possibly non-countably many
random variables, and generally his method is applied in the
literature. The relation between these two methods deserves
some discussion.

Let us first recall that if a class of random variables $S_t$,
$t\in T$, indexed by some index set $T$ is given, and a set $A$ is
measurable with respect to the $\sigma$-algebra generated by the
random variables $S_t$, $t\in T$, then there exists a countable
subset $T'=T'(A)\subset T$ such that the set $A$ is measurable also
with respect to the smaller $\sigma$-algebra generated by the random
variable $S_t$, $t\in T'$. Beside this, if the finite dimensional
distributions of the random variables $S_t$, $t\in T$, are given,
then by the results of classical measure theory the probability
of the events measurable with respect to the $\sigma$-algebra
generated by these random variables $S_t$, $t\in T$, is also
determined. But we cannot get the probability of all events we
are interested in such a way. In particular, if $T$ is a
non-countable set, then the events
$\left\{\oo\colon\;\supp_{t\in T}S_t(\oo)>u\right\}$ are
non-measurable with respect to the above $\sigma$-algebra, and
generally we cannot speak of their probabilities. To overcome
this difficulty Dudley worked out a theory which enabled him to
work also with outer measures. His theory is based on some
rather deep results of the analysis. It can be found for
instance in his book~[13].

I restricted my attention to such cases when after the completion of
the probability measure $P$ we can also speak of the real (and not
only outer) probabilities $P\(\supp_{t\in T}S_t>u\)$. I tried to
find appropriate conditions under which these probabilities really
exist. More explicitly, we are interested in the case when for all
$u>0$ there exists some set $A=A_u$ measurable with respect to the
$\sigma$-algebra generated by the random variables $S_t$, $t\in T$,
such that the symmetric difference of the sets $A_u$ and
$\left\{\oo\colon\;\supp_{t\in T}S_t(\oo)>u\right\}$ is contained
in a set measurable with respect to the $\sigma$-algebra generated
 by the random variables $S_t$, $t\in T$, which has probability
zero. In such a case the probability $P\(\supp_{t\in T}S_t>u\)$
can be defined as $P(A_u)$. This approach led me to the definition
of countable approximable classes of random variables. If this
property holds, then we can speak about the probability of the
event that the supremum of the random variables we are interested
in is larger than some fixed value. I proved a simple but
useful result in Lemma~4.4 which provides a condition for the
validity of this property. In Lemma~4.5 I proved with its help
that an important class of functions is countably approximable. It
seems that this property can be proved for many other interesting
classes of functions with the help of Lemma~4.4, but I did not
investigate this question in more detail.

The problem we met here is not an abstract, technical difficulty.
Indeed, the distribution of such a supremum can become different
if we modify each random variable on a set of probability zero,
although the finite dimensional distributions of the random
variables we consider remain the same after such an operation.
Hence, if we are interested in the probability of the supremum
of a non-countable set of random variables with described finite
dimensional distributions we have to describe more explicitly
which version of this set of random variables we consider. It
is natural to look for such an appropriate version of the
random field $S_t$, $t\in T$, whose `trajectories' $S_t(\oo)$,
$t\in T$, have nice properties for all elementary events
$\oo\in\Omega$. Lemma~4.4 can be interpreted as a result in
this spirit. The condition given for the countable
approximability of a class of random variables at the end of
this lemma can be considered as a smoothness condition about
the `trajectories' of the random field we consider. This
approach shows some analogy to some important problems in the
theory of stochastic processes when a regular version of a
stochastic process is considered and the smoothness properties
of its trajectories are investigated.

In our problems the version of the set of random variables $S_t$,
$t\in T$, we shall work with appears in a simple and natural
way. In these problems we have finitely many random variables
$\xi_1,\dots,\xi_n$ at the start, and all random variables
$S_t(\oo)$, $t\in T$, we are considering can be defined individually
for each $\oo$ as a functional of these random variables
$\xi_1(\oo),\dots,\xi_n(\oo)$. We take the version of the random
field $S_t(\oo)$, $t\in T$, we get in such a way and want to show
that it is countably approximable. In Section~4 this property is
proved in an important model, probably in the most important model
in possible applications we are interested in. In more complicated
situations when our random variables are defined not as a
functional of finitely many sample points, for instance in the case
when we define our set of random variables by means of integrals
with respect to a Gaussian random field it is harder to find the right
regular version of our sets of random variables. In this case the
integrals we consider are defined only with probability~1, and it
demands some extra work to find their right version. But in
the problems we study in this work our approach is satisfactory for
our purposes, and it is simpler than that of Dudley; we do not have
to follow his rather difficult technique. On the other hand, I must
admit that I do not know the precise relation between the approach
of this work and that of Dudley.

In Section~4 the notion of $L_p$-dense classes, $1\le p<\infty$,
also has been introduced. The notion of $L_2$-dense classes
appeared in the formulation Theorems~4.1 and~$4.1'$. It can be
considered as a version of the $\e$-entropy, discussed at many
places in the literature. On the other hand, there seems to be no
standard definition of the $\e$-entropy. The term of $L_2$-dense
classes seemed to be the appropriate object to work with in
this work. To apply the results related to $L_2$-dense classes we
also need some knowledge about how to check this property in
concrete models. For this goal I discussed here
Vapnik--\v{C}ervonenkis classes, a popular and important notion of
modern probability theory. Several books and papers, (see e.g. the
books~[13], [44],~[53] and the references in them) deal with this
subject. An important result in this field is Sauer's lemma,
(Lemma~5.1) which together with some other results, like Lemma~5.3
imply that several interesting classes of sets or functions are
Vapnik--\v{C}ervonenkis classes.

I put the proof of these results to the  Appendix, partly because
they can be found in the literature, partly because in this work
Vapnik--\v{C}ervonenkis classes play a different and less important
role than at other places. Here Vapnik--\v{C}ervonenkis classes are
applied to show that certain classes of functions are $L_2$-dense.
A result of Dudley formulated in Lemma~5.2 implies that a
Vapnik--\v{C}ervonenkis class of functions with absolute value
bounded by a fixed constant is an $L_1$, and as a consequence, also
an $L_2$-dense class of functions. The proof of this important
result which seems to be less known even among experts of this
subject than it would deserve is contained in the main text.
Dudley's original result was formulated in the special case when
the functions we consider are indicator functions of some sets.
But its proof contains all important ideas needed in the proof of
Lemma~5.2.

Theorem 4.2, which is the Gaussian counterpart of Theorems~4.1
and~$4.1'$ is proved in Section~6 by means of a natural and
important technique, called the chaining argument. This means the
application of an inductive procedure, in which an appropriate
sequence of finite subsets of the original set of random variables
is introduced, and a good estimate is given on the supremum of
the random variables in these subsets by means of an inductive
procedure. The subsets became denser subsets of the original set
of the random variables at each step of this procedure. This
chaining argument is a popular method in certain investigation.
It is hard to say with whom to attach it. Its introduction may
be connected to some works of R.~M.~Dudley. It is worth mentioning
that Talagrand~[52] worked out a sharpened version of it which
yields in the study of certain problems a sharper and more useful
estimate. But it seems to me that in the study of the problems of
this work it does not provide a real improvement.

Theorem 4.2 can be proved by means of the chaining argument, but
this method is not strong enough to supply a proof of Theorem~4.1.
The chaining argument provides only a weak estimate in this case,
because there is no good estimate on the probability that a sum of
independent random variables is greater than a prescribed value if
these random variables have too small variances. As a consequence
the chaining argument supplies a much weaker estimate than the result
we want to prove under the conditions of Theorem~4.1. Lemma~6.1
contains the result the chaining argument yields under these
conditions. In Section~6 still another result, Lemma~6.2 is
formulated. It can be considered as a special case of Theorem~4.1
where only the supremum of partial sums with small variances is
estimated. It is also shown that Lemmas~6.1 and~6.2 together imply
Theorem~4.1. The proof is not difficult, despite of some
non-attractive details. It has to be checked that the parameters
in Lemmas~6.1 and~6.2 can be fitted to each other.

Lemma~6.2 is proved in Section~7. It is based on a symmetrization
argument. This proof applies the ideas of a paper of Kenneth
Alexander~[2], and although its presentation is different from
Alexander's approach, it can be considered as a version of his
proof.

A similar problem should also be mentioned at this place.
M.~Talagrand wrote a series of papers about concentration
inequalities, (see e.g. [50] or [51]), and his research was also
continued by some other authors. I would mention the works of
M.~Ledoux~[27] and P.~Massart~[41]. Concentration inequalities
give a bound about the difference between the supremum of a set of
appropriately defined random variables and the expected value of
this supremum. They express how strongly this supremum is
concentrated around its expected value. Such results are closely
related to Theorem~4.1, and the discussion of their relation
deserves some attention. A typical concentration inequality is
the following result of Talagrand~[51].

\medskip\noindent
{\bf Theorem 18.1. (Theorem of Talagrand).} {\it Consider $n$
independent and identically distributed random variables
$\xi_1,\dots,\xi_n$  with values in some measurable space
$(X,\Cal X)$. Let $\Cal F$ be some countable family of
real-valued measurable functions of $(X,\Cal X)$ such that
$\|f\|_\infty\le b<\infty$ for every $f\in\Cal F$. Let
$Z=\supp_{f\in\Cal F}\summ_{i=1}^n f(\xi_i)$ and
$v=E(\supp_{f\in\Cal F}\summ_{i=1}^n f^2(\xi_i))$. Then for
every positive number~$x$,
$$
P(Z\ge EZ+x)\le K\exp\left\{-\frac 1{K'}\frac
xb\log\(1+\frac{xb}v\)\right\}
$$
and
$$
P(Z\ge EZ+x)\le K\exp\left\{-\frac{x^2}{2(c_1v+c_2bx)}\right\},
$$
where $K$, $K'$, $c_1$ and $c_2$ are universal positive constants.
Moreover, the same inequalities hold when replacing $Z$ by $-Z$.}

\medskip
Theorem~18.1 yields, similarly to Theorem~4.1, an estimate about
the distribution of the supremum for a class of sums of independent
random variables. It can be considered as a generalization of
Bernstein's and Bennett's inequalities when the distribution of the
supremum of partial sums (and not only the distribution of one
partial sum) is estimated. A remarkable feature of this
result is that it assumes no condition about the structure of the
class of functions $\Cal F$ (like the condition of $L_2$-dense
property of the class $\Cal F$ imposed in Theorem~4.1.) On the
other hand, the estimates in Theorem~18.1 contain the quantity
$EZ=E\(\supp_{f\in\Cal F}\summ_{i=1}^n f(\xi_i)\)$. Such an
expectation of some supremum appears in all concentration
inequalities. As a consequence, they are useful only if we can
bound the expected value of the supremum we want to estimate. This
is a hard question in the general case. There is a paper~[16] which
provides a useful estimate about the expected value of the
supremum of random sums under the conditions of Theorem~4.1.
But I preferred a direct proof of this result. Let me remark
that because of the above mentioned concentration inequality the
condition $u\ge\const\sigma\log^{1/2}\frac2\sigma$
with some appropriate constant which cannot be dropped from
Theorem~4.1 can be interpreted so that under the conditions of
Theorem~4.1 $\const\sigma\log^{1/2}\frac2\sigma$ is an upper bound
for the expected value of the supremum we are studying.

It is also worth mentioning Talagrand's work~[52] which
contains several interesting results similar to Theorem~4.1.
But despite their formal similarity, they are essentially
different from the results of this work. This difference
deserves some special discussion.

Talagrand proved in~[52] by working out a more refined, better
version of the chaining argument a sharp upper bound for the
expected value $E\sup\limits_{t\in T}\xi_t$ of the supremum of
countably many (jointly) Gaussian random variable with zero
expectation. This result is sharp. Indeed, Talagrand proved also
a lower bound for this expected value, and the proportion of his
upper and lower bound is bounded by a universal constant. He
also gave by applying similar arguments an upper bound for
$E\sup\limits_{f\in\Cal F}\sum\limits_{k=1}^N f(\xi_k)$
in Proposition~2.7.2 of his book, where $\xi_1,\dots,\xi_N$ is a
sequence of independent, identically distributed random variables
with some known distribution~$\mu$, and $\Cal F$ is a class of
functions with some nice properties. Then he proved in Chapter~3
some estimates with the help of this result for certain models
which solved some problems that could not be solved with the
help of the original version of the chaining argument.

Talagrand investigated in his book~[52] the expected value of the
supremum of partial sums, while we gave an estimate on its tail
distribution. But this is not a great difference. Talagrand's
results also give an estimate on the tail distribution of the
supremum by means of concentration inequalities, and actually his
proofs also provide a direct estimate for the tail distribution
we are interested in without the application of these results.
The main difference between the two works is that Talagrand's
method gives a sharp estimate for different classes of
functions~$\Cal F$.

Talagrand could prove sharp results in such cases when the class
of functions $\Cal F$ for which the supremum is taken consists of
smooth functions. An example for such classes of function which he
thoroughly investigated is the class of Lipschitz~1 functions. On
the other hand we can give sharp results in such cases when
$\Cal F$ consists of non-smooth functions. (See Example~5.5.)

This difference in the conditions of the results in these two
books is not a small technical detail. Talagrand exploited in
his proof that he worked with such classes of functions~$\Cal F$
from which he could select such a subclass of functions of
relatively small cardinality which is dense in $\Cal F$ in the
supremum norm. He needed this property, because this enabled
him to get sharp estimates on the tail distribution of the
differences of functions he had to work with by means of the
Bernstein's inequality. He needed such estimates to apply (a
refined version of) the chaining argument. On the other hand,
we considered such classes of functions $\Cal F$ which may have
no small subclasses which are dense in $\Cal F$ in the supremum
norm. I would characterize the difference between the results
of the two works in the following way. Talagrand proved the
sharpest possible estimates which can be obtained by a
refinement of the chaining argument, while our main problem
was to get sharp estimates also in such cases when the
chaining argument does not work.

\medskip
The main results of this work are presented in Section~8. A weaker
version of Theorem~8.3 about an estimate of the distribution of a
degenerate $U$-statistic was first proved in a paper of Arcones and
Gin\'e in~[3]. The result of Theorem~8.3 in the present form is
proved in my paper~[36]. Its version about multiple integrals with
respect to a normalized empirical measure formulated in Theorem~8.1
is proved in~[32]. This paper contains a direct proof. On the other
hand, Theorem 8.1 can be derived from Theorem~8.3 by means of
Theorem~9.4 of this paper. Theorem 8.5 is the natural Gaussian
counterpart of Theorem~8.3. The limit theorem about degenerate
$U$-statistics, Theorem~10.4 (and its version about limit theorems
for multiple integrals with respect to normalized empirical
measures, presented in Theorem~$10.4'$ of Appendix~C) was
discussed in this work to explain better the relation between
degenerate $U$-statistics (or multiple integrals with respect
to normalized empirical measures) and multiple Wiener--It\^o
integrals. A proof of this result based on similar ideas as that
discussed here can be found in~[14]. Theorem~6.6 of my lecture
note~[29] contains such a weakened version of Theorem~8.5 which
does not take into account the variance of the random integral.

Example~8.7 is a natural supplement of Theorem~8.5. It shows
that the estimate of Theorem~8.5 is sharp if only the variance
of a Wiener--It\^o integral is known. At the end of Section~13
I also mentioned the results of papers~[1] and~[26] without proof
which also have some relation to this problem. I discussed
mainly the content of~[26] and explained its relation to some
results discussed in this work. The proof of these papers
apply a method different of those of this work. It would be
interesting to prove them with the methods discussed here.
These papers contain such a refinement of Theorems~8.5 and~8.3
respectively whose estimates depend on some other rather
complicated quantities. In some cases they supply a better
estimate. On the other hand, in the problems discussed here
they have a restricted importance because their conditions are
hard to check.

Theorems~8.2 and~8.4 yield an estimate about the supremum of
(degenerate) $U$-statistics or of multiple random integrals with
respect to a normalized empirical measure when the class of kernel
functions in these $U$-statistics or random integrals satisfy some
conditions. They were proved in my paper~[34]. Earlier Arcones
and Gin\'e proved a weaker form of this result in paper~[4], but
their work did not help in the proof of the results of this note.
They were based on an adaptation of Alexander's method to the
multivariate case. Theorem~8.6 contains the natural Gaussian
counterpart of Theorems~8.2 and~8.4.

Example~8.8 in Section~8 shows that the condition
$u\le\const n\sigma^3$ imposed in Theorem~8.3 in the case $k=2$
cannot be dropped. The paper of Arcones and Gin\'e~[3] contains
another example explained by Talagrand to the authors of that
paper which also has a similar consequence. But that example
does not provide such an explicit comparison of the upper and
lower bound on the probability investigated in Theorem~8.3 as
Example~8.8. Similar examples could be constructed for all $k\ge1$.

Example 8.8 shows that at high levels only a very weak (and from
practical point of view not really important) improvement of the
estimation on the tail distribution of degenerate $U$-statistics
is possible. But probably there exists a multivariate version of
Bennett's inequality, i.e. of  Theorem~3.2 which provides such
an estimate. Moreover, there is some hope to get a similar
strengthened form of Theorems~8.2 and~8.4 (or of Theorem~4.2 in
the one-dimensional case). This question is not investigated in
the present work.

Section 9 deals with the properties of $U$-statistics. Its first
result, Theorem~9.1, is a rather classical result. It is the
so-called Hoeffding decomposition of $U$-statistics to the sum of
degenerate statistics. Its proof first appeared in the paper~[22],
but it can be found at many places. The explanation of this work
contains some ideas similar to~[49]. I tried to explain that
Hoeffding's decomposition is the natural multivariate version of
the (trivial) decomposition of sums of independent random variables
to sums of independent random variables {\it with expectation
zero}\/ plus the sum of the expectations of the original random
variables. Moreover, even the proof of the Hoeffding's
decomposition shows some similarity to this simple decomposition.

Theorem~9.2 and Proposition~9.3 can be considered as a continuation
of the investigation of the Hoeffding's decomposition in Theorem~9.1.
They tell how the properties of the kernel function of the original
$U$-statistic are inherited in the properties of the kernel
functions of the degenerate $U$-statistics taking part in its
Hoeffding decomposition. In several applications of Hoeffding's
decomposition we need such results.

The last result of Section~9, Theorem~9.4, enables us to reduce the
estimation of multiple random integrals with respect to normalized
empirical measures to the estimation of degenerate $U$-sta\-tis\-tics.
This result is a version of Hoeffding's decomposition, where
multiple integrals with respect to a normalized empirical
distribution are decomposed to the sum of degenerate $U$-statistics.
Multiple random integrals with respect to a normalized empirical
measure can be simply written as sums of $U$-statistics, and
by applying the Hoeffding decomposition for each term of these sums
we get the desired decomposition. Theorem~9.4 yields the result
we get in such a way. This formula is very similar to the original
Hoeffding decomposition. The main difference between them is that
the coefficients of the degenerate $U$-statistics in the
decomposition of Theorem~9.4 are relatively small. The cancellation
effect caused by integration with respect to a {\it normalized}\/
empirical measure is reflected in the appearance of small
coefficients in the decomposition given in Theorem~9.4.
Theorem~9.4 was proved in~[34]. The same proof is given in this
note, but some calculations are worked out in more detail.

Theorem~8.1 can be derived from Theorem~8.3 and Theorem~8.2 from
Theorem~8.4 by means of Theorem~9.4. The proof of the latter
results is simpler. The results of Sections 10--12 contain the
results needed in the proof of Theorem~8.3 and its Gaussian
counterpart Theorems~8.5 and~8.7. The proof of these results is
based on good estimates of high moments of degenerate
$U$-statistics and multiple Wiener--It\^o integrals. The
classical proof of the one-variate counterparts of these results is
based on a good estimate of the moment generating function. This
method was replaced by the estimate of high moments, because the
moment generating function of a $k$-fold Wiener--It\^o integral is
divergent for $k\ge3$, and this property is also reflected in the
behaviour of degenerate $U$-statistics. On the other hand, good
estimates on high moments can replace the estimate of the moment
generating function. A good estimate can be given for all moments
of a Wiener--It\^o integral, while we have a good estimate only on
not too high moments of degenerate $U$-statistics. This has the
consequence that we can give a good estimate on the tail
distribution of degenerate $U$-statistic only for not too large
values.

I know of two deep methods to study high moments of multiple
Wiener--It\^o integrals. Both of them can be adapted to the study
of the moments of degenerate $U$-statistics. They deserve a more
detailed discussion.

The first one of them is called Nelson's inequality named after
Edward Nelson who published it in his paper~[43]. This inequality
simply implies Theorem~8.5 about multiple Wiener--It\^o integrals,
although with worse constants. Later Leonhard Gross discovered a
deep and useful generalization of this result which he
published in the work {\it Logarithmic Sobolev inequalities}\/~[19].
In that paper Gross compared two Markov processes with the same
infinitesimal operator but with possibly different initial
distribution, where the second Markov process had stationary
distribution. He could give a sharp bound on the Radon--Nikodym
derivative of the distribution of the first Markov process with
respect to the (stationary) distribution of the second Markov
process at all time~$T$ on the basis of the properties of the
infinitesimal operator of the Markov processes. With the help of
this result he could prove a more general form of Nelson's
inequality. In particular, his result may help to prove (a weaker
version of) Theorem~8.3 (with worse universal constants). Let me
also remark that Gross' method works not only in the study of
these problems, but in several hard problems of the probability
theory. (See e.g~[20] or~[27]). Nevertheless, in the present note
I applied a different method, because this seemed to be more
appropriate here.

I applied a method related to the names of Kyoshi It\^o and Roland
L'vovich Dobrushin. This is the theory of multiple Wiener--It\^o
integrals with respect to a white noise. This integral was
introduced in paper~[24]. It is useful, because every random
variable measurable with respect to the $\sigma$-algebra generated
by the Gaussian random variables of the underlying white noise with
finite second moment can be written as the sum of Wiener--It\^o
integrals of different order. Moreover, if only Wiener--It\^o
integrals of symmetric kernel functions are taken, then this
representation is unique. An important result, the so-called
diagram formula, formulated in Theorem~10.2, expresses products
of Wiener--It\^o integrals as a sum of such integrals. This result
which shows some similarity to the Feynman diagrams applied in the
statistical physics was proved in~[9]. Actually this paper discussed
a modified version of Wiener--It\^o integrals which is more
appropriate to study the action of shift operators for non-linear
functionals of a stationary Gaussian field. But these modified
 Wiener--It\^o integrals can be investigated in almost the same way
as the original ones. The diagram formula has a simple consequence
formulated in Corollary of Theorem~10.2 of this note. It enables us
to calculate the expectation of products of Wiener--It\^o integrals,
in particular it yields an explicit formula about the moments of
a Wiener--It\^o integral. This result was applied in the proof of
Theorem~8.5, i.e.\ in the estimation of the tail-distribution of
Wiener--It\^o integrals. It\^o's formula for multiple Wiener--It\^o
integrals (Theorem~10.3) was proved in~[24].

The diagram formula has a natural and useful analog both for
degenerate $U$-statistics and multiple integrals with respect to a
normalized empirical measure. They enable us to express the product
of degenerate $U$-statistics and multiple integrals as the sum of
such expressions. These results enable us to adapt several useful
methods in the study of non-linear functionals of a Gaussian
random field to the study of non-linear functionals of normalized
empirical measures. A version of the diagram formula was proved
for degenerate $U$-statistics in~[36] and for multiple random
integrals with respect to a normalized empirical measures in~[32].
Let me remark that in the formulation of the result in the
work~[36] a different notation was applied than in the present
note. In that paper I wanted to formulate version of the diagram
formula for $U$-statistics with the help of such diagrams which
appear in the classical form of diagram formula presented for
Wiener--It\^o integrals. I could do this only in a somewhat
artificial way. In this work I formulated this result by
introducing first more general diagrams which may contain some
chains. The formulation of the result with the help of such more
general diagrams seems to be more natural. Let me also remark that
the study of results similar to the diagram formula for
Wiener--It\^o integrals did not get such an attention in the
literature as it would deserve in my opinion. I know only of one
work where such questions were investigated. It is the paper of
Surgailis~[46], where a version of the diagram formula is proved
for Poissonian integrals. The Corollary of Theorem~11.2 is of
special interest for us, because it enables us to prove such
moment estimates which are useful in the proof of Theorem~8.3.

It is worth mentioning that the problems about Wiener--It\^o
integrals are closely related to the study of Hermite polynomials
or to their multivariate version, to the so-called Wick polynomials.
(See e.g.~[29] or~[40] for the definition of Wick polynomials.)
Appendix~C contains the most important properties of Hermite
polynomials needed in the study of Wiener--It\^o integrals. In
particular, it contains the proof of Proposition~C2 which states
that the set of all Hermite polynomials is a complete orthogonal
system in the Hilbert space of the functions square integrable
with respect to the Gaussian distribution. This result can be
found for instance in Theorem~5.2.7 of~[48]. In the present proof
I wanted to show that this result is closely related to the
so-called moment problem, i.e.\ to the question when a
distribution is determined by its moments uniquely. This method,
with some refinement, can be applied to prove some
generalizations of Proposition~C2 about the completeness of
orthogonal polynomials with respect to more general weight
functions.

It\^o's formula creates a relation between Wiener--It\^o integrals
and Hermite polynomials. The results about multiple Wiener--It\^o
integrals have their analogs for Wick polynomials. Thus for
instance there is a diagram formula for the product of Wick
polynomials which also has some interesting generalizations.
Such questions are studied both in probability theory and
statistical physics, see~[40] and~[45]. The relation between
Wiener--It\^o integrals and Hermite  polynomials also has a
natural counterpart in the study of other multiple random
integrals. The so-called Appell polynomials, (see~[47]),
appeared in such a way.

Theorems~8.3,~8.5 and~8.7 were proved on the basis of the results
in Sections 10--12 and in Section~13. Section~13 also contains
the proof of a multivariate version of Hoeffding's inequality,
formulated in Theorem~13.3. This result is needed in the
symmetrization argument applied in the proof of Theorem~8.4. A
weaker version of it (an estimate with a worse constant in the
exponent) which would be satisfactory for our purposes would
simply follow from a classical result, called Borell's inequality.
But since this result is not discussed in this note, and I was
interested in a proof which yields the best estimate in the
exponent of this estimate I have chosen another proof, given
in~[35] which is based on the results of Sections~10--12.
Later I have learned that this estimate is contained in an
implicit form also in the paper~[6] of A.~Bonami.

Sections 14--17 are devoted to the proof of Theorems~8.4 and~8.6.
They are based on a similar argument as their one-variate
counterparts, Theorems~4.1 and~4.2. The proof of Theorem~8.6
about the supremum of Wiener--It\^o integrals is based, similarly
to the proof of Theorem~4.2 on the chaining argument. In the
proof of Theorem~8.4, the chaining argument yields only a weaker
result formulated in Proposition~14.1 which helps to reduce
Theorem~8.4 to the proof of Proposition~14.2. In the one-variate
case a similar approach was applied. In that case the proof of
Theorem~4.1 was reduced to that of Proposition~6.2 by means of
Proposition~6.1. The next step in the proof of Theorem~8.6 has
no one-variate counterpart. The notion of so-called decoupled
$U$-statistics was introduced, and Proposition~14.2 was reduced
to a similar result about decoupled $U$-statistics formulated
in Proposition~$14.2'$.

The adjective `decoupled' in the expression decoupled $U$-statistic
refers to the fact that it is such a version of a $U$-statistic
where independent copies of a sequence of independent and identically
distributed random variables are put into different coordinates of
the kernel function of the $U$-statistic. Their study is a popular
subject of some mathematicians. In particular, the main subject of
the book~[7] is a comparison of the properties of $U$-statistics
and decoupled $U$-statistics. A result of de la Pe\~na and
Montgomery--Smith~[8] formulated in Theorem~14.3 helps in reducing
some problems about $U$-statistics to a similar problem about
decoupled $U$-statistics. In this lecture note the proof of
Theorem~14.3 is given in Appendix~D. It follows the argument of
the original proof, but several steps are worked out in detail
where the authors gave only a very short explanation. Paper~[8]
also contains some kind of converse results to~Theorem~14.3, but
as they are not needed in the present work, I omitted their
discussion.

Decoupled $U$-statistics behave similarly to the original
$U$-statistics. Beside this, some symmetrization arguments
becomes considerably simpler if we are working with decoupled
$U$-statistics instead of the original $U$-statistics. This can
be exploited in some investigations. For example the proof of
Proposition~$14.2'$ is simpler than a direct proof of
Proposition~14.2. On the other hand, Theorem~14.3 enables us
to reduce the proof of Proposition~14.2 to that of
Proposition~$14.2'$, and we have exploited this possibility.

%The above example shows why the application of the symmetrization
%method and the introduction of degenerate $U$-statistics is useful
%in the study of certain problems. But the application of the
%symmetrization method has its price. Generally, if a (usual or
%decoupled) $U$-statistic is estimated with its help, then this
%$U$-statistic is replaced during the estimation by a larger
%$U$-statistic, (by a $U$-statistic with larger variance), and as a
%consequence we cannot get sharp estimates. In
%particular, the decoupling technique and the symmetrization
%argument made with its help can provide only the proof of a
%weakened version of Theorem~8.3 with worse universal constants.
%This is the reason why a different proof of this result was given
%in this work. (In an earlier version of this Lecture Note~[37]
%I described the proof of a weakened version of Theorem~8.3 by means
%of a symmetrization argument.)

The proof of Theorem~8.4 was reduced to that of Proposition~$14.2'$
in Section~14. Sections 15--17 deal with the proof of this result.
It was proved in my paper~[34]. The proof is similar to that of
its one-variate version, Proposition~6.2, but some additional
difficulties have to be overcome. The main difficulty appears when
we want to find the multivariate analog of the symmetrization
argument which could be carried out by means of the Symmetrization
Lemma, Lemma~7.1 and Lemma~7.2 in the one-variate case.

In the multivariate case Lemma~7.1 is not sufficient for us. We
work instead of it with a  generalized version of this result,
formulated in Lemma~15.2. The proof of Lemma~15.2 is not hard.
The real difficulty arises when we want to apply it in the proof
of Proposition~$14.2'$. We have to check formula~(15.3), and this
means in this case a non-trivial estimation of some complicated
conditional probabilities. This is the hardest part of the proof
of Proposition~$14.2'$.

Proposition $14.2'$ was proved by means of an inductive procedure
formulated in Proposition 15.3, which is the multivariate analog
of Proposition~7.3. A basic ingredient of both proofs was a
symmetrization argument. But while this symmetrization argument
could be simply carried out in the one-variate case, its
adaptation to the multivariate case in the proof of Theorem~15.3
was a most serious problem. To overcome this difficulty another
result was formulated in Proposition~15.4. Propositions~15.3
and~15.4 were proved simultaneously by means of an appropriate
inductive procedure. Their proofs were based on a refinement of
the arguments in the proof of Proposition~7.3. We also had to
apply Theorem~13.3, a multivariate version of Hoeff\-ding's
inequality, and some properties of the Hoeff\-ding decomposition
of $U$-statistics proved in Section~9.

