A NOTE ON THE APPROXIMATION OF

THE UNIFORM EMPIRICAL PROCESS

Péter Major

Mathematical Institute of the Hungarian Academy of Sciences

Summary: D. Mason and W. van Zwet (1987) gave an approximation of the uniform empirical process by a Brownian bridge which is a refinement of a result of Komlós–Major– Tusnády (1975). Their result is an improvement only if the process is considered in a small interval. In this note we show that in such cases a much better Poissonian approximation is possible which seems to be better applicable in certain cases. We also prove a multidimensional version of this result, where a sequence of uniform empirical processes is simultaneously approximated by partial sums of independent Poisson processes.

1. Introduction. Let ε_{1}, ε_{2}, …, be a sequence of independent, on the interval [0, 1] uniformly distributed random variables, and define the empirical distribution function F_{n}(t), n = 1, 2, …, as F_{n}(t) = \frac{1}{n}#\{ε_{j}, j ≤ n, ε_{j} ≤ t\}, 0 ≤ t ≤ 1. In this paper we investigate the (uniform) empirical process \sqrt{n}(F_{n}(t) − t). Mason and Zwet (1987) proved the following

Theorem A. For all n ≥ 1 a Brownian bridge B_{n}(t), 0 ≤ t ≤ 1, and a sequence of independent and on the interval [0, 1] uniformly distributed random variables ε_{1}, ε_{2}, … can be constructed in such a way that the empirical distribution function F_{n}(t) defined with the help of the above ε-s satisfies the relation

(1.1)  P ( sup_{0≤s≤ \frac{d}{n}} |n(F_{n}(s) − s) − \sqrt{n}B_{n}(s)| > C log d + x) < Ke^{−λx}

with some universal positive constants C, K and λ for all 0 ≤ x < ∞, 1 ≤ d ≤ n.

This is a refinement of a former result of Komlós, Major and Tusnády (KMT) (1975), where the same estimate is proved in the special case d = n. Theorem A is a real improvement only for d < n^{ε}, where ε > 0 can be chosen arbitrarily small. For such numbers d the empirical distribution function can be much better approximated in the interval [0, d/n] by a Poisson process. In Theorem 1 formulated below we present such an approximation.

Let P_{n}(t), 0 ≤ t ≤ 1, denote a Poisson process with parameter n, i.e. let P_{n}(t) be a process with independent stationary increments, P_{n}(0) = 0, and let P_{n}(v) − P_{n}(u), 0 ≤ u < v ≤ 1, be Poisson distributed with parameter n(u − v).

Typeset by AMS-TEX

Theorem 1. For all n ≥ 1 a Poisson process P_{n}(t) with parameter n on the interval [0, 1] and a sequence of independent, on the interval [0, 1] uniformly distributed random variables ε_{1}, …, ε_{n} can be constructed simultaneously in such a way that the empirical distribution function defined with the help of these ε-s satisfies the relation

P ( sup_{0≤s<n^{−2/3}} |n(F_{n}(s) − s) − (P_{n}(s) − ns)| > C) < K exp (−\frac{1}{8} \sqrt{n} log n)

with some universal constants C > 0 and K > 0.

We shall also prove the following variant of Theorem 1.

Theorem 1′. Let t_{n} → 0 be such that also \sqrt{n}t_{n} → 0. For all n ≥ 1 a Poisson process P_{n}(t) with parameter n on the interval [0, 1] and a sequence of independent, on the interval [0, 1] uniformly distributed random variables ε_{1}, …, ε_{n} can be constructed simultaneously in such a way that the empirical distribution function defined with the help of these ε-s satisfies the relation

P ( sup_{0≤s<t_{n}} |n(F_{n}(s) − s) − (P_{n}(s) − ns)| = 0) → 1 .

In Theorems 1 and 1′ we have approximated the empirical process by a Poisson process in a small neighbourhood of zero. This approximation can be combined by a Brownian bridge approximation of the empirical process in the remaining domain with the help of Theorem 3 in the KMT (1975) paper. We formulate this result in the case of Theorem 1′ in the following

Proposition. Beside the processes P_{n}(t) and F_{n}(t) in Theorem 1′ a process B_{n}(s), t_{n} ≤ s ≤ 1, can be constructed which is the restriction of a Brownian bridge to the interval [t_{n}, 1] in such a way that

