\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 tx\)\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