A universal result in almost sure central limit theory

István Berkes^{∗}, Endre Csáki

A. Rényi Institute of Mathematics, Hungarian Academy of Sciences P.O.B. 127, H–1364 Budapest, Hungary

Abstract

The discovery of the almost sure central limit theorem (Brosamler, 1988; Schatte, 1988) revealed a new phenomenon in classical central limit theory and has led to an extensive literature in the past decade. In particular, a.s. central limit theorems and various related ‘logarithmic’ limit theorems have been obtained for several classes of independent and dependent random variables. In this paper we extend this theory and show that not only the central limit theorem, but every weak limit theorem for independent random variables, subject to minor technical conditions, has an analogous almost sure version. For many classical limit theorems this involves logarithmic averaging, as in the case of the CLT, but we need radically different averaging processes for ‘more sensitive’ limit theorems. Several examples of such a.s. limit theorems are discussed.

MSC: Primary 60F15; Secondary 60F05.

Keywords: Almost sure central limit theorem; logarithmic averages; summation methods.

∗ Corresponding author. E-mail addresses: berkes@renyi.hu (I. Berkes), csaki@renyi.hu (E. Csáki).

1. Introduction

Starting with Brosamler (1988) and Schatte (1988), in the past decade several authors investigated the almost sure central limit theorem and related ‘logarithmic’ limit theorems for partial sums of independent random variables. The simplest form of the a.s. central limit theorem (Brosamler, 1988; Schatte, 1988; Lacey and Philipp, 1990; Fisher, 1989) states that if X_{1}, X_{2}, … are i.i.d. random variables with mean 0, variance 1 and partial sums S_{n} then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{S_{k}}{\sqrt{k}} < x\} = Φ(x)  a.s. for any x  (1.1)

where I denotes indicator function. Relation (1.1) is a weighted strong law for the events A_{k} = \{S_{k}/\sqrt{k} < x\}; note that the ordinary strong law

lim_{N→∞} \frac{1}{N} ∑_{k≤N} I \{\frac{S_{k}}{\sqrt{k}} < x\} = Φ(x) a.s. for any x

fails even for x = 0 by the arc sine law. This means that the relative frequencies of the events A_{k} = \{S_{k}/\sqrt{k} < x\} fluctuate without a limit, but an a.s. limit exists if we replace the counting measure with the logarithmic measure μ(A) = ∑_{k∈A} 1/k, A ⊂ N. This remarkable property of the logarithmic measure has been studied intensively in recent years and many extensions and variants of (1.1) have been obtained. Several papers investigated the general ASCLT

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{S_{k} − a_{k}}{b_{k}} < x\} = Φ(x)  a.s. for any x  (1.2)

for independent r.v.’s; see e.g. Atlagh (1993), Atlagh and Weber (1992, 1996), Berkes (1995), Berkes and Dehling (1993, 1994), Ibragimov (1996), Ibragimov and Lifshits (1998, 1999), Lifshits (2000a, 2000b), Móri (1993), Peligrad and Révész (1991), Rodzik and Rychlik (1994, 1996) and the references in the survey paper Berkes (1998). As it turned out, under mild moment conditions relation (1.2) follows from the the ordinary (weak) CLT

(S_{n} − a_{n})/b_{n} ⟶^{D} N(0, 1)  (1.3)

but in general the validity of (1.2) is a delicate question of a totally different character as (1.3). (See e.g. the counterexample in Lifshits, 2000a.) Starting with Weigl (1989) and Csörgő and Horváth (1992), several papers dealt with the fine asymptotic properties of the sum

∑_{k≤N} \frac{1}{k} (I \{\frac{S_{k} − a_{k}}{b_{k}} < x\} − Φ(x)) .

See Section 4 of Berkes (1998) for detailed references. For further results in the field (higher dimensions, local theorems, large deviations, weakly dependent sequences, etc.) we also refer to Berkes (1998).

All the above results are related to the central limit theorem, but there also exist a few results of the type (1.2) in connection with other classical weak limit theorems. Marcus and Rosen (1995), Csáki and Földes (1995) and Horváth and Khoshnevisan (1995) obtained analogues of (1.2) for local times and Fahrner and Stadtmüller (1998) and Cheng et al. (1998) proved a similar result for extreme order statistics. In fact, they showed that if X_{1}, X_{2}, … are i.i.d.r.v.’s with M_{n} = max_{k≤n} X_{k} and for some numerical sequences (a_{k}), (b_{k}) we have

(M_{k} − a_{k})/b_{k} ⟶^{D} G

for a nondegenerate distribution G, then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{M_{k} − a_{k}}{b_{k}} < x\} = G(x)  a.s. for any x.  (1.4)

Relation (1.4) is the exact analogue of the a.s. central limit theorem (1.2) for extremal statistics and raises the question which other weak limit theorems for independent r.v.’s have an almost sure ‘logarithmic’ version. The purpose of this paper is to prove the surprising fact that not only the CLT and limit theorems for local times and extrema, but every weak limit theorem for independent r.v.’s, subject to minor technical conditions, has an almost sure version. To formulate our result, we need a few preparatory remarks about the structure of weak limit theorems.

The generic form of a weak limit theorem for a sequence (X_{n}) of r.v.’s is

f_{k}(X_{1}, X_{2}, …) ⟶^{D} G  (1.5)

where f_{k} : R^{∞} → R are measurable functions and G is a distribution function. A few examples corresponding to well known limit theorems are:

(a)  f_{k}(x_{1}, x_{2}, …) = (x_{1} + ⋯ + x_{k})/\sqrt{k}  (CLT)
(b)  f_{k}(x_{1}, x_{2}, …) = a_{k}(max_{i≤k} x_{i} − b_{k})  (Limit theorems for extrema)

(c) f_{k}(x_{1}, x_{2}, …) = \sqrt{k} sup_{t} |k^{−1} ∑_{i≤k} I(x_{i} ≤ t) − F (t)| (empirical d.f.’s)

(d) f_{k}(x_{1}, x_{2}, …) = a_{k} (∑_{i≤k} I{x_{1} + ⋯ + x_{i} = 0} − b_{k}) (Local times)

(e) f_{k}(x_{1}, x_{2}, …) = a_{k} ( ∑_{1≤i_{1}<···i_{m}≤k} h(x_{i_{1}}, …, x_{i_{m}}) − b_{k}) (U-statistics).

In most cases of interest, the functions f_{k} depend only on finitely many of the x_{i}’s and in this paper we will consider only limit theorems of this kind. In this case, (1.5) reduces to the form

f_{k}(X_{1}, X_{2}, …, X_{n_{k}}) ⟶^{D} G

for some sequence (n_{k}) of positive integers. For notational simplicity, we first formulate our results for the case n_{k} = k (satisfied in all the above examples); we shall return to the general case in the next section.

The functions f_{k} in a limit theorem

f_{k}(X_{1}, X_{2}, …, X_{k}) ⟶^{D} G  (1.6)

must be measurable, but not all measurable f_{k} correspond to interesting limit theorems. For example, if f_{k}(x_{1}, x_{2}, …) = x_{1} + x_{2} for all k ≥ 1 and G denotes the convolution of the distributions of X_{1} and X_{2}, then (1.6) expresses a true statement, but it cannot be called a “limit theorem” because it involves only the variables X_{1} and X_{2}. A true limit theorem must involve infinitely many of the variables X_{i}, and it must have the property that for each k ≥ 1, the influence of the initial variables X_{1}, X_{2}, …, X_{k} on f_{l}(X_{1}, …, X_{l}) becomes eventually negligible as l → ∞, so that the validity of (1.6) is not influenced by changing finitely many X_{i}’s. We will formalize this condition by assuming that for each l > k ≥ 1 there exists a measurable function f_{k,l} : R^{l−k} → R such that

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ c_{k}/c_{l}  (1.7)

for some nondecreasing sequence c_{k} → ∞. For c_{k} = k^{α}, α > 0 (1.7) means that f_{l}(X_{1}, …, X_{l}) is close in probability to f_{k,l}(X_{k+1}, …, X_{l}) if k/l is small and thus f_{l} changes little in probability if we change its first εl variables, ε small. It is easy to verify (see Section 5) that all the limit theorems listed above satisfy this condition. In fact, as experience shows, most “usual” weak limit theorems have this proportionality property. For c_{k} = (log k)^{α}, α > 0, the right hand side of (1.7) will be small if log k/ log l ≤ ε, i.e. k ≤ l^{ε} with ε small. That is, in this case (1.7) means that f_{l}(x_{1}, …, x_{l}) depends negligibly on its first l^{ε} variables. Note that this segment is shorter than the segment of length εl obtained in the case c_{k} = k^{α}: the dependence of f_{l} on its initial variables became more sensitive. For even more slowly increasing (c_{k}) the segment of the initial, “irrelevant” variables of f_{l} gets even shorter, indicating a further increase of sensitivity of f_{l}.

A simple example for a limit theorem

f_{k}(X_{1}, …, X_{k}) ⟶^{D} G

where the dependence of f_{k} on its first εk variables is not negligible (i.e. (1.7) does not hold with c_{k} = k^{α}) is the Darling–Erdős (1956) limit theorem for the maximum of normed partial sums of independent random variables. This theorem states that if (X_{n}) is a sequence of independent random variables with mean 0, variance 1 and uniformly bounded third absolute moments, then letting S_{n} = X_{1} + ⋯ + X_{n} we have

a_{n} (max_{i≤n} \frac{S_{i}}{\sqrt{i}} − b_{n}) ⟶^{D} G

for suitable (a_{n}) and (b_{n}), where

G(x) = exp(−e^{−x}).

Here max_{i≤n} (S_{i}/\sqrt{i}) behaves like the maximum of the Ornstein-Uhlenbeck process U in [0, log n] and thus the probability that the maximum of S_{i}/\sqrt{i}, 1 ≤ i ≤ n is attained for some i ≤ \sqrt{n} is approximately 1/2. Hence changing the first \sqrt{n} of the variables X_{1}, …, X_{n} can change the value of max_{i≤n} (S_{i}/\sqrt{i}) radically on a set of probability near 1/2 and thus (1.7) fails with c_{k} = k^{α}.

We can now formulate our first general result providing the a.s. version of the weak limit theorems.

Theorem 1. Let X_{1}, X_{2}, … be independent random variables satisfying the weak limit theorem

f_{k}(X_{1}, X_{2}, …, X_{k}) ⟶^{D} G  (1.8)

where f_{k} : R^{k} → R (k = 1, 2 …) are measurable functions and G is a distribution function. Assume that for each 1 ≤ k < l there exists a measurable function f_{k,l} : R^{l−k} → R such that

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ A(c_{k}/c_{l})  (1.9)

with a constant A > 0 and a positive, nondecreasing sequence (c_{n}) satisfying c_{n} → ∞, c_{n+1}/c_{n} = O(1). Put

d_{k} = log(c_{k+1}/c_{k}), D_{n} = ∑_{k≤n} d_{k}.  (1.10)

Then we have

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x)  a.s. for any x ∈ C_{G}  (1.11)

where C_{G} denotes the set of continuity points of G. The result remains valid if we replace the weight sequence (d_{k}) by any (d_{k}^{∗}) such that 0 ≤ d_{k}^{∗} ≤ d_{k}, ∑ d_{k}^{∗} = ∞.