(1.2)  P ( sup_{t_{n}≤s≤1} |\sqrt{n}B_{n}(s) − n(F_{n}(s) − s)| > C log n + x) < Ke^{−λx} ,

where C > 0, K > 0 and λ > 0 are appropriate constants, and the processes B_{n}(s), t_{n} ≤ s ≤ 1 and P_{n}(t), 0 ≤ t ≤ t_{n} are conditionally independent with respect to the events nF_{n}(t_{n}) = k for all k = 0, 1, . . ..

Theorems 1 and 1′ can be useful if we want to investigate the limit distribution of a sequence of random variables which is obtained when a sequence of functionals F_{n} are applied to the empirical processes, i.e. when the functional may also depend on n. Such a problem is investigated e.g. in the paper of M. Csörgő et al. (1986). If the functional F_{n} depends only on the values of the empirical process in the interval [0, t_{n}] then by Theorem 1′ the uniform empirical process can be replaced by a standardized Poisson process, and the limit distribution of our sequences will be the same after this replacement. A Gaussian approximation is not always allowed, because the Gaussian approximation of the empirical process is not so good as the Poissonian one. If the functional F_{n} depends on the values of the empirical process on the whole interval [0, 1], but this dependence is much stronger on the interval [0, t_{n}] then Theorem 1′ can be applied together with the Proposition. Theorem 1 can be useful if we want to get a better information about the error committed by the Poissonian approximation.

Another problem where the Gaussian approximation is not always applicable, and a Poissonian approximation may be useful is the investigation of the law of iterated logarithm for the empirical process in small intervals. This problem is studied in Kiefer’s (1972) paper. If one tries to study this problem in the usual way then one has to apply the Borel–Cantelli lemma several times, and the main technical problem is to check whether certain sums of probabilities are convergent or divergent. If one substitutes these probabilities by those suggested by the Gaussian approximation one gets in certain cases wrong result, because the error committed by this substitution is too large. On the other hand Theorem 1 would allow us to make a Poissonian approximation also in such cases. Nevertheless it is more appropriate to have a result which automatically guarantees that the empirical process can be replaced by a Poisson process in such problems. This is done by Theorem 2 formulated below, or more precisely by its Part b).

Theorem 2. Part a) For all n = 1, 2, …, and 1/2 ≥ α ≥ 0 a sequence ε_{1}, ε_{2}, …, ε_{n} of independent and on the interval [0, 1] uniformly distributed random variables can be constructed together with a sequence P_{1}(t), P_{2}(t), …, P_{n}(t), of independent Poisson processes with parameter 1 on the interval [0, 1] in such a way that

(1.3) P (sup_{k≤n} sup_{0≤t<n^{−(1/2+α)}} |k(F_{k}(t) − t) − ∑_{j=1}^{k}(P_{j}(t) − t)| > m) ≤ C(m)n^{−2(m+1)α}

for all m = 0, 1, 2, ..., where the constants C(m) depends only on m.

Part b) For any δ > 0 an infinite sequence ε_{1}, ε_{2}, … of independent random variables with uniform distribution on the interval [0, 1] and an infinite sequence of independent Poisson processes P_{1}(t), P_{2}(t), … with parameter 1 on the interval [0, 1] can be constructed in such a way that

(1.4)  P(sup_{n} sup_{0<t<n^{−1/2−δ}} |n(F_{n}(t) − t) − ∑_{j=1}^{n}(P_{j}(t) − t)| < ∞) = 1 .

Part b) of Theorem 2 implies in particular that the restrictions of the empirical processes to the intervals [0, t_{n}], t_{n} → 0, satisfy the same laws of iterated logarithm as the averages \frac{1}{n} ∑_{i=1}^{n} P_{i}(t) of independent Poisson processes restricted to the same intervals [0, t_{n}], if n^{1/2+δ}t_{n} → 0 with some δ > 0. Hence the problems investigated by Kiefer can be reformulated to equivalent problems about the sums of independent Poisson processes. The condition t_{n} < n^{−1/2−δ} could be slightly weakened, but it is not essential, since it is satisfied in the most interesting and important case, namely when t_{n} = \frac{L(n)}{n}, and L(n) is bounded, or slowly tends to infinity.

