  
\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}

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 
all elements {\Bl $f\in{\cal F}$} have the properties

{\Prp $\int f(x)\mu(\,dx)=0$},
{\Prp $\sup_{x\in X}|f(x)|\le1$}, and

{\Prp $\int f^2(x)\mu(\,dx)\le\sigma^2$} with some {\Prp $0<\sigma^2\le 1$}.

\medskip
We also assume that {\Bl ${\cal F}$} is a class of functions 
{\Bl with polynomially increasing covering numbers} with exponent 
{\Prp $L$} and parameter {\Prp $D$}. (I recall its definition later.)

\medskip
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$}. Our goal is to 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. This may depend on {\Rd $\sigma^2$, $L$} 
and {\Rd $D$}.

\end{frame}

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

The sums {\Bl $S_n(f)=\frac1{\sqrt n}\sum\limits_{j=1}^n f(\xi_j)$}
are asymptotically Gaussian. Hence it is natural to look at a
Gaussian version of this problem, where we estimate the 
{\Rd supremum} of {\Rd Gaussian} random variables 
{\Prp $\eta_t$, $t\in T$}. We want to understand what kind of
methods and results this Gaussian version suggests.

This Gaussian problem can be solved with the help of the so-called
{\Rd chaining argument}. The estimate depends on the metric 
$d_2(\cdot,\cdot)$, defined as 
{\Rd $d_2(s,t)=\left[E(\eta_s-\eta_t)^2\right]^{1/2}$},
{\Prp $s,t\in T$}. 

A similar result holds if the random variables 
$\eta_t$, $t\in T$, may be non-Gaussian, but they satisfy the 
{\Bl Gaussian type inequality}
{\Rd \begin{equation}
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  \label{1}
\end{equation}}
with some constants $C_1>0$ and $C_2>0$.

The question arises whether such a result holds in our problem.

\end{frame}

\begin{frame}
We can formulate our problem in that form as its Gaussian counterpart.
By some classical estimates the {\Rd inequality (\ref{1})
holds} under some {\Rd restrictions} (if {\Prp $u>0$ is not too large,
$\sigma^2$ is not too small}). These conditions cannot be omitted.

As a consequence, we can give a good estimate in our problem only 
under some additional conditions. We can handle the case 
when {\Prp $\sigma^2$} is small only if we impose {\Bl new conditions} 
and find {\Bl new methods}.

\medskip
{\Rd The new condition:} {\Bl ${\cal F}$} is a {\Bl class of functions 
with polynomially increasing covering numbers}.

{\Rd The method of proof} applied in earlier papers: 
{\Bl Symmetrization argument}.

\medskip
The notion of  {\Prp class of functions with polynomially 
increasing covering numbers} is a natural version of
the {\Prp Vapnik--\v{C}ervonenkis classes} if we are working
with {\Bl classes of functions} instead of {\Bl classes of sets}.

\medskip
I give its definition in two steps.

\end{frame}

\begin{frame}

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}$}.

\medskip
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.

\end{frame}

\begin{frame}

In the {\Rd symmetrization argument} we exploit 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 {\Bl $\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 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$}, since in this case the 
'cancellation effect' of the symmetrization does not
work. 

\medskip
Our goal is to give a {\Prp sharp estimate 
for all $0\le\sigma^2<1$}. It turned out that the  
 {\Bl main result of this paper} the {\Rd Main theorem}
formulated below  {\Prp plays a crucial role} 
in achieving this goal.

\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 \begin{equation}
P\left(\sup_{f\in {\cal F}}|\bar S_n(f)|\ge u\right)\le D\rho^{Cu} \quad
\textrm{for all } u>41L \label{2} 
\end{equation}}
holds with some universal constant $1>C>0$. We can choose e.g. 
$C=\frac1{50}$.}

\end{frame}

\begin{frame} 

The following details may be interesting in this result:

1.) We assumed that {\Prp $\int |f(x)|\mu(\,dx)\le\rho$} for 
{\Bl $f\in{\cal F}$} with {\Prp $0<\rho\le n^{-200}$}, i.e.
{\Bl $\rho$ is very small.} 

2.) We did not need the condition {\Prp $\int f(x)\mu(\,dx)=0$} 
for $f\in{\cal F}$. 

3.) Formula {\Prp (\ref{2})} holds for {\Prp $u>41L$}, i.e. 
even at relatively {\Prp low levels}.

\medskip
There are simple examples that show that the {\Rd Main theorem} is a
{\Rd sharp estimate.}

\medskip
{\Rd Why is the above result interesting for us?}

\medskip
It is important for us not as a new estimate, but as a {\Rd new tool}
to investigate our problem.

\medskip
Since the condition {\Prp $0<\rho\le n^{-200}$} means that 
{\Prp $\rho$} is a polynomially decreasing function of the 
sample size {\Prp $n$} we can work out a {\Rd better estimate} 
in our problem with the help of a 
{\Prp Vapnik--\v{C}ervonenkis type method}
than the {\Bl symmetrization argument}.

\end{frame} 

\begin{frame} 

In my subsequent paper 
{\Green Sharp tail distribution estimates for the supremum 
of a class of sums of i.i.d. random variables}
I give a fairly complete solution of the problem mentioned
at the start of this talk with the help of {\Rd Main Theorem}.

\medskip
Here I could give a very concise explanation of this paper.
A more detailed version of a (possible) talk about the motivations
and content of this paper can be found on my homepage at the
address

\medskip
{\Rd http://www.renyi.hu/\~{ }major/talks/positive.html }

\medskip
On the subsequent paper  
{\Green Sharp tail distribution estimates for the supremum 
of a class of sums of i.i.d. random variables} at the address

\medskip
{\Rd http://www.renyi.hu/\~{ }major/talks/supremum.html }



\end{frame}

\end{document}