Theorem 1 shows that if a weak limit theorem (1.8) satisfies condition (1.9) then it has an a.s. weighted version with weights depending on the sequence c_{k} in (1.9). In the case c_{k} = k^{α} (1.10) gives

d_{k} ∼ const · 1/k

and thus (1.11) reduces to

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x)  a.s. for any x ∈ C_{G}.  (1.12)

Thus in this case the a.s. limit theorem corresponding to our weak limit theorem will involve logarithmic averages. This covers a very large class of limit theorems; several examples will be given in Section 5. Among others, we shall prove there analogues of the pointwise CLT for partial sums and partial maxima, extremal order statistics, empirical distribution functions, U–statistics, local times, return times, etc. If c_{k} = (log k)^{α}, then (1.10) gives

d_{k} ∼ const · \frac{1}{k log k}

and (1.11) reduces to

lim_{N→∞} \frac{1}{log log N} ∑_{k≤N} \frac{1}{k log k} I \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x) a.s. for any x ∈ C_{G}.

Such loglog averaging will appear, e.g., in the a.s. version of the Darling-Erdős limit theorem, see Section 5. Clearly, the slower the sequence (c_{n}) tends to infinity, the more “sensitive” limit theorems are permitted by (1.9), and the more the weights d_{k} differ from 1/k.

Any sequence D = (d_{1}, d_{2}, …) of positive numbers with ∑ d_{n} = ∞ defines a linear summation method (Riesz summation of order 1) as follows. Given a real sequence (x_{n}), put

σ_{n}^{(D)} = D_{n}^{−1} ∑_{k≤n} d_{k}x_{k}  where  D_{n} = ∑_{k≤n} d_{k}.

We say that (x_{n}) is D-summable if σ_{n}^{(D)} has a finite limit. By a classical theorem of Hardy (see e.g. Chandrasekharan and Minakshisundaram, 1952, p. 35; see also pp. 37-38 for a more general version due to Hirst), if two sequences D = (d_{n}) and D^{∗} = (d_{n}^{∗}) with partial sums D_{n} and D_{n}^{∗} satisfy D_{n}^{∗} = O(D_{n}) then, under mild regularity conditions, the summation procedure defined by D^{∗} is stronger (i.e. more effective) than the procedure defined by D in the sense that if a sequence (x_{n}) is D-summable then it is also D^{∗}-summable and to the same limit. Moreover, if D_{n}^{α} ≤ D_{n}^{∗} ≤ D_{n}^{β} for some 0 < α < β and sufficiently large n, then by a theorem of Zygmund (see also Chandrasekharan and Minakshisundaram, 1952, p. 35) the summation procedures defined by D and D^{∗} are equivalent, i.e., σ_{n}^{(D)} converges for some (x_{n}) iff σ_{n}^{(D^{∗})} does. Finally, if D_{n}^{∗} = O(D_{n}^{γ}) for all γ > 0 then the summation method defined by D^{∗} is strictly stronger than the method defined by D. (For further results see Chandrasekharan and Minakshisundaram, 1952, Chapter 2; we refer also to Bingham and Rogers, 1991 for various connections between summation methods and probability theory.) For example, logarithmic summation defined by d_{k} = 1/k is stronger than Cesàro (or (C, 1)) summation defined by d_{k} = 1; on the other hand, all summation procedures defined by d_{k} = (log k)^{α}/k, α > −1 are equivalent to logarithmic summation. Using the terminology of summation procedures, Theorem 1 means that the more “sensitive” the functional f_{k} in the weak limit theorem

f_{k}(X_{1}, …, X_{k}) ⟶^{D} G

is (i.e. the slower the sequence (c_{n}) in (1.9) tends to infinity), the more effective summation procedure has to be used in the corresponding strong limit theorem

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x) a.s. for any x ∈ C_{G}.

While the essential new information provided by Theorem 1 concerns nonlinear functionals f_{k}, the theorem sheds also new light on a curious phenomenon observed earlier in connection with the original a.s. central limit theorem. If X_{n} are independent random variables satisfying the Lindeberg condition (and thus the CLT), then the pointwise CLT can still fail (see Berkes and Dehling, 1993; Ibragimov and Lifshits, 1999), but as Atlagh (1993) showed, with properly chosen weights the pointwise CLT is always valid. More generally, Ibragimov and Lifshits (1999) showed that if (X_{n}) is a sequence of independent random variables satisfying (1.3) with some b_{n} ↑ ∞ and the left hand side of (1.3) has uniformly bounded p-th moments for some p > 0, then setting

d_{k} = (b_{k} − b_{k−1})/b_{k}, D_{n} = ∑_{k≤n} d_{k}

we have

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{\frac{S_{k} − a_{k}}{b_{k}} < x\} = G(x) a.s. for any x ∈ C_{G}.

Theorem 1 explains this phenomenon: if an independent sequence (X_{n}) with partial sums S_{n} satisfies (S_{n} − a_{n})/b_{n} ⟶^{D} G, then removing X_{1}, …, X_{k} from S_{n} for some k ≤ n will result of a change of (S_{n} − a_{n})/b_{n} in the order of magnitude b_{k}/b_{n} and thus Theorem 1 applies with c_{n} = b_{n}. If b_{n} grows like n^{γ} for some γ > 0, then b_{l}/b_{k} ∼ l/k and thus by Theorem 1 a pointwise CLT with weights 1/k is valid. However, if b_{n} grows, e.g., like (log n)^{γ}, γ > 0, then we have a more sensitive functional and Theorem 1 yields nonstandard weights. As the examples in Berkes and Dehling (1993), Ibragimov and Lifshits (1999) show, the use of weights different from 1/k is really necessary in this case.

Theorem 1 is the simplest one of the ‘universal’ results proved in our paper. In Section 2 we will formulate several extensions of Theorem 1 and in Section 3 we will discuss the weight sequences occuring in a.s. versions of weak limit theorems. The proofs of our theorems will be given in Section 4 and in Section 5 we will give examples and applications of our results.

2. Further results

Theorem 1 covers a very large class of limit theorems and condition (1.9) will be verified easily in all applications considered in Section 5. It should be noted, however, that condition (1.9) can be substantially weakened; the following result yields an essentially optimal condition under which the weak limit theorem

f_{k}(X_{1}, …, X_{k}) ⟶^{D} G  (2.1)

implies the a.s. result (1.11). Let log_{+} x = log x if x ≥ 1 and 0 otherwise.

Theorem 2. Let X_{1}, X_{2}, … be independent random variables, f_{k} : R^{k} → R (k = 1, 2 …) measurable functions and assume that for each 1 ≤ k < l there exists a measurable function f_{k,l} : R^{l−k} → R such that

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ C (log_{+} log_{+} (c_{l}/c_{k}))^{−(1+ε)}  (2.2)

for some constants C > 0, ε > 0 and a positive, nondecreasing sequence (c_{n}) satisfying c_{n} → ∞, c_{n+1}/c_{n} = O(1). Put

d_{k} = log(c_{k+1}/c_{k}), D_{n} = ∑_{k≤n} d_{k}.  (2.3)

Then for any distribution function G the relations

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x)  a.s. for any x ∈ C_{G}  (2.4)

and

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}P \{f_{k}(X_{1}, …, X_{k}) < x\} = G(x)  for any x ∈ C_{G}  (2.5)

are equivalent. The result remains valid if we replace the weight sequence (d_{k}) by any (d_{k}^{∗}) such that 0 ≤ d_{k}^{∗} ≤ d_{k}, ∑ d_{k}^{∗} = ∞.

Note that the log_{+} log_{+} in (2.2) equals 0 for 1 ≤ c_{l}/c_{k} ≤ e; in this case the right hand side of (2.2) is meant to be +∞ (and thus (2.2) is automatically satisfied in this case). Actually, the proof of Theorem 2 will use condition (2.2) only for c_{l}/c_{k} ≥ 3, when log_{+} log_{+} can be replaced by log log.

Assumption (2.2) of Theorem 2 is weaker than condition (1.9) in Theorem 1 and is actually sharp: Theorem 2 becomes false if we assume (2.2) only for ε = 0. This follows from a recent counterexample of Lifshits (2000a) related to the pointwise CLT, see Section 5. Observe also that in the theorem we state not only that the weak limit theorem (2.1) implies the strong result (2.4), but that the strong result (2.4) is actually equivalent to the weighted weak result (2.5). In addition to the case of weakly converging f_{k}(X_{1}, …, X_{k}), relation (2.5) covers also situations where the distribution of f_{k}(X_{1}, …, X_{k}) fluctuates without a limit. In Berkes and Dehling (1994) and Berkes et al. (1991) several examples are constructed (in the case of normalized partial sums) where (2.4) holds, but (2.1) fails. A more natural example for this phenomenon is the St. Petersburg game, see Berkes et al. (1999).

Theorem 1 permits various further generalizations. In what follows, we will investigate more general limit theorems of the type

f_{k}(X_{1}, X_{2}, …, X_{n_{k}}) ⟶^{D} G

with arbitrary n_{k} and also a.s. versions of weak limit theorems defined along subsequences. Finally, we will investigate the case when the discrete parameter sequence X_{n} is replaced by a continouos parameter process.

Schatte (1988) and Atlagh and Weber (1992) proved that if (X_{n}) is a sequence of i.i.d. random variables with EX_{1} = 0, EX_{1}^{2} = 1 then setting S_{k} = ∑_{i≤k} X_{i} we have

lim_{N→∞} \frac{1}{N} ∑_{k≤N} I \{\frac{S_{2^{k}}}{\sqrt{2^{k}}} < x\} = Φ(x) a.s. for any x.

(Actually, Schatte assumed also E|X_{1}|^{3} < +∞.) In other words, if we consider S_{n}/\sqrt{n} only along the subsequence 2^{k}, then the logarithmic averages in the pointwise central limit theorem can be replaced by ordinary (Cesàro) averages. The following theorem shows how to choose the weights in our general a.s. limit theorem (1.11) when we consider the functional f_{k}(X_{1}, …, X_{k}) only along a given subsequence (n_{k}) of integers.

Theorem 3. Let X_{1}, X_{2}, … be independent random variables, f_{k} : R^{k} → R (k = 1, 2 …) measurable functions and assume that for each 1 ≤ k < l there exists a measurable function f_{k,l} : R^{l−k} → R such that

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ C (log_{+} log_{+}(l/k))^{−(1+ε)}  (2.6)

for some ε > 0. Let (n_{k}) be an increasing sequence of positive integers satisfying n_{k+1}/n_{k} = O(1). Set

d_{k} = log(n_{k+1}/n_{k}), D_{n} = ∑_{k≤n} d_{k}.  (2.7)

Then for any distribution function G the relations

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{n_{k}}(X_{1}, …, X_{n_{k}}) < x\} = G(x) a.s. for any x ∈ C_{G}

and

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}P \{f_{n_{k}}(X_{1}, …, X_{n_{k}}) < x\} = G(x) for any x ∈ C_{G}

are equivalent. The result remains valid if we replace the weight sequence (d_{k}) by any (d_{k}^{∗}) such that 0 ≤ d_{k}^{∗} ≤ d_{k}, ∑ d_{k}^{∗} = ∞.