2. The proof of Theorem 1, Theorem 1′ and the Proposition. Let F (x) = F_{λ}(x) denote the (right continuous) Poisson distribution function with parameter λ, and G(x) = G_{n,p}(x) the (right continuous) binomial distribution function with parameters n and p. The following Lemma 1 plays an important role in the proof of Theorem 1. In Lemma 1 two random variables are constructed with distributions F and G which are close to each other if the parameters λ, n and p are appropriately chosen. We apply the quantile transformation, i.e. we make the following construction. Let γ be a uniformly distributed random variable on [0, 1], and put

(2.1)  ξ = k  if F (k) ≤ γ < F (k + 1), k = 0, 1, …

(2.1′)  η = k  if G(k) ≤ γ < G(k + 1), k = 0, 1, ….

Clearly ξ has a distribution F, and η a distribution G. We prove the following

Lemma 1. Choose λ = np and p = n^{−2/3} for the parameters of the distribution functions F and G. There is a constant C > 0 and a threshold n_{0} in such a way that for n > n_{0} the random variables ξ and η defined by (2.1) and (2.1′) satisfy the relation

|ξ − η| < C if ξ ≤ \sqrt{n}.

Proof of Lemma 1. It is enough to show that under the conditions of Lemma 1 there is some C > 0 such that

(2.2)  G(x − C) ≤ F (x) ≤ G(x + C) if x ≤ \sqrt{n}.

Let f(k) and g(k), k = 0, 1, 2, … denote the density functions of F and G. We shall prove (2.2) with the help of the following relations: There are some integers C > 0 and n > n_{0} such that if n > n_{0} then

(2.3)  1 − G(\sqrt{n} − C) > 1 − F (\sqrt{n}) > 1 − G(\sqrt{n} + C)

(2.3′)  g(k − C) > f(k) > g(k + C)  if np + C < k < \sqrt{n}

(2.3′′)  g(k − C) < f(k) < g(k + C)  if 0 ≤ k < np − C.

(We define g(k) = 0 for k < 0 in (2.3′′).) Relations Relations (2.3)–(2.3′′) imply (2.2) (with constant 2C instead of C). Indeed, by summing up (2.3) and (2.3′) for j = k ,k+1, …, \sqrt{n}−1 we get that 1−G(k−C) > 1−F (k) > 1−G(k+C) for np+C < k < \sqrt{n}, and relation (2.3′′) similarly implies that G(k − C) < F (k) < G(k + C) for 0 ≤ k ≤ np − C. Finally, for |k − np| ≤ C these relations imply that G(k − 2C) < F (k − C) < F (k) < F (k + C) < G(k + 2C).

To prove (2.3) and (2.3′) we estimate the ratios \frac{g(k)}{f(k)} and \frac{f(k+1)}{f(k)}. Since λ = np,

\frac{g(k)}{f(k)} = \frac{n(n − 1) ⋯ (n − k + 1)}{n^{k}(1 − p)^{k}}(1 − p)^{n}e^{np}

= exp\{n(p + log(1 − p)) − k log(1 − p) + ∑_{j=0}^{k−1} log (1 − \frac{j}{n}) \},

and

(2.4)  \frac{g(k)}{f(k)} = exp \{O(np^{2} + kp + \frac{k^{2}}{n} )\} for k ≤ \sqrt{n}.

Since p = n^{−2/3} the last relation implies that

(2.5)  α^{−1} < \frac{g(k)}{f(k)} < α for k < \sqrt{n}

with some 1 < α < ∞, and

(2.5′)  |\frac{g(k)}{f(k)} − 1| < αn^{−1/3}  if |k − np| < \frac{np}{2}.

Since

(2.6)  \frac{f(k + 1)}{f(k)} = \frac{λ}{k + 1} ,

the relations\frac{f(k+j)}{f(k)} > (3/2)^{j} and \frac{f(k−j)}{f(k)} < (4/5)^{j} hold if k > \frac{3}{2}np and 0 < j < np/4. These inequalities together with (2.4) imply (2.3′) for \frac{3}{2}np < k < \sqrt{n} with a sufficiently large C which is independent of n. Relation (2.3′′) for k < np/2 can be proved similarly. Since λ = n^{1/3}, relation (2.6) also implies that \frac{f(k−j)}{f(k)} < (1− \frac{1}{2}n^{−1/3})^{j} < 1− \frac{j}{4}n^{−1/3} and

