\magnification=1200
\hsize=16truecm
\input amstex
\TagsOnRight
\parskip=2pt plus1pt
\define\tR {R(t)}
\define\({\left(}
\define\){\right)}
\define\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi}
 
\centerline{\bf On the Tail Behavior of the Distribution Function of
Multiple}
\centerline{\bf Stochastic Integrals in Separable Metric Spaces}
\smallskip
\centerline{\it P\'eter Major$^1$, L\'{\i}dia Rejt\H{o},$^{1,2}$ }
\smallskip
\centerline{$^1$ Mathematical Institute of the Hungarian
Academy of Sciences, Budapest, Hungary}
\centerline{$^2$ Department of Mathematical Sciences,
University of Delaware,}
\centerline{Newark, Delaware, USA}
 
\medskip
{\narrower
\noindent{\bf Abstract.}\/
Let $\bar{\mu}_{n}(.)$ denote the empirical measure of a sample
of i.i.d. random variables with values on a separable metric space
$(X, {\Cal X})$ with distribution $\mu$. Define
$\mu_n(\cdot)=\sqrt{n}\(\bar\mu_n(\cdot)-\mu(\cdot)\)$
and consider the integrals
$$
\Cal I(t) = \int_{X_{t}} \int_{X} \dots
\int_{X} f(u_1,\dots,u_s) \mu_n(\,du_1) \dots \mu_n(\,du_s),
$$
\noindent where $X_s \subseteq X_t$ for all $s\le t$, $X_0=\emptyset$, $X_1=X$,
$\mu(X_t)=t$ and $f$ is a bounded measurable function which disappears
on the diagonal set of the product space $X^s$.
We give a sharp upper bound on the probability
$P\left(\sup\limits_{0\leq t \leq 1}\left|\Cal I(t) \right| \geq x\right)$.
This is a generalization of the result in paper [mp] where this estimate was
proved in the special case when the
space $X$ is the interval $[0,1]$, and the empirical distribution of a
sequence of independent and on $[0,1]$ uniformly distributed random
variables is considered.%\par}
\smallskip\noindent
{\bf Key words and phrases.}\/ Stochastic integrals, empirical
measure, separable metric space. \par}
 
\smallskip
\beginsection 1. Introduction
 
In this note we consider the empirical distribution of a sequence of
independent random variables on a separable metric space $(X,\Cal A)$,
take its natural standardization and bound the tail distribution of the
(random) integral of a bounded function which maps the $s$-fold product
$\underbrace{X\times \cdots \times X}_{s \; \text{times}}$ of the space
$X$ to the real line with respect to the $s$-fold product of the
standardized empirical distribution. We give a sharp bound, only
the universal constants appearing in this estimate will not be given.
In paper [mp] such an estimate was proved in the special case when the
space $X$ is the interval, $[0,1]$, and the empirical distribution of a
sequence of independent and on $[0,1]$ uniformly distributed random
variables is considered. We shall recall this result in Theorem~A.
Actually we shall show that the case of random variables on a general
metric space can be deduced from this special case by means of an
isomorphism.
 
Our motivation for proving such a result comes from the estimation of a
distribution function with the help of certain information. The result
which we formulate in Theorem~A turned out to be useful in the study of
the so-called product limit estimation (see[mp]) when a complicated
error
term, which is a non-linear functional of the standardized empirical
process, had to be bounded. In other problems, (see~[mrt]), a multiple
(random) integral of a function with respect to a standardized empirical
measure on a higher dimensional Euclidean space has to be estimated.
Since the proof of the result needed in this case is not harder for a
general separable metric space, we shall work on a metric space. The
above mentioned motivation can also explain why the estimates
formulated below contain a supremum in the first coordinate, a
generalization which may seem artificial at first sight. We want to
bound the supremum of the difference between the estimate and the
estimated function $F(t)$ for all~$t$. The supremum appearing in our
result will enable us to give a good bound on the error of the estimate
not only for a fixed~$t$, but for all~$t$ simultaneously. First we
formulate Theorem~A which will be the basis of our investigation.
\medskip\noindent {\bf Theorem A.} {\it Let
$\xi_1(\omega),\dots,\xi_n(\omega)$
be independent uniformly distributed random variables on $[0,1]$,
$F_n(u)=F_n(u,\omega)=\dfrac1n\#\{k\: 1\le k\le n,\; \xi_k\le u\}$,
$0\le u\le1$, their empirical distribution function and $\mu_n(u)=\sqrt
n(F_n(u)-u)$ the standardization of this empirical distribution
function. Let $f(u_1,\dots,u_s)$ be a function on $[0,1]^s$ such that
$\sup\limits_{u_1,\dots,u_s}|f(u_1,\dots,u_s)|\le1$, and
$f(u_1,\dots,u_s)=0$ if $u_j=u_k$ with some $1\le j<k\le s$.
There exist some universal constants $C_s$ and $\alpha_s$ depending
only on the dimension $s$ in such a way that
$$
P\left(\sup_{0\leq t \leq 1}\left|\int_0^t \int_0^1 \cdots
\int_0^1 f(u_1,\dots,u_s)\mu_n(\,du_1)\dots\mu_n(\,du_s)
\right|\ge x \right) \leq C_{s} \exp\left\{-\alpha_s x^{2/s}\right\}
\tag1.1
$$
for all $x>0$, and function $f$ with the above properties.}\medskip
As it is remarked in paper [mp] this result is sharp. To formulate its
generalization proved in this paper some notations have to be
introduced.
 
