
\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 tail distribution estimates  
for the supremum of a class  
of sums of i.i.d. random variables.} 

\author{P\'eter Major}

\maketitle

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

\end{frame}

\begin{frame} 

{\Rd An additional 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 tail distribution 
we are investigating is small only if 
{\Bl $v$ is larger than this concentration point}. In our 
estimation we want to find a {\Bl good level} above which 
this  tail distribution begins to {\Bl decrease radically}. 
This is a hard and important part of our problem.

\medskip
I recall the definition of {\Rd classes of functions with
polynomially incerasing covering numbers} together with the
{\Bl exponent $L$} and {\Bl parameter} $D$ of these 
classes. I do it in two steps.

This notion is a useful {\Bl version of the Vapnik--\v{C}ervonenkis
classes}, when we are working with classes of {\Prp functions} 
instead of classes of {\Prp sets}.

\end{frame}

\begin{frame}{Definition of a class of functions with 
polynomially increasing covering numbers}

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. 
{\Prp The 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
First I discuss an {\Rd example} which indicates what kind of
results we can expect in our problem. We are mainly
interested in the case when the {\Bl exponent} $L$ and the
{\Bl parameter} $D$ are {\Bl bounded} (by a number not depending
on $\sigma^2$), and {\Rd $\sigma^2$ may be very small}.

\end{frame}

\begin{frame}{A useful example} 

{\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 our conditions. It is a class of 
functions with polynomially increasing covering numbers 
with {\Bl exponent $L$} and {\Bl parameter $D$} which 
do not depend on {\Bl $\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}

Our first question: For {\Rd which numbers} is {\Bl $P_n(v)$} 
{\Rd much smaller than~1}? Answer to this question:

\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 we {\Bl cannot get a good estimate} on the
probability we are interested for {\Rd $v\le\hat u(\sigma)$}.
First I explain this result, then I discuss what we can say if 
{\Bl $v>\hat u(\sigma)$}.

\end{frame}

\begin{frame}

In {\Rd case 3}.) of this example {\Rd $\sigma^2$} is 
relatively {\Rd large}. In this case the $S_n(f)$ behaves 
{\Bl similarly to the Gaussian case}, (like  a functional 
of a Brownian bridge), and {\Bl similar estimates hold for 
the tail distribution of $\sup_{f\in{\cal F}}S_n(f)$} as in the 
corresponding Gaussian model. But to get such a good estimate 
{\Prp we need this condition.} K. S. Alexander also observed 
this fact in his research.

\medskip
In {\Rd case 2}.) $S_n(f)$ does {\Rd not} have a {\Rd good Gaussian}, 
but has a good {\Rd Poissonian approximation}. This provides a 
{\Bl slightly weaker estimate} than in case 1.), since the 
{\Prp Poissonian} tail distribution {\Prp tends to zero slower} 
at $\infty$ than the Gaussian one. Here we explained what 
we get in this case.

\medskip
In {\Rd case 1}.) we considered the case when 
{\Rd $\sigma^2$ is very small}. Here we exploited the trivial 
fact that if we take an arbitrary partition of the probability 
space {\Bl a sample point gets into one of the elements of the 
partition}. In this case this observation provides the 
{\Prp right estimate}.

\end{frame}

\begin{frame}

\medskip
The next {\Rd Theorem} (the main result of this paper) states that in the
general case we get an {\Rd estimate suggested by the above example}.
Actually the situation is somewhat more complex, since we also
consider the case when the parameters {\Bl $L$} and 
{\Bl $D$} may be {\Bl large}.

\medskip
We can get a good estimate on    
{\Prp $P(\sup_{f\in{\cal F}}|S_n(f)|>v)$} only if 
{\Prp $v>\hat u(\sigma)$}. We also want to find the 
{\Rd tail distribution} in this case. 
{\Bl Bernstein's and Bennett's inequality} suggest the  
upper bound {\Bl $e^{-C\sqrt n\log(v/\sqrt n\sigma^2}$}
if {\Bl $v\ge\textrm{const.}\,\sqrt n\sigma^2$} and 
{\Prp $e^{-Cv^2/\sigma^2}$} if 
{\Prp $v\le\textrm{const.}\,\sqrt n\sigma^2$}.
(See my lecture note 
{\Green On the estimation of multiple random integrals an $U$-statistics}).

\medskip
In {\Bl cases 1.) and 2.)} 
{\Prp $\hat u(\sigma)\ge\textrm{const.}\sqrt n\sigma^2$}, and
the {\Rd Theorem} gives the estimate we expect. {\Bl Case 3.)} 
is more complex. In the {\Rd Theorem} we give the estimate
we expect if {\Bl $v\ge \textrm{const.}\,\sqrt n\sigma^2$}. 
(The situation is somewhat more difficult, because we also deal 
with the case when the parameters {\Bl $L$} and {\Bl $D$} 
are large.) In {\Bl Case 3.)} it is possible that
{\Prp $\hat u(\sigma)<v\le\textrm{const.}\,\sqrt n\sigma^2$}. 
We prove the ({\Rd Gaussian}) estimate we expect in this case
in an {\Rd Extension of the Theorem}.   