\frac{f(k+j)}{f(k)} > (1+n^{−1/3})^{j} > 1+jn^{−1/3} if k > np+C and j < C with a sufficiently large C > 0 independent of n. This relation together with (2.5′) imply (2.3′) for np + C < k < \frac{3}{2}np. A similar estimation of \frac{f(k±j)}{f(k)} for k < np − C yields (2.3′′) in the remaining domain

np/2 < k < np − C. To prove (2.3) it is enough to check that \frac{f(k)}{1−F (k)} and \frac{g(k)}{1−G(k)} are bounded away from zero (and naturally also from infinity) for k > \sqrt{n}−C, and then the estimates given on \frac{f(k±j)}{f(k)} and \frac{g(k)}{f(k)} imply the required inequality. Lemma 1 is proved.

Proof of Theorem 1. Let us construct a pair of random variables (ξ, η) with distributions F and G satisfying Lemma 1. Let ε′_{1}, ε′_{2}, … be a sequence of independent uniformly distributed random variables on [0, n^{−2/3}], ε′′_{1}, ε′′_{2}, … a sequence of independent uniformly distributed random variables on [n^{−2/3}, 1] such that the pair (ξ, η) and the sequences ε′_{1}, ε′_{2}, …, ε′′_{1}, ε′′_{2}, … are independent of each other. Put nF_{n}(s) = #{ε′_{j}, ε′_{j} < s, j < η}, P_{n}(s) = #{ε′_{j}, ε′_{j} < s, j < ξ} for s < n^{−2/3}, and define n(F_{n}(s) − F_{n}(n^{−2/3})) = #{ε′′_{j}, ε′′_{j} < s, j ≤ n − η} if n^{−2/3} < s < n − η, and P_{n}(s) − P_{n}(n^{−2/3}) as a Poisson process with parameter n on the interval [n^{−2/3}, 1] independent of the above defined process P_{n}(s), 0 < s < n^{−2/3}. Then F_{n}(s) can be considered as an empirical distribution function (corresponding to the sample obtained from the random permutations of ε′_{1}, …, ε′_{η}, ε′′_{1}, …, ε′′_{n−η}), since it has the prescribed conditional distribution under the condition η = k. Similarly, P_{n}(s), 0 < s ≤ 1, is a Poisson process with parameter n. On the other hand |nF_{n}(s) − P_{n}(s)| ≤ |ξ − η| for 0 < s < n^{−2/3}. Hence by Lemma 1

P ( sup_{0<s<n^{−2/3}} |n(F_{n}(s) − s) − (P_{n}(s) − ns)| > C) < P(|ξ − η| > C) < P(ξ > \sqrt{n}) .

Since

P(ξ > \sqrt{n}) ≤ const.P(ξ = \sqrt{n})
= const. exp \{−n^{1/3} + \frac{1}{3} \sqrt{n} log n − log(\sqrt{n}!)\} ≤ Kexp \{−\frac{1}{8} \sqrt{n} log n\}

the above estimates imply Theorem 1.

Proof of Theorem 1′. We may assume without violating the generality that nt_{n} → ∞. The proof of Theorem 1′ is very similar to that of Theorem 1. The main difference is that now we need for each n, instead of the construction of Lemma 1, a pair of random variables (ξ_{n}, η_{n}) with distributions F_{λ}(x) and G_{n,p}(x), λ = np_{n} and p = p_{n} such that

(2.7)  P(ξ_{n} = η_{n}) → 1  as n → ∞ .

Then we can apply the same costruction as in the proof of Theorem 1, only now we have to work with the above pair (ξ_{n}, η_{n}), and the intervals [0, n^{−2/3}] and [n^{−2/3}, 1] must be replaced by the intervals [0, t_{n}] and [t_{n}, 1]. So it remains to prove relation (2.7).

We claim that

(2.8)  ∑_{k=0}^{∞} |P(ξ_{n} = k) − P(η_{n} = k)| → 0

First we show that relation (2.7) can be satisfied with an appropriate construction because of (2.8). Indeed, define the pair (ξ_{n}, η_{n}) by the following formulas:

P(ξ_{n} = η_{n} = k) = min{P(ξ_{n} = k), P(η_{n} = k)}

and

P(ξ_{n} = k, η_{n} = j)
= B_{n}^{−1}(P(ξ_{n} = k) − min{P(ξ_{n} = k), P(η_{n} = k)})(P(η_{n} = j)
− min{P(ξ_{n} = j), P(η_{n} = j)}) if j ≠ k ,