Let a probability space $(\Omega,{\Cal A},P)$ and a separable metric
space $(X, {\Cal X})$ be given.  Let $\xi\colon \Omega \to X$ be an
$X$ valued random variable on $ (\Omega,{\Cal A}, P)$. Let $\mu$ denote
the distribution of the random variable $\xi$, i.e. let
$$
\mu(B)=P(\xi \in B)=P(\xi^{-1}(B))\qquad \forall \; B \in {\Cal X}\;.
$$
Suppose that $\xi_1,\xi_2,\dots,\xi_n$ are independent, identically
distributed random variables on $(\Omega, {\Cal A}, P)$ with values
on the space $(X, {\Cal X})$ and distribution $\mu$.
Let us introduce the empirical measure
$$
\bar{\mu}_{n}(B) = \frac{1}{n}\sum_{i=1}^n I(\xi_i \in B) \qquad
\forall\; B\in \Cal X\;,
$$
and its standardization
$$
\mu_n (B)=\sqrt{n}\(\bar\mu_n(B)-\mu(B)\) \qquad\forall \; B\in \Cal
X\;.
$$
Let $X_t$, $0\leq t\leq1$ be a system of sets in ${\Cal X}$
with the following property: \medskip\noindent
{\bf Property (i)} $X_s \subseteq X_t$ for all $s\le t$,
$X_0=\emptyset$, $X_1=X$, $\mu(X_t)=t$.
\medskip
Let us consider the product space $ \underbrace{X\times
\cdots\times X}_{s\;{\text{times}}}=X^s$
with product measure $\mu^{(s)}(\cdot)$ and the diagonal set
$A\in X^s$ is defined as
$$
A=\{(x_1,\dots x_s)\: x_i=x_j \quad \text{for some }i\neq j \}
$$
Since $(X,\Cal X)$ is a separable metric space, $A$
is a measurable set in the product space, and if $\mu$ has no
atoms then $\mu^{(s)}(A)=0$.
 
Let  $\Cal F$ denote the set of the real valued measurable
functions $f(u_1,\dots,u_s)$ defined on the space $X^s$
whose absolute value is less than 1, and which disappear on the
diagonal set $A$, i.e. let
$$
\Cal F=\{f(u_1,\dots,u_s)\: |f|\le1, \quad f(u_1,\dots,u_s)=0\;
\forall \;  (u_1,\dots,u_s)\in A\}\;. \tag1.2
$$
We shall prove the following result:
\medskip\noindent {\bf Theorem 1.} {\it
There exist some universal constants $C_s$ and $\alpha_s$ depending
only on the dimension $s$ in such a way that
$$
P\left(\sup_{0\leq t \leq 1}\left|\int_{X_{t}} \int_{X} \dots
\int_{X} f(u_1,\dots,u_s) \mu_n(\,du_1) \dots \mu_n(\,du_s)
\right|\ge x \right) \le C_{s} \exp\left\{-\alpha_{s} x^{2/s}\right\}
\tag1.3
$$
for all  $f\in\Cal F$ and $x>0$, where the sets $X_t$, $0\leq t\leq1$
satisfy Property~(i).}\medskip\noindent
{\it Remark:}\/ The condition that the function $f$ in Theorem~1
disappears on the diagonal does not mean an important restriction in the
applications we have in mind. On the other hand one can get rid of this
condition by means of a more careful analysis if the contribution of the
integral on the diagonal is separately estimated.\medskip
 
