
\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

\begin{frame}{The problem we are interested in}

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}$} consisting of
countably many functions  be given on the
space {\Green $(X,{\cal X})$} with the properties 
{\Prp $\int f(x)\mu(\,dx)=0$},
{\Prp $\sup_{x\in X}|f(x)|\le1$} and 
{\Prp $\int f(x)^2\mu(\,dx)\le\sigma^2$} with some 
{\Prp $0<\sigma\le1$} for all elements {\Bl $f\in{\cal F}$}.

Let {\Bl ${\cal F}$} be a class of functions
with {\Bl polynomially increasing covering numbers} with 
{\Bl exponent $L\ge1$} and {\Bl parameter $D\ge1$}. (I recall
the definition of this notion later.) 

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\begin{equation}
P\left(\sup_{f\in{\cal F}} S_n(f)>v\right) 
\quad\textrm{for all numbers } v>0 \label{1}
\end{equation}}
of the supremum of these sums. This estimate may depend on 
{\Rd $\sigma$, $L$} and {\Rd $D$}.

\end{frame}

\begin{frame} 

An important result, called the {\Bl concentration inequality}, has
the consequence that there is a number {\Bl $v_0$} such that for 
{\Prp $v<v_0$} the {\Prp probability} in formula~(\ref{1}) is 
{\Prp almost 1}, while for {\Bl $v>v_0$,} it begins to 
{\Bl decrease rapidly}. An important part of our problem is to
give a {\Rd good estimate} on this numbern {\Rd $v_0$}.

\medskip
There is a solution for a natural {\Bl version} of 
our problem when we estimate the {\Bl supremum} of 
{\Bl Gaussian} random variables. This is done by means 
of a method called the {\Rd chaining argument}. 

A {\Prp similar estimate}  can be proved under some 
{\Prp restrictions} in our model with the help of the so-called 
{\Bl symmetrization argument}. Our goal is to prove a good 
estimate in {\Bl in the general case}, which holds without
these restrictions. 

\medskip
To discuss this problem first I recall the definition of 
{\Bl classes of functions with polynomially incerasing 
covering numbers} together with their {\Prp exponent $L$} 
and {\Prp parameter $D$}. I do this in two steps on the 
next page.

\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}{A useful example} 

First I present a simple example which may help to understand
how to {\Prp estimate} the {\Prp concentration point} $v_0$.

\medskip
{\Rd Example.}  Take a sequence of {\Bl independent, uniformly 
distributed} random variables $\xi_1,\dots,\xi_n$ on the unit 
interval~{\Bl $[0,1]$}, fix a number {\Prp $0\le\sigma^2\le 1$},
 and  define a class of functions ${\cal F}_\sigma$ and 
$\bar {{\cal F}_\sigma}$ as set of functions defined on the unit interval 
$[0,1]$ in the following way. ${\cal F}_\sigma=\{f_1,\dots,f_k\}$, 
and $\bar{{\cal F}}=\{\bar f_1,\dots,\bar f_k\}$ with 
{\Prp $k=k(\sigma)=[\frac1{\sigma^2}]$}, where $[\cdot]$ denotes 
integer part, and {\Rd $\bar f_j(x)=\bar f_j(x|\sigma)=1$  if 
$x\in[(j-1)\sigma^2,j\sigma^2)$}, $\bar f_j(x)=\bar f_j(x|\sigma)=0$ 
if  $x\notin[(j-1)\sigma^2,j\sigma^2)$, $1\le j\le k$, and 
{\Rd $f_j(x)=f_j(x|\sigma)=\bar f_j(x)-\sigma^2$}, $1\le j\le n$.

Give a good estimate on {\Rd $P_n(v)=P(\sup_j S_n(f_j)>v)$}.

\medskip 
${\cal F}$ satisfies the conditions in our problem. It is a 
class of functions with {\Bl polynomially increasing covering
numbers} with some {\Prp exponent $L$} and {\Prp parameter $D$} 
which do not depend on {\Prp $\sigma^2$}, and the parameter 
{\Rd $\sigma^2$} introduced in the model is an 
upper bound for all {\Rd $\int f_j(x)^2\mu(\,dx)$}. 