where B_{n} = 1 − ∑_{k=0}^{∞} min\{P(ξ_{n} = k), P(η_{n} = k)\}. (If B_{n} = 0 then we have \frac{0}{0} in the last formula which we define as 0.) Then the random variables ξ_{n} and η_{n} have the prescribed distribution, since

P(ξ_{n} = k, η_{n} ≠ k) = P(ξ_{n} = k) − min{P(ξ_{n} = k), P(η_{n} = k)} ,

and a similar relation holds also for η_{n}. It follows from (2.8) that B_{n} → 0, hence (2.7) also holds.

To prove (2.8) observe first that similarly to (2.4) we have

(2.9) \frac{P(ξ_{n} = k)}{P(η_{n} = k)} = exp \{O (np_{n}^{2} + kp_{n} + \frac{k^{2}}{n} )\} = exp\{O(np_{n}^{2})\}  if k < 2np_{n} .

Hence

∑_{k=0}^{2np_{n}} |P(ξ_{n} = k) − P(η_{n} = k)| ≤ {exp{O(np_{n}^{2})} − 1} ∑ P(η_{n} = k) = O(np_{n}^{2}) .

On the other hand

∑_{k=2np_{n}}^{∞} |P(ξ_{n} = k) − P(η_{n} = k)| ≤ P(ξ_{n} ≥ 2np_{n}) + P(η_{n} ≥ 2np_{n}) → 0 as n → ∞ .

These relations imply (2.8). Theorem 1′ is proved.

Proof of the Proposition. The conditional distribution of the process n[(F_{n}(s) − s) − (F_{n}(t_{n})−t_{n})], t_{n} ≤ s ≤ 1 under the condition nF_{n}(t_{n}) = k agrees with the distribution of an empirical distribution function multiplied by n−k from a sample of n−k elements with uniform distribution on the interval [t_{n}, 1]. Hence we can construct, with the help of Theorem 3 of KMT (1975), a Brownian bridge B̄_{n}(u), 0 ≤ u ≤ 1, on the conditional probability space P(· |nF_{n}(t_{n}) = k) such that

(2.10)  \begin{matrix}P( sup_{t_{n}≤s≤1}|n[(F_{n}(s)− & F_{n}(t_{n})) − (s − t_{n})] − \sqrt{n − k}B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} )| \\ > C log n + x| nF_{n}(t_{n}) = k) ≤ Ke^{−λx} . \end{matrix}

Since the distribution of B̄_{n}(·) does not depend on k it is a Brownian bridge also with respect to the original unconditional probability.

By Lemma 2 of KMT (1975) a standard Gaussian random variable ξ_{n} can be constructed with the help of the quantile transformation in such a way that

(2.11)  P (|\sqrt{nt_{n}(1 − t_{n})}ξ_{n} − n(F_{n}(t_{n}) − t_{n})| > C) ≤ Ke^{−λx} .

Since F_{n}(t_{n}) is independent of B̄_{n}(·) the random variable ξ_{n}, which is obtained as a transformation of the random variable F_{n}(t_{n}) − t_{n} with some randomization, is also independent of it. Define

B_{n}(s) = \sqrt{1 − t_{n}}B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} ) + \frac{1 − s}{1 − t_{n}} \sqrt{t_{n}(1 − t_{n})}ξ_{n}, t_{n} ≤ s ≤ 1.

We claim that the above defined process B_{n}(s) satisfies the Proposition. It is a Gaussian process, and simple calculation shows (by using the independence of B̄_{n}(·) and ξ) that it has the covariance function s(1 − s′) for t_{n} ≤ s ≤ s′ ≤ 1. The processes B_{n}(·) and P_{n}(·) are conditionally independent with respect to the condition F_{n}(t_{n}) = k. We have to prove relation (1.2).

Remark first that (2.10) also implies that

(2.12) \begin{matrix}P( sup_{t_{n}≤s≤1} |n[(F_{n}(s) − F_{n}(t_{n})) − (s − t_{n})] − \sqrt{n(1 − F_{n}(t_{n}))}B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} )| \\ > C log n + x) ≤ Ke^{−λx} . \end{matrix}

Moreover, we claim that (2.12′)