\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}
Next we consider the case {\Rd $\sigma^2\ge \frac{\log n}{8n}$}
and {\Rd $\sqrt n\sigma^2\ge v\ge\bar u(\sigma)$} with some
$\bar u(\sigma)$ which has the same order of magnitude as 
$\hat u(\sigma)$. Actually this result was proved earlier. 

\medskip
{\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})$}.}

\end{frame}

\begin{frame}{The idea of the proof}

We choose an appropriate number {\Bl $\delta>0$}, and choose 
by exploiting that ${\cal F}$ is a class of functions with 
{\Prp polynomially increasing covering numbers} 
{\Bl $m=D\delta^{-L}$} functions {\Bl $f_j\in{\cal F}$, 
$1\le j\le m$}, and set of functions 
{\Bl ${\cal D}_j\subset{\cal F}$} in such a  way that 
{\Prp $\int |g-f_j|\,d\mu\le\delta$, if $g\in{\cal D}_j$} 
and {\Prp $\bigcup_{j=1}^m{\cal D}_j={\cal F}$.}

We can write
{\Rd \begin{eqnarray}
&&
\!\!\!\!\!\!\!\!\!
P\left(\sup_{f\in{\cal F}}|S_n(f)|\ge v\right) \label{1}  \\
&& \!\!\!\!
\le P\left(\sup_{1\le j\le m}  |S_n(f_j)|\ge\frac v2\right)
+\sum_{j=1}^m
P\left(\sup_{f\in{\cal D}_j}|S_n(f-f_j)|\ge\frac v2\right). 
\nonumber
\end{eqnarray}  }

\end{frame}

\begin{frame}

We choose {\Bl $\delta>0$} in an appropriate way. Then we can 
give a good estimate on the second term of the sum at the 
right-hand side of (\ref{1}) by means of my paper
{\Green Sharp estimate on the supremum of a class of 
sums of small i.i.d. random variables}.

The first term can be estimated by means of the inequality
{\Rd $$
P\left(\sup_{1\le j\le m}  |S_n(f_j)|\ge\frac v2\right)
\le\sum_{j=1}^m P\left(|S_n(f_j)|\ge\frac v2\right)
$$}
and {\Bl Bennett's inequality}. The theorem can be proved 
in such a way.

\medskip
The {\Rd Extension of the Theorem} can be proved similarly.
Only in this case the first term at the right-hand side 
of~(\ref{1}) must be estimated in a different way. We 
exploit the properties of the class of functions 
{\Prp ${\cal G}=\{f_1,\dots,f_m\}$}, and give a good 
estimate with the help of the {\Bl chaining argument}.
(Observe that {\Rd ${\cal G}$} is a class of functions 
with {\Rd polynomially increasing covering numbers}).

\end{frame}

\begin{frame}{Some remarks on the problem}

In a previous paper I gave a good estimate on the probability
{\Prp $P(\sup_{f\in{\cal F}}S_n(f)>v)$} if ${\cal F}$ is a class 
of functions with {\Bl polynomially increasing covering numbers} 
consisting of functions bounded by~1, and 
{\Rd $\int |f(x)|\mu(\,dx)\le\rho$} with a sufficiently 
{\Rd small $\rho$}. More precisely, {\Bl$\rho\le n^{-\alpha}$} 
with an  appropriate {\Bl $\alpha>1$}. Here {\Bl $\mu$} 
denotes the distribution of the random variables we 
are working with.

\medskip
This result played a crucial role in our investigation. It enabled
us to reduce the problem to the case where we take the supremum 
for an {\Prp appropriate finite subset of ${\cal F}$}, because 
it made possible to control the 
{\Bl small contribution of the disregarded terms} 
to the supremum we are investigating. 

\medskip
This approach is similar to the {\Bl truncation technique} applied 
in the proof of {\Bl limit theorems}, by which the small but 
{\Prp irregular effect of the large terms} is disregarded. Here
a similar method is applied. 

\end{frame}

\begin{frame}

The {\Rd chaining argument} or a {\Rd more refined version} 
of it worked out by {\Rd Talagrand} enables us to 
handle the regular effects in similar problems. But the 
{\Prp control of the small irregularities} demands a 
{\Bl different method}. In earlier works the irregularities
were controlled by means of a method  called the
{\Prp symmetrization argument}. In the present paper I could
find a {\Bl more  powerful method} that works under
more general conditions.

\medskip
The {\Rd control of the irregular effects} is a more 
general, open problem. Here we exploited that 
the class of functions we are working with has 
{\Prp polynomially increasing covering numbers}. 
Other models have other good properties, and we 
have to find the method {\Rd to exploit them}.  

\medskip
On the other hand, I consider a method to control the 
irregularities good only if I see models where it
it gives new results. I met some 
{\Prp generalizations of the symmetrization argument} 
which demanded new complicated notions and arguments. 
But as I saw no real application of them I do not know 
whether they are useful.

\end{frame}

\end{document}








