   
\documentclass{beamer}

\usepackage{t1enc}
\usepackage[magyar]{babel}
\usepackage[latin2]{inputenc}
% \usepackage[t1]fontenc}
\usepackage{amssymb,amsthm}
\usepackage{epsfig,boxedminipage}
\usepackage{color}

\usetheme{Singapore}
%\usetheme{CambridgeUS}
%\usetheme{Berlin}
\setbeamertemplate{blocks}[rounded][shadow=true]
\setbeamertemplate{navigation symbols}{} 

\setbeamertemplate{frametitle}{
\vskip-14mm
\begin{center}
% \hrule\vskip3pt
%\fbox{
~\vskip-11mm
\textbf{\Rd\insertframetitle} 
                \hfill{\tiny \insertframenumber}
% Itt állitható a frame-szamolas
\vskip4pt
% \hrule
% }
 \vskip3pt\hrule
\par
\end{center}
}
\def\Rd{\color[rgb]{0.99,0,0.1}}
%\def\Rd{\color[rgb]{0.5,0,0.1}}
\def\Bl{\color[rgb]{0.0,0,0.7}}
\def\Prp{\color[rgb]{0.7,0,0.7}}
\def\Orange{\color[rgb]{0.8,0.5,0.0}}
%\def\Green{\color[rgb]{0,0.3,0}}
%\def\Green{\color[rgb]{0,0.8,0}}
%\def\Green{\color[rgb]{0.1,0.7,0.1}}
\def\Green{\color[rgb]{0.0,0.3,0.0}}
\def\Qco{\color[rgb]{0.6,0,0.2}}  % Question to be clarified
\def\DBl{\color[rgb]{0,0,0.2}}
\def\Brown{\color[rgb]{0,0.3,0.3}}
\def\final{\DBl \sf }
\def\Final{\DBl \sf }
\def\FinalT{\DBl \sf }

\begin{document}

% \textheight=400pt
% \textwidth=630pt

%\baselineskip=35pt

\title{ \Rd Sharp estimate on the supremum of a class 
\\ of sums of small i.i.d. random variables.}