\begin{matrix}P ( sup_{t_{n}≤s≤1} |n[(F_{n}(s) − F_{n}(t_{n})) − (s − t_{n})] − \sqrt{n(1 − t_{n})}B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} )| > C log n + x) \\ ≤ Ke^{−λx} , \end{matrix}

(with possibly different constants C, K and λ.) To prove (2.12′) we have to show that a negligible error is committed if the coefficient of B̄(·) in (2.12) \sqrt{n(1 − F_{n}(t_{n}))} is replaced by \sqrt{n(1 − t_{n})}. This follows from the following estimate:

P ( sup_{t_{n}≤s≤1}|(\sqrt{n(1 − t_{n})} − \sqrt{n(1 − F_{n}(t_{n}))} ) B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} ) |> x)

≤ P (|\sqrt{n(1 − t_{n})} − \sqrt{n(1 − F_{n}(t_{n}))}| > \sqrt{x}) + P ( sup_{0≤s≤1} |B̄_{n}(s)| > \sqrt{x})

≤ P (\sqrt{n}|F_{n}(t_{n}) − t_{n}| > \frac{1}{2} \sqrt{x}) + K exp (−\frac{x}{2}) ≤ Ke^{−λx} .

Now we can write for t_{n} ≤ s ≤ 1

\sqrt{n}B_{n}(s) − n(F_{n}(s) − s) = \frac{1 − s}{1 − t_{n}} \{\sqrt{nt_{n}(1 − t_{n})}ξ_{n} − n(F_{n}(t_{n}) − t_{n})\}

+ \{\sqrt{n(1 − t_{n})}B̄_{n} (\frac{s − t_{n}}{1 − t_{n}} ) − n[F_{n}(s) − F_{n}(t_{n}) − (s − t_{n})]\}

= \frac{1 − s}{1 − t_{0}} I_{1}(t_{n}) + I_{2}(s, t_{n}) .

Since the term I_{1}(t_{n}) is bounded in (2.11) and the term I_{2}(s, t_{n}) in (2.12′) the last identity implies (1.2). The Proposition is proved.

3. The proof of Theorem 2. First we formulate a lemma which is proved similarly to Theorem 1.

Lemma 2. Given some positive integer n and β > 0 let ξ_{1}, …, ξ_{n} be independent Poisson distributed random variables with parameters n^{−β} and η_{1}, …, η_{n} independent random variables such that P(η_{j} = 1) = 1 − P(η_{j} = 0) = n^{−β}, j = 1, …, n. A sequence ε_{1}, …, ε_{n} of independent, uniformly distributed random variables on [0, 1] and a sequence P_{1}(t), …, P_{n}(t), 0 < t < 1, of independent Poisson processes with parameter 1 can be constructed in such a way that

(3.1)  sup_{1≤k≤n} sup_{0≤s≤n^{−β}} |k(F_{k}(s) − s) − ∑_{j=1}^{k}(P_{j}(s) − s)| = sup_{1≤k≤n}|∑_{j=1}^{k}(ξ_{j} − η_{j})| ,

where the functions F_{k}(·) are the empirical distribution functions defined with the help of the above ε-s.

Lemma 2 enables us to reduce Part a) of Theorem 2 to a simpler problem. Namely, if we have a sequence ε_{1}, …, ε_{n} of independent uniformly distributed random variables on [0, 1] and a sequence P_{1}(t), …, P_{n}(t), 0 ≤ t ≤ 1 of independent Poisson processes with parameter 1 define ξ_{j} = P_{j}(n^{−(1/2+α)}) and η_{j} = jF_{j}(n^{−(1/2+α)}) − (j − 1)F_{j−1}(n^{−(1/2+α)}), j = 1, …, n, where F_{j}, j = 1, …, n, are the empirical distribution functions defined with the help of the sample ε_{1}, …, ε_{j}. Then Lemma 2 implies that a new sequence of independent uniformly distributed random variables on [0, 1] ε̄_{j}, j = 1, …, n and a new sequence of independent Poisson processes with parameter 1 P̄_{j}(t), j = 1, …, n, can be constructed in such a way that

sup_{1≤k≤n} sup_{0<s<n^{−(1/2+α)}}|k(F̄_{k}(s) − s) − ∑_{j=1}^{k}(P̄_{j}(s) − s)|