A special case of the theorem, when $s=1$. In this case the result of
Theorem 1 is the classical result of paper~[dkw] or in
multidimensional Euclidean space of paper~[(kif]. However we have not
determined the constant terms, whose calculation may demand more careful
analysis.
 
The paper consists of three sections. In Section 2 we prove two
lemmas, stating the theorem for  finite system of sets. In Lemma 1
a weakened version of Theorem~1 is proved by means of Theorem~A and
in the case of simple step functions, a notion which will be introduced
later. In Lemma 2  Theorem~1 is proved for general measurable functions
under the restriction that the supremum is taken only on a finite set
instead of all $0\le t\le1$. This is proved by means of an appropriate
approximation of general measurable functions by simply step functions.
Finally, Section 3 contains the proof of Theorem 1 in its original form.
 
\beginsection 2. Proof of some useful Lemmas
 
First we show that we may assume without violating the generality
that the measure $\mu$ has no atoms. Indeed, by taking direct product
with the space $([0,1], \Cal B_1,\lambda)$, where $\Cal B_1$ is the
Borel $\sigma$-algebra on $[0,1]$, and $\lambda$ is the Lebesgue
measure we can reformulate the result of Theorem 1 in a space where the
measure $\mu$ has no atoms. More explicitly, put
$$
\align
(\tilde\Omega, \tilde{\Cal A}, \tilde P)&=
(\Omega\times[0,1]^{n},\;\Cal A\times \Cal B_1^n\;
P\times \lambda^n),\\
(\tilde X, \tilde{\Cal X}) &=
(X\times [0,1], \; \Cal X \times \Cal B_1),\\
\tilde{X}_t &=  X_t \times [0,1]\;.\\
\tilde{\xi}_k (\tilde\omega) &= (\xi_k(\omega),x_k)
\text{ if }\tilde{\omega}=(\omega,x_1,\dots, x_n),\;x_i\in [0,1],
\endalign
$$
Given a function $f\in \Cal F$, put
$$
\tilde f(\tilde u_1, \dots, \tilde u_s)=
f(u_1,\dots,u_s)\text{ if} \;
\tilde u_j = (u_j,x_j),\; x_j\in [0,1],\quad j=1,\dots,n.
$$
Then the distribution $\tilde\mu$ of $\tilde\xi_k$,
$k=1,\dots,n$ has no atoms, and
$$
\align
&\int_{\tilde{X}_t} \int_{\tilde{X}} \ldots \int_{\tilde{X}}
\tilde{f} ( \tilde{u}_1 \ldots, \tilde{u}_s)
\tilde\mu_n(d\tilde{u}_1)\tilde\mu_n(d\tilde{u}_2) \ldots
\tilde\mu_n(d\tilde{u}_s)\\
&\qquad=\int_{X_{t}} \int_{X} \ldots
\int_{X} f(u_1, \ldots, u_s) \mu_n(du_1) \ldots \mu_n(du_s).
\endalign
$$
Hence it is enough to prove Theorem 1 to the \ $\tilde{}$ \ system whose
measure $\tilde\mu$ has no atoms, since it also implies
inequality~(1.3) for the original system.
 
The strategy of our proof is the following. First we prove the
estimate of Theorem~1 (when the supremum with respect of the first
coordinate is dropped) by means of Theorem~A for some special step
functions which are constant on some special rectangles. The class of
these step functions is sufficiently rich, so we can prove the
estimate of Theorem~1 by taking their closure in an appropriate way.
To prove the result with the supremum we shall consider such
partitions of the space $X$ which are adapted to the class of
functions $X_t$ appearing in Property~(i.). Hence we
introduce the following definitions.\medskip\noindent
{\bf Definition of simple step functions.} {\it A function
$f(u_1,\dots,u_s)\in \Cal F$ is a\/ {\rm simple step function} if a
partition $B_1,B_2,\dots,B_{\ell} $ of the space $X$ and a set of
numbers $ c_{j_1,\dots,j_s}$ indexed by the $s$-tuples $(j_1, \dots,
j_s)$, $1 \leq j_r \leq \ell$, $j_r \neq j_p$ if $r\ne p$, can be
given in such a way that
$$
f(u_1,\dots,u_s)=\cases c_{j_1,\dots,j_s}
&\text{ if } u_1\in B_{j_1}, \ldots, u_s\in B_{j_s} \; B_{j_p} \cap
B_{j_r}=\emptyset \\
&\quad \text{ if } p\ne r, \; 1 \leq p, r \leq s\\
0&\text{ otherwise.}
\endcases
$$
}\medskip \noindent
{\bf Definition of adapted partitions.} {\it A finite partition $B_1,
B_2, \dots, B_\ell$ of $X$ is called\/ {\rm adapted} to a system of
sets $X_t$, $0\le t\le1$, with Property~(i) and fixed numbers
$0=t_0<t_1<\dots<t_k=1$ if for all  $B_i$, $1\le i\le\ell$, there is
some index $j(i)$ in such a way that $B_i\in
X_{t_{j(i)}}\setminus X_{t_{j(i)-1}}$.} \medskip
\noindent{\it Remark.}\/ Let us consider a system of sets $X_t$ with
Property~(i), a finite set
of numbers $0=t_0<t_1<\dots<t_k=1$ and a finite partition
$\Cal B$ of $X$. Then it is always possible to define a finer partition
${\Cal B}'$ which is adapted to $X_t$ and $0=t_0<t_1<\dots<t_k=1$.
Indeed, the system of sets  $B_i \cap (X_{t_{j}}\setminus
X_{t_{j}-1}) $ for all $i$ and $j$ is a refinement of the
partition $\Cal B$ which is adapted to the system $X_t$ and the numbers
$0=t_0<t_1<\dots<t_k=1$.
 
In the sequel we use the letters $c_s, \alpha_s,$ etc. for some
appropriate constants. The same letter may denote different constant
in different formulas.
 
\medskip  \noindent
{\bf Lemma 1.} {\it Let $f(u_1,\dots,u_s)\in \Cal F$ be a simple step
function, where the class of functions $\Cal F$ was defined in (1.2).
Then
\item{(i)}
$$
 P \left(\left|\int_X\cdots\int_X f(u_1,\dots,u_s)\mu_n(\,du_1)
\dots\mu_n(\,du_s)\right|\ge x\right)\le C_{s} \exp\left\{-\alpha_{s}
x^{2/s}\right\} \tag2.1
$$
\item{(ii)} Let  $X_{t_j}$, $j=0,\dots,k$  be finitely many elements
of a system of sets with Property~(i). Then
$$
\aligned
&P \left( \sup_{t_j\:j=1,\ldots,k}\left|\int_{X_{t_j}}\int_{X}\dots
\int_X f(u_1,\dots,u_s)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge x\)\\
&\qquad\qquad\qquad \le C_s\exp\left\{-\alpha_{s} x^{2/s}\right\}
\endaligned \tag2.2
$$
}\medskip
\noindent {\it Proof.}\/ (i) Let us consider
 $([0,1],{\Cal B}_1,\lambda)$ where ${\Cal B}_1 $ is the Borel
$\sigma$-algebra on $[0,1]$, $\lambda$ is the Lebesgue measure
and $\eta_1,\dots,\eta_n$ are independent uniformly distributed random
variables on $[0,1]$ with empirical measure
$$
\bar\lambda_n(D)=\frac1n\sum_{i=1}^n I(\eta_i\in D)\quad
\forall \; D\in \Cal B_1\;,
$$
and $\lambda_n(D)=\sqrt n(\bar\lambda_n(D)-\lambda(D))$ denotes its
standardization. It is enough to construct a function
$ \tilde{f}\: [0,1]^s\to[-1,1]$ in a such a way that
$$
\aligned
&\int_X\dots\int_X f(u_1,\dots,u_s)\mu_n(\,du_1)\dots\mu_n(\,du_s)\\
&\qquad\overset{\Cal D}\to=\int_0^1\dots\int_0^1
\tilde f(x_1,\dots,x_s)\lambda_n(\,dx_1)\dots\lambda_n(\,dx_s)
\endaligned
\tag2.3
$$
where $\overset{\Cal D}\to=$ denotes equality in distribution,
since the desired estimate follows from Theorem~A. Let us define a
partition $D_1,\dots,D_\ell$, of the interval $[0,1]$ in such a way
that
$$
\lambda(D_i)=\mu(B_i)=P(\xi\in B_i),\; i=1,\ldots,\ell, \;
\bigcup_{i=1}^{\ell} D_i=[0,1] \tag2.4
$$
and put
$$
\tilde{f}(x_1,\dots,x_s)=\cases c_{j_1,\dots,j_s}
&\text{if }x_1\in D_{j_1},\dots,x_s\in D_{j_s}.\; 1\le j_r \le \ell\\
&\quad r=1,\dots\ell \;\;j_r\ne j_p \; \text{ if }p\ne r \\
0 &\text{otherwise.}
\endcases \tag2.5
$$
Then $\tilde f$ is a step function on $[0,1]^s$, and relation (2.3)
holds.
 
\noindent
(ii) Using the previous {\it Remark}\/ we can suppose that the
simple step function is defined on a finite partition $\Cal B$ which
is adapted to the system $X_t$ and the number $0\le t_1<\dots<t_k$.
Let us observe that the adapted partition, $\{B_i\}_{i=1}^\ell$ is
finer than the partition $\{X_{t_{j}}\setminus  X_{t_{j-1}}\}_{j=1}^k$.
This means that either $B_i\cap X_{t_{j}}=B_i$ or
$B_i\cap X_{t_j}=\emptyset$ for all $i=1,\ldots,\ell$, $j=1,\dots,k$.
Because $\mu(X_t)=t$, for all $0\leq t\leq 1$ it follows that
$\mu(B_i)\le t_{j(i)}-t_{j(i)-1}$. It is possible to construct a
partition $D_1,\dots,D_{\ell}$ of the interval $[0,1]$ with
property~(2.4) in such a way that it is finer than the partition
$ [0,t_1],(t_1,t_2],\dots,(t_{k-1},1]$. Let us define a step function
$\tilde f$ on $[0,1]^s$ with relation~(2.5). Then
$$
\align
&\int_{0}^{t_j} \ldots \int_{0}^{1} {\tilde{f}}(x_1, \ldots, x_s)
\lambda_n(dx_1) \ldots \lambda_n(dx_s)\\
&\qquad\overset{\Cal D}\to=
\int_{X_{t_{j}}} \ldots \int_{X} f(u_1, \ldots, u_s)
\mu_n(\,du_1) \dots \mu_n(\,du_s),\quad\forall \; j=1,\dots,k,
\endalign
$$
where $\overset{\Cal D}\to=$ means that the joint distribution of the
vectors $j=1,\dots,k$ on the left and right side agree.
Then statement (ii) of the lemma follows from Theorem~A.
%\hspace{\fill}\qed
\medskip \noindent
{\bf  Lemma 2.} {\it Statement (ii) of Lemma 1 holds for all measurable
$f(u_1, \ldots, u_s) \in {\Cal F} $ functions,
where the class of
functions $\Cal F$ was defined in (1.2).}\medskip
\noindent {\it Proof.} We prove this lemma in two steps. First we
show that it is enough to prove the statement for a general step
function, then we approximate a general step function
by  simple step functions for which the statement holds by Lemma~1.
 
For all bounded and measurable function $f$ it is possible to construct
a measurable step function $f'$ which is close to $f$ in the supremum
norm. It can be supposed that the step function $f'\in \Cal F$, i.e. it
is equal to zero on the diagonal set $A$ since $f\in \Cal F$.
More precisely for any $x>0$ and fixed dimension $s$ and number of
sample points $n$ there exist a step function $f'\in\Cal F$ on the
product space $(X^s,\Cal X^s) $ such that
$$
\sup_{(u_1,\ldots,u_s) \in X^s}
\left|f'(u_1,\dots,u_s)-f(u_1,\dots,u_s)\right|\le\frac x{2(2\sqrt
n)^s}\;. \tag2.6
$$
Then
$$
\aligned
&P\left(\sup_{t_j\: j=1,\dots,k}\left|\int_{X_{t_j}}\cdots\int_X
f(u_1,\ldots,u_s)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge x\right)\\
&\qquad\leq P\left(\sup_{t_j\:j=1,\ldots,k}\left|\int_{X_{t_j}}\cdots
\int_{X}\left(f-f'\right)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge
\frac x2\right)\\
&\qquad\qquad+P\left(\sup_{t_j\:j=1,\dots,k}
\left|\int_{X_{t_j}}\dots\int_X f'\mu_n(\,du_1)\dots\mu_n(\,du_s)
\right|\ge\frac x2\right).
\endaligned\tag2.7
$$
Since the total variation of $\mu_n$ is bounded by $2\sqrt n$ formula
(2.6) implies that
$$
\align
&\sup_{t_j\:j=1,\dots,k}\left|\int_{X_{t_j}}\cdots\int_X
\left(f-f'\right)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\\
&\qquad\le\sup_{t_j\: j=1,\dots,k}\int_{X_{t_j}}\cdots\int_{X}
\left|f-f'\right||\mu_n|(\,du_1)\dots|\mu_n|(\,du_s)\le\frac x2\;.
\endalign
$$
Thus the first term on the right-hand side of inequality~(2.7) equals
zero, and it is enough to prove Lemma~2 for step functions.
 
Let us consider a step function $f\in \Cal F$
$$
f(u_1,\dots,u_s)=\cases c_j
&\text{ if } (u_1,\dots,u_s) \in Y_j,\; Y_j\cap
A=\emptyset,\;j=1,\dots,k \\
&\quad Y_j\cap Y_i=\emptyset \text{ if }j\ne i,\;1\le i,j\le k\\
0 & \text{ otherwise.}
\endcases
$$
Since $(X,\Cal X)$ is a separable metric space any measurable set in
the product space  can be approximated with finite union of rectangular
type sets. More explicitly, for each $Y_j$ and for any given $\delta>0$
there exists finite union of disjoint rectangles $R_j'$ such that
$$
\mu^{(s)}(Y_j\triangle R_{j}^{'})\le\frac \delta2\;,
$$
where $\triangle$ denotes symmetric difference and $\delta>0$ is a
sufficiently small number which will be chosen later.
 
If $Y_j\cap A=\emptyset$, $j=1,\dots,k$, where $A$ denotes the diagonal
on $X^s$, then there exists a good approximating set $R_j$ of $Y_j$
consisting of finitely many disjoint rectangles such that also the
relation $R_j\cap A=\emptyset$ holds. Indeed, since $(X,\Cal X)$ is
separable metric space and $\mu^{(s)}(A)=0$, the diagonal set $A$ can
be covered by the union of finitely many rectangles $R''$ such that
$\mu^{(s)}(R'')\le\frac\delta2$. Then the sets $R_j=R_j'\setminus R''$
also can be represented as the union of finitely many disjoint
rectangles, they are disjoint from $A$ and close to the original $Y_j$,
i.e.
$$
\mu^{(s)}(Y_j\triangle R_j)\le\delta,\quad  j=1,\ldots,k\;.
$$
 
It is possible to define a simple step function $\tilde f$ with the
help of the approximating set of rectangles for which the set where
$\tilde f \ne f$ is small.
 
To do this first we replace the sets $R_j$ which approximate well the
level sets $Y_j$ and disjoint of the diagonal $A$ by such sets $\bar
R_j$ which also have this property and beside this, they are disjoint.
We define $\bar R_j=R_j\setminus \bigcap\limits_{\ell=1}^{j-1}
R_{\ell}$. These sets also can be represented as the union of disjoint
rectangles, they are disjoint. Since the sets $Y_j$ are disjoint,
$\mu(Y_j\triangle R_j)\le \delta$ for all $1\le j\le k$, $\mu(R_j\cap
R_\ell)\le 2\delta$ if $j\neq \ell$, and
$$
\mu ^{(s)}(\bar R_j \triangle Y_j) \leq 2j\delta\quad\text{for all }1\le
j\le k \tag2.8
$$
The simple step function $\tilde f$ will be defined as
$$
\tilde f(u_1,\dots,u_s)=\cases c_j &\text{if }(u_1,\dots,u_s)\in
\bar R_j, \quad j=1,\ldots,k \\
0&\text{ otherwise.}
\endcases
$$
Put $C=\{(u_1,\dots,u_s)\:f\ne\tilde f\}$. Then because of relation
(2.8)
$$
\mu^{(s)}(C)\le2(\delta+2\delta+\cdots+k\delta)=k(k+1)\delta\;.
\tag2.9
$$
Obviously
$$
\aligned
&P\left(\sup_{t_j\:j=1,\dots,k}
\left|\int_{X_{t_j}}\cdots\int_X f(u_1,\dots,u_s)
\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge x \right)\\
&\qquad\le P\left(\sup_{t_j\: j=1,\dots,k}
\left|\int_{X_{t_j}}\cdots\int_{X}\tilde f
\mu_n(\,du_1)\dots\mu_n(du_s)\right|\ge\frac x2\right)\\
&\qquad\qquad+P\left(\sup_{t_j\: j=1,\dots,k}
\left|\int_{X_{t_j}}\cdots\int_X\left(f-\tilde{f}\right)
\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge\frac x2\right).
\endaligned \tag2.10
$$
The first term at the right hand-side of~(2.10) is already estimated
in Lemma~1, and we will show that the second term is also small.
Since $|\mu_n|=|\sqrt n(\bar\mu_n-\mu)|\leq\sqrt n(\bar\mu_n+\mu)$
we get that
$$
\aligned
&P\left(\sup_{t_j\: j=1,\ldots,k}\left|\int_{X_{t_j}}\cdots \int_X
\left(f-\tilde f\right)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge
\frac x2\right) \\
&\qquad\leq P \left((2\sqrt{n})^s(\bar\mu_n+\mu)\times\cdots\times
(\bar\mu_n+\mu)(C)\ge\frac x2\right)\\
&\qquad=P\left((2\sqrt n)^s \sum_{\ell=0}^s {s\choose\ell}
\underbrace{\bar\mu_n\times\cdots\times\bar\mu_n}_{\ell
\text{ times}}\times
\underbrace{\mu\times\cdots\times\mu}_{s-\ell\text{ times}}
(C)\ge\frac x2\right)\\
&\qquad\leq\sum_{\ell=0}^s P\left(
\underbrace{\bar\mu_n\times\cdots\times\bar\mu_n}_{\ell\text{ times}}
\times\underbrace{\mu\times\cdots\times\mu}_{ s-\ell\text{times}}
(C)\ge \frac x{2(2\sqrt n)^s(s+1){s\choose \ell}}\right).
\endaligned\tag2.11
$$
Applying the Markov inequality to the last term of~(2.11)
results the following inequality
$$
\aligned
&P\left(\sup_{t_j\: j=1,\dots,k}\left|\int_{X_{t_j}}\cdots\int_X
\left(f-\tilde f\right)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|
\ge\frac x2\right) \\
&\qquad\leq\sum_{\ell=0}^s E(\underbrace{\bar\mu_n\times\cdots\times
\bar\mu_n}_{\ell\text{ times}}\times\underbrace{\mu \times\cdots\times
\mu}_{s-\ell \text{ times}}(C))
\frac{2(2\sqrt{n})^s(s+1){s\choose\ell}}x\;.
\endaligned\tag2.12
$$
Consider for fixed $\ell$ the expected value of the random variable
$$
\underbrace{\bar\mu_n\times \cdots\times\bar\mu_n}_{\ell
\text{ times}}\times\underbrace{\mu\times\cdots\times\mu}_{s-\ell
\text{ times}}(\cdot)
$$
on a rectangle $B=B_1\times\cdots\times B_s$ for which
$B\cap A=\emptyset$, i.e. none of the $\xi_i$-s is contained in more
than one $B_j$. Notice that
$$
\bar\mu_n\times\cdots\times\bar\mu_n(B_1\times\cdots\times B_{\ell})
=\frac1{n^\ell}\sum_{(j_1,\dots,j_{\ell})\: 1\leq j_i\leq n}
I(\xi_{j_1}\in B_1,\dots,\xi_{j_\ell}\in B_{\ell})\;.
$$
The above sum contains exactly $n(n-1)\cdots(n-\ell+1)$ different
terms and
$$
\aligned
&E\left(\underbrace{\bar\mu_n\times\cdots\times\bar\mu_n}_{\ell
\text{ times}}\times\underbrace{\mu\times\cdots\times\mu}_{s-\ell
\text{ times}}(B_1\times\cdots\times B_s)\right)\\
&\qquad=\frac{n(n-1)\cdots(n-\ell+1)}{n^\ell}\mu(B_1)\cdots\mu(B_{s})\\
&\qquad=\frac{n(n-1)\cdots(n-\ell+1)}{n^\ell}\mu^{(s)}(B)\;.
\endaligned\tag2.13
$$
Thus the above expected value is equal to a measure on the set of
rectangles disjoint from $A$. This measure can be extended for all
measurable set of the product space disjoint from $A$. Therefore
relation (2.13) holds for any measurable set disjoint from $A$.
From  relations (2.9) and (2.11)--(2.13)
it follows that
$$
\aligned
&P\left(\sup_{t_j\:j=1,\dots,k}\left|\int_{X_{t_j}}\cdots\int_X
\left(f-\tilde f\right)\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge
\frac x2\right)\\
&\qquad\leq\frac{2^{2s}n^{s/2}(s+1)k(k+1)\delta}x\;.
\endaligned\tag2.14
$$
With the choice of a
$$
\delta\le\frac{xC_{s}\exp\{-\alpha_{s}x^{2/s}\}}
{k(k+1)(s+1)2^{2s}n^{s/2}} \tag2.15
$$
the statement of the lemma follows from relations~(2.10),
~(2.14) and ~(2.15).  %\hspace{\fill} \qed
 
\beginsection 3. Proof of Theorem 1.
 
To prove Theorem~1 consider a system of sets $X_t$ with Property~(i).
Let $N=N(n,x,s)$ be an integer, and consider the sets $X_{j/N}$,
$j=0,1,\dots,N$. Then for any $t\:\frac jN\leq t<\frac {j+1}N$
$$
\aligned
&\sup_{0\leq t\leq1}\left|\int_{X_{t}}\cdots\int_X f\, \mu_n(\,du_1)
\dots\mu_n(\,du_s)\right|\\
&\qquad\leq \sup_{0\leq j\leq N}\left|
\int_{X_{j/N}}\cdots\int_X f\,\mu_n(\,du_1)\dots\mu_n(\,du_s)
\right|\\
&\qquad\qquad+\sup_{0\leq j<N}\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\cdots\int_X f \,\mu_n(\,du_1) \dots
\mu_n(\,du_s)\right|
\endaligned \tag3.1
$$
Hence
$$
\aligned
&P\left(\sup_{0\leq t\leq1}\left|\int_{X_{t}}\cdots\int_{X} f\,
\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge x\right)\\
&\qquad\leq  P\left(\max_{0\leq j\leq N}\left|
\int_{X_{j/N}}\cdots\int_X f\,\mu_n(\,du_1)\dots\mu_n(\,du_s)
\right|\ge\frac x2\right)\\
&\qquad\qquad+P\left(\max_{0\leq j<N}\sup_{\frac jN<t\leq\frac{j+1}N}
\left|\int_{X_t\setminus X_{j/N}}\cdots\int_X f\, \mu_n(\,du_1)
\dots\mu_n(\,du_s)\right|\ge\frac x2\right).
\endaligned \tag3.2
$$
It is enough to prove the theorem for the second term of the right-hand
side of ~(3.2), since the desired estimation is proved for the
first term in Lemma 2.
 
Let $B$ denote the event that the set $X_{j/N}\setminus X_{(j-1)/N}$
does not contain more than one $ \xi_k $ for all $ 1\leq j \leq N$.
Then
$$
B^c=\{\exists\; k,\ell,j\: \xi_k,\xi_{\ell}\in (X_{j/N}\setminus
X_{(j-1)/N}),\;k\neq\ell,\;1\leq k,\ell\leq n,\; 1\leq j \leq N \}\;.
\tag3.3
$$
For a fixed $j$,  $(1\leq j \leq N)$, it is obvious that
$P(\xi_k\in (X_{j/N}\setminus X_{(j-1)/N}))=\frac1N$ for any
$1\le k\le n$. Therefore for any fixed $j$, $1\le j\le N$
$$
P(\exists\;k,\ell\: \xi_k,\,\xi_{\ell} \in
(X_{j/N}\setminus X_{(j-1)/N}),\;
k\neq\ell,\; 1\le k,\ell\le n)\leq\left(\frac nN\right)^2 \;,
$$
and
$$
P(B^c)\leq N\left(\frac nN\right)^2=\frac {n^2}N\;. \tag3.4
$$
Choosing
$$
N\ge n^2\exp\left\{ x^{2/s}\right\},\tag3.5
$$
it follows that
$$
P(B^c)\leq\exp\left\{-x^{2/s}\right\}.\tag3.6
$$
Thus we need to prove, that
$$
\aligned
I=P&\left(\left\{\max_{0\leq j<N}\sup_{\frac jN<t\leq\frac{j+1}N}
\left|\int_{X_t\setminus X_{j/N}}\cdots\int_X f\,\mu_n(\,du_1)\dots
\mu_n(\,du_s)\right|\ge\frac x2\right\} \cap B\right)\\
&\qquad\qquad\leq c_1\exp\left\{-c_2x^{2/s}\right\}\;.
\endaligned \tag3.7
$$
Define the events
$$
\align
B_{i,j}&=\{\xi_i\in X_{(j+1)/N}\setminus X_{j/N},\;
\xi_\ell\notin X_{(j+1)/N}\setminus X_{j/N},\;\ell\neq i,\;
1\leq\ell\leq n\}\;,\\
B_{0,j}&=\{\xi_i\notin X_{(j+1)/N}\setminus X_{j/N},\; 1\leq i\leq n\}
\endalign
$$
for $i=1,\ldots,n$, $j=0,\dots,N-1$.
The event $B$ is the union of  the above disjoint events
$$
B=\bigcup_{j=0}^{N-1}\bigcup_{i=1}^n B_{i,j}.
$$
Thus
$$
\aligned
&I\leq\sum_{j=0}^{N-1}
P\left(\left\{\sup_{\frac jN<t\le\frac{j+1}N}\left|\int_{X_t\setminus
X_{j/N}}\cdots\int_X f \, \mu_n(\,du_1)\dots\mu_n(\,du_s)
\right|\ge\frac x2\right\}\cap B\right)\\
&\quad\qquad\sum_{j=0}^{N-1}\sum_{i=0}^n P\left(\left\{\sup_{\frac
jN<t\le \frac{j+1}N}\left|\int_{X_t\setminus X_{j/N}}\cdots\int_X f
\mu_n(\,du_1)\dots\mu_n(\,du_s)\right|\ge\frac x2\right\}\cap
B_{i,j}\right).
\endaligned\tag3.8
$$
To prove Theorem 1 it is enough to show that all terms of ~(3.8)
can be bounded as
$$
\aligned
&P\left(\left\{\sup_{\frac jN<t\le\frac{j+1}N}\left|\int_{X_t\setminus
X_{j/N}}\cdots\int_X f\,\mu_n(\,du_1)\cdots\mu_n(\,du_s)
\right|\ge\frac x2\right\}\cap  B_{i,j}\right)\\
&\qquad\qquad\qquad\qquad\qquad\leq\frac{c_1}{n\, N} e^{-c_2x^{2/s}}.
\endaligned\tag3.9
$$
Since $\mu_n(du_1)=\sqrt n(\bar\mu_n(du_1)-\mu(du_1))$ the
integral~(3.9) can be estimated in the following way:
$$
\aligned
&P\left(\left\{\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\cdots\int_X f \,\mu_n(\,du_1)\dots
\mu_n(\,du_s)\right|\ge\frac x2\right\}\cap B_{i,j}\right)\leq
II+III\\
&\qquad=P\left(\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\cdots\int_X f\, \sqrt n
\mu(\,du_1)\dots\mu_n(\,du_s)\right|\ge\frac x4\right)\\
&\quad\qquad+P\left.\left(\sup_{\frac jN<t\le \frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\cdots\int_X f\sqrt n\bar\mu_n(\,du_1)
\dots\mu_n(\,du_s)\right|\ge\frac x4 \right| B_{i,j}\right)
P(B_{i,j}).
\endaligned\tag3.10
$$
Because the integral in $II$ can be bounded as
$$
\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\cdots\int_X f \,\sqrt n
\mu(\,du_1)\dots\mu_n(\,du_s)\right|\leq
\frac{\sqrt n}N(2\sqrt n)^{s-1}\;,
\tag3.11
$$
and $II=0$ if $N$ is chosen in such a way that
$$
N\geq 2^{s+1}\frac{(\sqrt n)^s}x\;.
$$
In the estimation of $III$ we may assume that $i>0$ because $III=0$ if
there is no $\xi$ in the set $X_{(j+1)/N}\setminus X_{j/N}$.
Introduce the notation $Y_j=X_{(j+1)/N}\setminus X_{j/N}$, and
$Y_j^c=X\setminus Y_j$. Split the domain of integration
$(X_t\setminus X_{j/N})\times X^{s-1}$
in the way
$$
(X_t\setminus X_{j/N})\times X^{s-1}=
\bigcup\limits_{j(\ell)=\pm1,\;\ell=2,\dots,s}
(X_t\setminus X_{j/N})\times Z(j(2))\times\cdots\times Z(j(s))\;,
$$
where $Z(1)=Y_j$, $Z(-1)=Y_j^c$.
In this way we get a sum of $2^{s-1}$ stochastic integrals. Consider a
term containing at least one coordinate $Y_j$. For the sake of
simplicity consider such a term where the second coordinate is $Y_j$. In
this case we get by splitting the measure $\mu_n(du_2)=\sqrt n(\bar
\mu_n(du_2)-\mu(du_2))$ into two parts that
$$
\aligned
&\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j}\cdots\int_{Y_j^c}f \sqrt n
\bar\mu_n(\,du_1)\mu_n(\,du_2)\dots\mu_n(\,du_s)\right|\\
&\qquad\leq\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j}\cdots\int_{Y_j^c}f\sqrt n
\bar\mu_n(\,du_1)\sqrt n\bar\mu_n(\,du_2)\dots\mu_n(\,du_s)\right|\\
&\qquad\qquad +\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j}\cdots\int_{Y_j^c}f\sqrt n
\bar\mu_n(\,du_1)\sqrt n\mu(\,du_2)\dots\mu_n(\,du_s)\right|\;.
\endaligned \tag3.12
$$
Notice that in the first term on the right-hand side of~(3.12)
the first two coordinates of the domain of integration are contained in
the set $Y_j$, and in these coordinates integration is taken with
respect to the empirical measure $\bar\mu_n$. Because there is only one
sample element $\xi_i$ in $Y_j$, and $f=0$ on the diagonal set, this
implies that the first term at the right-hand side of~(3.12) equals
zero. The probability associated with the second term of the right-hand
side of~(3.12) can be bounded by using similar argument as in the
estimation of the term~$II$ in formula~(3.10). This time we have
$$
\aligned
&P\left(\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j}\cdots\int_{Y_j^c}f\sqrt n
\bar\mu_n(\,du_1)\sqrt n\mu(\,du_2)\dots\mu_n(\,du_s)\right|
\geq\frac x{2^{s+1}}\right),
\endaligned\tag3.13
$$
and choosing
$$
N>2^{s+1}\frac{(\sqrt n)^s}x \tag3.14
$$
the probability in~(3.13) is equal to 0.
To complete the proof of Theorem~1 we have to give a good estimate of
the following probability:
$$
\left. P\left(\sup_{\frac jN<t\le\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j^c}\cdots\int_{Y_j^c}f\sqrt n
\bar\mu_n(\,du_1)\mu_n(\,du_2)\dots\mu_n(\,du_s)\right| \geq
\frac x{2^{s+1}}\right|B_{i,j}\right).
\tag3.15
$$
%Let us observe that under the condition $B_{i,j}$, $i>0$ the
%random variable $\xi_i$ takes its values on $Y_j$ and the random
%variables $\xi_1,\dots,\xi_{i-1},\xi_{i+1},\dots,\xi_n$
%on $Y_j^c$ with probability~1.
Since the random variables $\xi$-s
are conditionally independent under the condition $B_{i,j}$, and only
the variable $\xi_i$ takes its values in $Y_j$, we are able to get rid
of the supremum taking the integral according to $u_1$:
$$
\aligned
&P\left(\left.\sup_{\frac jN<t\leq\frac{j+1}N}\left|
\int_{X_t\setminus X_{j/N}}\int_{Y_j^c}\cdots\int_{Y_j^c} f\sqrt n
\bar\mu_n(\,du_1)\mu_n(\,du_2)\dots\mu_n(\,du_s)\right|\geq
\frac x{2^{s+1}}\right| B_{i,j}\right)\\
&\qquad\leq P\left.\left(\left| \frac 1{\sqrt{n}}
\int_{Y_j^c}\cdots\int_{Y_j^c}f(\xi_i,u_2,\dots,u_s)
\mu_n(\,du_2)\dots\mu_n(\,du_s) \right|\geq
\frac{x}{2^{s+1}}\right|B_{i,j}\right)
\endaligned\tag3.16
$$
Let us denote by $\mu\prime$ the restriction of measure $\mu$
and by $\mu_{n1}$ the standardization of the empirical measure on
$Y_j^c$
$$
\aligned
\mu^*&=\frac{N}{N-1}\mu\prime,\\
\mu_{n1}(C)&=\sqrt{n-1}\left(\frac1{n-1}\sum_{k\ne i,\,k=1}^n
I(\xi_k\in C)-\mu^*(C)\right).
\endaligned\tag3.17
$$
for any measurable set $C\in Y_j^c$. On the set $Y_j^c$
$$
\mu_n=\frac{\sqrt{n-1}}{\sqrt{n}}\mu_{n1}-\frac{1}{\sqrt{n}}
\frac{N-n}N\mu^*.
\tag3.18
$$
Using the above decomposition of $\mu_n$ the $s-1$ integrals in formula
~(3.16) can be written as the sum of $2^{s-1}$ integrals and the
sum
$$
\aligned
&\sum_{\ell=0}^{s-1}
\sum_{{2\leq i_1<\cdots<i_{\ell}\leq s} \atop
{2\leq j_1<\cdots<j_{s-1-\ell\leq s}}} \\
&\quad P\left(\left|\left.
\int\limits_{Y_j^c}\cdots\int\limits_{Y_j^c}
f \mu^*(du_{j_1}) \dots\mu^*(du_{j_{s-1-l}})
\mu_{n1}(\,du_{i_1}) \dots \mu_{n1}(\,du_{i_{\ell}})\right| \geq
\frac{xn^{(s-\ell)/2}}{2^{2s+1}} \right| B_{i,j} \right )
\endaligned \tag3.19
$$
is an upper estimation of~(3.17). If $\ell=0$ only a deterministic
integral appears, and the associated probability is equal to
0 with the choice of a $x\geq c$. This condition is not a restriction.
The
statement of the theorem is trivial for small $x$ since the right-hand
side of~(1.3) is equal to 1 for $x\leq c$. For $\ell\geq1$
we shall bound each term of~(3.19) by first integrating with
respect to $u_{i_1},\dots,u_{i_{\ell}}$, and then for $\ell\geq1$
estimating the integrals arising this way with the help of Lemma 2.
Introduce the functions
$$
h(\xi_i,u_{i_1}, \dots, u_{i_{\ell}})=
\int_{Y_j^c}\cdots\int_{Y_j^c}f
\mu^*(\,du_{j_1})\dots\mu^*(\,du_{j_{s-1-l}})\;.
$$
Since $|h|\leq1$, and the functions $ h\in \Cal F$,
Lemma 2 is applicable for a general term of~(3.19)
with $s'=\ell$. Thus we get the following inequality:
$$
\aligned
&P\left(\left|\int_{Y_j^c}\cdots\int_{Y_j^c} f
\mu^*(\,du_{j_1})\dots\mu^*(\,du_{j_{s-1-\ell}})
\mu_{n1}(\,du_{i_1})\dots\mu_{n1}(\,du_{i_{\ell}})\right|\geq
\frac{x(\sqrt{n})^{s-\ell}}{2^{2s+1}} | B_{i,j} \right )\\
&\qquad\leq P\left (  \left | \int_{Y_j^c} \ldots \int_{Y_j^c} h\;
\mu_{n1}(du_{i_1}) \ldots \mu_{n1}(du_{i_{\ell}}) \right |  \geq
\frac{x \, (\sqrt{n})^{s-\ell}}{2^{2s+1}} | B_{i,j} \right )\\
&\qquad\leq c_1 \exp \left ( -c_2 x^{2/\ell} n^{(s-\ell)/\ell} \right).
\endaligned\tag3.20
$$
Again, if $x\leq c$
$$
c_1\exp \left\{-c_2 x^{2/\ell}n^{(s-\ell)/\ell}\right\}\leq
\frac1n c'_1 \exp \left\{-c_2'x^{2/s}\right\}.
\tag3.21
$$
Since  $P(B_{ij})\leq\frac{1}{N}$, inequality~(3.9)
follows from (3.10), (3.12), (3.15), (3.16) and~(3.19)--(3.21).
Theorem 1 is proved. % \hspace{\fill} \qed
 
 
\bigskip\noindent{\bf References:}
 
 
\item{dkw}
Dvoretzky, A., Kiefer, J.C. and Wolfowitz, J. (1956) Asymptotic minimax
character of the sample distribution function and of the classical
multinomial estimator, {\it Annals of Mathematical Statistics},
{\bf 27},  642--669.
 