Condition (2.6) covers ‘proportional’ limit theorems, i.e. limit theorems of the type (2.1) where f_{k} depends weakly on its first o(k) variables. (As we noted in Section 1, most “usual” limit theorems satisfy this condition; see the examples in Section 5.) It is worth writing out the theorem in detail in a special case, e.g. in the case of the CLT, when (X_{n}) is an i.i.d. sequence with EX_{1} = 0, EX_{1}^{2} = 1 and

f_{l}(x_{1}, …, x_{l}) = (x_{1} + ⋯ + x_{l})/\sqrt{l}

(see example (a) in Section 1). In this case Theorem 3 states that if (n_{k}) is an increasing sequence of positive integers with n_{k+1}/n_{k} = O(1) and d_{k} is defined by (2.7), then

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{\frac{S_{n_{k}}}{\sqrt{n_{k}}} < x\} = Φ(x) a.s. for any x.

If n_{k} = [k^{α}] (α ≥ 1) then d_{k} ∼ α/k, i.e. the weights are still logarithmic. If n_{k} = [e^{k^{α}}] (0 < α ≤ 1), then d_{k} ∼ α/k^{1−α}, which corresponds to a weaker summation procedure. The case n_{k} = 2^{k} covers the results in Atlagh and Weber (1992), Schatte (1988) mentioned above. Clearly, the faster (n_{k}) grows, the weaker the summation procedure in Theorem 3 becomes. For example, in the case n_{k} = 2^{k} one can use a weaker summation procedure (namely Cesàro summation) to get the a.s. convergence of indicators than in the case n_{k} = k, when logarithmic summation is needed. This effect is exactly the opposite as the effect of the functional f_{k} getting more and more sensitive: this latter leads to the need of using stronger averaging procedures. The same interpretation holds for Theorem 3 in case of general functionals f_{k}.

Our next theorem is a common generalization of Theorems 1–3:

Theorem 4. Let X_{1}, X_{2}, … be independent random variables, (n_{k}) an increasing sequence of positive integers, f_{k} : R^{n_{k}} → R (k = 1, 2 …) measurable functions and assume that for each 1 ≤ k < l there exists a measurable function f_{k,l} : R^{n_{l}−n_{k}} → R such that

E (|f_{l}(X_{1}, …, X_{n_{l}}) − f_{k,l}(X_{n_{k}+1}, …, X_{n_{l}})| ∧ 1) ≤ C (log_{+} log_{+}(c_{l}/c_{k}))^{−(1+ε)} (2.8)

for some constants C > 0, ε > 0 and a positive, nondecreasing sequence (c_{n}) with c_{n} → ∞, c_{n+1}/c_{n} = O(1). Put

d_{k} = log(c_{k+1}/c_{k}), D_{n} = ∑_{k≤n} d_{k}.

Then for any distribution function G the relations

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{k}(X_{1}, …, X_{n_{k}}) < x\} = G(x)  a.s. for any x ∈ C_{G}  (2.9)

and

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}P \{f_{k}(X_{1}, …, X_{n_{k}}) < x\} = G(x)  for any x ∈ C_{G}  (2.10)

are equivalent. The result remains valid if we replace the weight sequence (d_{k}) by any (d_{k}^{∗}) such that 0 ≤ d_{k}^{∗} ≤ d_{k}, ∑ d_{k}^{∗} = ∞.

In addition to the situations considered in Theorems 1, 2 and 3, Theorem 4 covers limit theorems of the type

f_{k}(X_{1}, …, X_{n_{k}}) ⟶^{D} G  (2.11)

with arbitrary (n_{k}).

In conclusion we extend our theorems to the case when the functionals f_{k} depend not on an independent sequence (X_{n}), but on a process {X(t), t ≥ 0} with independent increments:

Theorem 5. Let {X(t), t ≥ 0} be a process with X(0) = 0 and independent increments and let ξ_{1}, ξ_{2}, … be random variables such that ξ_{k} is measurable with respect to σ{X(t), 0 ≤ t ≤ k}. Assume that for each 1 ≤ k < l there exists a random variable ξ_{k,l} measurable with respect to σ{X(t′) − X(t) : k ≤ t ≤ t′ ≤ l} such that

E (|ξ_{l} − ξ_{k,l}| ∧ 1) ≤ C (log_{+} log_{+}(c_{l}/c_{k}))^{−(1+ε)}

for some constants C > 0, ε > 0 and a positive, nondecreasing sequence (c_{n}) with c_{n} → ∞, c_{n+1}/c_{n} = O(1). Put

d_{k} = log(c_{k+1}/c_{k}), D_{n} = ∑_{k≤n} d_{k}.

Then for any distribution function G the relations

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{ξ_{k} < x\} = G(x)  a.s. for any x ∈ C_{G}  (2.12)

and

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}P \{ξ_{k} < x\} = G(x)  for any x ∈ C_{G}  (2.13)

are equivalent.

This theorem is the exact analogue of Theorem 2 for processes; the analogues of Theorems 1, 3 and 4 can be formulated similarly. A typical application of Theorem 5 is the Darling-Erdős limit theorem for sup_{1≤t≤n} (W (t)/\sqrt{t}) where W is a Wiener process (see Section 5.)

We note that the following result is also true, where the sums in (2.12) and (2.13) are replaced by integrals.

Theorem 6. Let {X(t), t ≥ 0} be a process with X(0) = 0 and independent increments and let {ξ(t), t ≥ 0} be a process such that ξ(t) is measurable with respect to σ{X(u), 0 ≤ u ≤ t}. Assume that for each 1 ≤ s < t there exists a random variable ξ(s, t) measurable with respect to σ{X(u′) − X(u) : s ≤ u ≤ u′ ≤ t} such that

E (|ξ(t) − ξ(s, t)| ∧ 1) ≤ C (log_{+} log_{+}(c(t)/c(s)))^{−(1+ε)}

for some constants C > 0, ε > 0 and a positive, nondecreasing, continuous function (c(t), t ≥ 1) with lim_{t→∞} c(t) = +∞. Put D(t) = log c(t). Then for any distribution function G the relations

lim_{T →∞} \frac{1}{D(T)} ∫_{1}^{T} I \{ξ(t) < x\} dD(t) = G(x)  a.s. for any x ∈ C_{G}  (2.14)

and

lim_{T →∞} \frac{1}{D(T)} ∫_{1}^{T} P \{ξ(t) < x\} dD(t) = G(x)  for any x ∈ C_{G}  (2.15)

are equivalent.

3. Notes on weight sequences

Most pointwise central limit theorems in the literature use the weights d_{k} = 1/k and it might appear that these weights are the ’natural’ ones. In many situations, the weights 1/k are very convenient to work with: for example, in the case of i.i.d. normal random variables, the use of an exponential time transformation together with the ergodic theorem yields a very elegant proof of the pointwise central limit theorem. However, Theorem 1 shows that even in these cases the weight sequence 1/k is only one in a very large class of weight sequences that work equally well: for example, in the case of i.i.d. random variables (X_{n}) with mean 0 and variance 1 the relation

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{\frac{S_{k}}{\sqrt{k}} < x\} = Φ(x)  a.s. for any x  (3.1)

holds for all weight sequences 0 ≤ d_{k} ≤ 1/k, ∑ d_{k} = ∞, and it is easy to see that (3.1) remains valid also for several sequences d_{k} ≥ 1/k. For example, (3.1) holds with

d_{k} = (log k)^{α}/k,  (α > −1)  (3.2)

(in fact, by Zygmund’s theorem, the summation method belonging to the sequence in (3.2) is equivalent to logarithmic summation), and we shall see that (3.1) holds even with

d_{k} = exp((log k)^{α})/k  (3.3)

provided 0 ≤ α < 1/2. On the other hand, Schatte (1988) proved that (3.1) does not hold with d_{k} = 1 (Cesàro summation). Clearly, the larger the weight sequence (d_{k}) is, the stronger is the result (3.1) (see our earlier remarks on summation methods) and it would be of considerable interest to determine the optimal weights. As (3.3) gives logarithmic averaging for α = 0 and Cesàro averaging for α = 1, we see that in the pointwise CLT (3.1) we can go at least ”halfways” from logarithmic to Cesàro averaging. Whether (3.3) works also for some 1/2 ≤ α < 1 remains open. We note, however, that for every 1/2 ≤ α < 1 relation (3.1) holds at least with convergence in probability.

Similarly to the above remarks, the weights in Theorems 2-5 are far from being the only possible (or optimal) ones. For example, Zygmund’s theorem shows that Theorems 2-5 remain valid with

d_{k} = log(c_{k+1}/c_{k})(log c_{k})^{α}, (α > −1)

and if the right side of (2.2) is sharpened to C(c_{l}/c_{k})^{−γ} for some γ > 0 then we will prove that one can even choose

d_{k} = log(c_{k+1}/c_{k}) exp((log c_{k})^{α}), 0 ≤ α < 1/2.

On the other hand, the conclusion of the theorem fails generally for

d_{k} = log(c_{k+1}/c_{k})c_{k}^{α}, α > 0.

Again, the optimal weight sequence remains unknown.

In conclusion we note that by the assumption c_{k+1}/c_{k} = O(1) made in Theorems 1, 2, 4 and 5 the weight sequences (d_{k}) in all of our theorems are bounded. This condition can be easily removed: the proofs our theorems remain valid, with obvious changes, if c_{k+1}/c_{k} grows, e.g., with polynomial speed. However, it must be pointed out that the case c_{k+1}/c_{k} → ∞ covers only relatively uninteresting situations. For example, under c_{k+1}/c_{k} → ∞ condition (2.8) of Theorem 4 implies that

f_{l}(X_{1}, …, X_{n_{l}}) − f_{l−1,l}(X_{n_{l−1}+1}, …, X_{n_{l}}) ⟶^{P} 0

and thus setting f_{k}^{∗} = f_{k−1,k}, the limit theorem (2.11) reduces to the relation

f_{k}^{∗}(X_{n_{k−1}+1}, …, X_{n_{k}}) ⟶^{D} G

where for different k’s the left hand side contains disjoint sets of the X_{i}’s. From the law of the iterated logarithm it will follow easily that in this case the conclusion of the theorem holds with any positive weight sequence (d_{n}) satisfying

E_{n}^{2} := ∑_{k≤n} d_{k}^{2} → ∞  (3.4)

and

d_{n} = o (E_{n}/(log log E_{n})^{1/2}) .  (3.5)

Moreover, this result is optimal, i.e. replacing the o in (3.5) by O the result becomes false. Condition (3.5) permits almost exponential increase of the weights d_{n}; for example, the conclusion of the theorem holds if d_{n} = e^{n/(log n)^{γ}}, γ > 1, and we will see that it generally fails if d_{n} = e^{n/ log n}. That our theorems cannot hold with exponential weights (d_{n}) (except in trivial cases) is obvious from the fact that for exponential (d_{n}) the summability procedure belonging to (d_{n}) is equivalent to convergence (see Chandrasekharan and Minakshisundaram, 1952, p. 13), and thus (2.9) means almost sure convergence of I {f_{k}(X_{1}, …, X_{n_{k}}) < x} to G(x) for all x ∈ C_{G}, which is impossible except if G is concentrated in a single point c and f_{k}(X_{1}, …, X_{n_{k}}) → c a.s.

4. Proof of the theorems

