\magnification=\magstep1 \hsize=15truecm \input amstex \TagsOnRight \parindent=20pt \parskip=1.5pt plus 1pt \define\const{\text{\rm const.}\,} \define\Cov{\text{\rm Cov}\,} \define\Var{\text{\rm Var}\,} \font\script =cmcsc10 \font\kisbetu=cmr8 \centerline{\bf ESTIMATION OF MULTIPLE RANDOM INTEGRALS} \centerline{\bf AND $U$-STATISTICS.} \smallskip %\centerline{Inauguration Speech for the Hungarian Academy of Sciences} %\smallskip \centerline{\it P\'eter Major} \centerline{\it Alfr\'ed R\'enyi Alfr\'ed Mathematical Institute} \centerline{\it of the Hungarian Academy of Sciences} \medskip\noindent {\narrower This text is an enlarged version of my inauguration talk to the Hungarian Academy of Sciences. First I formulate the problems discussed in this talk and briefly indicate the questions which inspired me to work on this subject. Then I write down the main results, discuss their background together with some pictures and mathematical ideas which explain them better. \par} \beginsection 1. Introduction. Formulation of the problems. To formulate the problems first I introduce some notations. \noindent Let $\xi_1,\dots,\xi_n$ be a sequence of independent and identically distributed random variables with some probability distribution $\mu$ on a measurable space $(X,\Cal X)$ and let $\mu_n$, $$ \mu_n(A)=\dfrac1n\#\{j\:\,\xi_j\in A,\;1\le j\le n\},\quad A\in\Cal X, $$ denote its empirical distribution. Let a measurable function $f(x_1,\dots,x_k)$ of $k$-variables be given on the product space $(X^k,\Cal X^k)$. Take the $k$-fold direct product of the normalized version $\sqrt n(\mu_n-\mu)$ of this empirical measure $\mu_n$ and consider the integral of the function $f$ with respect to it. More explicitly, the (random) integral $$ \aligned J_{n,k}(f)&=\frac{n^{k/2}}{k!} \int' f(x_1,\dots,x_k)(\mu_n(\,dx_1)-\mu(\,dx_1))\dots (\mu_n(\,dx_k)-\mu(\,dx_k)),\\ &\;\;\text{where the prime in $\tsize\int'$ means that the diagonals } x_j=x_l,\; 1\le ju)$ under appropriate conditions for the function $f$. \medskip \item{} (The omission of the diagonals $x_j=x_l$, $j\neq l$, from the domain of integration turned out to be natural in possible applications.) The second, more general problem is the following one. \medskip \item{} {\it Problem B).} Let a nice class $\Cal F$ of functions $f(x_1,\dots,x_k)$ be given on the space $(X^k,\Cal X^k)$. Give a good estimate on the probabilities $P\left(\sup\limits_{f\in\Cal F}J_{n,k}(f)>u\right)$, where $J_{n,k}(f)$ denotes the integral of the function $f$ defined in formula (1.1). \medskip It turned out useful to study these two problems together with their $U$-statistic analogues. To formulate them first I recall the definition of $U$-statistics. \medskip\noindent {\bf The definition of $U$-statistics.} {\it Let a sequence $\xi_1,\dots,\xi_n$ of independent and identically distributed random variables be given with values on some measurable space $(X,\Cal X)$ together with a function $f(x_1,\dots,x_k)$ on the $k$-fold product space $(X^k,\Cal X^k)$ with some $k\le n$. The expression $$ I_{n,k}(f)=\frac1{k!}\sum\limits\Sb 1\le j_s\le n,\; s=1,\dots, k\\ j_s\neq j_{s'} \text{ if } s\neq s'\endSb f\left(\xi_{j_1},\dots,\xi_{j_k}\right) \tag1.2 $$ is called a $U$-statistic of order $k$ with kernel function $f$.} \medskip I formulated the following versions of the above two problems. \item{} {\it Problem A$'$).} Give a good estimate on the probabilities $P(n^{-k/2}I_{n,k}(f)>u)$ under appropriate conditions for the function $f$. \medskip \item{} {\it Problem B$'$).} Let a nice class $\Cal F$ of functions $f(x_1,\dots,x_k)$ be given on a (product) space $(X^k,\Cal X^k)$ together with a sequence of independent and identically distributed random variables $\xi_1,\dots,\xi_n$ with values in $(X,\Cal X)$. Give a good estimate on the probabilities $P\left(\sup\limits_{f\in\Cal F}n^{-k/2}I_{n,k}(f)>u\right)$, where $I_{n,k}(f)$ denotes the $U$-statistic of order $k$ with kernel function $f$ defined in formula~(1.2). \medskip It may be useful to remark that a $U$-statistic of order $k$ with the kernel function $f$ can be rewritten as $$ I_{n,k}(f)=\frac{n^k}{k!}\int' f(x_1,\dots,x_k)\mu_n(\,dx_1)\dots\mu_n(\,dx_k), $$ where $\mu_n$ is the empirical distribution of the sequence $\xi_1,\dots,\xi_n$. This shows that the essential difference between the random integrals introduced in formula (1.1) and the $U$-statistics is that in the random integrals $J_{n,k}(f)$ integration is taken with respect to the `normalized' measures $\mu_n-\mu$, while in the integral representation of the $U$-statistics $I_{n,k}(f)$ with respect to the `non-normalized' measures $\mu_n$. \medskip I met the above problems when tried to adapt a simple method applied in the study of the asymptotic behaviour of maximum likelihood estimates to the investigation of harder problems. In the study of maximum likelihood estimates the root of the so-called maximum likelihood equation has to be well estimated. This can be done by means of a good approximation of the function in the maximum likelihood equation which is obtained with the help of its Taylor expansion if the high order terms of this expansion are omitted. It has to be shown that such an approximation causes only a negligibly small error. But this can be proved relatively simply. I tried to apply a similar method in the study of some so-called non-parametric maximum likelihood estimation problems. Such a problem arises for instance if we want to estimate an unknown distribution function by means of some partial information. In the study of the error of such an estimate in a fixed point a version of the Taylor expansion can be applied together with the omission of the higher order terms. But in this case it is much harder to show that such an approximation causes only a negligibly small error. To prove this a good solution of Problem~A is needed. If we want to bound the error of the estimation in all points simultaneously, then we need a good solution of Problem~B. In the investigation of general non-parametric estimation problems several additional difficulties have to be overcome, but the solution of Problems~A and~B is especially important. Beside this, these problems are related to a better understanding of some fundamental probabilistic phenomena. Hence I found useful a detailed study of the above questions. \beginsection 2. An overview of the problems. The study of the one-variate case. Before a detailed discussion it is worth thinking over what kind of results can be expected. Let us observe that the normalized signed measures $\sqrt n(\mu_n-\mu)$ converge to a Gaussian field as $n\to\infty$. Hence it is natural to expect that under very general conditions such results hold both in the solution of Problem~A and Problem~B which their Gaussian counterparts suggest. But we have to understand the answer to the following two questions. \medskip \item{1.)} What kind of estimates do the Gaussian counterparts of these problems suggest? \item{2.)} What does the expression `under very general conditions' mean? \medskip To clarify the above questions it is useful to study first Problem~A in the case $k=1$ when the distribution of sums of independent random variables has to be bounded. Such a bound is given in the following classical result called Bernstein's inequality. \medskip\noindent {\bf Bernstein's inequality.} {\it Let $\xi_1,\dots,\xi_n$ be independent random variables which satisfy the relations $P(|\xi_j|\le1)=1$ and $E\xi_j=0$, $1\le j\le n$. Let us introduce the notation $\sigma_j^2=E\xi_j^2$, $1\le j\le n$, $S_n=\sum\limits_{j=1}^n \xi_j$ and $V_n^2=\text{\rm Var}\, S_n =\sum\limits_{j=1}^n\sigma_j^2$. The inequality $$ P(S_n>u)\le\exp\left\{-\frac{u^2}{2V_n^2\left(1+\frac u{3V_n^2} \right)}\right\} \tag2.1 $$ holds for all numbers $u>0$.} \medskip Bernstein's inequality yields an estimate on the distribution of sums of independent random variables suggested by the central limit theorem, although the coefficient $1+\frac u{3V_n^2}$ in the denominator of the upper bound slightly modifies the picture. In the next remark the effect of this factor is considered in different cases. \medskip \item{a)} If $u\le \varepsilon V_n^2$ with some small number $\varepsilon>0$, then $P(S_n>u)\le e^{-(1-\varepsilon)u^2/2V_n^2}$. This is almost such a good estimate as the estimate obtained by a formal application of the central limit theorem. \item{b)} If $u\le 3 V_n^2$, then $P(S_n>u)\le e^{-\text{const.}\, u^2/2V_n^2}$. This is a bound similar to that suggested by the central limit theorem, only it has a worse constant in the exponent. \item{c)} If $u\gg V_n^2$, then $$ P(S_n>u)\le e^{-u}. \tag2.2 $$ This is a very bad bound. In particular, it does not depend on the variance of the sum. \medskip The question arises whether Bernstein's inequality can be improved in the `bad case' $u\gg V_n^2$. To this question a positive answer can be given. Bennett's inequality formulated below yields a slight improvement of Bernstein's inequality in this case. \medskip\noindent {\bf Bennett's inequality.} {\it Let $\xi_1,\dots,\xi_n$ be a sequence of independent random variables which satisfy the relations $P(|\xi_j|\le1)=1$ and $EX_j=0$, $1\le j\le n$. Put $\sigma_j^2=E\xi_j^2$, $1\le j\le n$, $S_n=\sum\limits_{j=1}^n \xi_j$ and $V_n^2=\text{\rm Var}\,S_n=\sum\limits_{j=1}^n\sigma_j^2$. Then the inequality $$ P(S_n>u)\le\exp\left\{-V^2_n\left[\left(1+\frac u{V^2_n}\right) \log\left(1+\frac u{V^2_n}\right)-\frac u{V^2_n}\right]\right\} $$ holds for all numbers $u>0$. Hence there exists a constant $B=B(\varepsilon)>0$ for all $\varepsilon>0$ such that $$ P(S_n>u)\le\exp\left\{-(1-\varepsilon)u\log \frac u{V^2_n} \right\}\quad\text{if } u>BV_n^2, $$ and there exists a number $K>0$ such that $$ P(S_n>u)\le\exp\left\{-Ku\log \frac u{V^2_n} \right\}\quad\text{if }u\ge3V_n^2. \tag2.3 $$} \medskip Formula (2.3) yields a slight improvement of formula (2.2), but even this bound is very far from the estimate suggested by the central limit theorem. On the other hand, as the next example shows, this estimate cannot be improved. \medskip\noindent {\bf Lower bound for the distribution of sums of independent random variables in an appropriate example.} {\it Let us fix a positive integer $n$ together with two positive numbers $u$ and $\sigma^2$ which satisfy the relations $0<\sigma^2\le\frac18$, $n>3u\ge6$ and $u>3n\sigma^2$. Let us introduce the quantity $V_n^2=n\sigma^2$, and consider a sequence of independent and identically distributed random variables $\xi_1,\dots,\xi_n$ such that $P(\xi_j=1)=P(\xi_j=-1)=\frac{\sigma^2}2$ and $P(\xi_j=0)=1-\sigma^2$. Put $S_n=\sum\limits_{j=1}^n \xi_j$. In this example $ES_n=0$, $\text{\rm Var}\,S_n=V_n^2$, and $$ P(S_n\ge u)>\exp\left\{-Ku\log \frac u{V^2_n}\right\} \tag2.4 $$ with some appropriate number $K>0$.} \medskip In formula (2.4) that probability is bounded from below in a special case which is bounded from above in~(2.3). These two estimates are very similar. The only difference between them is that they may contain a different constant $K>0$. The above results can be summarized in the following way. For small numbers $u>0$ the probability $P(S_n>u)$ satisfies a good estimate suggested by the central limit theorem. Such a situation holds if $u\le \varepsilon V_n^2$. This probability satisfies a slightly weaker estimate for not too large numbers~$u$ (if $\varepsilon V_n^2\le u\le CV_n^2$ with some fixed number $C>0$), and it satisfies only very weak estimates for large numbers~$u$ (if $u\gg V_n^2$). \beginsection 3. Some results useful in the study of the general case. In the solution of Problem A) in the general case $k\ge1$ similar results hold as in the special case $k=1$ discussed before. To understand their similarity better it is useful to study first the following two questions. \medskip\noindent {\it Question 1.}\/ In the case $k=1$ the sum of independent random variables with {\it zero expectation} was considered. What kind of normalization corresponds to this zero expectation in the case $k\ge2$? \medskip\noindent {\it Question 2.}\/ In the case $k=1$ the central limit theorem and the behaviour of the normal distribution function were in the background of the estimates. What kind of limit theorem and estimation take their part in the case $k\ge2$? \medskip\noindent {\it Discussion of the first question.}\/ \medskip\noindent It is useful to consider first the second moment of the expressions we are investigating. In the case $k=1$ independent random variables of expectation zero are summed up. In this case the identity $$ \text{Var}\,\left(\sum\limits_{k=1}^n\xi_k\right)= \sum\limits_{k=1}^n\text{Var}\,\xi_k, $$ holds because of the identity $E\xi_i\xi_j=0$ for all pairs $i\neq j$. The multivariate version of this identity (in the case of $U$-statistics) would be the identity $$ \align I_{n,k}(f)&=\text{Var}\,\left(\frac1{k!} \sum \Sb 1\le j_s\le n,\; s=1,\dots, k,\; \\ j_s\neq j_{s'} \text{ if } s\neq s' \endSb f(\xi_{j_1},\dots,\xi_{j_k})\right) \\ &=\frac1{k!} \sum\Sb 1\le j_s\le n,\; s=1,\dots, k,\; \\ j_s\neq j_{s'} \text{ if } s\neq s'\endSb \text{Var}\, f(\xi_{j_1},\dots,\xi_{j_k}) \endalign $$ This identity holds if $$ Ef(\xi_{j_1},\dots,\xi_{j_k})f(\xi_{j_1'},\dots,\xi_{j_k'})=0 $$ for all pairs of $k$-tuples such that $\{j_1,\dots,j_k\}\neq \{j_1',\dots,j_k'\}$. The above relation holds for the degenerate $U$-statistics introduced below. \medskip\noindent {\bf Definition of degenerate $U$-statistics.} {\it Take a $U$-statistic $I_{n,k}(f)$ determined by a sequence of independent and identically distributed random variables $\xi_1,\dots,\xi_n$ with distribution $\mu$ and a kernel function $f(x_1,\dots,x_k)$. This $U$-statistic is degenerate if $$ \align &E(f(\xi_1,\dots,\xi_k)|\xi_1=x_1,\dots,\xi_{j-1}=x_{j-1}, \xi_{j+1}=x_{j+1},\dots,\xi_k=x_k)=0 \\ &\qquad\qquad \text{for all indices }1\le j\le k\text{ and values } x_s\in X, \; s\in\{1,\dots,k\}\setminus\{j\}. \endalign $$ }\medskip A $U$-statistic is degenerate if its kernel function is canonical, i.e. it satisfies the following property. \medskip \noindent {\bf Definition of canonical functions.} {\it A function $f(x_1,\dots,x_k)$ defined on the $k$-fold direct product $(X^k,\Cal X^k)$ is canonical with respect to a probability measure $\mu$ on the space $(X,\Cal X)$ if $$ \align &\int f(x_1,\dots,x_{j-1},u,x_{j+1},\dots,x_k)\mu(\,du)=0 \\ &\qquad\text{for all indices \ } 1\le j\le k\text{ and values } x_s\in X,\; s\in\{1,\dots,k\}\setminus\{j\}. \endalign $$ \medskip} The notion of degenerate $U$-statistics is useful, because in some sense such $U$-statistics behave so as sums of independent random variables with {\it expectation zero}. Beside this, the study of general $U$-statistics can be reduced to the study of degenerate $U$-statistics by means of the following Hoeffding-decomposition. \medskip\noindent {\bf Hoeffding decomposition of general $U$-statistics.} {\it All $U$-statistics $I_{n,k}(f)$ of order $k$ can be written in the form of linear combination $$ I_{n,k}(f)=\sum_{j=0}^k n^{k-j} I_{n,j}(f_j) \tag3.1 $$ of {\rm degenerate $U$-statistics} $I_{n,j}(f_j)$. The (canonical) kernel functions $f_j$ (of $j$ variables) of the degenerate $U$-statistics $I_{n,j}(f_j)$, $0\le j\le k$, can be calculated explicitly. It can be shown that they satisfy the inequality $$ \int f_j^2(x_1,\dots,x_j)\mu(\,dx_1)\dots\mu(\,dx_j) \le\int f^2(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k) $$ for all indices $0\le j\le k$.} \medskip The problems about the behaviour of the multiple random integrals $J_{n,k}(f)$ defined in formula (1.1) can also be reduced to problems about the behaviour of degenerate $U$-statistics by means of their appropriate decomposition. Such expressions can be written as the linear combination $$ J_{n,k}(f)=\sum_{j=0}^k c(n,j) n^{-j/2}I_{n,j}(f_j) \tag3.2 $$ of degenerate $U$-statistics with the same kernel functions $f_j$ which appear in formula (3.1) and with some appropriate coefficients $c(n,j)$ such that $c(n,j)u)$ for all numbers $u>0$. \medskip \item{} {\it Problem B$''$).} Let a nice class $\Cal F$ of functions $f(x_1,\dots,x_k)$ of $k$ variables be given. Take the Wiener--It\^o integral $Z_{\mu,k}(f)$ of all functions $f\in\Cal F$ with respect to a white noise $\mu_W$. Give a good estimate on the distribution of the supremum of these random integrals, i.e. on the probability $P\left(\sup\limits_{f\in\Cal F}Z_{\mu,k}(f)>u\right)$ for all numbers $u>0$. \beginsection 4. Results about the distribution of random integrals and $U$-statistics. It is worth considering first Problem~$A'')$ about the estimation of Wiener--It\^o integrals. I present a result in this direction. \medskip\noindent {\bf Estimation about the tail distribution of Wiener--It\^o integrals.} {\it Let a white noise $\mu_W$ be given with reference measure $\mu$ together with a function $f(x_1,\dots,x_k)$ of $k$ variables on a measurable space $(X,\Cal X)$ such that $$ \int f^2(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k)\le\sigma^2 $$ with some number $\sigma^2<\infty$. The Wiener--It\^o integral $$ Z_{\mu,k}(f)=\frac1{k!}\int f(x_1,\dots,x_k)\mu_W(\,dx_1)\dots\mu_W(\,dx_k) $$ introduced in formula (3.3) satisfies the inequality $$ P(k!|Z_{\mu,k}(f)|>u)\le C \exp\left\{-\frac12\left(\frac u\sigma\right)^{2/k}\right\} $$ for all numbers $u>0$ with some constant $C=C(k)>0$ depending only on the multiplicity $k$ of the integral.} \medskip The next example shows that the above estimate is sharp. \medskip\noindent {\bf Lower bound on the tail distribution of a special Wiener--It\^o integral.} {\it Let a $\sigma$-finite measure $\mu$ be given on a measurable space $(X,\Cal X)$ together with a white noise $\mu_W$ on $(X,\Cal X)$ with this reference measure $\mu$. Let $f_0(x)$ be a real valued function on the space $(X,\Cal X)$ such that $\int f_0(x)^2\mu(\,dx)=1$. Let us introduce the function $f(x_1,\dots,x_k)=\sigma f_0(x_1)\cdots f_0(x_k)$ with some number $\sigma>0$, and consider the Wiener--It\^o integral $Z_{\mu,k}(f)$ introduced in formula (3.3). Then the identity $$ \int f(x_1,\dots,x_k)^2\,\mu(\,dx_1)\dots\,\mu(\,dx_k)=\sigma^2 $$ holds, and the Wiener--It\^o integral $Z_{\mu,k}(f)$ satisfies the inequality $$ P(k!|Z_{\mu,k}(f)|>u)\ge \frac{\bar C}{\left(\frac u\sigma\right)^{1/k}+1} \exp\left\{-\frac12\left(\frac u\sigma\right)^{2/k}\right\} $$ for all numbers $u>0$ with some appropriate constant $\bar C>0$.} \medskip \medskip The integral $\sigma^2=\int f(x_1,\dots,x_k)^2\,\mu(\,dx_1)\dots\,\mu(\,dx_k)$ in the above results agrees with the variance of the random integral $(k!)^{-1/2}Z_{\mu,k}(f)$. Hence these results can be interpreted so that $$ P(Z_{k,\mu}(f)>u)\le\text{const.}\, P(\sigma\eta^k>u) $$ for all numbers $u>0$, where $\eta$ is a standard normal random variable, and $\sigma^2=(k!)^{-1/2}EZ_{\mu,k}(f)^2$. Furthermore, this estimate is sharp. Similar, but slightly weaker estimates hold for degenerate $U$-statistics and multiple random integrals with respect to normalized empirical distributions. \medskip\noindent {\bf Estimate on the tail distribution of degenerate $U$-statistics.} {\it Let $\xi_1,\dots,\xi_n$ be a sequence of independent and identically distributed random variables on a measurable space $(X,\Cal X)$ with distribution $\mu$. Take a function $f(x_1,\dots,x_k)$ on the space $(X^k,\Cal X^k)$ canonical with respect to the measure $\mu$ which satisfies the conditions $$ \align \|f\|_\infty&=\sup_{x_j\in X, \,1\le j\le k}|f(x_1,\dots,x_k)|\le 1 \tag4.1 \\ \|f\|^2_2&=\int f^2(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k) \le\sigma^2 \tag4.2 \endalign $$ with some number $0<\sigma^2\le1$, and consider the (degenerate) $U$-statistic defined in formula (1.2) with the help of these quantities. Then there exist some constants $A=A(k)>0$ and $B=B(k)>0$ depending only on the order $k$ of the $U$-statistic such that the inequality $$ P(k!n^{-k/2}|I_{n,k}(f)|>u)\le A\exp\left\{-\frac{u^{2/k}}{2\sigma^{2/k} \left(1+B\left(un^{-k/2}\sigma^{-(k+1)}\right)^{1/k}\right)}\right\} \tag4.3 $$ holds for all numbers $0\le u\le n^{k/2}\sigma^{k+1}$.} \medskip The above estimate can be considered as a multivariate generalization of Bernstein's inequality. For multiple integrals with respect to normalized empirical distributions the following similar estimate holds. \medskip\noindent {\bf Estimate about the tail distribution of random integrals with respect to normalized empirical distributions.} {\it Let a sequence $\xi_1,\dots,\xi_n$ of independent and identically distributed random variables be given with distribution $\mu$ which take their values on a measurable space $(X,\Cal X)$ together with a function $f(x_1,\dots,x_k)$ on the $k$-fold product space $(X^k,\Cal X^k)$ which satisfy relations (4.1) and (4.2) with some constant $0<\sigma\le1$. Then there exist some constants $C=C_k>0$ and $\alpha=\alpha_k>0$ depending only on the multiplicity $k$ of the integral $J_{n,k}(f)$ defined in formula (1.1) such that the inequality $$ P\left(|J_{n,k}(f)|>u\right)\le C \exp\left\{-\alpha \left(\frac u\sigma\right)^{2/k}\right\} \quad \text{for all numbers } 0u)$ of the normalized sum $n^{-1/2}S_n$ of $n$ independent, identically distributed, bounded random variables with expectation zero satisfies only a very weak estimate if $u\gg n^{1/2}\sigma^2$, an estimate which is very far from the bound suggested by the central limit theorem. Similarly, in the case $k\ge2$ the tail distribution $P(k!n^{-k/2}I_{n,k}(f)>u)$ of degenerate $U$-statistics satisfies a much weaker estimate than the bound suggested by the behaviour of Wiener--It\^o integrals if $u\gg n^{k/2}\sigma^{k+1}$. This means that the previous estimates about the tail distribution of degenerate $U$-statistics and integrals with respect to normalized empirical distributions are sharp also in that sense that they give the domain where the sharp estimate suggested by the behaviour of Wiener--It\^o integrals holds. For the sake of completeness I present in the case $k=2$ such a degenerate $U$-statistic whose tail-distribution satisfies only a much weaker estimate than formula~(4.3) if $u\gg n\sigma^3$. \medskip\noindent {\bf Lower bound for the tail distribution of a special degenerate $U$-statistic in the case $k=2$.} {\it Let $\xi_1,\dots,\xi_n$ be a sequence of independent, identically distributed random variables with values on the two-dimensional Euclidean space. Let $\xi_j=(\eta_{j,1},\eta_{j,2})$, $1\le j\le n$, where $\eta_{j,1}$ and $\eta_{j,2}$ are independent random variables, $P(\eta_{j,1}=1)=P(\eta_{j,1}=-1)=\frac{\sigma^2}8$, and $P(\eta_{j,1}=0)=1-\frac{\sigma^2}4$, $P(\eta_{j,2}=1)=P(\eta_{j,2}=-1)=\frac12$ for all indices $1\le j\le n$. Let us introduce the function $f(x,y)=f((x_1,x_2),(y_1,y_2))=x_1y_2+x_2y_1$, $x=(x_1,x_2)\in R^2$, $y=(y_1,y_2)\in R^2$, and define the $U$-statistic of order 2 $$ I_{n,2}(f)=\sum_{1\le j,k\le n,\,j\neq k} (\eta_{j,1}\eta_{k,2}+\eta_{k,1}\eta_{j,2}) $$ with this kernel function $f$ and the independent random variables $\xi_1,\dots,\xi_n$. The expression $I_{n,2}(f)$ is a degenerate $U$-statistic. Furthermore, if $u\ge B_1n\sigma^3$ with some appropriate constant $B_1>0$, $B_2^{-1}n\ge u\ge B_2n^{-2}$ with some sufficiently large number $B_2>0$, and $\frac1n\le\sigma\le1$, then the inequality $$ \align P(n^{-1}I_{n,2}(f)>u)&\ge \exp\left\{-Bn^{1/3}u^{2/3}\log \left(\frac u{n\sigma^3}\right)\right\} \\ &= \exp\left\{-B\frac u\sigma\left(\frac{n\sigma^3} u\right)^{1/3} \log\left(\frac u{n\sigma^3}\right)\right\} \endalign $$ holds with some constant $B>0$, which depends neither on the number~$n$ nor on the parameter $\sigma$.} \medskip \beginsection 5. A brief explanation of the results. It is worth showing that the high even order moments $EI_{n,k}(f)^{2M}$ of a degenerate $U$-statistic $I_{n,k}(f)$ of order $k$ satisfy such estimates as the moments $E\eta^{2kM}$ of a Gaussian random variable $\eta$ with expectation zero and appropriate variance. Such estimates (together with the Markov inequality) imply the inequalities we want prove, and beside this there is a method which enables us to bound such moments. Such moments can be estimated by means of the so-called diagram formula about random integrals. This formula makes possible to express the moments we are interested in as the sum of certain integrals defined with the help of some diagrams. To give a good estimate on the moments we want to bound it has to be shown that the ``diagrams corresponding to the Gaussian effect'' yield the main contribution to them. In such a way we can get an explanation why the tail distribution of degenerate $U$-statistics and random integrals satisfy such an estimate which the behaviour of Wiener--It\^o integrals (i.e. the Gaussian case) suggests. The explanation of the details in the estimation of multiple random integrals or degenerate $U$-statistics of order $k\ge2$ demands the application of rather complicated notations. This requires much work which cannot be done in a short summary paper. Hence I omit its discussion. On the other hand, I consider a special case of this problem, the estimation of the moments of sums of independent random variables. This may explain very much also about the general case. Let $\xi_1,\dots,\xi_n$ be a sequence of independent and identically distributed random variables such that $E\xi_1=0$, $\text{Var}\,\xi_1=\sigma^2$, and let us estimate the even moments of the sum $S_n=\sum\limits_{j=1}^n \xi_j$. The identity $$ ES_n^{2M}=\sum\Sb (j_1,\dots,j_s,l_1,\dots,l_s)\\ j_1+\dots+j_s=2M,\, j_u\ge 2,\text{ for all indices } 1\le u\le s \\ l_u\neq l_{u'} \text { if } u\neq u'\endSb E\xi_{l_1}^{j_1}\cdots E\xi_{l_s}^{j_s} \tag5.1 $$ holds. Simple combinatorial considerations show that in the sum at the right-hand side of the identity~(5.1) most terms are indexed with such a vector $$ (j_1,\dots,j_M,l_1,\dots,l_M) $$ for which $j_u=2$ for all numbers $1\le u\le M$. The number of such terms equals $\binom nM\frac{(2M)!}{2^M}\sim n^M\frac{(2M)!}{2^MM!}$. Hence it is natural to expect that in typical cases $ES_n^{2M}\sim \left(n\sigma^2\right)^M\frac{(2M)!}{2^MM!}$. This consideration suggests the estimate $$ \sum_{1\le l_10$ there exists a subclass $\Cal G_{\varepsilon}=\{g_1,\dots,g_m\}\subset\Cal G$ in the space $L_2(Y,\Cal Y,\nu)$ consisting of $m\le D\varepsilon^{-L}$ elements such that $\inf\limits_{g_j\in \Cal G_\varepsilon}\int |g-g_j|^2\,d\nu <\varepsilon^2$ for all functions~$g\in \Cal G$.} \medskip The other useful notion is the following one. \medskip\noindent {\bf Definition of $L_2$-dense classes of functions.} {\it Let us have a measurable space $(Y,\Cal Y)$ and a set $\Cal G$ of $\Cal Y$-measurable real valued functions on this space. We call $\Cal G$ an $L_2$-dense class of functions with parameter $D$ and exponent $L$ if it is $L_2$-dense with parameter $D$ and exponent $L$ with respect to all probability measures $\nu$ on $(Y,\Cal Y)$.} \medskip It is useful to consider first Problem~B$''$) about the supremum of Wiener--It\^o integrals, then to describe the results on Problems~B) and~B$'$) about the supremum of random integrals with respect to normalized empirical distribution and degenerate $U$-statistics and to compare these results. \medskip\noindent {\bf Estimate about the tail distribution of the supremum of Wiener--It\^o integrals.} {\it Let us consider a measurable space $(X,\Cal X)$ together with a $\sigma$-finite non-atomic measure~$\mu$ on it, and let $\mu_W$ be a white noise with reference measure $\mu$ on $(X,\Cal X)$. Let $\Cal F$ be a countable and $L_2$-dense class of functions $f(x_1,\dots,x_k)$ on $(X^k,\Cal X^k)$ with some parameter $D$ and exponent $L$ with respect to the product measure $\mu^k$ such that $$ \int f^2(x_1,\dots,x_k)\mu(\,dx_1)\dots \mu(\,dx_k)\le\sigma^2 \quad \text{\rm with some } 0<\sigma\le1 \text { \rm for all } f\in \Cal F. $$ Let us consider the multiple Wiener integrals $Z_{\mu,k}(f)$ introduced in formula (3.3) for all~$f\in\Cal F$. The inequality $$ P\left(\sup_{f\in \Cal F}|Z_{\mu,k}(f)|>u\right)\le C(D+1) \exp\left\{-\alpha\left(\frac u\sigma\right)^{2/k}\right\} $$ holds with some universal constants $C=C(k)>0$ and $\alpha=\alpha(k)>0$ if $$ \left(\frac u\sigma\right)^{2/k}\ge ML \log\frac2\sigma \tag6.1 $$ with some appropriate constant $M=M(k)>0$.} \medskip In the above result --- disregarding the value of the universal constants appearing in it --- the same estimate is obtained about the tail distribution of Wiener--It\^o integrals (under appropriate conditions) as in the estimate about the tail distribution of a single Wiener--It\^o integral. The only essential difference between these two results is that in the present case an additional condition formulated in formula~(6.1) had to be imposed. It is not difficult to present such an example which shows that such a condition is really needed. But here I omit its description. The next result is an estimate on the tail-distribution of the supremum of random integrals $J_{n,k}(f)$ defined in formula (1.1). \medskip\noindent {\bf Estimate on the tail distribution of the supremum of multiple integrals with respect to a normalized empirical distribution.} {\it Let us have a probability measure $\mu$ on a measurable space $(X,\Cal X)$ together with a countable and $L_2$-dense class $\Cal F$ of functions $f=f(x_1,\dots,x_k)$ of $k$ variables with some parameter~$D$ and exponent~$L$, $L\ge1$, on the product space $(X^k,\Cal X^k)$ such that $$ \|f\|_\infty=\sup\limits_{x_j\in X,\;1\le j\le k}|f(x_1,\dots,x_k)|\le 1, $$ and $$ \|f\|_2^2=Ef^2(\xi_1,\dots,\xi_k)=\int f^2(x_1,\dots,x_k) \mu(\,dx_1)\dots\mu(\,dx_k)\le \sigma^2 $$ for all functions $f\in \Cal F$ with some constant $0<\sigma\le1$. Then there exist some constants $C=C(k)>0$, $\alpha=\alpha(k)>0$ and $M=M(k)>0$ depending only on the parameter $k$ such that the supremum of the random integrals $J_{n,k}(f)$, $f\in \Cal F$, defined by formula (1.1) satisfies the inequality $$ P\left(\sup_{f\in\Cal F}|J_{n,k}(f)|\ge u\right)\le CD \exp\left\{-\alpha\left(\frac u{\sigma}\right)^{2/k}\right\}, $$ provided that $$ n\sigma^2\ge \left(\frac u\sigma\right)^{2/k}\ge M(L+\beta)^{3/2}\log\frac2\sigma, $$ where $\beta=\max\left(\frac{\log D}{\log n},0\right)$ and the numbers $D$ and $L$ agree with the parameter and exponent of the $L_2$-dense class~$\Cal F$.} \medskip A similar estimate holds for the supremum of degenerate $U$-statistics $I_{n,k}(f)$, $f\in\Cal F$. The only difference in comparison with the above result that in the case of the supremum of $U$-statistics the additional condition has to be imposed that the $U$-statistics $I_{n,k}(f)$ must be degenerate. An essential difference between the results about the estimation of the supremum of Wiener--It\^o integrals $Z_{\mu,k}(f)$ and integrals with respect to normalized empirical distribution $J_{n,k}(f)$ is that in the first case the class of functions $\Cal F$ had to be $L_2$-dense with respect to the product measure $\mu^k$, while in the second case a more restrictive condition was imposed. In the case of supremum of integrals with respect to a normalized empirical distribution the class of functions $\Cal F$ had to satisfy the $L_2$-property, i.e. it had to be $L_2$-dense with respect to all probability measures. The question arises what the cause of this difference is. The supremum of Wiener--It\^o integrals can be bounded by means of a simple and natural method, the so-called `chaining argument'. In the case of the random integrals $J_{n,k}(f)$ this method is not strong enough to solve the problem, it only yields some partial results. To get a complete solution some additional methods have to be applied, and their application demands some additional restrictions. The elaboration of the details would demand much work and the application of methods essentially different from previous ones. Hence I shall present only a brief sketch of the main ideas. The main emphasize will be put on the explanation of the main problems and methods. First I briefly explain the `chaining argument'. \medskip\noindent {\it The `chaining argument', and the boundary of this method.} \medskip Let us apply the notation worked out in the formulation of the results about the supremum of Wiener--It\^o integrals. Let us take for all indices $N=1,2,\dots$ such a system of increasing subsets $\Cal F_1\subset\Cal F_2\subset\cdots\subset\Cal F_N \subset\cdots\subset\Cal F$ of the class of functions $\Cal F$ with relatively small cardinalities which satisfy the relation $$ \inf_{g\in\Cal F_N}\int \left(f(x_1,\dots,x_k)-g(x_1,\dots,x_k) \right)^2\mu(\,dx_1)\dots\mu(\,dx_k)\le 2^{-2N}\sigma^2. $$ for all functions $f\in\Cal F$. The probabilities $$ P\left(\sup_{g\in\Cal F_N}Z_{\mu,k}(g)>u\left(1-2^{-N}\right)\right) $$ can be well estimated by means of a recursion for $N=1,2,\dots$, since for all functions $g\in \Cal F_{N+1}$ there exists a function $g'\in\Cal F_N$ (close to it) for which $$ \int\left(g(x_1,\dots,x_k)-g'(x_1,\dots,x_k)\right)^2 \mu(\,dx_1)\dots\mu(\,dx_k) \le 2^{-2N}\sigma^2. $$ Hence the probability $$ P(|Z_{\mu,k}(g)-Z_{\mu,k}(g')|>2^{-N}u)=P(|Z_{\mu,k}(g-g')|>2^{-N}u) $$ can be well estimated by means of the previous results about the tail distribution Wiener--It\^o integrals. By working out the details the result about the tail distribution of the supremum of Wiener--It\^o integrals can be relatively simply proved. \medskip The above considered `chaining argument' is not strong enough to estimate the supremum of integrals with normalized empirical distribution or of degenerate $U$-statistics. It only makes possible to reduce the problem to the case when the expressions $ \sigma^2(f)=\int f^2(x_1,\dots,x_k)\mu(\,dx_1)\dots\mu(\,dx_k) $ are small for all functions $f\in\Cal F$. The `chaining argument' is a weak method in the study of this problem for the following reason. There are only very weak estimates on probabilities of the form $$ P(I_{n,k}(f)>u) \quad \text{or} \quad P(J_{\mu,k}(f)>u) $$ if $\sigma^2(f)$ is very small, and the number $u$ is relatively large. This is the consequence of the previously discussed fact that there cannot be given such a good estimate for the tail distribution of degenerate $U$-statistics or random integrals with respect to a normalized empirical distribution function with small variance as the Gaussian comparison would suggest. This difficulty can be overcome by means of a different method, by means of a symmetrization argument. This method consists of reducing the estimation of a probability of the type $$ P\left(\frac1{k!} \sup_{f\in\Cal F} \sum \Sb 1\le j_s\le n,\; s=1,\dots, k,\\ j_s\neq j_{s'} \text{ if } s\neq s'\endSb f(\xi_{j_1},\dots,\xi_{j_k})>u\right) $$ to a probability of the type $$ P\left(\frac1{k!} \sup_{f\in\Cal F} \sum\Sb 1\le j_s\le n,\; s=1,\dots, k, \\ j_s\neq j_{s'} \text{ if } s\neq s'\endSb \varepsilon_{j_1}\dots\varepsilon_{j_k} f(\xi_{j_1},\dots,\xi_{j_k})>u\right), \tag6.2 $$ where $\varepsilon_1,\dots,\varepsilon_n$ are independent random variables with distribution $P(\varepsilon_j=1)=P(\varepsilon_j=-1)=\frac12$ for all indices $1\le j\le n$. Beside this, they are also independent of the random variables $\xi_1,\dots,\xi_n$. The probabilities in formula (6.2) can be well estimated by means of a `conditioning argument'. In the application of this method the conditional probability of the investigated event has to be bounded under the condition $\xi_1=x_1$,\dots, $\xi_n=x_n$ for all possible values $x_1,\dots,x_n$. There are good methods to estimate such type of conditional probabilities, but they are not discussed here. On the other hand, these methods work only if the class of functions $\Cal F$ is $L_2$-dense. This is the reason why this property appears in this problem. \medskip\noindent There is a point which should be emphasized even in this sketchy discussion of the problems. In the study of the supremum of random integrals with respect to a normalized empirical distribution or of degenerate $U$-statistics a different method was applied in the estimation of random variables with relatively large and small variance. In the case of relatively large variance the `chaining argument' works, while in the case of small variance an appropriate symmetrization argument was applied. Behind the different approaches in these two cases there is a deeper reason. The `chaining argument' works well only in the study of the supremum of degenerate $U$-statistics or random integrals with respect to a normalized empirical measures with not too small variance; in the case when the $U$-statistics and random integrals satisfy such estimates which their `Gaussian type limits' suggest. There can be defined some `irregular events' whose appearance implies that the $U$-statistics or random integrals take extremely large values. But in the case of random variables with not too small variances the probability of such irregular events is very small, and their effect can be disregarded. The case of $U$-statistics or random integrals with a small variance is different. In this case the probability of these irregularities (compared to the events of regular events) is relatively large, and in the estimation of the probabilities we are interested in their effect is dominant. The `chaining argument' works well in the case when the effect of the irregularities is negligible, and nice `Gaussian type estimates' hold. On the other hand, if the effect of the irregularities is non-negligible, then it is useful to apply symmetrization type arguments. \medskip\noindent In this work I tried to describe briefly the result of an important subject together with the heuristic picture behind the results. A more detailed discussion of this subject can be found in my work~[1]. Beside this, I plan to publish a Lecture Note which also contains a complete discussion of the technical details. For the time being this Lecture Note~[2] can be found only on my homepage. Both works~[1] and~[2] contain a more detailed list of references. \beginsection References \item{1.)} P\'eter Major: Tail behaviour of multiple random integrals and $U$-statistics. {\it Probability Reviews.} 448--505, (2005) \item{2.)} P\'eter Major: On the tail behavior of multiple random integrals and degenerate $U$-statistics. http://www.renyi.hu/\~{}major \bye