= sup_{1≤k≤n}|k(F_{k}(n^{−(1/2+α)}) − n^{−(1/2+α)}) − ∑_{j=1}^{k}(P_{j}(n^{−(1/2+α)}) − n^{−(1/2+α)})| .

This relation enables us to drop sup_{0<t<n^{−(1/2+α)}} from (1.3) and to consider only the argument t = n^{−(1/2+α)} instead.

Proof of Lemma 2. Let ε′_{1}, ε′_{2}, …, be a sequence of independent uniformly distributed random variables on [0, n^{−β}] which is independent of the random variables ξ-s and ηs, put S_{k} = ∑_{j=1}^{k} ξ_{j}, and T_{k} = ∑_{j=1}^{k} η_{j}, k = 1, …, n. If η_{k} = 1 define ε_{k} = ε′_{l} with l = T_{k}. Define the Poisson process P_{k}(t) in the interval [0, n^{−β}] in the following way: It has jumps in the points ε′_{j}, …, ε′_{j+p} with j = S_{k−1} + 1, j + p = S_{k}. (If S_{k−1} + 1 > S_{k} then it has no jumps in this interval.) Define the Poisson processes P_{k}(t), 0 < t < 1, in such a way that on the interval [0, n^{−β}] they agree with the already defined Poisson processes, and the processes P_{k}(t)−P_{k}(n^{−β}), n^{−β} < t < 1, k = 1, 2, … are independent of the processes P_{k}(t), 0 < t < n^{−β}, and of each other. Otherwise they are arbitrarily defined. Finally, let ε′′_{1}, ε′′_{2}, … be a sequence of independent uniformly distributed random variables on the interval [n^{−β}, 1] which is independent both of the sequence ε′_{1}, ε′_{2}, … and the η-s, and define ε_{k} = ε′′_{k} if η_{k} = 0. Then the sequences ε_{1}, …, ε_{n} and P_{1}(t), …, P_{n}(t) have the prescribed distributions. On the other hand relation (3.1) holds, since for all 1 ≤ k ≤ n

sup_{0≤s<n^{−β}} |k(F_{k}(s) − s) − ∑_{j=1}^{k}(P_{j}(s) − s)| = |T_{k} − S_{k}| .

Proof of Theorem 2. Part a.) By Lemma 2 it is enough to construct a sequence of independent Poisson distributed random variables ξ_{1}, …, ξ_{n} with parameter n^{−(1/2+α)} and a sequence of independent random variables η_{1}, …, η_{n}, P(η_{j} = 1) = 1 − P(η_{j} = 0) = n^{−(1/2+α)} in such a way that

(3.2)  P( sup_{1≤k≤n}|∑_{j=1}^{k}(ξ_{j} − η_{j})| > m) ≤ C(m)n^{−2(m+1)α}

for all m = 0, 1, . . .. Let us consider two independent Poisson processes P_{1}(t) and P_{2}(t) with parameter 1, and define ξ_{j} = P_{1}(jn^{−(1/2+α)})−P_{1}((j−1)n^{−(1/2+α)}), j = 1, 2, …, n. To define η_{j} let us first introduce the random variables ξ′_{j} = P_{2}(js) − P_{2}((j − 1)s), j = 1, …, n, where e^{−s} = (1−n^{−(1/2+α)}) exp(n^{−(1/2+α)}). Let η_{j} = 1 if ξ_{j} +ξ′_{j} ≥ 1, and zero otherwise. Then both sequences ξ_{1}, …, ξ_{n} and η_{1}, …, η_{n} consist of independent random variables with the right distribution. (Observe that P(η_{j} = 0) = P(ξ_{j} = 0, ξ′_{j} = 0) = exp(−n^{−(1/2+α)}−s) = 1−n^{−(1/2+α)}.) It remains to show that the above defined ξ_{j}-s and η_{j}-s satisfy (3.2). Observe that ∑_{j=1}^{k}(η_{j} −ξ_{j}) ≤ ∑_{j=1}^{k} ξ′_{j}, and ∑_{j=1}^{k}(ξ_{j} −η_{j}) ≤ ∑_{j=1}^{k} ξ̄_{j} with ξ̄_{j} = ξ_{j} − 1 if ξ_{j} > 0, and ξ̄_{j} = 0 if ξ_{j} = 0. Hence

(3.3) P ( sup_{1≤k≤n} ∑_{j=1}^{k}(η_{j} − ξ_{j}) > m) ≤ P (∑_{j=1}^{n} ξ′_{j} ≥ m + 1) ≤ C(m)n^{−2(m+1)α},

