\magnification=\magstep1
\hsize=16truecm
\input amstex
\parindent=20pt
\parskip=3pt plus 1pt
\TagsOnRight
\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\centerline{\bf The approximation of the normalized empirical
distribution} \centerline{\bf function by a Brownian bridge}
\smallskip
\centerline{\it by P\'eter Major}
\centerline{Mathematical Institute of the Hungarian Academy of
Sciences} \bigskip \noindent
{\narrower{\narrower
{\it Abstract:}\/ In this work an (asymptotically) optimal approximation
of the normalized empirical distribution function by a Brownian bridge
is presented in the form of a series of problems. The formulation of the
problems and their solutions are separated in this text. The
discussion is based on the paper {\it An approximation of partial sums
of independent RV's and the sample DF. ~I.}\/ written by
J\'anos Koml\'os, P\'eter Major and G\'abor Tusn\'ady which appeared
in the journal {\it Zeitschrift f\"ur Wahrscheinlichkeitstheorie und
verwandte Gebiete}\/ {\bf32} (1975), pages 111--131. The main
difference between this text and the original paper is
that here the details are worked out thoroughly, all ``it is easy to
see that \dots" type arguments are omitted. The problems formulated in
this work are of different level of difficulty. My main goal was to
give a complete and understandable explanation. I discussed some
technical problems in detail and tried to explain
the ideas behind them even if this caused sometimes
certain repetition and made the text longer. \par}\par}
\beginsection The formulation of the main problem
In this series of problems we investigate the approximation of the
normalized empirical distribution function by a Brownian bridge. Let us
formulate this problem in more details.
Let $B(t)=B(t,\oo)$, $0\le t\le 1$, be a Brownian bridge on a
probability space $(\Omega,\Cal B,P)$, i.e.\ let $B(t)$ be a Gaussian
process with expectation $EB(t)=0$ and covariance function
$EB(s)B(t)=\min(s,t)-st$, $0\le s,t\le 1$. Furthermore, we assume that
the trajectories $B(\cdot,\oo)$ of the Brownian bridge are continuous
functions on the interval $[0,1]$ for all elementary events $\oo\in
\Omega$. It follows from classical results of the probability theory
that Brownian bridges with the above properties really exist.
Let $P_n(t)$, $0\le t\le1$, denote the empirical distribution function
corresponding to a sample consisting of $n$ independent and on the
interval $[0,1]$ uniformly distributed random variables, i.e.\
let $\zeta_1,\dots,\zeta_n$ be a sequence of independent and on the
interval $[0,1]$ uniformly distributed random variables, and put
$P_n(t)=\dfrac1n \sum\limits_{j=1}^n I(\{\zeta_j\le t\})$, $0\le
t\le1$, where $I(A)$ denotes the indicator function of the set $A$.
Let
$$
Z_n(t)=\sqrt n[P_n(t)-t]\;,\quad 0\le t\le 1,
$$
be its standardization which we shall further call the standardized
empirical distribution function. The covariance function of the
processes $Z_n(t)$ and $B(t)$, $0\le t\le 1$, agree. We want to show
that these two processes can be put close to each other with the help
of an appropriate construction. More explicitly, we want to prove the
following result: \vfill\eject
\headline{\ifodd\pageno \hfill {\it Approximation of the empirical
distribution function} \hfill \else \hfill {\it P\'eter
Major} \hfill \fi}
\noindent
{\bf Approximation Theorem.} {\it Let a Brownian bridge $B(t)$ be given
on a sufficiently rich probability space $(\Omega,\Cal B,P)$.
Then for all numbers $n=2,3,\dots$ a sequence $\zeta_1,\dots,\zeta_n$ of
independent and on the interval $[0,1]$ uniformly distributed random
variables can be constructed in such a way that the empirical
distribution function $P_n(t)=\dfrac1n
\sum\limits_{k=1}^nI(\{\zeta_n\le t\})$ and its
standardization $Z_n(t)=\sqrt n[P_n(t)-t]$, $0\le t\le 1$, made with
the help of these random variables $\zeta_1,\dots,\zeta_n$ satisfy
the relation
$$
P\(\sqrt n\sup_{0\le t\le 1}|Z_n(t)-B(t)|>C_1\log n+x\)\le
C_2e^{-\lambda x}
$$
for all numbers $x>0$ with some universal (independent of the
parameter $n$) constants $C_1>0$, $C_2>0$ and $\lambda>0$.}
\medskip\noindent {\it Remark:}\/ The probability space where we
want to make a construction satisfying the {\it Approximation
Theorem}\/ is sufficiently rich if there exists a sequence $\eta_k$,
$k=1,2,\dots$, of independent and on the interval $[0,1]$ uniformly
distributed random variables on it which is also independent of the
Brownian bridge $B(t)$. At the expense of some extra-work such a
modified construction could be made which applies no extra random
variables beside the Browian bridge $B(t)$. But it is more convenient
to carry out the construction presented in his work, and the
extra-condition we have imposed is not a serious restriction in
possible applications of the result.
\medskip
In the construction satisfying the above {\it Approximation Theorem}\/
we shall construct the empirical distribution function $P_n(t)$ as an
appropriate transform of the Brownian bridge in such a way that
its normalization $Z_n(t)$ is close to the Brownian bridge $B(t)$.
The method of this construction is an appropriate adaptation
of the quantile transform to the present problem. The main difficulty
is caused by the fact that the multi-dimensional distributions of an
empirical distribution function are also prescribed, while the
quantile transform only deals with the construction of random
variables with a prescribed one-dimensional distribution. To overcome
this difficulty we shall construct the (standardized) empirical
distribution function $Z_n(t)$ by means of a fixed Brownian bridge
$B(t)$ subsequently for newer and newer points $t$ in such a way
that the random variable $Z_n(t)$ has that conditional distribution
which the values of the previously constructed random variables
$Z_n(s)$ prescribe. We do this subsequently, and in the $l$-th step
we define the process $Z_n(t)$ in the diadic points $t=k2^{-l}$,
$k=0,1,\dots,2^l$. In the present problem the conditional
distributions we have to work with can be well handled. The
construction gives a good approximation because in the $l$-th step
we define the values of the process in all points $t_{k,l}=k2^{-l}$,
$1\le k\le 2^l$, which is a relatively dense subset of the interval
$[0,1]$. If the supremum of the process $\sqrt n(Z_n(t)-B(t))$ in the
already constructed points increases in each step relatively little,
then this method provides a good approximation. By working out the
details we can show that roughly speaking the above supremum
increases only with a constant in each step. In such a way we get a
construction for which the supremum of the difference $\sqrt
n(Z_n(t)-B(t))$ is less than $\const\log n$ with probability almost
one. It is worth mentioning that this result is sharp. The difference
$\sqrt n(Z_n(t)-B(t))$ is greater than $\const\log n$ with (another)
appropriate positive constant for an arbitrary construction. The
proof of this statement is considerably simpler than the proof of the
{\it Approximation Theorem}, and we shall discuss it in another series
of problems.
To apply the quantile transform method in our problem we need a sharp
limit theorem for the conditional distribution function of the random
variables $Z_n(t_2)-Z_n(t_1)$ under appropriate conditions. Moreover,
to get sharp results it is not sufficient to have a good limit theorem
in the usual way. We need such large deviation type results which also
describe the goodness of approximation in the case of non-typical
values or non-typical conditions. We formulate a classical result of
the large deviation theory in the special case we need it. Then we
formulate two problems whose solutions supply a good bound on the
goodness of the approximation of the quantile transformation in the
case we need it.
We shall apply the following notations. Let
$\varphi(x)=\frac1{\sqrt {2\pi}}e^{-x^2/2}$ denote the standard normal
density and $\Phi(x)=\int_{-\infty}^x \varphi(x)\,dx$ the standard
normal distribution function. We shall need the following result.
\medskip
\noindent {\bf Theorem.} {\it Let $F_n(x)$ be the standardization of
the binomial distribution $B\(n,\frac12\)$ with parameters
$n$ and $p=\frac 12$, i.e.\ let
$F_n(x)=P\(2\dfrac{\eta_1+\cdots+\eta_n-\frac n2}{\sqrt n}0$ and
$A>0$ in such a way that the distribution function $F_n(x)$
satisfies the following inequalities in the interval $|x|\le A\sqrt n$:
$$
\align
\(1-\Phi(x)\)\exp\left\{-\frac{K(x^3+1)}{\sqrt n}\right\}&\le1-F_n(x)
\le \(1-\Phi(x)\)\exp\left\{\frac{K(x^3+1)}{\sqrt n}\right\}\\
\Phi(-x)\exp\left\{-\frac{K(x^3+1)}{\sqrt n}\right\}&\le F_n(-x)\le
\Phi(-x)\exp\left\{\frac{K(x^3+1)}{\sqrt n}\right\},\\
&\qquad\qquad\qquad\qquad\qquad \text{\rm if }0\le x\le A\sqrt n.
\endalign
$$
(The statement of this theorem actually holds for all constants
$A<\frac12$ and appropriate $K=K(A)$, but we shall not need this
sharper result.) } \medskip
Let us remark that the above theorem is the special case of a more
general result. A $B(n,\frac12)$ distributed random variable, as we
have remarked in the formulation of this theorem, can be represented
as the sum of $n$ independent $B(1,\frac12)$ distributed random
variables. It follows from the general theory of the large deviations
that the estimation formulated in the theorem also holds for
normalized sums of independent identically distributed random
variables if the summands have moment generating function, i.e.\ if
the distribution function $F(x)$ of the summands satisfies the
condition $\int e^{tx}F(\,dx)<\infty$ if $|t|0$. This result and its proof can also be
found in problem~22 of the series of problem {\it The Theory of
Large Deviation I.}\/ in my homepage. (At present it exists only in
Hungarian.)
\beginsection 1. Problems
\item{1.)} There exist such constants $C_1>0$ and $C_2>0$ for which
$$
\align
C_1(x+2)&<\frac {\varphi(x)}{1-\Phi(x)}0$ and $C_2>0$ such that
for all $x>0$ and $|h|0, \\
e^{C_2h(x+2)}&<\frac {\Phi(-x+h)}{\Phi(-x)}0,
\endalign
$$
and (considering the cases $h>0$ and $h<0$ separately)
$$
\align
e^{C_1|h|(x+2)}&<\frac {1-\Phi(x+h)}{1-\Phi(x)}0$. Let us prove with the help of the above formulated
large deviation {\it Theorem}\/ that the distribution function
$F_{n,m}(x)$ satisfies the estimate
$$
\align
1-F_{m,n}(x)&=(1-\Phi(x))\exp\left\{O\(\frac{x^3+\frac{|n-m|}{\sqrt
n}(x^2+x)+1} {\sqrt n}\)\right\}\\
F_{m,n}(-x)&=\Phi(-x)\exp\left\{O\(\frac{x^3+\frac{|n-m|}{\sqrt
n}(x^2+x)+1} {\sqrt n}\)\right\}
\endalign
$$
if $0\le x\le A\sqrt n$ and $|n-m|0$ and $B>0$. The $O(\cdot)$ in the above formula is
uniform in the variables $n$, $m$ and $x$.
\item{} Let $\eta$ be a random variable with standard normal
distribution, and define an $F_{m,n}$ distributed random variable
$\xi_{m,n}=F_{m,n}^{-1}(\Phi(\eta))$. Prove with the help of the
previous estimate that there exist constants $A>0$ and $K>0$ and a
threshold $n_0=n_0(B)$ in such a way that for all numbers $n>n_0$
$$
|\xi_{m,n}-\eta|0$, and let us construct for all
constants $l=0,1,\dots, L-1$ the random variables $Z_n(k2^{-(l+1)})$,
$V_{k,l+1}(n)$, $\bar V_{k,l+1}(n)$, $1\le k\le 2^{(l+1)}$, through
formulas (5a)--(5f) by induction with respect to the parameter $l$. (We
define $Z_n(0)\equiv Z_n(1)\equiv0$, $V_{0,1}(n)\equiv0$ and
$m_0=n$ which relations are needed to start this construction for
$l=0$). The distribution of the random vector $Z_n(k2^{-L})$, $1\le
k\le 2^L$, defined in such a way agrees with the joint distribution of
the values of a normalized empirical distribution function in the
coordinate points $t=k2^{-L}$, $k=1,\dots,2^L$. The random vectors
$V_{k,l}(n)$ and $\bar V_{k,l}(n)$ constructed in such a way and the
process $Z_n(t)$ (more precisely its restriction to the points a
$k2^{-L}$ which we have constructed through this procedure) satisfy
the properties (1)---(4). More precisely they satisfy formula (1b)
for $l\le L$ and that part of formula (4) which contains the random
variables $V$ and $\bar V$ with indices $l\le L-1$. Furthermore,
the relation $\Cal G_l(n)\subset \Cal F_l$ holds for all numbers $l\le
L$.
\item{5b.)} Let us consider the random variables $Z_n(k2^{-L})$,
$0\le k\le 2^L$, defined in the previous problem, ($Z_n(0)\equiv0$),
and put $m_k=\sqrt n\(Z_n(k2^{-L})-Z_n((k-1)2^{-L})\)+n2^{-L}$, $1\le
k\le 2^L$. For all numbers $k=1,\dots,2^L$ let us construct a sequence
$\zeta_1^{(k)},\dots,\zeta_{m_k}^{(k)}$ of independent and in the
interval $[(k-1)2^{-L},k2^{-L}]$ uniformly distributed random
variables consisting of $m_k$ terms. For different numbers $k$ let
these sequences $\zeta_1^{(k)},\dots,\zeta_{m_k}^{(k)}$ be independent
of each other.
\item{} Let us consider the union of these random sequences, and put
the elements of this unified sequence in an increasing order. The
random sequence $0\le \zeta^*_1\le \zeta^*_2\le\dots\le\zeta^*_n$
obtained in such a way is an ordered sample made from $n$ independent
and in the interval $[0,1]$ uniformly distributed random variables, i.e.
its distribution agrees with the distribution of a sequence which we
obtain by putting the elements of a sequence $\zeta_1,\dots,\zeta_n$ of
independent random variables with uniform distribution on the interval
$[0,1]$ into increasing order. If we choose one of the permutations
$(\pi(1),\dots,\pi(n))$ of the set $\{1,\dots,n\}$ randomly and
independently of the random sequence $0\le \zeta^*_1\le
\zeta^*_2\le\dots\le\zeta^*_n$, and in such a way that all possible
permutations of the set $\{1,\dots,n\}$ are chosen with the same
probability $\frac1{n!}$, then the coordinates of the random vectors
$(\zeta_1,\dots,\zeta_n)=(\zeta^*_{\pi(1)},\dots,\zeta^*_{\pi(n)})$
are independent and in the interval $[0,1]$ uniformly distributed
random variables.
\item{} Let us construct the standardized empirical distribution
function $Z_n(t)$ with the help of the above constructed sequence
$(\zeta_1,\dots,\zeta_n)$ of independent and in the interval $[0,1]$
uniformly distributed random variables. The values of this
standardized empirical distribution functions in the points
$t=k2^{-L}$, $0\le k\le 2^L$, equal the previously defined
random variables $Z_n(k2^{-L})$, $1\le k\le 2^L$. \medskip
We want to show that the originally given Brownian bridge $B(t)$ and
standardized empirical distribution function $Z_n(t)$ made from the
sequence of independent and in the interval $[0,1]$ uniformly
distributed random variables $\zeta_1,\dots,\zeta_n$ constructed in
problems~5a and~5b satisfy the {\it Approximation Theorem}\/ if the
number $L=L(n)$ of halving in problems~5a and~5b
is sufficiently large. For instance $L=L(n)=n$ is an appropriate choice.
Furthermore, we assume that $n\ge n_0$ with a sufficiently large fix
number~$n_0$. In order to prove the {\it Approximation Theorem}\/ we
shall estimate the probabilities
$$ \allowdisplaybreaks
\align
&P\(\sup_{1\le k\le 2^l}\sqrt n |Z_n(k2^{-l})-B(k2^{-l})|>\frac x2\)
\tag6a\\
&P\(\sqrt n\supp_{(k-1)2^{-l}\le t\le k2^{-l}}
\left|Z_n(t)-Z_n\(\frac{k-1}{2^l}\)\right|>\frac x4\) \tag6b \\
\intertext{and}
& P\(\sqrt n\supp_{(k-1)2^{-l}\le t\le k2^{-l}}
\left|B(t)-B\(\frac{k-1}{2^l}\)\right|>\frac x4\) \tag6c
\endalign
$$
for all numbers $x>C_0\log n$, with appropriate constants $C_0>0$,
$l=l(x)$ and all numbers $1\le k\le 2^l$. We shall deduce {\it the
Approximation Theorem}\/ from a good bound on the above probability
together with an appropriate choice of the parameter $l=l(x)$ in them.
The hardest and most important task is to estimate the probability
in formula~(6a). Let us also remark that from the above expressions
only formula (6a) depends on the construction, i.e.\ on the joint
distribution of the processes $Z_n(t)$ and $B(t)$. To give a good
estimate on it first we formulate the following problem~6, whose
solution follows from the result of problem~2 and the structure of the
above described construction of the process $Z_n(t)$. \medskip
\item{6.)} Let $U_{k,l}$, $V_{k,l}(n)$ $\bar U_{k,l}$ and
$\bar V_{k,l}(n)$ be the random variables defined by means of formulas
(1)---(4) through a Brownian bridge $B(t)$ and the previously
constructed empirical process $Z_n(t)$. Let us consider such a number
$l$ for which $l\le L$, where $L$ is the number appearing in the
construction of the standardized empirical number $Z_n(t)$, ``the
number of halving". Let us show that there exist some constants $K>0$
and $A>0$ such that the inequalities
$$
\aligned
2^{-(l+2)/2}\left|\bar U_{2k-1,l+1}-\bar V_{2k-1,l+1}(n)\right|&=
2^{-(l+2)/2}\left|\bar U_{2k,l+1}-\bar V_{2k,l+1}(n)\right|\\
&<\frac{K}{\sqrt n}\(\bar U_{2k-1,l+1}^2+V_{k,l}^2(n)+1\)\\
&=\frac{K}{\sqrt n}\(\bar U_{2k,l+1}^2+V_{k,l}^2(n)+1\),
\endaligned \tag7a
$$
and
$$
\aligned
&\max\(2^{-(l+2)/2}\left|U_{2k-1,l+1}-V_{2k-1,l+1}(n)\right|,\;
2^{-(l+2)/2}\left|U_{2k,l+1}-V_{2k,l+1}(n)\right|\) \\
&\qquad <\frac K{\sqrt n}\(\bar U_{2k-1,l+1}^2+V_{k,l}^2(n)+1\)
+\frac{2^{-(l+1)/2}}2 \left|U_{k,l}-V_{k,l}(n)\right|\\
&\qquad =\frac{K}{\sqrt n}\(\bar U_{2k,l+1}^2+V_{k,l}^2(n)+1\)
+\frac{2^{-(l+1)/2}}2 \left|U_{k,l}-V_{k,l}(n)\right|
\endaligned \tag7b
$$
hold for all $1\le k\le 2^l$ if $|\bar U_{2k-1,l+1}|u_{j-1}$, $1\le j\le l$.
Let us introduce the notation $k_j=u_j2^j$, $0\le j\le l$.
Furthermore, let $U_{k,l}$, $V_{k,l}(n)$ and $\bar U_{k,l}$, $\bar
V_{k,l}(n)$ be the random variables defined in formula (1)---(4). Then
$$
\aligned
Z_n(t)=Z_n\(k2^{-l}\)&
=\sum_{j=1}^{l}\e(j)2^{-(j+1)/2}\(\sqrt2 V_{k_{j-1}+1,j-1}(n)
-V_{k_{j}+1,j}(n)\) \\
B(t)=B\(k2^{-l}\)&=\sum_{j=1}^{l}\e(j)2^{-(j+1)/2}
\(\sqrt2U_{k_{j-1}+1,j-1}-U_{k_{j}+1,j}\).
\endaligned \tag8a
$$
\item{} Furthermore,
$$
\aligned
&2^{-(j+1)/2}\left|V_{k_j+1,j}(n)-U_{k_j+1,j}\right|\\
&\qquad \le \frac{K}{\sqrt n}\(\sum_{s=0}^{j-1} 2^{-s}\(\bar
U^2_{k_{j-s}+1,j-s}+V^2_{k_{j-s-1}+1,j-s-1}(n)+1\)\),
\endaligned \tag8b
$$
and
$$
\aligned
&\sqrt n|Z_n(t)-B(t)|=\sqrt n\left|Z_n (k2^{-l})-B(k(2^{-l})\right| \\
&\qquad \le 4K\(\sum_{j=1}^l\(\bar U^2_{k_{j}+1,j}
+V^2_{k_{j-1}+1,j-1}(n)+1\)\)
\endaligned \tag8c
$$
on the set
$$
\align
\bold B&=\bold B(t)=\bold B(k2^{-l}) \\
&=\bigcap_{j=1}^{l}\(\left\{\oo\:|\bar
U_{2k_{j-1}+1,j}(\oo)|<\frac{A\sqrt n}{2^{j/2}}\right\}\cap
\left\{\oo\:|V_{k_{j-1}+1,j-1}(n)(\oo)|<\frac{A\sqrt n}
{2^{j/2}}\right\}\),
\endalign
$$
where the constants $K>0$ and $A>0$ agree with those introduced in
problem~6.
\medskip
We shall show that the probability in formula (6a) will be bounded in
the following way.
$$
\align
P&\(\sup_{1\le k\le 2^n}\sqrt n
\left|Z_n\(k2^{-l}\)-B\(k2^{-l}\)\right|>\frac x2\)0, \text{ if }
C_0\log n\le x\le C^{-1}n \text{ and } 2^{-l}\ge C xn^{-1},
\endalign
$$
where $C_0>0$ and $C>0$ are sufficiently large positive numbers $n\ge
n_0$, and $n_0=n_0(C_0,C)$ is an appropriate threshold index.
The restriction $x>C_0\log n$ in the estimate (9) makes no problem in
the proof of the {\it Approximation Theorem}\/ because in this result
only the case $x\ge\const\log n$ has to be considered. Neither the
condition $x\le C^{-1}n$ causes a big problem, because the case
$x\ge C^{-1}n$ can be simply handled in the proof of the {\it
Approximation Theorem}. The inequality $2^{-l}\le Cxn^{-1}$ imposed
for the number $l=l(x)$ tells us how dense subset can be taken in the
estimate~(9). It will turn out that this subset is sufficiently dense
for our purposes, and the {\it Approximation Theorem}\/ will
follow from the estimate (9) and a good bound on the expressions in
formulas (6b) and~(6c).
Formula (9) will be deduced from formula (8c) and the results of the
subsequent problems~8--12. These problems contain the conditions imposed
in formula~(9). \medskip
\item{8.)} The joint distribution of the random variables $\bar
U_{2k_{j-1}+1,j}$, $1\le j\le l$ appearing in inequality~(8c) and the
joint distribution of the random variables $\bar U_{1,j}$, $1\le j\le
l$, agree. Similarly, the joint distribution of the random variables
$V_{k_{j-1}+1,j-1}(n)$, $1\le j\le l$, and $V_{1,j-1}(n)$, $1\le j\le
l$, $1\le j\le l$, agree. Furthermore, the random variables $\bar
U_{1,j}$, $1\le j\le l$ are independent, and they have standard normal
distribution.
\item{} Let the inequalities $C_0\log n\le x\le C^{-1}n$ and $2^{-l}\ge
C\frac{x}n$ hold with some sufficiently large constants $C_0>0$ and
$C>0$. Then the probability of the set $\bold B$ introduced in
problem~7 satisfies the inequality $1-P(\bold B)\le e^{-D_1x}$ with an
appropriate constant $D_1=D_1(C)>0$. If the above considered constant
$C>0$ is sufficiently large and $n\ge n_0$, where $n_0$ is an
appropriate threshold, then
$$
P\(18K\sum_{j=1}^l \bar U_{1,j}^2>x\)\le e^{-D_2x}
$$
with an appropriate number $D_2>0$. (In this formula the same
constant $K$ appears as in the problems~6 and~7.)
\medskip
We remark that the last estimate (if we are not interested in the choice
of the constants in them) is sharp. Indeed, even a single term of this
sum, being the square of a random variable with standard normal
distribution, takes a value larger than $x>0$ with probability larger
than $e^{-\const x}$. This means that disregarding the constant in the
exponent we can get as good an estimate for the probability that this
sum consisting of $l$ terms is greater than $x$, as for the probability
of the event that a single term of the sum is larger than this bound.
Such an estimate holds if the number of terms are chosen so that the
expected value of the sum is smaller than $\alpha x$ with some number
$0<\alpha<1$.
To prove formula (9) we shall show that
$$
\aligned
P&\(18K\sum_{j=1}^l V_{k_{j-1}+1,j-1}(n)^2>x\)=
P\(18K\sum_{j=1}^l V_{1,j-1}(n)^2>x\)\\
&\qquad=P\(18K\sum_{j=1}^l 2^jZ_n\(\frac{1}{2^{j-1}}\)^2>x\)\le
e^{-D_3x} \endaligned
\tag10
$$
with some appropriate constant $D_3>0$, if $C_0\log n\le x\le C^{-1}n$
and $2^{-l}\ge C xn^{-1}$ with appropriate constants $C_0>0$ and $C>0$.
(The first two identities in formula (10) follow from the result of
problem~8 and the definition of the random variables appearing in
formula~(10).) First we consider the following problem. \medskip
\item{9.)} Let us deduce formula (9) from the results of problems~7
and~ 8 and the estimate in formula (10).\medskip
Let us remark that formula (10) is similar to the last estimate of
problem~8. Furthermore, the standardized empirical process $Z_n(t)$
behaves similarly to the Brownian bridge $B(t)$. It is not difficult to
prove such an analog of formula~(10) where the random variables
$V_{k_{j-1}+1,j-1}(n)$ are replaced by the random variables
$U_{k_{j-1}+1,j-1}$. This suggests that estimate (10) should also hold.
The main technical difficulty in its proof arises because the
standardized empirical distribution function $Z_n(t)$ is not a process
with independent increment. Hence the most powerful methods of
probability theory which are mainly appropriate for the investigation
of processes with independent increments do not supply a simply way to
prove formula~(10). We shall overcome this difficulty by applying a
classical method the so-called Poissonian approximation.
First we describe the Poissonian approximation we shall apply and
explain how it helps to simplify the proof of formula~(10). Let
$\zeta_k$, $k=1,2,\dots$, be a sequence of independent and in the
interval $[0,1]$ uniformly distributed random variables, and let
$\kappa_n$ be a Poisson distributed random variable with parameter~$n$,
i.e. let $P(\kappa_n=j)=\dfrac{n^j}{j!}e^{-n}$, $j=0,1,2,\dots$, which
is independent of the sequence $\zeta_k$, $k=1,2,\dots$. Define the
stochastic processes
$$
\align
Z_n(t)&=\dfrac1{\sqrt n}\(\summ_{k=1}^nI(\{\zeta_k\le t\})-nt\)\tag11a\\
X_n(t)&=\dfrac1{\sqrt n}\(\summ_{k=1}^{\kappa_n}I(\{\zeta_k\le t\})-nt\)
\tag11b\\
\intertext{and}
Y_n(t)&=\dfrac1{\sqrt n}\summ_{k=n}^{\kappa_n}I(\{\zeta_k\le t\}),
\quad 0\le t\le 1, \tag11c
\endalign
$$
where $I(A)$ denotes the indicator set of the set $A$, and in the
case $\kappa_nx\)&\le
P\(72K\sum_{j=1}^l 2^jX_n\(\frac{1}{2^{j-1}}\)^2>x\)\\
&\qquad +P\(72K\sum_{j=1}^l 2^jY_n\(\frac{1}{2^{j-1}}\)^2>x\).
\endaligned \tag12
$$
The proof of the inequality (12) will be part of the problems
10 and 11. We shall be able to bound the second term at the right-hand
side of inequality~(12), because the sum defining the random variable
$Y_n(\cdot)$ contains relatively few, $|\kappa_n-n|$ terms. Hence it
can be bounded with the help of relatively weak estimations. This will
be done in problems~10 and~11.
The estimation of the first term at the right-hand side of inequality is
relatively simple, because $X_n(t)$ is a standardized Poisson process
with parameter $n$, i.e. for arbitrary constants $0\le
t_00$ there exists a constant $B_2=B_2(B_1)>0$
such that $P(|\kappa_n-n|\ge y)\le e^{-B_2y^2/n}$.
\item{} Let us fix some positive real number $x>0$ and positive integer
$l$. Let $\zeta_k$, $k=1,2,\dots$, be a sequence of independent and in
the interval $[0,1]$ uniformly distributed random variables, and let us
define the following stochastic processes $\bar Y_{n,m}(t)$ and random
variables $\xi_k$:
$$
\bar Y_{n,m}(t)=\dfrac1{\sqrt n}\summ_{k=1}^mI(\{\zeta_k\le t\}),\quad
m=0,1,2,\dots,
$$
$$
\xi_k=\xi_{k,l}=\sum_{j=1}^l 2^{j/2}I\(\zeta_k<\frac1{2^{j-1}}\),\quad
k=1,2,\dots.
$$
Then for arbitrary an constant $B>0$ the following relation holds:
$$
\align
&P\(72 K\sum_{j=1}^l 2^jY_n\(\frac1{2^{j-1}}\)^2>x\)
\le P\(|\kappa_n-n|> B\sqrt {nx}\)\\
&\qquad\qquad +P\(\sqrt{72 K}\sum_{j=1}^l 2^{j/2}\bar Y_{n,B\sqrt{nx}}
\(\frac{1}{2^{j-1}}\)>\sqrt x \) \tag13 \\
&\qquad= P\(|\kappa_n-n|> B\sqrt {nx}\)
+P\(\frac{\sqrt{72 K}}{\sqrt n}\sum_{k=1}^{B\sqrt {nx}} \xi_k>\sqrt x\).
\endalign
$$
The random variables $\xi_k=\xi_{k,l}$, $k=1,2,\dots$, defined in this
problem are independent and identically distributed.
\medskip
We want to give an in the infinity exponentially decreasing bound for
the second term at the right-hand side of formula (12). To do this it is
enough to give a good bound on the expression at the right-hand
side of formula~(13). To do this we have to bound the probability of
such an event that the sum of certain independent random variables is
greater than a given number. The probability theory has standard
methods for the investigation of such problems, and they can be
applied also in the present case.
If we want to give a good bound on the probability that a random
variable $S$ takes a value greater than $A=A(x)$ with some number $A$
depending on~$x$, more explicitly if we want to give an upper bound of
the form $e^{-\const x}$ for the probability of this event,
then the following argument is often useful. The inequality
$P(S>A)=P\(\frac xA S>x\)\le e^{-x} E\exp\{\frac xA S\}$ holds. If we
can show that $E\exp\{\frac xA S\}\le e^{\alpha x}$ with some constant
$\alpha<1$, then we get the desired estimate. In the next problem we
want to show that this method also works in the case we
are interested in. \medskip
\item{11.)} Let us apply the notations introduced in the
previous problem. Let us consider such real constant $x>0$ and
positive integer $l>0$ which satisfy the inequalities $C_0\log
nCxn^{-1}$ with some fixed constants $C>0$ and
$C_1>0$. Let us show that in this case there exists a constant $\bar
K=\bar K(C)>0$ such that for all sufficiently large $n$
$$
E\exp\left\{\frac{\sqrt x}{\sqrt n}\xi_k\right\}\le 1+\frac{\bar K\sqrt
x} {\sqrt n}.
$$
Let us prove with the help of the above estimate and the result of
problem~10 (by choosing the constant $B>0$ in it sufficiently small),
that for such constants $x$ and $l$ which satisfy the above conditions
the inequality
$$
P\(72 K\sum_{j=1}^l 2^jY_n\(\frac1{2^{j-1}}\)^2>x\)0$ for all sufficiently
large $n$. \medskip
We also want to give a good bound on the distribution of the first term
at the right-hand side of formula (12). The standardized Poisson process
appearing here is a process with independent increments. But the terms
in the sum we have to investigate, the random variables
$X_n\(2^{-j-1}\)^2$ are not independent, since these terms are the
increments of the process $X_n(t)$ in the overlapping
intervals $[0,2^{-j-1}]$. But it is relatively simple to overcome this
difficulty, if we write the random variable $X_n\(2^{-j-1}\)$ as the
sum of the increment of the process $X_n(t)$ on appropriate disjoint
intervals, then we bound the square of the sums got in this way by the
Cauchy--Schwarz inequality and sum up these inequalities. In such a way
we can write that
$$
\align
2^jX_n\(\frac1{2^{j-1}}\)^2&=2^j\Biggl(
\sum_{k=j}^{l} 2^{-(k-j)/4}\cdot 2^{(k-j)/4}
\[X_n\(\frac1{2^{k-1}}\)-X_n\(\frac1{2^{k}}\)\]\\
&\qquad\qquad+2^{-(l-j)/4}\cdot 2^{(l-j)/4}
X_n\(\frac1{2^{l}}\)\biggr)^2 \tag15 \\
&\le 2^j B\(\sum_{k=j}^{l} 2^{(k-j)/2} \[X_n\(\frac1{2^{k-1}}\)-X_n
\(\frac1{2^{k}}\)\]^2+2^{(l-j)/2} X_n^2\(\frac1{2^{l}}\)\)
\endalign
$$
for all numbers $j=1,\dots,l$ with the constant
$B=B_j=\summ_{k=j}^l2^{-(k-j)/2}+2^{-(l-j)/2}<5$.
We want to show with the help of the inequality (15) that the
estimation of the first term in formula (12) can be reduced to the
estimation of sums of appropriate linear combination of squares of
independent standardized Poisson distributed random variables. The
problem which arises in such a way is very similar to the last
estimate in problem~8, and it can be solved similarly. However, a
new difficulty appears when handling this problem, because the square
of a standardized Poisson distributed random variable --- unlike the
square of a normally distributed random variable --- has no exponential
moments. This difficulty can be overcome by a natural truncation of
the terms in the sum under consideration. The contribution of the
terms with too large values have only negligible contribution to the
sum, and the truncated random variables have finite exponential moments
which can be well bounded. Let us also remark that here we did not
really exploited that we work with Poissonian distributed random
variables. In the case when the approximation of partial sums of
independent random variables with Brownian motion is investigated,
then a similar problem discussed appears, but in that problem sums of
independent random variables play the role of the Poisson process. It
can be solved in the same way because sums of independent random
variables with exponential moments have a similarly good Gaussian
approximation as a Poissonian random variable with a large
parameter.\medskip
\item{12.)} Let us show that
$$
\aligned
&P\(72K\sum_{j=1}^l 2^jX_n\(\frac{1}{2^{j-1}}\)^2>x\)\\
&\qquad\le P\(1500K\(\sum_{k=1}^{l} \frac{2^k}n (\eta_k-E\eta_k)^2+
\frac{2^l}n (\eta_{l+1}-E\eta_{l+1})^2\) >x\),
\endaligned \tag16
$$
where $\eta_k$, $k=1,\dots,l+1$, are independent random variables,
$\eta_k$ has Poissonian distribution with parameter
$\lambda_k=\lambda_{k,n}=n2^{-k}$, if $1\le k\le l$, and $\eta_{l+1}$
has Poissonian distribution with parameter
$\lambda_{l+1}=\lambda_{l+1,n}=\lambda_l$.
\item{} Let us define the truncation $\bar\eta_k=\bar\eta_k(n)$ of the
random variables $\eta_k$, $1\le k\le l+1$ in the following way:
$$
\bar\eta_k=\left\{
\aligned
\eta_k-E\eta_k &\quad\text{if }|\eta_k-E\eta_j|u)\le2\exp\left\{-\dfrac{u^2}{8n2^{-k}}\right\}$,
if $u0$ (independent of the parameter $n$)
for all $1\le k\le l+1$.
\item{} Let us consider a real number $x>0$ and an integer $l>0$
which satisfy the inequalities $C_0\log nCxn^{-1}$ with appropriate constants $C>0$ and $C_0>0$,
and let the relation $n\ge n_0$ hold, where $n_0=n_0(C,C_0)$ is an
appropriate threshold. Let us show in this case that
$$
P\(72K\sum_{j=1}^l 2^jX_n\(\frac{1}{2^{j-1}}\)^2>x\)\le e^{-D_5x}
\tag17
$$
with an appropriate constant $D_5>0$. Let us show that formulas (10) and
(9) follow from the already proved inequalities. \medskip
To carry out the proof of the {\it Approximation Theorem}\/ we still
need a good estimate on the probabilities in formulas (6b) and~(6c).
First we formulate a {\it Statement}\/ which we shall prove
and which supplies great help in bounding the probabilities in formulas
(6b) and~(6c). \medskip\noindent
{\bf Statement:} {\it Let $B(t)$, $0\le t\le1$, be a Brownian
bridge, and $Z_n(t)$, $0\le t\le1$, a standardized empirical
distribution function made from $n$ independent and in the interval
$[0,1]$ uniformly distributed random variables. Let us fix a real number
$0\le y\le n$. Then for all real numbers $L>0$ there exist such
positive constant $\alpha=\alpha(L)>0$ and threshold index
$n_0=n_0(L)$ for which the processes $B(t)$ and $Z_n(t)$ satisfy the
following inequalities:
$$
\align
P\(\sup_{0\le ty\)&\le 2e^{-\alpha y}, \tag18a
\\ P\(\sup_{0\le ty\)&\le 2e^{-\alpha y},
\tag18b
\endalign
$$
if $n\ge n_0$. The constant $\alpha>0$ and the threshold index $n_0$ can
be given as the function of the number $L$ i.e.\ the threshold index
$n_0$ can be given independently of the number $y$, and the exponent
$\alpha>0$ depends neither on the number $y$ nor the threshold index
$n_0$.} \medskip
We did not try to determine the optimal constants in formulas
(18a) and (18b), since we do not need it. The determination of the
optimal constant is sufficiently simpler in formula (18a) since the
Brownian bridge is a Gaussian process, and the investigation of such
processes is considerably simpler. The heuristic content of (18b) is
that the process $Z_n(t)$ for large indices $n$ behaves
similarly to a Brownian bridge, hence it satisfies similar estimates.
The next lemma which supplies a bound on the distribution of the
maximum of a process with independent increment plays an important role
in the proof of the {\it Statement}. We shall give the proof of this
lemma in an {\it Appendix}. \medskip\noindent
{\bf Lemma.} {\it Let $\xi_1$,\dots, $\xi_n$ be independent random
variables, for which $E\xi_k\ge0$, $Ee^{s\xi_k}=e^{B_k(s)}$ with some
fixed $s>0$ and numbers $B_k(s)$, $k=1,\dots,n$. Put
$S_k=\sum\limits_{j=0}^k \xi_j$, $k=1,\dots,n$.
$S_k=\sum\limits_{j=0}^k \xi_j$, $k=1,\dots,n$. Then
$$
P\(\sup_{1\le k\le n}S_k>x\)\le \exp\left\{-sx+\sum_{k=1}^n
B_k(s)\right\}
$$
for all $x>0$.
Let $X(t)$, $a\le t \le b$, be a stochastic process with independent
increments in an interval $[a,b]$ i.e. let us assume that the random
variables $X(t_1)-X(a)$, $X(t_2)-X(t_1)$,\dots, $X(b)-X(t_k)$ are
independent for all numbers $k$ and $a\le t_1\le t_2\le\cdots\le t_k\le
b$. Let us also assume that the trajectories of the process $X(t)$
are continuous or more generally so called cadlag (continue \`a
droite, limite \`a gauche), i.e. continuous from the right functions
which have a left-side limit in all points $a\le t**x\)\le e^{-sx}Ee ^{s(X(b)-X(a))}
$$
holds for all numbers $s>0$. (This formula is meant in such a way that
the right-hand side of the inequality is infinity in the case when
the expectation $Ee^{s(X(b)-X(a))}$ does not exist.)}
\medskip\noindent{\it Remark:}\/ The condition $E\xi_k\ge 0$ or the
monotonicity of the function $m(t)$ is required, because this guarantees
that the partial sums $S_k$, $k=1,2,\dots,n$, or respectively the
process $X(t)$, $a\le t\le b$, has a positive trend.
The probability theory has several results which state that the maximum
of the partial sum random variables with non-negative expectation is
not much greater than the sum of all random variables. The previous {\it
Lemma}\/ is also such a result. It states that a natural bound on the
sum of all random variables also supplies a bound for the maximum of
all partial sums. \medskip
The previous {\it Lemma}\/ cannot be applied directly for the proof of
the {\it Statement}, since neither the Brownian bridge nor a
standardized empirical process are processes with independent increment.
But we can prove the {\it Statement}\/ with the help of the
following observation. If $W(t)$, $0\le t\le1$, is a Wiener process,
that is it is such a Gaussian process for which $EW(t)=0$, and
$EW(s)W(t)=\min(s,t)$ for all $0\le s,t\le 1$, then $W(t)$ is a process
with independent process (and we may also assume that its trajectories
are continuous function), and the stochastic process $B(t)=W(t)-tW(t)$
is a Brownian bridge. The other result of the {\it Statement},\/ the
estimate (18b) can be proved by means of a Poissonian approximation
defined with the help of formulas (11a)---(11c). \medskip
\item{13.)} Let us prove that modification of inequality (18a)
in which the Brownian bridge $B(t)$ is replaced by a Wiener process
$W(t)$. Let us also prove that modification of the inequality
(18b) in which the process $Z_n(t)$ is replaced by a standardized
Poisson process $X_n(t)$ with parameter~$n$.
(We have defined a standardized Poisson process with parameter $n$ in
formula (11b).)
\item{14.)} Let us prove inequality (18) by means of the result of the
previous result and the representation of a Brownian bridge $B(t)$ in
the form $B(t)=W(t)-tW(1)$, where $W(t)$ is a Wiener process.
\item{} Let us consider the process $Y_n(t)$, $0\le t\le1$, defined in
formula (11c). Let us show that this process satisfies the inequality
$$
P\(\sqrt n\sup_{0\le t\le L\tfrac yn}|Y_n(t)|\ge y\)\le 2e^{-\alpha y}
$$
for all $L\ge0$ $n>n_0$ with an appropriate threshold index
$n_0$ and appropriate number $\alpha=\alpha(L)>0$. Let us prove with
the help of this inequality and the result of the previous problem
the inequality (18b). \medskip
It is not difficult to prove the {\it Approximation Theorem}\/ with the
help of the above result. Given some number $x$ such that $C_0\log n1$ let us choose a constant
$l=l(x)$ in such a way that $C\dfrac xn\le 2^{-l}<2C\dfrac xn$. Then
the previous results enable us both to give a good bound on the
probability $P\(\supp_{1\le k\le 2^l}\sqrt n|Z_n(k2^{-l})-B(k2^{-l})|
\ge \dfrac x2\)$ and to estimate the fluctuation of the processes
$\sqrt n B(t)$ and $\sqrt n Z_n(t)$ in the intervals $(k-1)2^{-l}\le
t< k2^{-l}$, $1\le k\le 2^l$, assuming that the constant $C>0$
(independently of $n$) is chosen sufficiently large. In the case
$x>C^{-1}n$ the proof of the statement of the {\it Approximation
Theorem}\/ is considerably simpler. In this case the rough estimate
$\sqrt n|Z_n(t)-B(t)|\le \sqrt n (|Z_n(t)|+|B(t)|)$ is also sufficient
for our goals.\medskip
\item{15.)} Prove the {\it Approximation Theorem}\/ with the help of the
previous results.
\vfill\eject
\beginsection Some comments about the main result discussed in this
paper
The main result of this work is contained in the paper of J\'anos
Koml\'os, P\'eter Major and G\'abor Tusn\'ady {\it An approximation of
partial sums of independent RV's and the sample DF. ~I.}\/
in the journal {\it Zeitschrift f\"ur Wahrscheinlichkeitstheorie und
verwandte Gebiete} {\bf32} (1975), pp.\ 111--131. This article does not
work out all details of the proof. It also contains an analogous result
about the approximation of partial sums of independent random variables
by a Wiener process. The two results are based on the same ideas and the
above mentioned paper works out only the approximation of the partial
sums or independent random variables in detail.
The main difference between the discussion of the above mentioned paper
and of this work is that here we also worked out those details which are
very natural to expect, but whose precise proof is a little bit
inconvenient. Such difficulties arise because we have to work with
``almost" but not completely independent random variables. Beside this,
I thought that a detailed discussion of certain classical methods like
for instance the Poissonian approximation may be interesting and
instructive in itself. So I tried to explain the ideas behind some
technical steps even if it made the discussion considerably longer.
In a subsequent series of problems I shall also discuss the
approximation of partial sums of independent random variables. In that
work I shall not work out all details. Instead of it I shall try to
explain the basic problems in that subject. Furthermore I try to explain
with the help of some examples which details must be investigated
especially carefully.
The proof of the {\it Approximation Theorem}\/ is also contained in some
works which appeared after the paper of Koml\'os, Major and Tusn\'ady.
Those who are interested more in this subject can study the works of
G\'abor Tusn\'ady, Jean Bretagnolle, and Pierre Massart. These papers
also investigate the problem how small constants can be chosen
in the {\it Approximation Theorem}. Here we have not dealt with this
problem.
It us worth mentioning that in some papers the construction satisfying
the {\it Approximation Theorem}\/ and the prof of the result is based on
an expansion with respect to Haar functions. Although in my discussion
the Haar functions did not appear, the two discussions do not differ
essentially. One can say that in these two approaches the same
construction is explained in a different language. I briefly write down
the argument of the construction made on the basis of expansion with
respect to Haar functions.
Let $\varphi_1(t)$, $\varphi_2(t)$, \dots, be an arbitrary system of
complete orthogonal functions on the space $L_2([0,1],\lambda)$, where
$\lambda$ denotes the Lebesgue measure, and let $\eta_1,\eta_2,\dots$,
be a sequence of independent random variables with standard normal
distribution. By a result of probability theory the stochastic
process
$$
W(t)=\sum_{l=1}^\infty\eta_l \int_0^t \varphi_l(s)\,ds,\quad 0\le t\le1
$$
is a Wiener process. Indeed, the above defined process is a Gaussian
process (the infinite sum in this expression is convergent with
probability one for all numbers $0\le t\le1$, $EW(t)=0$, and the
covariance function of the process is
$$
EW(s)W(t)=\sum_{l=1}^\infty \int_0^s \varphi_l(u)\,du
\int_0^t \varphi_l(u)\,du=\min(s,t)\quad\text{for all numbers }0\le
s,t\le 1.
$$
The last identity is a consequence of the Parseval formula by which
$$
\min(s,t)=\int_0^1 I_{[0,s]}I_{[0,t]}(u)\,du=\summ_{l=1}^\infty a_lb_l,
$$
where $I_{[a,b]}(\cdot)$ is the indicator function of the
interval $[a,b]$, and $a_l=\int_0^1 I_{[0,s]}(u)\varphi_l(u)\,du$,
$b_l=\int_0^1 I_{[0,t]}(u)\varphi_l(u)\,du$. In a complete proof
we also should show that the trajectories of the above defined process
are continuous. But we shall apply this representation only in a special
case, and we shall not need the statement about the continuity of the
trajectories. (On the other hand, in the special case we shall consider
the proof of the continuity of the trajectories is relatively simple.)
Let us recall the definition of Haar functions. Let us define the
functions $\chi_{k,l}(u)$, $0\le l<\infty$, $1\le k\le 2^l$,
on the interval $[0,1]$ by the formulas
$\chi_{0,1}(u)\equiv1$, $\chi_{k,l}(u)=2^{l/2}$, if $(k-1)2^{-l}\le
u<(2k-1)2^{-l}$, $\chi_{k,l}(u)=-2^{l/2}$, if $(2k-1)2^{-l}\le
u0.
$$
It follows from these inequalities that $C_1(x+2)<\dfrac
{\varphi(x)}{1-\Phi(x)}0$ and $C_2>0$. Furthermore, since both functions $\varphi(x)$
and $1-\Phi(x)$ are separated from zero and infinity if $x$ is in a
finite domain, the above inequality holds for all $x>-1$. By the
identities $\varphi(-x)=\varphi(x)$ and $\Phi(-x)=1-\Phi(x)$ the second
inequality in part~a) of problem~1 is equivalent to the first one.
\itemitem{b.)}
$$
\log\frac {1-\Phi(x+h)}{1-\Phi(x)}=h
\left.\frac d{dx}\log\(1-\Phi(x)\)\right|_{x=u}= -h
\frac{\varphi(u)}{1-\Phi(u)},
$$
where $u$ is an appropriate number in the interval $[x,x+h]$.
Hence in the case $|h|<|x|+1$
$$
C_1(x+2)<\dfrac{\varphi(u)}{1-\Phi(u)}-1
$$
by the already proven part of the problem. By substituting this
relation to the previous identity we get the first identity of the
problem in the case $h>0$ (and $x>-1$). The second identity follows
from this one by the relation $\Phi(-u) =1-\Phi(u)$. The case $h<0$
can be similarly handled or it can be reduced to the case $h>0$.
\item{2.} First we prove the asymptotic relation for the
distribution function $F_{m,n}(x)$.
\item{} By the {\it (large deviation) Theorem}\/ formulated at the
beginning of this series of problems and the result of problem~1
$$
\align
1-F_{m,n}(x)&=\(1-\Phi\(\sqrt{\frac nm} x\)\)
\exp\left\{O\(\frac{x^3+1} {\sqrt n}\)\right\}\\
&=\(1-\Phi(x)\)
\exp\left\{O\(\left|\sqrt{\frac nm} -1\right|(x^2+2x)+\frac{x^3+1}
{\sqrt n}\)\right\}\\
&=(1-\Phi(x))\exp\left\{O\(\frac{x^3+\frac{|n-m|}{\sqrt n}(x^2+x)+1}
{\sqrt n}\)\right\}
\endalign
$$
if $0\le x\le\bar A\sqrt nx$, because $\left|\sqrt{\dfrac nm}
-1\right|(x^2+2x)\le \const \dfrac{|n-m|}n(x^2+2x)$ if the conditions of
problem~2 hold. The other inequality can be proved similarly.
\item{} We prove with the help of the already proved inequality that
there exists such a constant $K>0$ for which
$$
\aligned
&1-F_{m,n}(x+h(x))\le 1-\Phi(x)\le1-F_{m,n}(x-h(x)),\\
&\qquad\text{with }h(x)=h_{m,n}(x)=K\frac{x^2+\frac{|n-m|}{\sqrt
n}(|x|+1)+1} {\sqrt n},
\endaligned \tag2.1
$$
if $0\le x\le \bar A\sqrt n$ with some appropriate $\bar A>0$. Indeed,
in this case
$$
\align
&\log\dfrac{1-F_{m,n}(x+h(x))}{1-\Phi(x)}=
\log\dfrac{1-F_{m,n}(x+h(x))}{1-\Phi(x+h(x))}+
\log\dfrac{1-\Phi(x+h(x))}{1-\Phi(x)}\\
&\quad\le \frac {K_1}{\sqrt
n}\((x+h(x))^3+\dfrac{|n-m|}{\sqrt n}\((x+h(x))^2+x
+h(x)\)+1\)-C_1h(x)(x+2) \endalign
$$
with appropriate constants $K_1>0$ and $C_1>0$ if the inequalities
$|x+h(x)|0$, $B>0$ and $K>0$ in such a way that under the
conditions $x<\bar A\sqrt n$, $|n-m|0$ and $B>0$ (depending on the number~$K$) sufficiently small,
then the inequalities $|x+h_{m,n}(x)|0$ if $|\eta|\le \bar A\sqrt n$
and $|n-m|\le Bn$. (In the last estimation we have exploited that
$\dfrac{|n-m|}{\sqrt n}(|\eta|+1)\le
\dfrac12\(\dfrac{(n-m)^2}n+\eta^2+1\)$.) In such a way he have solved
problem~2 (with the notation $\bar A$ instead of $A$ in the last
relation).
\smallskip \item{}{\it Remark:}\/ Actually we have proved the following
slightly stronger estimate:
$$
|F_{m,n}^{-1}(\Phi(\eta))-\eta|\le K\dfrac{\eta^2+\frac{|n-m|}
{\sqrt n}(|\eta|+1)+1}{\sqrt n} \quad\text{on the set }
\{|\eta|0$ appearing at the end of its formulation is chosen sufficiently
small. On the other hand, $\bar V_{2k-1,l+1}(n)-\bar U_{2k-1,l+1}
=F_{m_k,l}^{-1}(\Phi(\eta))-\eta$ by formula (5b) with the function
$F_{m_k,l}(x)$ defined in $(5\text{a}')$ which agrees with the function
$F_{\bar n,\bar m}(x)$ in problem~2. Beside this the appropriate
term in the estimate of problem~2 satisfies the relation $\dfrac{(\bar
n-\bar m)^2}{\bar n}=\dfrac{V_{k,l}(n)^2}2\dfrac {\bar m}{\bar n}=\const
V_{k,l}(n)^2$. Hence the first part of relation~(7a) follows from the
result of problem~2. Its second part is a simple consequence of the
relation $\bar U_{2k-1,l+1}=-\bar U_{2k-1,l+1}$. The inequality~(7b) is
a consequence of formula~(7a), since
$$
|U_{2k-1,l+1}-V_{2k-1,l+1}(n)|\le|\bar U_{2k-1,l+1}-\bar
V_{2k-1,l+1}(n)|+\dfrac{|U_{k,l}-V_{k,l}(n)|}{\sqrt 2},
$$
and
$$
|U_{2k,l+1}-V_{2k,l+1}(n)|\le|\bar U_{2k-1,l+1}-\bar
V_{2k-1,l+1}(n)|+\dfrac{|U_{k,l}-V_{k,l}(n)|}{\sqrt 2}.
$$
These relations hold, since $V_{2k-1,l}(n)=\bar
V_{2k-1,l}(n)+\dfrac{V_{k,l}(n)}{\sqrt2}$,
$U_{2k-1,l}=\bar U_{2k-1,l}+\dfrac{U_{k,l}}{\sqrt2}$
by the identities $E(V_{2k-1,l}(n)|\Cal
G_l(n))=\dfrac{V_{k,l}(n)}{\sqrt2}$ and $E(U_{2k-1,l}(n)|\Cal
F_l)=\dfrac{U_{k,l}}{\sqrt2}$ proved in problems~3 and~4. Beside
this a similar relation holds also for the random variables
$V_{2k,l}(n)$ and $U_{2k,l}$.
\item{7.)} By the definition of the random variables $V_{k,l}$ and
numbers $\e(j)$ and $k(j)$ the identity
$$
\align
\e(j)2^{-(j+1)/2}&\(\sqrt2 V_{k_{j-1}+1,j-1}(n)
-V_{k_{j}+1,j}(n)\)\\
&\qquad=\e(j)\(Z_n(k_j2^{-j})-Z_n(k_{j-1}2^{-(j-1)}\)
\endalign
$$
holds for all numbers $1\le j\le l$. Indeed, either $\e(j)=0$ when
the above identity is obvious or $\e(j)=1$ when $k_j=2k_{j-1}+1$ and
the identity follows from the definition of the random variables
$V_{k,l}(n)$. By summing up these identities and exploiting the
relations $Z_n(k_l2^{-l})=Z_n(t)$ and $Z_n(k_0)=Z_n(0)=0$ we get the
first line of formula~(8a) about the representation of the random
variable $Z_n(t)$. The analogous formula about the expression $B(t)$
can be proved similarly.
\item{} In the proof of relation (8b) we apply formula (7b) with the
choice $l=j-s-1$ and $k=k_{j-s-1}+1$. If
$u_{j-s-1}=k_{j-s-1}2^{-j-s-1} =u_{j-s}=k_{j-s}2^{-j-s}$, then
$k_{j-s}+1=2(k_{j-s-1}+1)-1$, and we consider the first term at
left-hand side term together with the first expression at the
right-hand side of this inequality. If
$u_{j-s-1}=k_{j-s-1}2^{-j-s-1}\frac{A\sqrt n}{2^{j/2}}\)
&=P\(\frac{2^{j/2}}{\sqrt n}\left|\sum_{k=1}^n(\chi_k-E\chi_k)\right|>
\frac{A\sqrt n}{2^{j/2}}\)\\
&=P\(\left|\sum_{k=1}^n(\chi_k-E\chi_k)\right|>\frac{A n}{2^{j}}\),
\endalign
$$
where $\chi_k$, $1\le k\le n$, are independent random variables, and
$P(\chi_k=1)=1-P(\chi_k=0)=2^{-(j-1)}$. This relation implies that
$$
Ee^{t(\chi_k-E\chi_k)}=\(1-\dfrac1{2^{j-1}}
+\dfrac{e^t}{2^{j-1}}\)e^{-t/2^{j-1}},
$$
and from here
$Ee^{t(\chi_k-E\chi_k)}\le\exp\left\{\dfrac{e^t-1}{2^{j-1}}-\dfrac
t{2^{j-1}}\right\}\le\exp\left\{\dfrac{10t^2}{2^j}\right\}$ if
$|t|<1$. In the latter estimations we exploited that the inequalities
$t+1\le e^t$ and $e^t-1-t<5t^2$ hold if $|t|\le1$. By the previous
estimates
$E\(\exp\left\{t\summ_{k=1}^n(\chi_k-E\chi_k)\right|\right\}\le
e^{10t^2n2^{-j}}$ if $|t|<1$, and
$$
\aligned
&P\(V_{k_{j-1}+1,j-1}(n)>\frac{A\sqrt n}{2^{j/2}}\)
=P\(\exp\left\{t\sum_{k=1}^n(\chi_k-E\chi_k)\right\}
>e^{Ant/2^j}\) \\
&\qquad\le e^{n2^{-j}(10t^2-At)}\le e^{-\bar D2^{l-j}x} \quad
\text{for all numbers }1\le j\le l.
\endaligned \tag2.2a
$$
with an appropriate constant $\bar D>0$ if $j\le l$. In the last
inequality we have exploited that $10t^2-At<-D'$ with an
appropriate constant $D'>0$, if the number $t>0$ is chosen
sufficiently small, and $-n2^{-j}=-2^{l-j}2^{-l}n\le
-Cx2^{l-j}$ under the conditions of problem~8.
\item{} As $\bar U_{k_{j-1}+1,j-1}$ is a random variable with standard
normal distribution, hence simple calculation yields that
$$
\aligned
P\(|U_{k_{j-1}+1,j-1}(\oo)|<\frac{A\sqrt n}{2^{j/2}}\)&\le
e^{-A^2n2^{j-1}}\le e^{-D''2^{l-j}x} \\
\quad \text{for all numbers }1\le j\le l.
\endaligned \tag2.2b
$$
The estimate (2.2a) remains valid if the random variable
$V_{k_{j-1}+1,j-1}(n)$ is replaced by $-V_{k_{j-1}+1,j-1}(n)$.
If we sum up the inequalities (2.2a) theirs analogs formulated above
and the inequality (2.2b) for all numbers $1\le j\le n$, then we get
the inequalities $1-P(\bold B)\le e^{-D_1x}$.
\item{} To prove the last estimate of problem~8 let us consider the
square of a normally distributed random variable, and let us calculate
the moment generating function of the normalization of the random
variables formulated in such a way. If $\eta$ is a random variable
with standard normal distribution, then
$$
Ee^{t(\eta^2-E\eta^2)}=Ee^{t(\eta^2-1)}=\frac{e^{-t}}{\sqrt {2\pi}}
\int e^{tx^2-x^2/2}\,dx=\dfrac{e^{-t}}{\sqrt{1-2t}},\quad\text{if
}t<\frac12.
$$
It follows from here that $\log
Ee^{t(\eta^2-E\eta^2)}=-t-\frac12\log(1-2t)x\)=P\(\exp\left\{\frac14
\sum_{j=1}^l (\bar U_{1,j-1}^2-E\bar U_{1,j-1}^2)\right\}
>e^{x/72K}\)\\
&\qquad\le e^{l/16-x/72K}\le e^{-x/144K} =e^{-D_2x},
\endalign
$$
as we formulated in the problem, under the condition $l\le\frac
x{9K}$. This inequality holds, since under the conditions of problem~8 \
$l\le\log C+\log n-\log x\le 2\log n\le \dfrac{2x}{C_0}\le\dfrac x{9K}$
if the constant $C_0$ is chosen sufficiently large in these conditions,
and $n\ge n_0$ with an appropriate index $n_0$.
\item{9.)} Inequality (8c) holds for all $t=k2^{-l}$, $k=1,\dots,2^l$,
on the set $\bold B_0=\bigcapp_{k=1}^{2^l}\bold B(k2^{-l})$, where the
set $\bold B(t)$ was defined after formula~(8c). On the basis of the
results of problem~8
the inequality $1-P(\bold B_0)\le 2^l e^{-D_1x}\le \dfrac n{Cx}
e^{-D_1x}\le ne^{-D_1x}\le e^{x/C_0-D_1x}\le e^{-D_1x/2}$ holds if
the constant $C_0$ and the threshold index $n_0$ are chosen
sufficiently large in the condition $x\ge C_0\log n$ of problem~9.
\item{} Hence inequality~(8c) and the first part of problem~8 imply that
$$
\align
P&\(\sup_{1\le k\le 2^l}\sqrt n |Z_n(k(2^{-l})-B(k2^{-l})|>\frac x2\) \\
&\qquad \le e^{-D_1x/2}+2^l P\(4K\sum_{j=1}^l\(\bar U^2_{1,j}
+V^2_{1,j-1}(n)+1\)\ge\frac x2\)\\
&\qquad \le e^{-D_1x/2}+2^l P\(18K\sum_{j=1}^l \bar U^2_{1,j-1}>x\)
+2^l P\(18K\sum_{j=1}^l V^2_{1,j-1}>x\).
\endalign
$$
In the last inequality we exploited that $4K\summ_{j=1}^l1=4Kl\le\dfrac
x{18}$, because $l\le \log n\le \dfrac x{C_0}\le \dfrac x{72K}$, if in
the condition of relation~(9) the constant $C_0>0$ and threshold index
$n_0$ for which $n\ge n_0$ are chosen sufficiently large. Hence on the
basis of formula~(10), the last inequality of problem~8 and the previous
estimate the left-hand side of the expression~(9) can be bounded from
above by the $e^{D_1x/2}+2^l\(e^{-D_2x}+e^{-D_3x}\)$. As $2^l\le
n\le e^{\min (D_2,D_3)x/2}$, if the constant $C_0>0$ and threshold index
$n_0$ are appropriately chosen in formula~(9), this implies the
statement of problem~9.
\item{10.)} As $Z_n(t)=X_n(t)-Y_n(t)$, $Z_n(t)^2\le
2X_n(t)^2+2Y_n(t)^2$, and
$$
\align
&P\(18\sum_{j=1}^l 2^jZ_n^2\(\frac{1}{2^{j-1}}\)>x\)\\
&\qquad \le P\(36\sum_{j=1}^l 2^j\(X^2_n\(\frac{1}{2^{j-1}}\)
+Y^2_n\(\frac{1}{2^{j-1}}\)\)>x\) \\
&\qquad\le P\(72K\sum_{j=1}^l 2^jX_n\(\frac{1}{2^{j-1}}\)^2>x\)
+P\(72K\sum_{j=1}^l 2^jY_n\(\frac{1}{2^{j-1}}\)^2>x\).
\endalign
$$
This is formula (12).
\item{} If $\kappa_n$ is a Poisson distributed random variable with
parameter $n$, then the moment generating function of the random
variable $\kappa_n-n$ is
$$
Ee^{t(\kappa_n-n)}=e^{-tn}\summ_{k=0}^\infty
\dfrac{n^k}{k!}e^{-n+tk}=e^{n(e^t-1-t)}.
$$
This implies because of the inequality $n(e^t-t-1)\le t^2$, under the
condition $|t|\le1$ that $Ee^{t(\kappa_n-n)}\le e^{nt^2}$, if
$|t|\le1$. Hence $P(\kappa_n-n>y)\le e^{nt^2-ty}\le e^{-y^2/4n}$ with
the choice $t=\frac y{2n}$, if $y\le 2n$. Similarly,
$P(\kappa_n-n<-y)\le e^{-y^2/4n}$. The slightly more general statement
formulated about $\kappa_n-n$ also holds. Indeed, if the condition
$|y|\le 2n$ is replaced by the condition $|y|\le B_1n$, then the
previous relation remains valid if the exponent $-y^2/4n$ is replaced
by the exponent $-B_2y^2/n$ with an appropriate constant~$B_2>0$.
\item{} To prove formula (13) let us observe that the random
variables $Y_n(t)$ in (11c) are non-negative, hence
$$
P\(72 K\sum_{j=1}^l 2^jY_n\(\frac1{2^{j-1}}\)^2>x\)\le P\(
\(\sqrt{72K}\sum_{j=1}^l 2^{j/2} Y_n\(\frac{1}{2^{j-1}}\)\)^2>x\).
$$
Then taking the conditional probability at the left-hand side of the
next formula with respect to the condition $\kappa_n-n=m$,
$-\infty\sqrt x\)\\
&\qquad=\sum_{m=-\infty}^\infty P\(\sqrt{72 K} \sum_{j=1}^l 2^{j/2}
\bar Y_{n,|m|} \(\frac{1}{2^{j-1}}\)>\sqrt x \)P(\kappa_n-n=m)\\
&\qquad\le P\(\sqrt{72 K} \sum_{j=1}^l 2^{j/2}
\bar Y_{n,B\sqrt {nx}} \(\frac{1}{2^{j-1}}\)>\sqrt x \)
P(|\kappa_n-n|\le B\sqrt {nx})\\
&\qquad \qquad +P(|\kappa_n-n|> B\sqrt {nx}).
\endaligned \tag2.3
$$
The last relation of formula~(2.3) can be seen with the help of the
observation that the first probability in the second line of
formula~(2.3) is a monotone increasing function of the parameter
$|m|=|\kappa_n-n|$. By fixing the number $M=B\sqrt{nx}$, and
by replacing the parameter $m$ by $M$ in the case $|m|\le M$ and
applying the trivial upper bound~1 for this probability we
get the last inequality in formula~(2.3).
\item{} The inequality in formula (13) is a simple consequence of
relation~(2.3) and the formula before it. Finally the identity
formulated at the end of formula (13) follows from a simple
calculation if we put the definition of the random variable $\bar
Y_{n,B\sqrt{nx}}$ in the expression at the second line of formula~(13),
change the order of summation in the double sum obtained in such a way
and put together the terms depending on the variable $\zeta_k$, $1\le
k\le B\sqrt{nx}$, in the form of a single random variable $\xi_k$.
\item{} The random variables $\xi_k=\xi_{k,l}$ are functions of the
independent random variables $\zeta_k$. It follows from this fact and
the explicit form of the definition of the random variables $\xi_k$
that they are independent and identically distributed.
\item{11.)} If the conditions of the problem are satisfied, then
$2^{l/2}\le\sqrt{\dfrac n{Cx}}$, and $\dfrac{\sqrt x}{\sqrt n}{\xi_k}
\le \dfrac{\sqrt x}{\sqrt n}\dfrac{2^{(l+1)/2}}{\sqrt2-1}\le
\dfrac{\sqrt x}{\sqrt n} \sqrt{\dfrac n{Cx}}\dfrac{\sqrt2}{\sqrt2-1}
=\dfrac{\sqrt2}{(\sqrt2-1)\sqrt C}$. Hence
$\exp\left\{\dfrac{\sqrt x}{\sqrt n}{\xi_k}\right\}\le 1+\bar C
\dfrac{\sqrt x}{\sqrt n}{\xi_k}$ with an appropriate number $\bar C=\bar
C(C)>0$, and $E\exp\left\{\dfrac{\sqrt x}{\sqrt n}{\xi_k}\right\}\le
1+\bar C \dfrac{\sqrt x}{\sqrt n}E{\xi_k}\le 1+\bar K \dfrac{\sqrt
x}{\sqrt n}$ with an appropriate number $\bar K=\bar K(C)$, as we have
claimed, since $E\xi_k=\summ_{j=1}^l 2^{-j/2-1}\le \sqrt2+1$.
\item{} This implies that
$$
\align
P\(\frac{\sqrt{72 K}}{\sqrt n}\sum_{k=1}^{B\sqrt {nx}} \xi_k>\sqrt x\)
&=P\(\exp\left\{\frac{\sqrt x}{\sqrt n}\sum_{k=1}^{B\sqrt
{nx}}\xi_k\right\} >\exp\left\{\frac x{\sqrt{72 K}}\right\}\)\\
&\le\(1+\bar K\dfrac{\sqrt x}{\sqrt n}\)^{B\sqrt{nx}}\!\!
\exp\left\{-\frac x{\sqrt{72 K}}\right\}\le e^{B\bar Kx-x/{\sqrt{72
K}}}.
\endalign
$$
Let us choose the number $B=\dfrac1{12\bar K\sqrt K}$ in the last
inequality. In such a way we have proved that the probability considered
in this relation is less than $e^{-\const x}$. On the other hand, by the
first statement of problem~10 the inequality
$P(|\kappa_n-E\kappa_n|>B\sqrt{nx})u)\le2\exp2\left\{-\dfrac{u^2}
{8n2^{-k}}\right\}$ was already proved in problem~10 in the case
$u0$. (In these inequalities we have not tried to
give estimates with optimal constants. Further we have formulated them
in such a way that the case $k=l+1$ has not to be considered
separately.) In particular, with the choice $u=n2^{-k}$ we get the
estimate $P(|\eta_k-E\eta_k|\ge n2^{-k})\le2\exp\left\{-\dfrac
n{2^{(k+3)}}\right\}$. To prove the inequality
$E\exp\left\{n2^{-(k+4)}\bar\eta_k^2\right\} \le B$ let us introduce the
distribution functions $F_k(y)=F_{n,k}(y)=P(|\bar\eta_k|x\)
\le P\(1500K\(\sum_{k=1}^{l} \frac{2^k}n\bar\eta_k^2+
\frac{2^l}n \bar\eta_{l+1}^2\)>x\)\\
&\hskip7truecm +\sum_{k=1}^{l+1}P\(|\eta_k-E\eta_k|>2^{-k}n\)\\
&\qquad \le P\(\exp\left\{\sum_{k=1}^{l} \frac{2^{(k-4)}}n\bar\eta_k^2+
\frac{2^{(l-4)}}n \bar\eta_{l+1}^2\right\}>\exp
\left\{\frac{x}{24000K}\right\} \)\\
&\qquad\qquad\qquad +2\sum_{k=1}^{l+1}e^{-n2^{-(k+3)}}\le
e^{Bl-x/24000K}+\const e^{-n2^{-(l+4)}}.
\endalign
$$
If $x>C_0\log n$ with a sufficiently large constant $C_0>0$,
then $Bl-\dfrac x{24000K}\le -\dfrac x{30000K}$ and $n
2^{-(l+4)}\ge\const x$, since $Bl\le B\log n+\const\le
\dfrac{B}{C_0}x+\const\le\dfrac x{120000}$ under these conditions with
a sufficiently large constant $C_0$, and since
$n2^{-l}\ge Cx$, hence $n 2^{-(l+4)}\ge\const x$. These inequalities
imply formula~(17).
\item{} Inequality (10) is a simple consequence of formulas (12),
(14) (17), and relation (9) holds because of the result of
problem~9 from relation~(10) and the results of problems~7 and~8.
\item{13.)} Both a Wiener process $W(t)$ and a standardized Poisson
process $X_n(t)$ are processes with independent increments, and the
identities $EW(t)=0$ and $EX_n(t)=0$ hold for all numbers $0\le t\le1$.
Furthermore, the trajectories of a Wiener process are continuous and the
trajectories of a standardized Poisson process are cadlag (continuous
from the right with left-hand side limits) functions. Hence the
{\it Lemma}\/ formulated in this work can be applied both for the
processes $\pm B(t)$ and $\pm X_n(t)$.
\item{} Since $W(t)$, $t\ge0$, is a normally distributed random variable
with expectation zero and variance $t$, hence $Ee^{\pm
sW(t)}=e^{ts^2/2}$, and by the last inequality of the {\it Lemma}\/
$$
P\(\sup_{0\le ty\)\le
\exp\left\{ns^2L\frac y{2n}-sy\right\}
$$
with arbitrary number $s>0$. With the choice $s=\frac 1L$ this
inequality yields the analog of inequality (18a) for the Wiener process
with parameter $\alpha=\frac1{2L}$.
\item{} The proof of the analog of inequality (18b) for a standardized
Poisson process is similar. The random variable $\sqrt nX_n(t)$ is a
Poisson distributed random variable with parameter $\sqrt nt$ minus its
expected value. Hence, as it was shown for instance in the solution of
problem~10, $E e^{\pm s\sqrt nX_n(t)}\le e^{s^2t}$, if $0\le s\le1$.
Hence an application of the lemma yields with the choice
$s=\frac1{2L}$ that
$$
P\(\sup_{0\le ty\)\le
e^{s^2L y-sy}=e^{-y/4L},
$$
if $L\ge\frac12$, and $s\le1$ as a consequence. If $L\le\frac12$, then
exploiting that the probability at the left-hand side of
formula~(18) is a monotone increasing function of the parameter~$L$ we
get that the estimate (18b) holds in this case with the same coefficient
as in the case $L=\frac12$. (Actually the inequality could be improved
in this case, but we shall not need such an improvement.)
\item{14.)} The proof of formula (18a) can be obtained from the result
of problem~13 by means of the representation of a Brownian bridge
through a Wiener process in the following way:
$$
\align
&P\(\sup_{0\le ty\)\le
P\(\sup_{0\le t\frac y2\)\\
&\quad\; +P\(\sqrt n L\frac yn|W(1)|\ge \frac y2\)
\le 2e^{-\alpha y}+P\(|W(1)|\ge \frac{\sqrt n}{2L}\)\le
2e^{-\alpha y}+2e^{-n/8L^2}.
\endalign
$$
Formula (18a) follows from this inequality because of the condition
$0y\)\le 2e^{-\alpha y}+
P\(\sup_{0\le t\frac y2\), \tag2.4
$$
where the series of random variables $Y_n(t)$ are defined in
formula~(11c). The second term at the right-hand side of
formula~(2.4) can be bounded similarly to the method applied in
problem~11. Let us consider the conditional distribution of the
process $Y_n(t)$ under the condition $\kappa_n=m$,
$m=0,\pm1,\pm2,\dots$. Then we get similarly to the proof of
formula~(2.3) that
$$
\aligned
P\(\sup_{0\le t\frac y2\)&\le
P\(\sup_{0\le t\frac
y2\) \\
&\qquad +P\(|\kappa_n-n|>B\sqrt {ny}\),
\endaligned \tag2.5
$$
where the process $\bar Y_{n,m}(t)$ was defined before the formulation
of problem~10, before formula~(13), and $\kappa_n$ is the Poisson
distributed random variable with parameter~$n$ which appears in the
definition of the process $Y_{n}(t)$ given in formula~(11), and $B>0$
is an arbitrary positive number. The right-hand side of formula~(2.5)
can be well estimated by means of the calculation
$$
\align
&P\(\sup_{0\le t\frac
y2\) =P\(\sqrt n\bar Y_{n,B\sqrt{ny}}\(\frac{Ly}n\)\ge \frac y2\)\\
&\qquad =P\(\sum_{j=1}^{B\sqrt ny}\chi_j>\frac y2\)\le
\(Ee^{\chi_1}\)^{B\sqrt{ny}}e^{-y/2},
\endalign
$$
where $\chi_1,\chi_2,\dots$, are independent, identically distributed
random variables with distribution
$P(\chi_1=1)=1-P(\chi_1=0)=L\dfrac yn$. Hence we get, because of the
condition $y\le n$ that $Ee^{\chi_1}=1+\dfrac{Ly}n(e-1)\le
\exp\left\{(e-1)\dfrac{Ly}n\right\}\le
\exp\left\{L(e-1)\sqrt{\dfrac{y}n}\right\}$.
\item{} Let us apply the previous estimates with the choice of parameter
$B=\dfrac1{6L}$ together with the estimate on the distribution function
$\kappa_n-n$ given in problem~10. They yield the inequalities
$$
P\(\sup_{0\le t\frac
y2\)\le \(Ee^{\chi_1}\)^{\sqrt{ny}/6L}e^{-y/2}\le e^{(e-1)y/6-y/2}\le
e^{-y/6},
$$
and $P\(|\kappa_n-n|>\dfrac1{6L}\sqrt{yn}\)\le e^{-\const y}$. These
estimates yield a bound on the expression in formula~(2.5) with the
choice $B=\dfrac1{6L}$ which implies that the expression in
formula~(2.4) is less than $2e^{-\alpha y}$ with an appropriate
constant $\alpha>0$. In such a way we have solved problem~14.
\item{15.)} Let us choose such numbers $C_0>0$, $C>0$ and $D>0$
and threshold index $n_0$ for which relation~(9) holds if the real
number $x>0$ and integer $l>0$ satisfy the conditions $C_0\log n\le
x\le C^{-1}n$ and $2^{-l}\ge C xn^{-1}$, and $n\ge n_0$. First we
show the slightly weaker result by which the estimate of the {\it
Approximation Theorem}\/ holds for all numbers $x$ which satisfy the
relation $C_0\log n\le x\le C^{-1}n$ with these numbers~$C$ and~$C_0$
if $n\ge n_0$.
\item{} Let us choose that positive integer $l=l(x)$ for which
$2Cxn^{-1}>2^{-l}\ge C xn^{-1}$ with the constant $C>0$ considered
above. We show with the help of relations (18a) and (18b) proved in
problem~14 that
$$
\aligned
P\(\sup_{1\le k\le 2^l}\sup_{(k-1)2^{-l}\le t\frac x4\)&\le
e^{-\alpha x},\\
P\(\sup_{1\le k\le 2^l}\sup_{(k-1)2^{-l}\le t\frac x4\)&\le
e^{-\alpha x}
\endaligned \tag2.6
$$
with an appropriate constant $\alpha>0$ and the previously defined
integer $l=l(x)$ if $x\ge C_0\log n$ with an appropriate constant
$C_0>0$. To prove relation (2.6) let us observe that formulas
(18a) and (18b) remain valid if at their left-hand side the domain
$0\le t\le L\dfrac yn$ where supremum is taken is replaced by another
domain $u\le t\le u+L\dfrac yn$ such that $0\le u\le 1-\dfrac yn$.
Indeed, the probability of the event obtained after such a replacement
agrees with the original probability. We show with the help of this
modified version of formulas~(18a) and (18b) with the choice of
parameters $y=\dfrac x4$, $L=\dfrac 8C$ and $u=(k-1)2^{-l}$, $1\le
k\le 2^l$ that the probabilities at the left-hand side of the
expression~(2.6) are less than $2^{l+1}e^{-\alpha x}$. To show this
it is enough to check that the inner supremum in those expressions
were taken on intervals of length $2^{-l}\le 2\dfrac x{Cn}=L\dfrac
x{4n}$ and the outside supremum is taken over $2^l$ terms. Let us
finally observe that $2^{l+1}\le \dfrac{2n}{Cx}\le n\le e^{\alpha
x/2}$, if $x\ge C_0\log n$, i.e.\ if $n\le e^{x/C_0}$ with a
sufficiently large number $C_0$. This argument implies formula~(2.6)
(with parameter $\alpha/2>0$ instead of parameter $\alpha>0$.)
\item{} The above mentioned weakened form of the {\it Approximation
Theorem}\/ is a simple consequence of formulas~(9) and~(2.6).
Indeed, given a number $0\le t\le1$, let us consider the integer
$k=k(t)$, $1\le k\le 2^l$ for which $(k-1)2^{-l}\le tx\)\\
&\qquad\le P\(\sqrt n\sup_{0\le t\le 1}|B(t))|>\frac x2\)+
P\(\sqrt n\sup_{0\le t\le 1}|Z_n(t))|>\frac x2\) \\
&\qquad \le e^{-Cx^2/n}\le
e^{-\bar Cx}
\endaligned \tag2.7
$$
with appropriate constants $C>0$ and $\bar C>0$. Let us remark that the
condition $0\le\frac x2\le n$ appears in formulas (18a) and~(18b), hence
we need some special considerations in the proof.
The first term in the second line
of formula~(2.7) can be estimated similarly to the expression in
formula~(18a) for all numbers $x>C^{-1}n$ which expression yields an
estimate on the supremum of a Brownian bridge. (In the proof of this
estimate we applied the representation of a Brownian bridge by a
Wiener process, and the condition $x\le n$ was not needed there. Now we
wrote a sharp upper bound for the probability we wanted to estimate,
only the constant $C>0$ appearing there is not calculated explicitly.)
The Poisson approximation applied in the proof of formula~(18b)
does not yield a good estimate in the case $x\gg n$, but in the case
$\frac x2>n$ we do not need this approximation. In this case the
trivial identity
$$
P\(\sqrt n\supp_{0\le t\le 1}|Z_n(t))|>n\)=0
$$
is applicable. Hence formula~(2.7) holds, and the {\it Approximation
Theorem}\/ holds for all $x\ge C^{-1}n$.
\item{} Although the special investigation of the case $n\le n_0$ has
no great importance, we remark that the {\it Approximation Theory}\/
holds in this case, too. Too see this it is enough to observe that
since the parameter~$n$ is bounded, hence the second, and as a
consequence the first line of inequality~(2.7) is less than
$C_1e^{-C_2x}$ for all numbers $x\ge0$ with some appropriate
constants $C_1>0$ and~$C_2>0$.
\vfill\eject
\beginsection Appendix
{\bf Proof of the Lemma:}
\medskip\noindent
Let us define the following random variable (stopping rule) $\tau$
which tells us the smallest index $k$ for which an element of
the sequence of partial sums $S_k=\summ_{j=1}^k\xi_k$, $k=1,\dots,n$,
is larger than a number $x>0$:
$$
\tau=\tau(x,n)=\cases \min\{k\: S_k> x\} &\text{if }\supp_{1\le k\le
n}S_k> x\\
n &\text{if }\supp_{1\le k\le n}S_k\le x
\endcases \quad .
$$
As $P\(\supp_{1\le k\le n}S_k> x\)=P\(S_\tau> x\)$, it is natural
to prove the first inequality of the {\it Lemma}\/ by giving a good
estimate on the exponential moments $Ee^{sS_\tau}$ of the random
variable $S_\tau$.
It follows from standard results of the martingale theory that
for arbitrary real number $s\ge0$ $Ee^{sS_\tau}\le Ee^{sS_n}$.
To prove this it is useful to show that for all numbers $s\ge0$
the sequence $(e^{sS_k},\Cal F_k)$, $k=1,\dots,n$, where $\Cal
F_k=\sigma(\xi_1,\dots,\xi_k)$ is the $\sigma$-algebra generated
by the random variables $\xi_1,\dots,\xi_k$, is a supermartingale
i.e.\ $E\(e^{sS_{k+1}}|\Cal F_k\)\ge e^{sS_k}$ with probability~one.
It is not difficult to see this inequality by using the properties
of conditional expectations, the identity
$e^{sS_{k+1}}=e^{sS_k}e^{s\xi_{k+1}}$ and the independence
of the random variable $\xi_{k+1}$ of the $\sigma$-algebra~$\Cal F_k$.
This implies that $E\(e^{sS_{k+1}}|\Cal F_k\)=e^{sS_k}
Ee^{s\xi_{k+1}}\ge e^{sS_k}$, since $Ee^{s\xi_{k+1}}\ge
e^{Es\xi_{k+1}}\ge1$ by the Jensen inequality and the
condition $E\xi_{k+1}\ge0$.
A simple but fundamental result of the martingale theory states that
if the series $(e^{sS_k},\Cal F_k)$, $k=1,\dots,n$, is a
supermartingale and the stopping rule $\tau$ satisfies the inequality
$\tau\le n$ with probability one, then $Ee^{sS_\tau}\le
Ee^{sS_n}$. It is not difficult to prove the above inequality, but
since the argument of the proof is essentially different from the
method of this work we omit it. It may be worth mentioning that this
inequality has the following heuristic content: In an advantageous
game the further we play the greater our expected gain will be.
It follows from the (only partly proved) estimate on the
exponential moment that
$$
\align
P\(\supp_{1\le k\le n}S_k> x\)&=P\(S_\tau> x\)=P\(e^{sS_\tau}>e^{sx}\)
\le Ee^{sS_\tau}e^{-sx} \\
&\le E e^{sS_n}e^{-sx}=\exp\left\{-sx+\sum_{k=1}^n B_k(s)\right\},
\endalign
$$
and this is the first statement of the Lemma.
To prove the second statement of the lemma let us introduce for
all numbers $n=1,2,\dots$ the numbers $t_{k,n}=a+(b-a)k2^{-n}$,
$0\le k\le 2^n$ and the random variables
$\xi_{k,n}=X(t_{k,n})-X(t_{k-1,n})$, $1\le k\le 2^n$, Then for a fixed
number $n$ the random variables $\xi_{k,n}$, $1\le k\le 2^n$, are
independent, since the process $X(t)$ has independent increments
and $X(t_{k,n})-X(a)=\summ_{j=1}^k\xi_{j,n}$,
$1\le k\le n$. Furthermore, $E\xi_{k,n}\ge0$ for $1\le k\le n$,
and since the trajectories of the stochastic process $X(t)$
are continuous or cadlag (continuous from the right with left-hand
side limit) functions, hence for all numbers $x>0$
$$
\left\{\oo\:\supp_{a\le t\le b}\(X(t,\oo)-X(a,\oo)\)>x\right\}
=\bigcupp_{n=1}^\infty\left\{\oo\: \supp_{1\le k\le
2^n}\(X(t_{k,n},\oo)-X(a,\oo)\)>x\right\}.
$$
Beside this the sets in the union at the right-hand side of the last
relation constitute a series of sets monotone increasing by the
parameter~$n$. From this fact and the already proven part of the {\it
Lemma}
$$
\align
P\(\sup_{a\le t\le b} (X(t)-X(a))>x\)&=\lim_{n\to\infty}
P\(\supp_{1\le k\le 2^n}\(X(t_{k,n})-X(a)\) >x\) \\
&\le\lim_{n\to\infty} e^{-sx}\prod_{k=1}^{2^n}Ee^{s\xi_{k,n}}
=e^{-sx}Ee ^{s(X(b)-X(a))},
\endalign
$$
and this is the second statement of the {\it Lemma}.
\bye
**