\end{frame}

\begin{frame}

{\Rd Our first problem:} Find a good lower bound
for the numbers {\Rd $v_0$} for which {\Rd $P_n(v)\ll 1$} 
only for {\Rd $v>v_0$}. The next result gives a solution.

\medskip\noindent
{\Rd An estimate on the function $P_n(v)$ in the models 
of the above example.} A number $\bar C>0$ can be 
chosen in such a way that for all $\delta>0$ there is an 
index $n_0(\delta)$ such that for all sample sizes 
$n\ge n_0(\delta)$ and numbers $0\le\sigma\le1$ the inequality 
{\Rd $$
P_n(\hat u(\sigma))=P\left(\sup_{f\in{{\cal F}_\sigma}}|S_n(f)|
\ge\hat u(\sigma)\right)\ge1-\delta, 
$$}
holds with 

1.) {\Rd $\hat u(\sigma)=\frac{\bar C}{\sqrt n}$} if 
{\Bl $\sigma^2\le n^{-400}$},

2.) {\Rd $\hat u(\sigma)=\frac{\bar C}{\sqrt n}\frac{\log n}
{\log(\frac{\log n}{n\sigma^2})}$}  if
{\Bl $n^{-400}<\sigma^2\le\frac{\log n}{8n}$}, and

3.) {\Rd $\hat u(\sigma)=\bar C\sigma\log^{1/2}\frac2\sigma$} 
if {\Bl $\frac{\log n}{8n}\le\sigma^2\le1$.}

\medskip
This result says that {\Rd $v_0\ge \hat u(\sigma)$} for the numbers
{\Rd $v_0$} with the above demanded property. Our results will show that 
{\Bl this estimate is sharp}. The above example helps us to 
understand what kind of result we can expect in the general case. 

\end{frame}


\begin{frame}

Next I explain the {\Bl picture behind this result}.

\medskip
In {\Rd case 3}.) of this example {\Rd $\sigma^2$} is 
relatively {\Rd large}, and we get such an estimate for the
{\Bl best choice of $\hat u(\sigma)$} as in the {\Rd Gaussian case}.

\medskip
In {\Rd case 2}.) we get a right choice for {\Bl $\hat u(\sigma)$} not 
by a {\Rd Gaussian} but by a {\Rd Poissonian approximation} of our model.

\medskip
In {\Rd case 1}.)
{\Rd $\sigma^2$ is very small}. We can make a trivial estimate
by exploiting that given an arbitrary partition of our space,
some element of this partitition contains a given sample point. 
In this case this fact yields the {\Prp right estimate} for 
{\Bl $\hat u(\sigma)$}.

\medskip
Next I formulate the {\Rd Theorem}, and its {\Rd Extension}, the main 
results of my paper. They say that in the general case we have the
estimate that the above {\Prp Example} and some {\Prp classical 
estimates on the tail distribution} of sums of independent 
random variables suggest.

\end{frame}

\begin{frame}

{\Rd {\bf Theorem.}} {\it Let a sequence of i.i.d. random 
variables $\xi_1,\dots,\xi_n$,  $n\ge2$, with values in 
$(X,{\cal X})$  with some distribution~$\mu$ and a countable 
class of functions ${\cal F}$ on the same space $(X,{\cal X})$ 
with polynomially {\Bl increasing covering numbers} with
exponent {\Bl $L\ge1$} and parameter {\Bl $D\ge1$} be given. 
Let the functions $f\in{\cal F}$ satisfy the relations
{\Prp $\sup_{x\in X}|f(x)|\le 1$, $\int f(x)\mu(\,dx)=0$}, 
and {\Prp $\int f^2(x)\mu(\,dx)\le\sigma^2$} with some 
number {\Prp $0\le\sigma^2\le1$} for all $f\in{\cal F}$. 
The {\Prp normalized sums} $S_n(f)$, $f\in{\cal F}$, 
satisfy the inequality
{\Rd $$
P\left(\sup_{f\in{\cal F}}|S_n(f)|\ge v\right)\le 
C_1 e^{-C_2\sqrt n v\log(v/\sqrt n\sigma^2}
\quad \textrm{for all } v\ge u(\sigma) 
$$}
with some universal constants $C_j>0$, $1\le j\le 5$, 
if one of the following conditions is satisfied.

1.) {\Rd $\sigma^2\le\frac1{n^{400}}$}, and  
{\Bl $u(\sigma)=\frac{C_3}{\sqrt n}(L+\frac{\log D}{\log n})$},

2.) {\Rd $\frac1{n^{400}}<\sigma^2\le\frac {\log n}{8n}$}, 
and {\Bl $u(\sigma)=\frac{C_4}{\sqrt n}
\left(L\frac{\log n}{\log(\frac{\log n}{n\sigma^2})}+\log D\right)$},