We shall give the proof of Theorem 4; the proofs of Theorems 5 and 6 are similar. Despite the large generality of our theorems, the proofs will be rather simple; we will use essentially the same second order argument that was used in the proof of the original versions of the ASCLT (see e.g. Lacey and Philipp, 1990; Schatte, 1988). Let

0 ≤ d_{k} ≤ log(c_{k+1}/c_{k}),  D_{n} = ∑_{k≤n} d_{k} → ∞.  (4.1)

By a well known principle in the theory of the pointwise central limit theorem (see e.g. Lacey and Philipp, 1990), it suffices to prove that for any bounded Lipschitz 1 function g : R → R we have

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k} [g (f_{k}(X_{1}, …, X_{n_{k}})) − Eg (f_{k}(X_{1}, …, X_{n_{k}}))] = 0  a.s.  (4.2)

Put

ξ_{k} = g (f_{k}(X_{1}, …, X_{n_{k}})) − Eg (f_{k}(X_{1}, …, X_{n_{k}}))

and let K ≥ 1 denote a constant such that

|g(x)| ≤ K and |g(x) − g(y)| ≤ K|x − y| for any x, y ∈ R.  (4.3)

Then for any 1 ≤ k < l with c_{l}/c_{k} ≥ 3 we get, using (2.8), (4.3) and the fact that f_{k}(X_{1}, …, X_{n_{k}}) and f_{k,l}(X_{n_{k}+1}, …, X_{n_{l}}) are independent,

|E(ξ_{k}ξ_{l})| = |Cov (g (f_{k}(X_{1}, …, X_{n_{k}})) , g (f_{l}(X_{1}, …, X_{n_{l}}))) | = |Cov (g (f_{k}(X_{1}, …, X_{n_{k}})) , g (f_{l}(X_{1}, …, X_{n_{l}})) − g (f_{k,l}(X_{n_{k}+1}, …, X_{n_{l}}))) | ≤ 2K · E|g (f_{l}(X_{1}, …, X_{n_{l}})) − g (f_{k,l}(X_{n_{k}+1}, …, X_{n_{l}})) | ≤ 2K · E (K|f_{l}(X_{1}, …, X_{n_{l}}) − f_{k,l}(X_{n_{k}+1}, …, X_{n_{l}})| ∧ 2K) ≤ 4CK^{2} (log log(c_{l}/c_{k}))^{−(1+ε)} .

(4.4)

Now

E( ∑_{k≤N} d_{k}ξ_{k})^{2} ≤ 2 ∑_{1≤k≤l≤N} d_{k}d_{l}|E(ξ_{k}ξ_{l})|.  (4.5)

Let N be so large that D_{N} ≥ 4. By (4.4), the contribution of those terms in the sum on the right side of (4.5) where

c_{l}/c_{k} ≥ exp(D_{N}^{1/2})

is at most

C^{∗}(log D_{N})^{−1−ε} ∑_{1≤k≤l≤N} d_{k}d_{l} ≤ C^{∗}(log D_{N})^{−1−ε}D_{N}^{2}.

On the other hand, letting M = sup_{n≥1}(c_{n+1}/c_{n}), the relation c_{l}/c_{k} ≤ exp(D_{N}^{1/2}) implies

log c_{l+1} − log c_{k} ≤ log M + D_{N}^{1/2}

and thus (4.1) and the trivial estimate |E(ξ_{k}ξ_{l})| ≤ 4K^{2} show that the contribution of those terms on the right hand side of (4.5) where c_{l}/c_{k} < exp(D_{N}^{1/2}) is

≤ 8K^{2} ∑_{k=1}^{N} d_{k} ∑_{{l≥k: c_{l}≤c_{k} exp (D_{N}^{1/2})}} d_{l} ≤ const · ∑_{k=1}^{N} d_{k} ∑_{{l≥k: c_{l}≤c_{k} exp (D_{N}^{1/2})}}(log c_{l+1} − log c_{l})

≤ const · ∑_{k=1}^{N} d_{k} (log M + D_{N}^{1/2}) ≤ const · D_{N}^{3/2}.

Hence setting

T_{N} = \frac{1}{D_{N}} ∑_{k≤N} d_{k}ξ_{k}

we get

ET_{N}^{2} ≤ const · (log D_{N})^{−1−ε}.

Let η > 0 be so small that (1 + ε)(1 − η) > 1. Since (d_{n}) is bounded by (4.1) and c_{n+1}/c_{n} = O(1), we have D_{n+1}/D_{n} → 1 and thus we can choose a nondecreasing sequence (N_{k}) of positive integers such that

D_{N_{k}} ∼ e^{k^{1−η}}  (4.6)

and consequently

ET_{N_{k}}^{2} ≤ const · k^{−1−ϱ}

for some ϱ > 0. Hence we have ∑_{k=1}^{∞} |T_{N_{k}}|^{2} < +∞ a.s., implying T_{N_{k}} → 0 a.s. Now for N_{k} < N ≤ N_{k+1} we have

|T_{N}| ≤ |T_{N_{k}}| + \frac{2K}{D_{N}} ∑_{i=N_{k}+1}^{N} d_{i} = |T_{N_{k}}| + 2K (1 − \frac{D_{N_{k}}}{D_{N}} ) .

Since D_{N_{k+1}}/D_{N_{k}} → 1 by (4.6), it follows that T_{N} → 0 a.s., completing the proof of (4.2).

If condition (2.8) of Theorem 4 is assumed only for l > k ≥ A with some constant A > 0, then the theorem remains valid with the summations in (2.9) and (2.10) extended for A ≤ k ≤ N. (The proof requires only trivial changes.) In this case f_{l}, f_{k,l}, c_{k} need not even be defined if k or l is < A. A similar remark applies in our other theorems.

It is easily seen that if the right hand side of (2.8) is replaced by C(c_{l}/c_{k})^{−γ} for some γ > 0, then in Theorem 4 we can choose

d_{k} = log(c_{k+1}/c_{k}) exp ((log c_{k})^{α}) 0 ≤ α < 1/2.

In this case instead of (4.4) we get |E(ξ_{k}ξ_{l})| ≤ const · (c_{l}/c_{k})^{−γ} and thus the contribution of those terms in (4.5) where c_{l}/c_{k} ≥ (log D_{N})^{2/γ} is at most D_{N}^{2}(log D_{N})^{−2}. On the other hand, in the present case we get by elementary calculations

D_{n} ∼ const · (log c_{n})^{1−α} exp ((log c_{n})^{α})

and consequently

exp ((log c_{n})^{α}) ∼ const · D_{n}/(log D_{n})^{(1−α)/α}.

Thus the contribution of those terms in (4.5) where c_{l}/c_{k} < (log D_{N})^{2/γ} is

≤ 8K^{2} · ∑_{k=1}^{N} d_{k} ∑_{{l≥k: c_{l}≤c_{k}(log D_{N})^{2/γ}}}(log c_{l+1} − log c_{l}) exp((log c_{l})^{α})

≤ const · exp((log c_{N})^{α}) ∑_{k=1}^{N} d_{k} log log D_{N} = const · exp((log c_{N})^{α}) D_{N} log log D_{N}

≤ const · D_{N}^{2} log log D_{N}/(log D_{N})^{(1−α)/α} ≤ const · D_{N}^{2}/(log D_{N})^{−(1+ε)}

for sufficiently large N; here ε > 0 by α < 1/2. The rest of the proof is the same as above.

The previous argument breaks down for 1/2 ≤ α < 1, but it is worth noting that even in this case we have T_{N} ⟶^{P} 0 and thus relation (2.10) implies (2.9) at least in probability. Whether we can have a.s. convergence in this case remains open.

We finally prove the claim, made in Section 3, that if in Theorem 4 the function f_{k}(x_{1}, …, x_{n_{k}}) depends only on x_{n_{k−1}+1}, …, x_{n_{k}} (i.e., if different f_{k}’s depend on disjoint segments of the sequence x_{1}, x_{2}, …), then the conclusion of the theorem holds for any weight sequence (d_{n}) satisfying (3.4), (3.5) and this becomes false if we replace the o in (3.5) by O. The direct part is easy: letting g denote a bounded Lip 1 function on R, we have to verify, just as in the proof above,

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}ξ_{k} = 0  a.s.  (4.7)

where

ξ_{k} = g(f_{k}(X_{n_{k−1}+1}, …, X_{n_{k}})) − Eg(f_{k}(X_{n_{k−1}+1}, …, X_{n_{k}})).

Clearly, (3.5) implies

max_{k≤n} d_{k} = o (E_{n}/(log log E_{n})^{1/2})

and thus

E_{n}^{2} ≤ (max_{k≤n} d_{k}) D_{n} = o (D_{n}E_{n}/(log log E_{n})^{1/2})

whence

E_{n} = o (D_{n}/(log log E_{n})^{1/2}) .  (4.8)

Now (ξ_{n}) is a uniformly bounded sequence of independent, zero mean random variables and if Eξ_{n}^{2} ≥ c > 0 for some constant c then the variance of ∑_{k≤n} d_{k}ξ_{k} lies between positive constant multiples of E_{n} and thus (3.5) shows that Kolmogorov’s LIL applies to the sequence (d_{n}ξ_{n}). Hence we get, using also (4.8), that

∑_{k≤n} d_{k}ξ_{k} = O (E_{n}(log log E_{n})^{1/2}) = o(D_{n}) a.s.

and thus (4.7) is valid. If inf Eξ_{n}^{2} = 0 then we get the same conclusion by replacing ξ_{n} by ξ_{n}^{∗} = ξ_{n} + ζ_{n}, where ζ_{n} are independent r.v.’s, independent also of the ξ_{n}’s, such that P (ζ_{n} = 1) = P (ζ_{n} = −1) = 1/2.

Conversely, let (X_{n}) be an i.i.d. sequence with P (X_{1} = 1) = P (X_{1} = −1) = 1/2 and let n_{k} = k, f_{k}(x_{1}, …, x_{n_{k}}) = f_{k}(x_{k}) = x_{k}, d_{k} = e^{k/ log k}. Simple calculations show that

D_{n} = ∑_{k≤n} d_{k} = ∑_{k≤n} e^{k/ log k} ∼ e^{n/ log n} log n  (4.9)

E_{n}^{2} = ∑_{k≤n} d_{k}^{2} = ∑_{k≤n} e^{2k/ log k} ∼ \frac{1}{2}e^{2n/ log n} log n  (4.10)

and thus

d_{n} = O (E_{n}/(log log E_{n})^{1/2}) .

Let G(x) denote the distribution function having jump 1/2 at x = −1 and x = 1. Clearly P {f_{k}(X_{k}) < x} = G(x) for all x and thus

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}P \{f_{k}(X_{k}) < x\} = G(x) for any x ∈ C_{G}

but we will show that

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{f_{k}(X_{k}) < x\} = G(x) a.s. for any x ∈ C_{G}

is not valid. Specifically, we prove that setting η_{k} = I {f_{k}(X_{k}) < 0} − P {f_{k}(X_{k}) < 0}, the relation

lim_{n→∞} \frac{1}{D_{n}} ∑_{k≤n} d_{k}η_{k} = 0  a.s.  (4.11)

is not valid. To see this, let i_{n} be the smallest integer such that D_{i_{n}} ≥ e^{n}. By the relation D_{n+1}/D_{n} → 1 we have D_{i_{n}} ∼ e^{n} and it is also easily seen that i_{n} ∼ n log n. Relations (4.9), (4.10) imply