(here we use that ∑_{j=1}^{n} ξ′_{j} is a Poisson distributed random variable with parameter ns ≤ n^{−2α}) and

P ( sup_{1≤k≤n} ∑_{j=1}^{k}(ξ_{j} − η_{j}) > m) ≤ P (∑_{j=1}^{n} ξ̄_{j} ≥ m + 1) (3.4)

≤ exp(−2α(m + 1) log n)E exp(2α log n ∑_{j=1}^{n} ξ̄_{j})
= (E exp(2αξ̄_{1} log n))^{n}n^{−2(m+1)α}.

We claim that E exp(2αξ̄_{1} log n) ≤ 1 + \frac{C}{n} with some C > 0 independent of n. This inequality together with (3.4) and (3.3) imply (3.2) and hence also Part a) of Theorem 2. We have

E exp(2αξ̄_{1} log n) ≤ 1 + ∑_{j=1}^{∞} \frac{exp(−n^{−(1/2+α)} + 2jα log n)}{(j + 1)!}n^{−(j+1)(α+1/2)}

≤ 1 + ∑_{j=1}^{∞} \frac{1}{(j + 1)!}n^{(j−1)(α−1/2)−1} ≤ 1 + \frac{C}{n}

for 0 ≤ α ≤ 1/2.

Proof of Part b.) Let us fix some 1/2 > δ > 0, and apply Part a) with α = δ and 2^{n}, n = 0, 1, . . .. Because of formula (1.3) in the special case m = 0 we can construct a sequence of independent Poisson processes P_{1}^{(n)}(t), …, P_{2^{n}}^{(n)}(t) with parameter 1 and a sequence of independent uniformly distributed random variables on [0, 1] ε_{1}^{(n)}, …, ε_{2^{n}}^{(n)} in such a way that (3.5)

P(∑_{j=1}^{k} P_{j}^{(n)}(t) = kF_{k}^{(n)}(t) for 0 ≤ t < 2^{−(1/2+δ)n} and all k = 1, …, 2^{n}) ≤ C2^{−2nδ}.

(The upper index in F_{k}^{(n)} denotes that this empirical distribution function is constructed with the help of the sample ε_{1}^{(n)}, …, ε_{2^{n}}^{(n)}.) We may assume that the above defined sequences ε_{j}^{(n)} and P_{j}^{(n)} are independent for different n. Define P_{j}(t) = P_{j+1−2^{n}}^{(n)}(t) and ε_{j} = ε_{j+1−2^{n}}^{(n)} for 2^{n} ≤ j < 2^{n+1}, n = 0, 1, 2, . . .. Then relation (3.5) implies that the events A_{n}

A_{n} = { ∑_{j=2^{n}}^{k} P_{j}(t) = kF_{k}(t)−(2^{n} − 1)F_{2^{n}−1}(t)

for all 0 ≤ t ≤ 2^{−n(1/2+δ)} and 2^{n} ≤ k < 2^{n+1}}

satisfy the relation

∑_{n=1}^{∞} P(A_{n}) < ∞.

Hence by the Borel–Cantelli lemma there is a random threshold n(ω) such that for n > n(ω)

∑_{j=2^{n}}^{k} P_{j}(t) − t = k(F_{k}(t) − t) − (2^{n} − 1)[F_{2^{n}−1}(t) − t]
for all 2^{n} ≤ k < 2^{n+1} and t < k^{(−1/2+δ)}

with probability 1. The last relation implies Part b) of Theorem 2.

References: Kiefer, J. (1972). Iterated logarithm analogues for sample quantiles when p_{n} ↓ 0. Proc. 6.th Berkeley Sympos. Math. Statist. Probab. Univ. of California Press 1, 227–244 Komlós, J., Major, P., Tusnády, G. (1975). An approximation of partial sums of independent r.v.’s and the sample d.f. I. Z. Wahr. verw. Gebiete 34 33–58 Csörgő, M., Csörgő, S., Horváth, L., Mason, D.M. (1986). Normal and stable convergence of integral functions of the empirical distribution functions. Ann. Probab. 14 86–118 Mason, D.M., van Zwet, W. (1987). A refinement of the KMT inequality for the uniform empirical process. Ann. Probab. 15 871–884