3.) {\Rd $\frac{\log n}{8n}<\sigma^2\le1$}, and
{\Bl $u(\sigma)=\frac{C_5}{\sqrt n}(n\sigma^2+L\log n+\log D)$}. 
}

\end{frame}

\begin{frame}

{\Rd {\bf Extension of the Theorem.}} {\it Let us consider, 
similarly to the Theorem, a sequence of i.i.d. random 
variables $\xi_1,\dots,\xi_n$, $n\ge2$, 
with values in a space $(X,{\cal X})$ with some 
distribution {\Rd $\mu$} which satisfies 
{\Prp the conditions of the Theorem}. In the case     
{\Rd $\frac{\log n}{8n}<\sigma^2\le1$}
the supremum 
of the {\Prp normalized sums $S_n(f)$}, $f\in{\cal F}$, 
satisfies the inequality 
{\Rd $$
P\left(\sup_{f\in{{\cal F}}}|S_n(f)|\ge v\right)
\le Ce^{-\alpha v^2/\sigma^2} 
$$}
with appropriate (universal) constants $\alpha>0$, $C>0$ 
and $C_6>0$ if {\Rd $\sqrt n\sigma^2\ge v\ge\bar u(\sigma)$}, 
where $\bar u(\sigma)$ is defined as 
{\Bl $\bar u(\sigma)=C_6\sigma(L^{3/4}\log^{1/2}\frac2\sigma 
+(\log D)^{1/2})$}.}

\medskip 
In {\Prp cases 1.) and 2.)} Theorem gives a good estimate for 
{\Prp $v\ge u(\sigma)$} with an {\Prp $u(\sigma)$}  suggested by the 
{\Prp Example}. It is a {\Bl (non-Gaussian)} estimate suggested by 
{\Bl Bennett's inequality}. In {\Prp case 3.)} the {\Prp Theorem} 
and its {\Prp Extension} {\Rd together} give a good estimate. It holds 
for {\Rd $v\ge\bar u(\sigma)$}, as it is suggested by the 
{\Prp Example}. The {\Rd Extension} gives a good 
{\Rd Gaussian estimate} if 
{\Prp $\bar u(\sigma)\le v\le\sqrt n\sigma^2$}. 
{\Bl Over this level} we have a weaker estimate 
formulated in the {\Bl Theorem}.

\end{frame}

\begin{frame} 

{\Rd The main ideas of the proof:} I can simplify our problem with 
the help of my paper {\Green Sharp estimate on the supremum of 
a class of sums of small i.i.d. random variables} by exploiting 
that we are working with a class of functions with 
{\Bl polynomially increasing covering numbers}. This enables us 
to reduce our problem to the case when we have finally many 
random sums {\Prp $S_n(f)$} with some nice properties. The reduced 
problem  can be solved by means of classical methods, like the
{\Bl Chaining argument} and {\Bl good estimates} for sums 
of i.i.d. random variables.

\medskip
The main point of the proof is that we can separate the {\Prp regular} 
and {\Prp irregular} contributions to the supremum we are 
investigating. The {\Bl regular part} can be well investigated by 
{\Bl classical tools} like the chaining argument. The real novelty 
in my research was to find a {\Rd new method} for the estimation of 
the {\Rd irregular effects}. This demanded the application of 
{\Rd new arguments}. 


\medskip
I put a more detailed version of this talk to the address

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



\end{frame}



\end{document}