∑_{i=i_{n}+1}^{i_{n+1}} d_{i}^{2} ∼ const · \frac{e^{2n}}{log n}.  (4.12)

Now η_{n} are i.i.d. symmetric two-valued random variables and simple calculations show that the finite sequence {d_{i}η_{i}; i_{n} + 1 ≤ i ≤ i_{n+1}} satisfies the conditions of Feller’s large deviation theorem (see Feller, 1943, Theorem 1). It follows that if x_{n} = c_{0}\sqrt{log n} (n = 1, 2, …) with a sufficiently small absolute constant c_{0} then

P \{ ∑_{i=i_{n}+1}^{i_{n+1}} d_{i}η_{i} ≥ x_{n} ( ∑_{i=i_{n}+1}^{i_{n+1}} d_{i}^{2})^{1/2}\} ≥ const · \frac{1}{\sqrt{n}} as n → ∞.

In view of (4.12) this implies that for a sufficiently small positive constant c_{1} we have

P \{ ∑_{i=i_{n}+1}^{i_{n+1}} d_{i}η_{i} ≥ c_{1}e^{n}\} ≥ const · \frac{1}{\sqrt{n}}

and thus

P { ∑_{i=i_{n}+1}^{i_{n+1}} d_{i}η_{i} ≥ c_{1}e^{n} i.o.} = 1.  (4.13)

Now if (4.11) were true then by the definition of i_{n} and D_{i_{n}} ∼ e^{n} it would follow that

∑_{i=i_{n}+1}^{i_{n+1}} d_{i}η_{i} = o(e^{n}) a.s.

which contradicts to (4.13).

5. Applications

In this section we shall give several applications of our theorems.

1. Partial sums. Let X_{1}, X_{2}, … be independent random variables with partial sums S_{n} = ∑_{k≤n} X_{k} and assume that (S_{n} − a_{n})/b_{n} ⟶^{D} G for some distribution function G and numerical sequences (a_{n}), (b_{n}) satisfying b_{n} ↑ ∞, b_{n+1}/b_{n} = O(1). Assume also that

E (log_{+} log_{+} |\frac{S_{n} − a_{n}}{b_{n}} |)^{1+δ} ≤ K  (n = 1, 2, …)  (5.1)

for some constants δ > 0, K > 0. Then the assumptions of Theorem 2 are satisfied with c_{k} = b_{k} and

f_{l}(x_{1}, …, x_{l}) = (∑_{i=1}^{l} x_{i} − a_{l}) /b_{l}, f_{k,l}(x_{k+1}, …, x_{l}) = ( ∑_{i=k+1}^{l} x_{i} − (a_{l} − a_{k})) /b_{l}.

Indeed, letting g(x) = 1+(log_{+} log_{+} x)^{1+δ}, the function x/g(x) is continuous for x ≥ 0 and increasing for x ≥ x_{0} and thus there exists a number a_{0} > 0 such that x/y ≤ g(x)/g(y) for 0 ≤ x ≤ y, y ≥ a_{0}. Hence letting λ = b_{l}/b_{k} and assuming λ ≥ a_{0} we get, using (5.1),

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1)

= E (|\frac{S_{k} − a_{k}}{b_{l}} | ∧ 1) = E (\frac{1}{λ} \{|\frac{S_{k} − a_{k}}{b_{k}} | ∧ λ\}) ≤ \frac{1}{g(λ)}Eg (|\frac{S_{k} − a_{k}}{b_{k}} | ∧ λ)

≤ \frac{1}{g(λ)}Eg (|\frac{S_{k} − a_{k}}{b_{k}} |) ≤ const · (log_{+} log_{+} \frac{b_{l}}{b_{k}} )^{−(1+δ)} .

(5.2)

Increasing the constant if necessary, the last expression in (5.2) will exceed 1 for 1 ≤ b_{l}/b_{k} ≤ a_{0}, and thus the relation

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ const · (log_{+} log_{+} \frac{b_{l}}{b_{k}} )^{−(1+δ)}

holds for all l ≥ k ≥ 1, showing that Theorem 2 applies with c_{k} = b_{k}. If we assume also

b_{l}/b_{k} ≥ C(l/k)^{γ}  (l ≥ k)  (5.3)

for some constants C > 0, γ > 0, then the last expression in (5.2) is bounded by const · (log_{+} log_{+}(l/k))^{−(1+δ)} and thus Theorem 2 applies with c_{k} = k, in which case (2.3) gives d_{k} ∼ const/k. Hence we obtain Theorem A. Let X_{1}, X_{2}, … be independent random variables with partial sums S_{n} and assume that (S_{n} − a_{n})/b_{n} ⟶^{D} G for some distribution function G and numerical sequences (a_{n}), (b_{n}) satisfying b_{n} ↑ ∞, b_{n+1}/b_{n} = O(1). Assume also that (5.1) holds for some constants δ > 0, K > 0. Then

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{\frac{S_{k} − a_{k}}{b_{k}} < x\} = G(x)  a.s. for any x ∈ C_{G}  (5.4)

where d_{k} and D_{k} are defined by

d_{k} = log(b_{k+1}/b_{k}), D_{n} = ∑_{k≤n} d_{k}.  (5.5)

If the norming factors b_{n} satisfy also (5.3), then (5.4) holds with d_{k} = 1/k, D_{N} = log N.

In the case d_{k} = 1/k this was proved by Berkes and Dehling (1993); the general case extends also a result of Ibragimov and Lifshits (1999) who proved the same conclusion under the stronger moment condition

E |\frac{S_{n} − a_{n}}{b_{n}} |^{p} ≤ K (n = 1, 2, …, p > 0)

instead of (5.1).

Recently Lifshits (2000a) constructed a sequence (X_{n}) of independent r.v.’s with mean 0 and finite variances whose partial sums S_{n} satisfy S_{n}/\sqrt{n} ⟶^{D} N(0, 1) and

E (log_{+} log_{+} |\frac{S_{n}}{\sqrt{n}}|) ≤ K (n = 1, 2, …)

for some constant K > 0 but the a.s. central limit theorem

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{S_{k}}{\sqrt{k}} < x\} = Φ(x) a.s. for any x

is not valid. This shows that condition (5.1) of Theorem A is sharp even in the case a_{n} = 0, b_{n} = \sqrt{n}. In view of the estimate (5.2), this implies that assumption (2.2) of Theorem 2 is also sharp, and thus the same holds for the analogous conditions in Theorems 3, 4, 5.

2. Extremes. Let X_{1}, X_{2}, … be i.i.d. random variables and (a_{n}), (b_{n}) numerical sequences. Then the assumptions of Theorem 1 are satisfied with c_{k} = k and

f_{l}(x_{1}, …, x_{l}) = a_{l} (max_{i≤l} x_{i} − b_{l}) , f_{k,l}(x_{k+1}, …, x_{l}) = a_{l} ( max_{k+1≤i≤l} x_{i} − b_{l}) .

Indeed, in this case f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l}) differs from zero only if

max_{1≤i≤k} X_{i} > max_{k+1≤i≤l} X_{i}

and we will see below that the probability of this event is ≤ k/l. Therefore