\item{kif}
Kiefer, J.C. (1961) On large deviation of the empiric D.F. of vector
chance variables and a law of iterated logarithm, {\it Pacific J.
Mathematics}, {\bf 2},  649--660.
 
\item{mp}
Major, P. (1988) On the tail behaviour of the distribution function
of multiple stochastic integrals,  {\it Probability Theory and
Related Fields}, {\bf 78},  419--435.
 
 
\item{mr}
Major, P. and Rejt\H{o}, L. (1988) Strong embedding of the distribution
function under random censorship, {\it Annals of Statistics}, {\bf 16},
1113--1132.
 
 
\item{mrt}
Major, P., Rejt\H o, L. and Tusn\'ady, G. (1997) Strong embedding
of a baseline function estimator in the Cox model,
(manuscript).
 
 
\bye
 
\item{}Dehling, H., Denker, M., Philipp, W. (1987)
The almost sure invariance principle for the empirical process of
$U$-statistic structure.
{\it Ann.-Inst.-H.-Poincare-Probab.-Statist.} {\bf 23},
%[Annales-de-l'Institut-Henri-Poincare.-Probabilites-et-Statistique] 23 (1987),
no. 2, pp 121--134.
 
\item{tal}
Talagrand, M. (1994) Sharper bounds for Gaussian and
empirical processes. {\it Annals of Probability} {\bf 22}. pp 28--76.
 
 