\author{P\'eter Major}

\maketitle

\begin{frame}{Formulation of the problem, motivation, and methods to
solve it}

{\Rd The problem:}

Let {\Green $\xi_1,\dots,\xi_n$} be a sequence of i.i.d. random
variables with some distribution  {\Rd  $\mu$} on a measurable
space {\Green $(X,{\cal X})$}.

Let a class of functions {\Bl ${\cal F}$} be given on the
space {\Green $(X,{\cal X})$} with some nice properties, such that 
{\Prp $\int f(x)\mu(\,dx)=0$} and  % \hfill\break
{\Prp $\sup_{x\in X}|f(x)|\le1$} for all elements
{\Bl $f\in{\cal F}$}.

Define the normalized sums 
{\Rd $S_n(f)=\frac1{\sqrt n}\sum_{j=1}^n f(\xi_j)$} 
for all {\Bl $f\in\cal F$}, and give a good estimate on the 
tail distribution  
{\Rd$$
P\left(\sup_{f\in{\cal F}} S_n(f)>x\right) 
\quad\textrm{for all numbers } x>0
$$}
of the supremum of these sums.

\end{frame}

\begin{frame}

{\Rd An important remark:} By an important result, called the 
{\Bl concentration inequality}, the distribution of this
supremum is concentrated in a {\Prp small neighbourhood of a concentration
point}. As a consequence, the above probability is small only if 
{\Bl $x$ is larger than this concentration point}. An {\Rd important} 
and hard part of the {\Rd problem} is to find a {\Bl good level} above 
which this  probability begins to {\Bl decrease radically}. This means 
a good estimate on value  of the {\Prp concentration point}. 
This is the hardest part of the problem.

\medskip
(We want to give an estimate on the {\Bl concentration point} with the 
accuracy of a {\Prp universal multiplying constant}.)

\end{frame}

\begin{frame}{Our motivations to study this problem}

{\Bl Motivation 1.:} {\Rd Dudley's theory of uniform central limit theorem.}
Given a nice {\Prp class of functions $\cal F$} and a sequence of 
{\Prp i.i.d. random variables $\xi_1,\dots,\xi_n$} prove that the class of
normalized sums 
{\Bl $S_n(f)=\frac1{\sqrt n}\sum_{j=1}^nf(\xi_j)$, $f\in{\cal F}$,}  
satisfy some sort of {\Bl functional limit theorem}. 

Crucial point of the proof: Show that 
{\Bl $\sup_{f,f'\in{\cal F}'}S_n(f-f')$ is small} if  
{\Prp ${\cal F}'\subset{\cal F}$}, and {\Prp ${\cal F}'$} has the 
property that {\Prp $E[f(\xi_1)-f'(\xi_1)]^2<\delta$} with a small 
{\Rd $\delta>0$} for {\Rd all $f,f'\in{\cal F}'$}. We have formulated 
a natural generalization of this problem, where we may consider
{\Bl $\delta_n\to0$} as {\Bl $n\to\infty$} instead of a fixed $\delta>0$.

\end{frame}

\begin{frame}

{\Bl Motivation 2.:} To get good {\Rd limit theorems} for so-called 
{\Rd non-parametric maximum likelihood estimates} it is useful to
prove sharp {\Bl estimates on the tail distribution} of the 
{\Prp supremum of multiple integrals} with respect 
to normalized empirical distibution functions, i.e. of expressions 
of the form:
{\Rd \begin{eqnarray*}
&&\sup_{f\in{\cal F}}\idotsint f(x_1,\dots,x_k)\\
&&\qquad \sqrt n(dF_n(x_1)-dF(x_1))\dots \sqrt n (dF_n(x_k)-dF(x_k)),
\end{eqnarray*} }
where {\Rd $F$} is a distribution function {\Rd $F_n$} is the 
{\Rd empirical distribution function} of an $F$ distributed sample, 
and {\Rd ${\cal F}$} is a nice class of functions of {\Rd $k$ variables}. 
(See my lecture note {\Green On the estimation of multiple random 
integrals and $U$-statistics.}) Here we investigate this problem 
for {\Rd $k=1$}.

\end{frame}

\begin{frame}{The Gaussian version of the problem}

The sums {\Bl $S_n(f)=\frac1{\sqrt n}\sum\limits_{j=1}^n f(\xi_j)$}
satisfy the central limit theorem. Hence it is natural to
consider a {\Prp Gaussian version} of our problem. We want 
to understand what kind of results and methods suggests 
the result of this Gaussian version.

{\Rd The Gaussian problem:} Let {\Green $\eta_t$, $E\eta_t=0$, $t\in T$}, 
be  a countable  set of random variables with (jointly)
{\Rd Gaussian distribution}. Put 
{\Rd $d_2(s,t)=\left[E(\eta_s-\eta_t)^2\right]^{1/2}$},
{\Prp $s,t\in T$}. Then {\Bl $d_2(s,t)$} is a metric on the 
parameter set {\Green $T$}. Give a good estimate on the
probability  {\Bl $P\left(\sup_{t\in T}\eta_t>x\right)$} 
for all numbers ${\Bl x>0}$ with the help of the
function {\Bl $d_2(s,t)$}. 

\end{frame}

\begin{frame}{The result about the Gaussian problem} 

There is a simple and natural method, called  the 
{\Rd chaining argument} to study this problem. It yields the
following result.  

{\Rd {\bf Theorem.}}
{\it Let $\eta_t$, $t\in T$, be a set of Gaussian random
variables indexed by a countable set $T$. Assume that {\Bl $E\eta_t=0$, 
$E\eta_t^2\le\sigma^2$} with some $0\le\sigma\le1$ for all
$t\in T$, and the metric
{\Rd $d_2(s,t)=\left[E(\eta_s-\eta_t)^2\right]^{1/2}$}, $s,t\in T$,
has the following property. There exist some constants 
{\Prp $L\ge1$} and~{\Prp $D\ge1$} 
such that for all $0\le\varepsilon\le1$ a subset 
{\Bl $\{t_1,\dots,t_P\}\subset T$} can be found
with cardinality {\Bl $P\le D\varepsilon^{-L}$} for which 
{\Bl $\min_{1\le j\le P}d_2(t,t_j)\le\varepsilon$}
for all $t\in T$. Then the inequality
{\Rd \begin{eqnarray*}
&&P\left(\sup_{T \in T}|\eta_t|
\ge u\right)\le C(D+1) \exp\left\{-\frac1{256}
\left(\frac u{\sigma}\right)^2\right\} \\
&&\qquad\qquad\qquad\qquad 
\textrm{if }u\ge ML^{1/2}\sigma \log^{1/2}\frac2\sigma
\end{eqnarray*}}
holds with some universal constants $C>0$ and $M>0$.}

\end{frame}

\begin{frame}{A comparison of our problem with the above result} 

In our problem {\Prp ${\cal F}$} plays the role of the parameter set 
{\Prp $T$}, and
{\Bl $d_2(f,g)^2=E(S_n(f-g)^2)=\int[f(x)-g(x)]^2\mu(\,dx)$}, 
$f,g\in{\cal F}$.

The previous theorem also holds if the random variables 
$\eta_t$, $t\in T$, are non-Gaussian, but they satisfy the 
{\Bl Gaussian type inequality}
{\Rd $$
P(|\eta_t-\eta_s|>u)\le C_1 e^{-C_2u^2/d_2(s,t)^2} \quad\textrm{for all }
s,t\in T \textrm{ and } u>0
$$}
with some constants $C_1>0$ and $C_2>0$.

What is the case in our problem?

Some classical results (e.g. {\Prp Bernstein's inequality}) 
provide the above inequality under some restriction, 
(e.g. if {\Bl $u\le\textrm{const.}\sqrt nd_2^2(s,t)$}), but it may 
not hold without such a restriction. (See my lecture note 
{\Green On the estimation of multiple random  integrals and 
$U$-statistics}, Chapter~3.)

\end{frame}

\begin{frame}

To get results similar to the Gaussian case for {\Bl sums of 
bounded i.i.d. random variables} some {\Rd additional restriction} 
has to be imposed, and the proof requires new ideas. I know of 
two approaches.

{\Rd Approach 1.} {\Bl Due to Talagrand.} Define the metric 
{\Prp $d_\infty(f,g)=\sup_{x\in X}|f(x)-g)x)|$, $f,g\in{\cal F}$}, and 
introduce {\Bl the additional condition} that there exist some constants
$D\ge 1$ and $L\ge1$ such that for all $0\le\varepsilon\le1$ 
{\Rd $P\le D(n^{-1/2}\varepsilon)^{-L}$} functions $f_j\in{\cal F}$,
$1\le j\le P$, can be found for which 
{\Prp $\min_{1\le j\le P}d_\infty(f,f_j)\le\varepsilon$ for all 
$f\in{\cal F}$}.
This condition together with the {\Rd condition on the metric 
$d_2(\cdot,\cdot)$} in the theorem about the Gaussian version imply a
similar estimate. Talagrand proved a stronger result formulated with a
different terminology in his book {\Green The generic chaining}.

\medskip
The proof is based on an appropriate version of the 
{\Rd chaining argument}. In the proof we exploit that if 
the terms of a sum of independent random variables have 
a very  {\Bl small bound} in the supremum norm, then the 
{\Prp tail distribution} of the sum has a good 
{\Prp  Gaussian upper bound} even at high levels.

\end{frame}

\begin{frame}

Talagrand found interesting applications of his result, 
but there are important models where it does not work.

\medskip
{\Rd Example where Talagrand's result cannot be applied.}
Let $(X,{\cal X})$ be the unit interval $[0,1]$ with the Borel 
$\sigma$-algebra, let {\Bl $\xi_1,\dots,\xi_n$} be i.i.d. random
variables on $[0,1]$ with {\Bl uniform distribution}. Put 
{\Prp ${\cal F}=\{f_{a,b}(x)\}$}, where 
{\Green $0\le a<b\le a+\sigma^2$} with a {\Green small number $\sigma^2>0$},
$a,b$ are rational numbers, and {\Prp $f_{a,b}(x)=I_{a,b}(x)-(b-a)$}, 
where $I_{a,b}(\cdot)$ is the indicator function of the interval $(a,b)$.

\medskip
This example satisfies the conditions we imposed for our models,
and the {\Bl condition} imposed {\Bl on the metric $d_2(\cdot,\cdot)$}
with parameters $L$ and $D$ which have an {\Prp upper bound not 
depending on $\sigma^2$}, but the {\Bl $d_\infty(\cdot,\cdot)$}
metric behaves badly. But all {\Prp functions $f_{a,b}$} are far 
from each other in the {\Prp supremum norm}.

To handle such models we introduce a different method. 

\end{frame}

\begin{frame}

{\Rd Approach 2.} (Based on a {\Rd Vapnik--\v{C}ervonenkis} type 
argument.) We formulate an {\Rd additional condition on ${\cal F}$} 
with the help of a notion called the 
{\Prp class of functions with polynomially increasing covering numbers}
instead of the condition about the behaviour of the 
{\Prp $d_\infty$ metric}. We prove results with its help. 

\medskip
We give the {\Prp definition of a class of functions with 
polynomially increasing covering numbers} in two steps.

First step of the definition.

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

\end{frame}

\begin{frame}

Second step of the definition.

\medskip
{\Rd {\bf Definition of a class of functions with polynomially
increasing covering numbers.}} We say that a
class of functions $\cal F$ has {\Bl polynomially increasing 
covering numbers} with {\Prp parameter~$D$} and {\Prp exponent $L$} 
if the inequality
{\Rd $$
\sup_\nu {\cal N}(\varepsilon,{\cal F},L_1(\nu))\le D\varepsilon^{-L} 
$$}
holds for all {\Bl $0<\varepsilon\le 1$} with the number 
{\Rd $\sup_\nu {\cal N}(\varepsilon,{\cal F},L_1(\nu))$} 
introduced in the previous definition.

\medskip 
There is a good estimate for the probability of 
$P(\sup_{f\in{\cal F}}|S_n(f)>x)$ if the class of 
functions ${\cal F}$ has polynomially increasing covering 
numbers with some parameter $D\ge1$ and $L\ge1$. See 
{\Green On the estimation of multiple random integrals
and $U$-statistics, Theorem 4.1.} This result describes 
fairly well when we can get {\Rd such a good estimate} in our 
problem as in its {\Rd Gaussian counterpart}. 

\end{frame}

\begin{frame}

The proof is based on some {\Bl ideas of K. S. Alexander}, 
and applies the so-called {\Rd symmetrization argument}. 
It says that under some not too restrictive conditions 
{\Rd $\sup_{f\in{\cal F}}\sum_{j=1}^n f(\xi_j)$} has 
a similar tail distibution as its {\Bl randomized version} 
{\Rd $\sup_{f\in{\cal F}}\sum_{j=1}^n\varepsilon_j f(\xi_j)$}, 
where $\varepsilon_1,\dots,\varepsilon_n$ are i.i.d. random 
variables, independent also of the random variables $\xi_j$, 
and {\Rd $P(\varepsilon_1=1)=P(\varepsilon_1=-1)=\frac12$}.

The symmetrized version
{\Rd $\sup_{f\in{\cal F}}\sum_{j=1}^n\varepsilon_j f(\xi_j)$} 
can be better handled than the original expression, and this 
is exploited in the {\Bl symmetrization argument.}. 

\medskip
Nevertheless, this technique gives a weak estimate 
if {\Bl $Ef(\xi_1)^2\le\sigma^2$ for all $f\in{\cal F}$} 
with a {\Rd very small $\sigma^2$}. In this case the above 
mentioned Theorem~4.1 in my lecture note does not give a 
sharp estimate. Our goal is to give a {\Prp sharp estimate 
in all cases}. It turned out that the next result, the 
{\Prp main result of the paper} under discussion, 
{\Prp plays a crucial role} in achieving this goal.

Here is this result. 

\end{frame}

\begin{frame}

\medskip
{\Rd {\bf Main theorem.}} {\it  Let $\cal F$ be a finite or countable 
class of functions on a measurable space $(X,{\cal X})$ which 
has {\Rd polynomially increasing covering numbers} with some 
{\Rd parameter $D\ge1$} and exponent {\Rd $L\ge1$}, and
{\Rd $\sup_{x\in X} |f(x)|\le 1$} for {\Bl all $f\in{\cal F}$}. 
Let $\xi_1,\dots,\xi_n$, $n\ge2$, be a sequence of i.i.d. 
random variables with values in the space $(X,{\cal X})$ 
with a {\Bl distribution $\mu$}, and assume that the inequality 
{\Rd $\int |f(x)|\mu(\,dx)\le\rho$} holds for {\Bl all 
$f\in{\cal F}$} with a number {\Rd $0<\rho\le n^{-200}$}. Put 
{\Prp $\bar S_n(f)=\bar S_n(f)(\xi_1,\dots,\xi_n)=\sum_{j=1}^nf(\xi_j)$} 
for all $f\in{\cal F}$. The inequality 
{\Rd $$
P\left(\sup_{f\in {\cal F}}|\bar S_n(f)|\ge u\right)\le D\rho^{Cu} \quad
\textrm{for all } u>41L 
$$}
holds with some universal constant $1>C>0$. We can choose e.g. 
$C=\frac1{50}$.}

\medskip
(The condition {\Rd $\int f(x)\mu(\,dx)=0$} for all $f\in{\cal F}$ 
is not needed in this result.)

\end{frame}

\begin{frame}{An example that may help to understand the content 
of the Main theorem}

Let $(X,{\cal X})$ be a {\Bl finite set with $N$ elements}, 
{\Prp $\mu$ the uniform distribution} on it, 
($\mu(A)=\frac1N\cdot\textrm{the number of elements in }A$.)
Fix a number $d\ge1$ and let ${\cal F}$ be the set of indicator 
functions of the {\Bl subsets of $X$ containing at most $d$ elements.} 
Let $\xi_1,\dots,\xi_n$ be i.i.d. random variables, and define 
{\Rd $\bar S_n(f)=\sum_{1\le j\le n}f(\xi_j)$} with their help. 

\medskip
Question: What can we say about 
{\Rd $P(\sup_{f\in{\cal F}}\bar S_n(f)>u)$}? 

\medskip
We are interested in the case when {\Prp $\frac nN$ is small}. 
It is clear that {\Rd $P(\sup_{f\in{\cal F}}\bar S_n(f)\ge u)=1$} 
if {\Bl $u\le d$}. If {\Prp $u>d$}, then this probability is a 
{\Prp fast decreasing function of $u$}.
(See Section~1 of the paper for details.) On the other hand the 
indicator functions {\Bl $\{x\colon\, f(x)=1\}$, $f\in{\cal F}$}, 
constitute a (classical)
{\Bl example of Vapnik--\v{C}ervonenkis classes}. 

\end{frame} 

\begin{frame} 

The notion of {\Rd class of functions with polynomially 
increasing covering numbers} can be considered as a 
{\Rd version of Vapnik--\v{C}ervonenkis classes} for 
classes of functions, and these two notions behave similarly. 
In particular, by some results the class of functions in the 
above example has polynomially increasing covering numbers 
with {\Bl exponenent $L=(1+\varepsilon)d$} for all 
$\varepsilon>0$ and appropriate $D=D(\varepsilon)$. 

Some considerations show that the main theorem can be interpreted
in the following way:

\medskip
For a {\Prp class of functions ${\cal F}$ with polynomially 
increasing covering numbers} and the property that 
{\Bl $\sup_{f\in{\cal F}}\int |f(x)|\mu(\,dx)$} is very {\Bl small} 
the {\Rd tail distribution of $|\sup_{f\in{\cal F}}\bar S_n(f)|$}
satisfies such an inequality that the above (simple) example suggests. 

\end{frame}

\begin{frame} {The real role of the Main theorem}

We are interested in the Main theorem not for itself. It is 
interesting for us, because it yields a {\Rd better application 
of the Vapnik--\v{C}ervonenkis argument} than the 
{\Bl symmetrization method}.

\medskip
The condition {\Rd $\int |f(x)|\mu(\,dx)\le\rho$} for all
{\Rd $f\in{\cal F}$} with {\Rd $0<\rho\le n^{-200}$} 
is not very restrictive. This (together with the existence of 
{\Prp polynomially increasing covering numbers} in our models) 
enables us to split up the class of functions ${\cal F}$ into 
{\Rd the union of relatively few subsets ${\cal F}_j$}, $1\le j\le M$,  
($M\le n^K$  with some $K>0$) in such a way that fixing 
some $f_j\in{\cal F}_j$ the {\Rd tail distribution of 
$\sup_{f\in{\cal F}_j}|\bar S_n(f-f_j)|$} can be well bounded by 
means of the Main theorem.

\medskip
Since we have to work only with {\Bl polynomially many 
subsets ${\cal F}_j\subset{\cal F}$} we can give a 
better, more complete solution of our problem. This is 
the topic of my paper {\Green Sharp tail distribution 
estimates for the supremum of a class of sums 
of i.i.d. random variables.}

\end{frame}

\begin{frame}{The main ideas of the proof}

Let $X$ be a {\Bl finite set} with {\Bl $2^k$} elements with a 
{\Bl large integer $k$}, {\Rd $\mu$} be the 
{\Rd uniform distribution on $X$}. Consider a model satisfying
the conditions of the Main theorem with such an $X$ and $\mu$, 
and prove the estimate of the  Main theorem for 
{\Rd $P(\sup_{f\in{\cal F}}\bar S_n(f)|\ge n)$}. We may 
assume that {\Rd $f(x)\ge0$} for all $x\in X$ and $f\in{\cal F}$.

\medskip
We prove first this special result in {\Bl Theorem 1A} and 
then the Main theorem with its help. We prove {\Bl Theorem 1A} 
with the help of an {\Rd induction procedure for $k$} with a 
{\Prp large starting number $k_0$}. The {\Bl starting step} of
the induction is done in {\Bl Lemma 3.1}. 
%We need the condition
%$\int |f(x)|\mu(\,dx)\le\rho$ for all $f\in{\cal F}$ with 
%a small number $\rho$ to start our induction with a 
%large $k_0$.

To carry out our {\Bl induction procedure} we need a 
result formulated in {\Bl Lemma 3.2.} This states 
that if a class of functions ${\cal F}$ with 
{\Bl polynomially increasing covering numbers} on a set 
$X$ of {\Prp cardinality $2^k$} with a 
{\Bl large number $k$} has the property
{\Rd $\int f(x)\mu(\,dx)\le\rho$} for all $f\in{\cal F}$ 
with the {\Rd uniform distribution $\mu$ on $X$}, then
this property is preserved for {\Bl most subsets}
of $X$ with {\Prp cardinality $2^{k-1}$} if $\rho$ is
replaced by a {\Bl slightly larger $\bar\rho$}. 

\end{frame}

\begin{frame}

To prove Theorem 1A observe that
{\Bl $\sup_{f\in{\cal F}}\bar S_n(f)\ge n$} if and only if 
there is some $f\in{\cal F}$ for which {\Bl $f(\xi_j)=1$ 
for all $1\le j\le n$}. Hence to prove Theorem 1A we have 
to give a good estimate on the {\Bl number of sequences} 
{\Rd $(x_{l_1},\dots,x_{l_n})\in X^n$} such that
{\Rd $x_{l_j}\in B_f=\{x\colon\,f(x)=1\}$} for all 
{\Rd $1\le j\le n$}, and some {\Rd $f\in{\cal F}$}. We 
prove such an estimate by means of induction with 
respect to $k$ with the help of Lemma~3.2. 

\medskip
We assume that an appropriate estimate holds on the number 
of such sequences for classes of functions ${\cal F}$ with 
{\Bl polynomially increasing covering numbers} with 
{\Bl exponent $L\ge1$} and {\Bl parameter $D\ge1$} on a set 
$X$ of {\Prp cardinality $2^{k-1}$} if also the condition 
{\Rd $\int |f(x)|\mu(\,dx)\le\rho_{k-1}$}
holds for {\Rd all $f\in{\cal F}$} with an appropriately chosen
{\Rd $\rho_{k-1}$}. Then we prove the analogous result for 
parameter $k$ with an appropriately chosen $\rho_k$ by means
of Lemma~3.2. 

We define for all functions $f\in {\cal F}$ and sets
$B\subset X$ of cardinality $2^{k-1}$ the function
{\Prp $f_B$} as the {\Prp restriction of $f$ to $B$}, 
and put {\Prp ${\cal F}_B=\{f_B\colon\,f\in{\cal F}\}$}. 

\end{frame}

\begin{frame}

Then by  applying the {\Prp inductional hypothesis for $k-1$} 
for the sets $B\subset X$ of cardinality $2^{k-1}$ 
with the classes of functions ${\cal F}_B$ and taking an 
{\Prp average for all sets $B$ of cardinality $2^{k-1}$} 
we get an estimate on the number of sequences 
{\Bl $(x_{l_1},\dots,x_{l_n})\in X^n$} with the
requested properties. In this calculation we  
{\Rd apply Lemma~3.2} and choose the constants $\rho_k$ 
in an appropriate way. If we do this carefully, then we can
carry out the {\Bl induction procedure}, and by letting 
{\Bl $k\to\infty$} we get the {\Rd proof of Theorem~1A}. 

\medskip
The crucial part of the problem is the {\Rd proof of Lemma~3.2}.
Its main step is to show that 
{\Rd $\int (f_B-f_{X\setminus B})\,d\mu$ is small} with 
probability almost~1 for any $f\in{\cal F}$, if we 
{\Rd choose the set $B$ randomly} among the sets $B\subset X$ 
of {\Prp cardinality $2^{k-1}$}, and $f_B$ denotes the 
restriction of $f$ to the set $B$. This implies that
$\int f_B\,d\mu_B\le\bar\rho$ with a number slightly larger
than $\rho$ with probability almost 1, where {\Bl $\mu_B$} is 
the {\Bl uniform distribution on $B$}. With an appropriate choice
of $\bar\rho$ we can achieve that even  
{\Rd $\sup_{f\in{\cal F}}\int f_B\,d\mu_B\le\bar\rho$ with 
probability almost 1}. Here we exploit that ${\cal F}$ has
{\Prp polynomially increasing covering numbers}. The last 
inequality implies Lemma~3.2. 

\end{frame}

\begin{frame}

We can estimate the tail distribution of 
{\Rd $\int (f_B-f_{X\setminus B})\,d\mu
=2^{-k}(\sum_{x\in B}f(x)-\sum_{x\notin B}f(x))$}, where $B$ is
a randomly chosen subset of $X$ with cardinality $2^{k-1}$ by
means of a method that appeared also in  the proof of
{\Green Lemma 3} of the paper {\Green Koml\'os--Major--Tusn\'ady: 
An approximation of partial sums of independent rv's and the sample DF}. 

The method: Take a {\Prp pairing $(x_{l_1},x_{l_2})$,\dots
 $(x_{l_{2^k}-1},x_{l_{2^k}})$ of the set $X$}, and define a random set
$B$  with $2^{k-1}$ elements by putting in each pair one 
{\Bl randomly chosen} element into the set $B$ and the other one 
into the complementary set. We can well estimate the 
{\Rd tail distribution of $2^{-k}(\sum_{x\in B}f(x)-\sum_{x\notin B}f(x))$}
if we choose only {\Rd sets $B$ obtained in such a way} e.g. with 
the help of {\Bl Hoeffding's inequality}. Then {\Rd averaging 
for all possible pairings} of $X$ we can
get the estimate we need to complete the proof of Lemma~2.2.

Finally I briefly explain how to prove the Main theorem with the
help of Theorem~1A.

\end{frame}

\begin{frame}%{Completion of the proof}

First I give a good estimate on 
{\Bl $P(\sup_{f\in{\cal F}}\bar S_n(f)>u)$} for {\Bl all $u>0$} 
under the conditions of Theorem~1A in {\Rd Lemma~4.1}. 
To prove this estimate I show that the event 
{\Bl $\sup_{f\in{\cal F}}\bar S_n(f)>u$} may hold only if for 
some {\Prp index $j$} there is a relatively long sequence 
$\{l_1,\dots,l_s\}\subset\{1,\dots,n\}$ such that
{\Prp $f(\xi_{l_1})\ge2^{-j}$,\dots, $f(\xi_{l_s})\ge2^{-j}$} 
for some {\Prp $f\in{\cal F}$}. The probability of such an event
can be well estimated with the help of {\Rd Theorem~1A}. Then
a careful calculation provides the {\Rd proof of Lemma~4.1.}

\medskip
The Main theorem is proved by means of {\Prp Lemma 4.1}. We 
can reduce the proof to the case when {\Rd ${\cal F}$} is a 
{\Rd finite set}. If its cardinality is $R$, then we can 
approximate  ${\cal F}=\{f_1,\dots,f_R\}$ with a class of 
functions ${\cal G}=\{g_1,\dots,g_R\}$ whose elements take only 
{\Bl finitely many values}, the $\mu$-distribution of all events 
$\{g_1(x)=u_1,\dots,g_R(x)=u_R\}$ is an {\Bl integer multiplied
by $2^{-k}$} with some number $k$, and the functions {\Prp $g_j$}
are so {\Prp close to the functions $f_j$} that it is
enough to prove the Main Theorem for  {\Rd ${\cal G}$} instead of 
{\Rd ${\cal F}$}. On the other hand, this can be done  with the 
help of {\Rd Lemma~4.1}.

\end{frame}

\end{document}