E (|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ k/l.

Thus we obtain the following result (see Cheng et al., 1998; Fahrner and Stadtmüller, 1998):

Theorem B. Let X_{1}, X_{2}, … be i.i.d. random variables such that setting M_{k} = max_{i≤k} X_{i} we have

a_{k}(M_{k} − b_{k}) ⟶^{D} G

for some numerical sequences (a_{n}), (b_{n}) and a distribution function G. Then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{a_{k}(M_{k} − b_{k}) < x\} = G(x) a.s. for any x ∈ C_{G}.

We note that, as observed in Cheng et al. (1998), Fahrner and Stadtmüller (1998), Theorem B becomes false if we replace logarithmic averages by ordinary (Cesàro) averages.

It remains to prove that if 1 ≤ k < l and X_{1}, …, X_{l} are i.i.d. random variables, then

P ( max_{1≤i≤k} X_{i} > max_{k+1≤i≤l} X_{i}) ≤ k/l.  (5.6)

Letting F denote the (left continuous) distribution function of X_{1}, the distribution functions of the two random variables in (5.6) are H_{1}(x) = F (x)^{k} and H_{2}(x) = F (x)^{l−k} and thus the probability in (5.6) equals

∫_{−∞}^{∞} H_{2}(x)dH_{1}(x) = ∫_{−∞}^{∞} F (x)^{l−k}kF (x)^{k−1}dF (x) ≤ ∫_{0}^{1} kt^{l−1}dt = k/l

where in the second step we used the fact that

∫_{−∞}^{∞} ψ(F (x))dF (x) ≤ ∫_{0}^{1} ψ(t)dt  (5.7)

for any nondecreasing function ψ on [0, 1]. To verify (5.7), let F^{−1}(t) = sup{x : F (x) ≤ t} and let U be a r.v. uniformly distributed on (0, 1). Then F (F^{−1}(t)) ≤ t for all t ∈ (0, 1) and the r.v. Y = F^{−1}(U) has distribution function F. Thus the left hand side of (5.7) equals

Eψ(F (Y)) = Eψ(F (F^{−1}(U))) ≤ Eψ(U) = ∫_{0}^{1} ψ(t)dt,

as claimed.

Theorem B extends easily to independent, not identically distributed random variables. Note that the identical distribution of the X_{i} was used only to obtain (5.6) and the proof remains valid if (5.6) holds with the right hand side replaced by C(k/l) for a constant C. This modified inequality holds, in turn, if for any l ≥ 1 and any permutation {i_{1}, …, i_{l}} of {1, 2, …, l} we have

P (X_{i_{1}} ≥ max (X_{i_{2}}, …, X_{i_{l}})) ≤ C/l.  (5.8)

Condition (5.8) is satisfied, e.g., if the distributions of the X_{i} are continuous and resemble each other in the sense that there exists a continuous distribution function F and positive constants γ_{1}, γ_{2} (necessarily γ_{1} ≤ 1) such that for all i ≥ 1

γ_{1}(1 − F (t)) ≤ P (X_{i} ≥ t) ≤ γ_{2}(1 − F (t)) for all t ∈ R.

Indeed, letting F_{i} denote the distribution function of X_{i} and using the postulated bounds for P (X_{i} ≥ t) we get that the probability in (5.8) equals

∫_{−∞}^{∞}(1 − F_{i_{1}}(x))d (∏_{r=2}^{l} F_{i_{r}}(x))

≤ γ_{2} ∫_{−∞}^{∞}(1 − F (x))d (∏_{r=2}^{l} F_{i_{r}}(x)) = γ_{2} ∫_{−∞}^{∞} (∏_{r=2}^{l} F_{i_{r}}(x)) dF (x)

≤ γ_{2} ∫_{−∞}^{∞} (1 − γ_{1}(1 − F (x)))^{l−1} dF (x) ≤ γ_{2} ∫_{0}^{1} (1 − γ_{1}(1 − u))^{l−1} du ≤ \frac{γ_{2}}{γ_{1}} l^{−1}

where we used (5.7) again.

Obviously, one cannot hope that (5.6) holds for independent X_{i} with radically different distributions. An instructive example is given by the case when the distribution function of X_{k} is F (x)^{c_{k}−c_{k−1}} where F is a fixed distribution function and (c_{k}) is an increasing sequence with c_{0} = 0 and c_{1} ≥ 1. In this case the distribution functions H_{1}(x) and H_{2}(x) of max_{1≤i≤k} X_{i} and max_{k+1≤i≤l} X_{i} are F (x)^{c_{k}} and F (x)^{c_{l}−c_{k}}, respectively, and thus the probability in (5.6) is

∫_{−∞}^{∞} H_{2}(x)dH_{1}(x) = ∫_{−∞}^{∞} F (x)^{c_{l}−c_{k}}c_{k}F (x)^{c_{k}−1}dF (x) ≤ c_{k}/c_{l}

where we used (5.7) in the last step. Thus (5.6) can fail, but Theorem 1 still applies in this case and we get the following theorem extending Theorem B:

Theorem C. Let X_{1}, X_{2}, … be independent random variables such that the distribution of X_{k} is F (x)^{c_{k}−c_{k−1}} where (c_{k}) is an increasing sequence satisfying c_{0} = 0, c_{1} ≥ 1, c_{n} → ∞ and c_{n+1}/c_{n} = O(1). Let M_{k} = max_{i≤k} X_{i} and assume that

a_{k}(M_{k} − b_{k}) ⟶^{D} G

for some numerical sequences (a_{n}), (b_{n}) and a distribution function G. Then letting d_{k} = log(c_{k+1}/c_{k}) and D_{n} = ∑_{k≤n} d_{k}, we have

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{a_{k}(M_{k} − b_{k}) < x\} = G(x) a.s. for any x ∈ C_{G}.

3. Maxima of partial sums. Let X_{1}, X_{2}, … be independent random variables with partial sums S_{n} = ∑_{k≤n} X_{k} and let S_{n}^{∗} = max_{k≤n} S_{k}. Assume that for some positive numerical sequence (b_{n}) we have

E (log_{+} log_{+} |\frac{S_{n}}{b_{n}} |)^{1+δ} ≤ K  (n = 1, 2, …)  (5.9)

for some K > 0, δ > 0 and the analogous relation for S_{n}^{∗} is also valid. Then the assumptions of Theorem 2 are satisfied with c_{k} = b_{k} and

f_{l}(x_{1}, …, x_{l}) = \frac{1}{b_{l}} max_{i≤l} (x_{1} + ⋯ + x_{i})

f_{k,l}(x_{k+1}, …, x_{l}) = \{ \begin{matrix}\frac{1}{b_{l}} max_{k+1≤i≤l} (x_{k+1} + ⋯ + x_{i}) if i_{0} > k \\ 0 if i_{0} ≤ k \end{matrix}

where 1 ≤ i_{0} ≤ l is the smallest integer where s_{i} = x_{1} + … + x_{i}, 1 ≤ i ≤ l, reaches its maximum. Indeed, letting s_{j}^{∗} = max_{i≤j} s_{i}, observe that the difference

Δ = f_{l}(x_{1}, …, x_{l}) − f_{k,l}(x_{k+1}, …, x_{l})

equals s_{k}^{∗}/b_{l} if i_{0} ≤ k, while for i_{0} > k the sum x_{k+1} + … + x_{i}, k + 1 ≤ i ≤ l reaches its maximum also at i = i_{0} and thus Δ = s_{k}/b_{l}. Therefore

E(|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ∧ 1) ≤ E (|\frac{S_{k}}{b_{l}} | ∧ 1) + E (|\frac{S_{k}^{∗}}{b_{l}} | ∧ 1)

and thus estimate (5.2) applies with trivial changes. Hence we obtain

Theorem D. Let X_{1}, X_{2}, … be independent r.v.’s with partial sums S_{n} and let S_{n}^{∗} = max_{k≤n} S_{k}. Let (b_{n}) be a positive numerical sequence satisfying b_{n} ↑ ∞, b_{n+1}/b_{n} = O(1) and assume that

S_{n}^{∗}/b_{n} ⟶^{D} G

for some distribution function G and also that (5.9) and its analogue for S_{n}^{∗} hold. Then

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{\frac{S_{k}^{∗}}{b_{k}} < x\} = G(x) a.s. for any x ∈ C_{G}

where d_{k} and D_{k} are defined by (5.5). If the norming factors b_{n} satisfy also (5.3), then the last convergence relation holds with d_{k} = 1/k, D_{N} = log N.

An analogous result holds for the absolute maxima S_{n}^{∗∗} = max_{k≤n} |S_{k}|; the proof is similar.

4. Empirical distribution functions. Let X_{1}, X_{2}, … be i.i.d. random variables with continuous distribution function F and let

F_{n}(x) = \frac{1}{n} ∑_{k≤n} I(X_{k} < x)  (5.10)

be the empirical distribution function of the sample (X_{1}, …, X_{n}). Then the assumptions of Theorem 1 are satisfied with c_{k} = k and

f_{l}(x_{1}, …, x_{l}) = \frac{1}{\sqrt{l}} sup_{x} |∑_{i≤l} (I(x_{i} < x) − F (x))| ,

f_{k,l}(x_{k+1}, …, x_{l}) = \frac{1}{\sqrt{l}} sup_{x} | ∑_{k+1≤i≤l} (I(x_{i} < x) − F (x))| .

Indeed, letting λ = \sqrt{l/k} and

T_{k} = sup_{x} |∑_{i≤k} (I(X_{i} < x) − F (x))|

we get

E|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})| ≤ E|T_{k}/\sqrt{l}| ≤ const · (k/l)^{1/2}

since E|T_{k}/\sqrt{k}| is bounded (see Dvoretzky et al., 1956, Lemma 2). Also, the classical theorem of Kolmogorov-Smirnov implies that

f_{k}(X_{1}, …, X_{k}) ⟶^{D} G

where

G(x) = ∑_{j=−∞}^{∞}(−1)^{j}e^{−2j^{2}x^{2}}.

Thus Theorem 1 implies

Theorem E. Let X_{1}, X_{2}, … be i.i.d. random variables with continuous distribution function F, let F_{n} be the empirical distibution function defined by (5.10) and let

D_{n} = sup_{x} |F_{n}(x) − F (x)|

be the Kolmogorov statistics. Then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\sqrt{k}D_{k} < x\} = ∑_{j=−∞}^{∞}(−1)^{j}e^{−2j^{2}x^{2}} a.s. for any x.

A similar argument yields the one-sided result

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\sqrt{k}D_{k}^{+} < x\} = 1 − e^{−2x^{2}} a.s. for any x

where D_{n}^{+} = sup_{x}(F_{n}(x) − F (x)).

5. U-statistics. Let X_{1}, X_{2}, … be an i.i.d. sequence, m ≥ 1 an integer and h(x_{1}, …, x_{m}) a symmetric measurable function satisfying

Eh^{2}(X_{1}, … X_{m}) < ∞.

Let

U_{n} = \frac{1}{\binom{n}{m}} ∑_{1≤i_{1}<...<i_{m}≤n} h(X_{i_{1}}, …, X_{i_{m}})

be the corresponding U-statistic. Set θ = Eh(X_{1}, …, X_{m}), and put for 1 ≤ j ≤ m

h_{j}(x_{1}, …, x_{j}) = Eh(x_{1}, …, x_{j}, X_{j+1}, …, X_{m}), ζ_{j} = Var h_{j}(X_{1}, …, X_{j}).

It is known (see e.g. Serfling, 1980, p. 182) that

0 = ζ_{0} ≤ ζ_{1} ⋯ ≤ ζ_{m} = Var h(X_{1}, …, X_{m}) < ∞.

Let c ≥ 1 denote the smallest integer such that ζ_{c} > 0; we call c the critical parameter of the statistic U_{n}. It is known that n^{c/2}(U_{n} − θ) has a nondegenerate limit distribution. (See e.g. Koroljuk and Borovskich, 1994; we refer also to Denker, 1985; Giné and Zinn, 1994 and the references there for various further related results.) Put h̃(X_{1}, …, X_{m}) = h(X_{1}, …, X_{m}) − θ and set, for any 1 ≤ k < l,

f_{l}(x_{1}, …, x_{l}) = \frac{l^{c/2}}{\binom{l}{m}} ∑_{1≤i_{1}<...<i_{m}≤l} h̃(x_{i_{1}}, …, x_{i_{m}}),

f_{k,l}(x_{k+1}, …, x_{l}) = \frac{l^{c/2}}{\binom{l}{m}} ∑_{k+1≤i_{1}<...<i_{m}≤l} h̃(x_{i_{1}}, …, x_{i_{m}}).

We claim that

E(|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})|)^{2} ≤ C(k/l)  (k ≤ l)  (5.11)

for some positive constant C; this will show that Theorem 1 applies in our case. Relation (5.11) can be equivalently written as

E(l^{c/2}U_{k,l})^{2} ≤ C(k/l)  (5.12)

where

U_{k,l} = \frac{1}{\binom{l}{m}} ∑_{1≤i_{1}<...<i_{m}≤l}^{∗} h̃(X_{i_{1}}, …, X_{i_{m}}).

and the * means that at least one of i_{1}, …, i_{m} lies in the interval [1, k]. To prove (5.12) we note that if {a_{1}, …, a_{m}} and {b_{1}, …, b_{m}} are two sets of distinct positive integers with j common elements, then

Eh̃(X_{a_{1}}, …, X_{a_{m}})h̃(X_{b_{1}}, …, X_{b_{m}}) = ζ_{j}.  (5.13)

(see Serfling, 1980, p. 183). Now expanding U_{k,l}^{2} and using (5.13) and ζ_{j} = 0 for j < c, we get nonzero terms belonging only to such sets {a_{1}, …, a_{m}} and {b_{1}, …, b_{m}} which have at least c common elements. Thus among a_{1}, …, a_{m}, b_{1}, …, b_{m} there are at most 2m − c different ones, moreover, at least one of these elements must be in the interval [1, k]. Therefore, the number of choices for the union set {a_{1}, …, a_{m}, b_{1}, …, b_{m}} is at most kl^{2m−c−1}. Once this union set is fixed, each of the sets {a_{1}, …, a_{m}} and {b_{1}, …, b_{m}} can be chosen at most in C_{m} ways, where C_{m} = \binom{2m}{m}. Thus, the number of nonzero terms in E(U_{k,l})^{2} is at most C_{m}^{2}kl^{2m−c−1}. By the Cauchy-Schwarz inequality, the left hand side of (5.13) is at most γ_{0} = Var h(X_{1}, …, X_{m}) and since we have \binom{l}{m} ∼ l^{m}, (5.12) follows. Hence we proved the following theorem:

Theorem F. Let X_{1}, X_{2}, … be i.i.d. random variables, m ≥ 1 a fixed integer and

U_{n} = \frac{1}{\binom{n}{m}} ∑_{1≤i_{1}<...<i_{m}≤n} h(X_{i_{1}}, …, X_{i_{m}})

where h(x_{1}, …, x_{m}) a symmetric measurable function satisfying

Eh^{2}(X_{1}, … X_{m}) < ∞.

Let θ = Eh(X_{1}, …, X_{m}) and let c be the critical parameter of the statistic U_{n}. Then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{k^{c/2}(U_{k} − θ) < x\} = F (x) a.s. for any x ∈ C_{F}

where F is the limit distribution of n^{c/2}(U_{n} − θ).

6. Local times. Let X_{1}, X_{2}, … be i.i.d. integer valued random variables with EX_{1} = 0. Put ψ(v) = E(e^{ivX_{1}}) and assume that ψ(2πt) = 1 if and only if t is an integer and ψ satisfies

\frac{1}{2π} ∫_{−π}^{π} \frac{ψ(v)}{1 − λψ(v)}dv ∼ \frac{a}{(1 − λ)^{β}} , as λ → 1

where 0 < β ≤ 1/2. Putting S_{n} = X_{1} + … + X_{n}, it follows that the random walk {S_{n}, n ≥ 1} is aperiodic and X_{1} is in the domain of normal attraction of a stable law of order α = 1/(1 − β). (Note that 1 < α ≤ 2.) Define the local time ξ(z, n) by

ξ(z, n) = ∑_{i=1}^{n} I{S_{i} = z},  z ∈ Z.  (5.14)

It was shown by Darling and Kac (1957) that

lim_{n→∞} P \{\frac{ξ(0, n)}{an^{β}} < x\} = F_{β}(x) = \frac{1}{πβ} ∑_{j=1}^{∞} \frac{(−1)^{j−1}}{j!j} sin(πβj)Γ(1 + βj)x^{j}.  (5.15)

Kesten and Spitzer (1979) showed that for some constant c we have

Eξ(0, n) ≤ cn^{β}, E (ξ(z, n) − ξ(0, n))^{2} ≤ c|z|^{β/(1−β)}n^{β}.

Thus choosing

\begin{aligned}f_{l}(x_{1}, …, x_{l}) & = \frac{1}{al^{β}} ∑_{i=1}^{l} I\{x_{1} + … + x_{i} = 0\} \\ f_{k,l}(x_{k+1}, …, x_{l}) & = \frac{1}{al^{β}} ∑_{i=k+1}^{l} I\{x_{k+1} + … + x_{i} = 0\} \end{aligned}

we have E|f_{l}(X_{1}, …, X_{l}) − f_{k,l}(X_{k+1}, …, X_{l})|

= E |\frac{ξ(0, l)}{al^{β}} − \frac{ξ(S_{k}, l) − ξ(S_{k}, k)}{al^{β}} |

= E |\frac{ξ(0, k)}{al^{β}} − \frac{ξ(S_{k}, l) − ξ(S_{k}, k) − (ξ(0, l) − ξ(0, k))}{al^{β}} |

≤ \frac{C}{a} ((k/l)^{β} + l^{−β}E|S_{k}|^{β/2(1−β)}l^{β/2}) ≤ C′ ((k/l)^{β} + (k/l)^{β/2})

Thus using Theorem 1 we get the following

Theorem G. Let the random walk {S_{n}, n ≥ 1} satisfy the above conditions and let ξ(z, n) be its local time defined by (5.14). Then

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{ξ(0, k)}{ak^{β}} < x\} = F_{β}(x) a.s. for any x

where F_{β} is the distribution function defined by (5.15).

7. Return times. Let 0 = τ_{0} < τ_{1} < … be the successive times of return to the origin of a two dimensional simple symmetric random walk and put X_{n} = τ_{n} − τ_{n−1} (n = 1, 2, …). Clearly, (X_{n}) is an i.i.d. sequence; it is known (see Dvoretzky and Erdős, 1951) that

P (X_{1} > t) ∼ \frac{c}{log t}  as t → ∞.  (5.16)

Setting M_{k} = max_{i≤k} X_{i}, relation (5.16) implies

\frac{1}{k} log M_{k} ⟶^{D} H

where

H(x) = \{ \begin{matrix}e^{−c/x} & if x > 0 \\ 0 & if x ≤ 0 \end{matrix}  (5.17)

Now Theorem 1 applies to the sequence (X_{n}) with c_{k} = k and

f_{l}(x_{1}, …, x_{l}) = \frac{1}{l} log max_{i≤l} x_{i}, f_{k,l}(x_{k+1}, …, x_{l}) = \frac{1}{l} log max_{k+1≤i≤l} x_{i}.

(This can be verified exactly as in the case of Theorem B.) Hence we get

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{1}{k} log M_{k} < x\} = H(x) a.s. for any x.

But M_{k} ≤ τ_{k} ≤ kM_{k} and thus (log τ_{k} − log M_{k})/k → 0 a.s. Thus we proved Theorem H. Let 0 = τ_{0} < τ_{1} < … be the successive times of return to the origin of a two dimensional simple symmetric random walk. Then we have

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{1}{k} log τ_{k} < x\} = H(x) a.s. for any x

where H is the distribution function defined by (5.17).

Actually, all we used about the i.i.d. sequence (X_{n}) was its positivity and (5.16), hence the same argument shows that if (X_{n}) is a positive i.i.d. sequence satisfying (5.16) then setting S_{k} = ∑_{i≤k} X_{i} we have

lim_{N→∞} \frac{1}{log N} ∑_{k≤N} \frac{1}{k} I \{\frac{1}{k} log S_{k} < x\} = H(x) a.s. for any x.

8. Darling-Erdős type limit theorems. Let (X_{n}) be a sequence of independent random variables with mean 0, variance 1 and uniformly bounded third absolute moments. Put S_{k} = X_{1} + ⋯ + X_{k}. By a well known theorem of Darling and Erdős (1956) we have

a_{n} (max_{k≤n} \frac{S_{k}}{\sqrt{k}} − b_{n}) ⟶^{D} G

where

a_{n} = (2 log log n)^{1/2}, b_{n} = (2 log log n)^{1/2} + \frac{log log log n − log 4π}{2(2 log log n)^{1/2}}  (n ≥ 3) (5.18)

and

G(x) = exp(−e^{−x}).  (5.19)

(Actually, the assumption on the third moments can be weakened, see Einmahl, 1989; Oodaira, 1976; Shorack, 1979.) An analogous result holds for the Wiener process W, in fact we have

a_{n} ( sup_{1≤t≤n} \frac{W (t)}{\sqrt{t}} − b_{n}) ⟶^{D} G  (5.20)

where (a_{n}), (b_{n}) and G are the same as above. We now show that

lim_{N→∞} \frac{1}{D_{N}} ∑_{k≤N} d_{k}I \{a_{k} ( sup_{1≤t≤k} \frac{W (t)}{\sqrt{t}} − b_{k}) < x\} = G(x) a.s. for any x

for a suitable (d_{k}), where D_{N} = ∑_{k≤N} d_{k}. To this end, let

c_{n} = exp(\sqrt{log log n}), A_{n} = exp (log n/ exp(\sqrt{log log n})) (n ≥ 3),

ξ_{l} = a_{l} ( sup_{1≤t≤l} \frac{W (t)}{\sqrt{t}} − b_{l}) (l ≥ 3),

and put for l ≥ k ≥ 3

ξ_{k,l} = \{ \begin{matrix}a_{l} ( sup_{A_{l}^{2}≤t≤l} \frac{W (t) − W (k)}{\sqrt{t}} − b_{l}) if k ≤ A_{l} \\ 0 if k > A_{l}. \end{matrix}

Clearly ξ_{k,l} is measurable with respect to σ{X(t′) − X(t) : k ≤ t ≤ t′ ≤ l}. We claim that

E (|ξ_{l} − ξ_{k,l}| ∧ 1) ≤ 4(c_{k}/c_{l})^{1/2}  (3 ≤ k < l, l ≥ l_{0})  (5.21)

where l_{0} is an absolute constant. In the case k > A_{l} relation (5.21) is valid since the left hand side is at most 1, while the right hand side exceeds 1 since

c_{k} ≥ exp (\sqrt{log log A_{l}}) = exp ((log log l − \sqrt{log log l})^{1/2}) ≥ exp (\sqrt{log log l} − 1) ≥ c_{l}/4.

To prove (5.21) for k ≤ A_{l} we first note that the stationarity and Markov property for the Ornstein-Uhlenbeck process imply easily that

P \{ sup_{1≤t≤T} \frac{W (t)}{\sqrt{t}} = sup_{1≤t≤T′} \frac{W (t)}{\sqrt{t}}\} = \frac{log T}{log T′}  for any T′ ≥ T > 1  (5.22)

and thus

P \{ sup_{1≤t≤l} \frac{W (t)}{\sqrt{t}} ≠ sup_{A_{l}^{2}≤t≤l} \frac{W (t)}{\sqrt{t}}\} = \frac{log A_{l}^{2}}{log l} = \frac{2}{c_{l}} .  (5.23)

Now setting

ξ_{l}^{∗} = a_{l} ( sup_{A_{l}^{2}≤t≤l} \frac{W (t)}{\sqrt{t}} − b_{l})

we have by (5.23)

P (ξ_{l} ≠ ξ_{l}^{∗}) = 2/c_{l}

and thus

E (|ξ_{l} − ξ_{l}^{∗}| ∧ 1) ≤ 2/c_{l} ≤ 2c_{k}/c_{l} ≤ 2(c_{k}/c_{l})^{1/2}.  (5.24)

Hence to prove (5.21) it suffices to show that

E (|ξ_{l}^{∗} − ξ_{k,l}| ∧ 1) ≤ (c_{k}/c_{l})^{1/2}.  (5.25)

Now by k ≤ A_{l} we have

|ξ_{l}^{∗} − ξ_{k,l}| ≤ \frac{|W (k)|}{A_{l}}a_{l}

and thus

E|ξ_{l}^{∗} − ξ_{k,l}|^{2} ≤ \frac{k}{A_{l}^{2}} a_{l}^{2} ≤ \frac{a_{l}^{2}}{A_{l}} ≤ exp (−\sqrt{log l}) ≤ \frac{1}{c_{l}} ≤ \frac{c_{k}}{c_{l}}

which implies (5.25) by the Cauchy-Schwarz inequality. Since the number of pairs (k, l) with 3 ≤ k < l < l_{0} is finite, (5.21) implies that

E (|ξ_{l} − ξ_{k,l}| ∧ 1) ≤ C(c_{k}/c_{l})^{1/2} ≤ C′(log_{+} log_{+}(c_{l}/c_{k}))^{−2} (3 ≤ k < l)

for some constants C > 0, C′ > 0. Hence using Theorem 5 we get that

lim_{N→∞} \frac{1}{D_{N}} ∑_{k=3}^{N} d_{k}I \{a_{k} ( sup_{1≤t≤k} \frac{W (t)}{\sqrt{t}} − b_{k}) < x\} = G(x)  a.s. for any x  (5.26)

where

d_{k} ∼ \frac{1}{2k log k\sqrt{log log k}} ,  D_{N} ∼ \sqrt{log log N}  (5.27)

by d_{k} = log(c_{k+1}/c_{k}) and simple calculations. (Note that ξ_{l}, ξ_{k,l}, c_{k} are defined only for l ≥ k ≥ 3, but this does not cause any difficulty, as we observed in Section 4.) By the theorem of Zygmund mentioned after Theorem 1 the summation procedure belonging to the weights in (5.27) is equivalent to the summation procedure belonging to d_{k}^{∗} = 1/k log k, D_{N}^{∗} ∼ log log N. Hence we proved the following

Theorem J. Let W be a Wiener process. Then

lim_{N→∞} \frac{1}{log log N} ∑_{k=3}^{N} \frac{1}{k log k} I \{a_{k} ( sup_{1≤t≤k} \frac{W (t)}{\sqrt{t}} − b_{k}) < x\} = G(x) a.s. for any x (5.28)

where (a_{n}), (b_{n}) and G(x) are defined by (5.18) and (5.19), respectively.

Using Theorem 6 instead of Theorem 5, the same procedure leads to

lim_{T →∞} \frac{1}{log log T} ∫_{3}^{T} \frac{1}{t log t}I \{a_{t} ( sup_{1≤u≤t} \frac{W (u)}{\sqrt{u}} − b_{t}) < x\} dt = G(x) a.s. for any x.

Using an a.s. invariance principle, it is easy to extend Theorem J for partial sums. Let (X_{n}) be a sequence of independent random variables with mean 0, variance 1 and uniformly bounded (2 + δ)-th moments for some δ > 0; put S_{k} = X_{1} + ⋯ + X_{k}. Then one can define the sequence (X_{n}), together with a Wiener process W, on a suitable probability space such that

S_{n} − W (n) = O(n^{1/2−η})  a.s.  (5.29)

for some constant η > 0. (See e.g. Strassen, 1967.) The last relation easily implies

a_{k} ( max_{(log k)^{3}≤i≤k} \frac{S_{i}}{\sqrt{i}} − sup_{(log k)^{3}≤t≤k} \frac{W (t)}{\sqrt{t}}) → 0  a.s.  (5.30)

where (a_{k}) is defined by (5.18). (Cf. also Oodaira, 1976; Shorack, 1979.) Note that i and t in (5.30) are restricted to the interval [(log k)^{3}, k], but since the LIL implies

sup_{1≤t≤(log k)^{3}} |\frac{W (t)}{\sqrt{t}}| = O(log log log k)^{1/2}) a.s.,

it follows that

a_{k} ( sup_{1≤t≤(log k)^{3}} \frac{W (t)}{\sqrt{t}} − b_{k}) → −∞  a.s.  (5.31)

and thus (5.28) remains valid if we extend the sup only for (log k)^{3} ≤ t ≤ k. Since changing the random variable ξ_{k} by o(1) in (2.12) does not affect the validity of (2.12) (see e.g. Lacey and Philipp, 1990), (5.30) implies that (5.28) holds if sup_{1≤t≤k}(W (t)/\sqrt{t}) is replaced by max_{(log k)^{3}≤i≤k}(S_{i}/\sqrt{i}). Finally, the last maximum can be replaced by max_{i≤k}(S_{i}/\sqrt{i}), as it follows from the the analogue of (5.31) for the (X_{n}). Thus we proved the following result:

Theorem K. Let (X_{n}) be a sequence of independent random variables with mean 0, variance 1 and uniformly bounded (2 + δ)-th moments for some δ > 0. Put S_{k} = ∑_{i≤k} X_{i}. Then

lim_{N→∞} \frac{1}{log log N} ∑_{k=3}^{N} \frac{1}{k log k} I \{a_{k} (max_{i≤k} \frac{S_{i}}{\sqrt{i}} − b_{k}) < x\} = G(x) a.s for any x

where (a_{n}), (b_{n}) and G(x) are defined by (5.18) and (5.19), respectively.

In the case when the random variables X_{n} are i.i.d., the moment conditions in Theorem K can be weakened: in this case the theorem holds under assuming only

EX_{1} = 0,  EX_{1}^{2} = 1,  E (X_{1}^{2} log_{+} log_{+} |X_{1}|) < ∞.  (5.32)

The proof is similar to the above, just in this case instead of (5.29) we use the a.s. invariance principle

S_{n} − W (n) = o (\sqrt{n}(log log n)^{−1/2}) a.s.

valid under (5.32) (see Einmahl, 1987). Observing also that the a.s. invariance principle (5.29) is actually valid for a large class of weakly dependent sequences (X_{n}) (see Philipp and Stout, 1975), it follows that Theorem K also holds in many dependent situations.

Acknowledgements

The authors are indebted to A. Chuprunov, L. Horváth, D. Khoshnevisan and W. Philipp for valuable conversations. Research supported by Hungarian National Foundation for Scientific Research, Grant T 29621.

References

Atlagh, M., 1993. Théorème central limite presque sûr et loi du logarithme itéré pour des sommes de variables aléatoires indépendantes. C. R. Acad. Sci. Paris Sér. I. 316, 929–933.

Atlagh, M., Weber, M., 1992. Un théorème central limite presque sûr relatif à des sous-

suites. C. R. Acad. Sci. Paris Sér. I 315, 203–206. Atlagh, M., Weber, M., 1996. Une nouvelle loi forte des grandes nombres. In: Bergelson,

V., March, P., Rosenblatt, J. (Eds.), Convergence in Ergodic Theory and Probability, W. de Gruyter, Berlin, pp. 41–62.

Berkes, I., 1995. On the almost sure central limit theorem and domains of attraction.

Probab. Theory Related Fields 102, 1–18. Berkes, I., 1998. Results and problems related to the pointwise central limit theorem. In:

Szyszkowicz, B. (Ed.), Asymptotic results in Probability and Statistics (a volume in honour of Miklós Csörgő), Elsevier, Amsterdam, pp. 59–96.

Berkes, I., Csáki, E., Csörgő, S., 1999. Almost sure limit theorems for the St. Petersburg

game. Statist. Probab. Letters 45, 23–30. Berkes, I., Dehling, H., 1993. Some limit theorems in log density. Ann. Probab. 21,

1640–1670. Berkes, I., Dehling, H., 1994. On the almost sure central limit theorem for random variables

with infinite variance. J. Theoret. Probab. 7, 667–680. Berkes, I., Dehling, H., Móri, T.F., 1991. Counterexamples related to the a.s. central limit

theorem. Studia Sci. Math. Hungar. 26, 153-164. Bingham, N.H., Rogers, L.C.G., 1991. Summability methods and almost sure convergence.

In: Bellow, A., Jones, R. (Eds.), Almost Everywhere Convergence II. Academic Press, New York, pp. 69–83.

Brosamler, G., 1988. An almost everywhere central limit theorem. Math. Proc. Cambridge

Phil. Soc. 104, 561–574. Chandrasekharan, K., Minakshisundaram, S., 1952. Typical Means. Oxford University

Press. Cheng, S., Peng, L., Qi, Y., 1998. Almost sure convergence in extreme value theory.

Math. Nachr. 190, 43–50. Csáki, E., Földes, A., 1995. On the logarithmic average of additive functionals. Statist.

Probab. Letters 22, 261–268.

Csörgő, M., Horváth, L., 1992. Invariance principles for logarithmic averages. Math. Proc.

Cambridge Phil. Soc. 112, 195–205. Darling, D., Erdős, P., 1956. A limit theorem for the maximum of normalized sums of

independent random variables. Duke Math. J. 23, 143–155. Darling, D., Kac, M., 1957. On occupation times for Markoff processes. Trans. Amer.

Math. Soc. 84, 444–458. Denker, M., 1985. Asymptotic Distribution Theory in Nonparametric Statistics. F. Vieweg

& Sohn, Braunschweig and Wiesbaden. Dvoretzky, A., Erdős, P., 1951. Some problems on random walk in space. Proc. Second

Berkeley Symp. Math. Statist. Prob., Univ. of California Press, pp. 353–367. Dvoretzky, A., Kiefer, J., Wolfowitz, J., 1956. Asymptotic minimax character of the sample

distribution function and the classical multinomial estimator. Ann. Math. Statist. 27, 642–649.

Einmahl, U., 1987. Strong invariance principles for partial sums of independent random

vectors. Ann. Probab. 15, 1419–1440. Einmahl, U., 1989. The Darling-Erdős theorem for sums of i.i.d. random variables. Probab.

Theory Related Fields 82, 241–257. Fahrner, I., Stadtmüller, U., 1998. On almost sure max-limit theorems. Statist. Probab.

Letters 37, 229–236. Feller, W., 1943. Generalization of a probability limit theorem of Cramér. Trans. Amer.

Math. Soc. 54, 361–372. Fisher, A., 1989. A pathwise central limit theorem for random walks. Preprint. Giné, E., Zinn, J., 1994. A remark on convergence in distribution of U-statistics. Ann.

Probab. 22, 117–125. Horváth, L., Khoshnevisan, D., 1995. Weight functions and pathwise local central limit

theorems. Stochastic Process. Appl. 59, 105–123. Ibragimov, I.A., 1996. On almost sure versions of limit theorems. (In Russian.) Dokl.

Akad. Nauk 350, 301–303. Ibragimov, I.A., Lifshits, M., 1998. On the convergence of generalized moments in almost

sure central limit theorem. Statist. Probab. Letters 40, 343–351. Ibragimov, I.A., Lifshits, M., 1999. On almost sure limit theorems. Th. Probab. Appl.

44, 254–272. Kesten, H., Spitzer, F., 1979. A limit theorem related to a new class of self similar

processes. Z. Wahrsch. Verw. Gebiete 50, 5–25.

Koroljuk, V.S., Borovskich, Yu.V., 1994. Theory of U-statistics. Kluwer, Dordrecht. Lacey, M., Philipp, W., 1990. A note on the almost everywhere central limit theorem.

Statist. Probab. Letters 9, 201–205. Lifshits, M., 2000a. On the difference between CLT and ASCLT. (In Russian) Zapiski

Seminarov POMI 260, 186–201. Lifshits, M., 2000b. An almost sure limit theorem for sums of random vectors. Preprint. Marcus, M., Rosen, J., 1995. Logarithmic averages for the local time of recurrent random

walks and Levy processes. Stochastic Process. Appl. 59, 175–184. Móri, T.F., 1993. On the strong law of large numbers for logarithmically weighted sums.

Ann. Univ. Sci. Budapest. Sect. Math. 36, 35–46. Oodaira, H., 1976. Some limit theorems for the maximum of normalized sums of weakly

dependent random variables. Proc. Third Japan-USSR Symposium on Probability Theory. Lecture Notes Math. No. 550, Springer, Berlin. pp. 467–474.

Peligrad, M., Révész, P., 1991. On the almost sure central limit theorem. In: Bellow, A., Jones, R. (Eds.), Almost Everywhere Convergence II. Academic Press, New York, pp. 209–225.

Philipp, W., Stout, W., 1975. Almost sure invariance principles for partial sums of weakly

dependent random variables. Memoirs of the AMS, No. 161. Rodzik, B., Rychlik, Z., 1994. An almost sure central limit theorem for independent

random variables. Ann. Inst. H. Poincaré 30, 1–11. Rodzik, B., Rychlik, Z., 1996. On the central limit theorem for independent random

variables with almost sure convergence. Probab. Math. Statist. 12, 299–309. Schatte, P., 1988. On strong versions of the central limit theorem. Math. Nachr. 137,

249–256. Serfling, R., 1980. Approximation Theorems of Mathematical Statistics. Wiley, New York. Shorack, G., 1979. Extension of the Darling and Erdös theorem on the maximum of

normalized sums. Ann. Probab. 7, 1092–1096. Strassen, V., 1967. Almost sure behavior of sums of independent random variables and

martingales. Proc. Fifth Berkeley Symp. Math. Statist. Probab., Vol II, Part I, Univ. of California Press, pp. 315–343.

Weigl, A., 1989. Zwei Sätze über die Belegungszeit beim Random Walk. Diplomarbeit, TU Wien.