Ergodic Behaviour of Affine Recursions III

Positive Recurrence and Null Recurrence

Hans G. Kellerer

Mathematisches Institut der Universität München

Theresienstraße 39, D-8000 München 2, Germany

October 30, 1992

Summary. This paper is concerned with the discrete–time Markov process (X_{n})_{n≥0} solving the stochastic difference equation X_{n} = Y_{n}X_{n−1} + Z_{n} for n ∈ N, where (Y_{n}, Z_{n})_{n∈N} is a sequence of i.i.d. random variables independent of the initial variable X_{0} and, in accordance with most applications, the state space is restricted to R_{+}. The study of the recurrent case is completed by distinguishing positive and null recurrence, corresponding to a finite and infinite invariant measure, respectively.

1991 Mathematics Subject Classification. Primary 47A35, 60J05; Secondary 54H20, 60G18, 60G30.

Introduction

This is the final part of work begun in … and continued in …. It studies affine recursions on R_{+}, i.e. sequences (X_{n})_{n≥0} defined by

X_{n} = Y_{n}X_{n−1} + Z_{n} for n ∈ N.

Here, (Y_{n}, Z_{n})_{n∈N} is a sequence of independent identically distributed R_{+}^{2}– valued random variables which is independent of the initial variable X_{0} ≥ 0. Without loss of generality, the common distribution ν of (X_{n}, Z_{n}), n ∈ N, will be assumed to belong to the class N defined in Section 0.

The object of Part II was to study the asymptotic behaviour of (X_{n})_{n≥0} in the recurrent case, i.e. under the assumption that the sequence does not diverge to infinity. A central result assigns an essentially unique invariant measure to (the transition kernel of) a recurrent sequence (X_{n})_{n≥0}. As a consequence mean as well as pointwise ergodic theorems for ratios can be established. Part III strengthens this study by distinguishing positive recurrence and null recurrence; its contents are summarized below.

Section 8. It is only natural to classify the recurrent case further: the sequence (X_{n})_{n≥0} is called “positive recurrent” if the invariant measure is finite and “null recurrent” otherwise. This yields the connection between the present work and the existing literature, because a finite invariant measure can be normalized to a stationary distribution. An example for positive recurrence is the regenerative case (8.3) and a simple necessary condition requires divergence of the associated random walk (S_{n})_{n≥0} to −∞ (8.4). If it exists, the stationary distribution equals the distribution of ∑_{n∈N} Y_{1} … Y_{n−1}Z_{n} (8.2). Employing Kesten’s extension of the strong law of large numbers a criterion for positive recurrence can be established (8.5), which can be shown to be best possible in a sense (8.6). When combined with earlier results, this leads to a very satisfasctory trichotomy: under a weak boundedness condition on Z_{n}, the affine recursion (X_{n})_{n≥0} is positive recurrent resp. null recurrent resp. transient, if the associated random walk (S_{n})_{n≥0} diverges to −∞ resp. oscillates resp. diverges to +∞ (8.7). The section closes with a stability result for the stationary distribution under a uniform boundedness condition for moments of Y_{n} and Z_{n} of some order (8.8).

Section 9. As in classical Markov chain theory positive recurrence can be characterized by weak convergence of the laws L(X_{n}) to the stationary distribution, while in the null recurrent case the total mass disappears to infinity (9.1). In the positive recurrent case the ergodic theorems from Section 7 can be strengthened considerably: Under the stationary distribution the sequence (X_{n})_{n≥0} is actually mixing (9.2), while under an arbitrary initial law almost sure convergence of successive averages holds more generally than for bounded continuous functions (9.3). The second half of this section treats mean passage times. While ascending ladder indices have a finite expectation in any case (9.4), the ergodic behaviour of the sequence is essential for descending ladder indices (9.5). The section closes with an extension of the main criterion for positive/null recurrence from classical Markov chain theory to the topological setting (9.6).

Section 10. Since the moments of a stationary distribution μ, as far as they exist, can be obtained recursively from the mixed moments of Y_{n} and Z_{n} (10.1), it is of interest whether μ is determined by all of the moments ∫ x^{k}dμ, k ∈ N. This leads in a natural way to the weakly contractive case (10.2). The strongly contractive case establishes the connection with self– similarity. It provides one of the rare situations allowing explicit results, for instance concerning uniform distributions (10.3). The second half of this section studies the multiplicative model with Y_{n} ≤ 1, which is important in some applications. Here at least a partial answer concerning the singularity of the stationary distribution is possible (10.4). Finally, the exact order in which an upper limit ∞ is approached by (X_{n})_{n≥0} is derived (10.6).

In conclusion, here are some directions for further research:

— As already mentioned, the extension from R_{+} to R – for some results without difficulties – on the whole is a nontrivial problem.

— It is much easier to keep the state space R_{+} and to deal with other monotone recursions as for instance the process

X_{n} = Y_{n}X_{n−1} ∨ Z_{n} for n ∈ N,

as considered by Goldie [16] and Rachev [34] (for a special case see also Alpuim [1]).

— New problems arise, if the total order in R is given up and R^{k} is considered instead; for some results in the additive model see Elton and Yan [12].

— A multidimensional generalization results also from autoregressive processes of higher order, treated in the context of random matrices for instance by Kesten [24].

— Even more general is a treatment in the framework of topological semigroups as begun by Mukherjea and Tserpes [31] and continued recently in the special case of nonnegative matrices by Mukherjea [30].

— There are, moreover, attempts to weaken the asumption on the sequence (Y_{n}, Z_{n})_{n∈N} to stationarity and ergodicity; here Borovkov [4] and Brandt [5] have to be mentioned.

— Finally, it is only natural to ask for continuous–time analogues; for these Wolfe [40] and de Haan and Karandikar [19] may be consulted.

8. Positive recurrence and null recurrence

A further classification in the recurrent case is suggested by (5.6):

(8.1) Definition. Let ν be recurrent with invariant measure μ. Then the distribution ν (or the kernel P or the process (X_{n})_{n≥0}) is called (a) “positive recurrent” if μ(R_{+}) < ∞,

(b) “null recurrent” if μ(R_{+}) = ∞.

The simplest example for positive recurrence is provided by the case \overline{x} < ∞, in which the support of μ is bounded. A first general criterion, derived under moment conditions but not restricted to the case Y, Z ≥ 0, was given by Vervaat [39]. In the present framework it is easily established:

(8.2) Theorem. ν is positive recurrent if and only if

W := ∑_{n∈N} Y_{1} … Y_{n−1}Z_{n} < ∞ a.s.

In this case the stationary distribution is given by L(W).

Proof. 1. If the invariant measure μ is finite, μ ∈ M_{1}(R_{+}) may be assumed as well. Under the initial law μ the sequence (X_{n})_{n≥0} is stationary, and with the dual sequence (W_{n})_{n≥0}, defined in Section 0, this implies by monotonicity

μ([0, t]) = (lim inf_{n→∞}) ∫ P(X_{n}^{x} ≤ t) μ(dx)
≤ lim inf_{n→∞} P(X_{n}^{0} ≤ t)
= lim inf_{n→∞} P(W_{n} ≤ t)
= P(W ≤ t)
≤ P(W < ∞),

which for t → ∞ yields the assertion.

2. To prove the converse, let (Y_{0}, Z_{0}) be independent of (Y_{n}, Z_{n}), n ∈ N, with distribution ν. Then Z_{0} + Y_{0}W is distributed as W, hence μ = L(W) is a stationary distribution for P. Moreover, the recurrence of ν is a consequence of (2.2b), because the potential kernel G := ∑_{n≥0} P^{n} satisfies by monotonicity

G(0; [0, t]) ≥ ∫ G(x; [0, t]) μ(dx)
= ∑_{n≥0} (μP^{n})([0, t])
= ∑_{n≥0} μ([0, t]) for all t ≥ 0. □

To derive the stationary distribution μ associated with a positive recurrent distribution ν, (8.2) is not of much use. For some explicit examples, obtained by an ad hoc principle in the framework of exponential families, see [7].

The next result strengthens (2.3):

(8.3) Proposition. ν is positive recurrent whenever P(Y = 0) > 0.

Proof. Since Y_{n} = 0 for some n ∈ N with probability 1, the series in (8.2) is a finite sum almost surely. □

In this context it is worthwhile to point out the following:

— The stationary distribution μ can be computed, at least in principle, from the probabilities p := P(Y = 0) and q := 1 − p and the distributions ν_{0} and ν′ of (Y, Z) under the condition Y = 0 and Y ≠ 0, respectively (the assumption q ≠ 0 is no real restriction). To this end let (Y_{0}, Z_{0}) and (Y′_{n}, Z′_{n}), n ∈ N, be independent with distributions ν_{0} and ν′, respectively, and denote by W′_{n} the analogue of W_{n} with (Y′_{m}, Z′_{m}), m < n, replacing (Y_{m}, Z_{m}), m < n, and (Y_{0}, Z_{0}) replacing (Y_{n}, Z_{n}). Then it is easily seen that

μ = ∑_{n∈N} p q^{n−1}μ′_{n} with μ′_{n} := L(W′_{n}).

— While in the null recurrent case the hypotheses of (6.4) are satisfied and thus the invariant measure is nonatomic, in the positive recurrent case the mass μ({0}) of the stationary distribution can be computed from the equation

μ({0}) = (μ ⊗ ν)({(x; y, z) : yx + z = 0})
= μ({0}) P(Z = 0) + μ(]0, ∞[) P(Y = 0 = Z),

resulting in

μ({0}) = P(Y = 0 = Z) / (1 − P(Y ≠ 0 = Z)).

— If Y is restricted to the values 0 and 1, then the Laplace transform ψ of μ can be computed from (5.7). To this end let χ_{i} denote the Laplace transform of the distribution of Z under the condition Y = i (i = 0, 1). Then ψ(0) = 1 leads to

ψ(u) = P(Y = 0) χ_{0}(u) / (1 − P(Y = 1) χ_{1}(u))

(for a related result see [39]).

Next, the analogue of (2.4) can be stated, providing a necessary condition for positive recurrence instead of a sufficient condition for transience:

(8.4) Proposition. If ν is positive recurrent, then S_{n} → −∞.

Proof. Assuming sup_{n≥0} S_{n} = +∞, consider the random times T_{1} < T_{2} < … when (S_{n})_{n≥0} hits R_{+} (being defined with probability 1). Since T_{k}, k ∈ N, are stopping times with respect to (Y_{n}, Z_{n})_{n∈N}, the random variables Z_{T_{k} +1}, k ∈ N, are independent and distributed as Z. Thus

W ≥ ∑_{k∈N} Y_{1} … Y_{T_{k}}Z_{T_{k} +1} ≥ ∑_{k∈N} Z_{T_{k} +1}

diverges almost surely and (8.2) yields a contradiction. □

That the converse of (8.4) does not hold in general is an immediate consequence of (2.5).

A first criterion for P(W < ∞) = 1 appears in [27] under the assumption E(log Y) < 0, ensuring S_{n} → −∞. Later its sufficiency was shown by Vervaat [39] along the same lines but under a weaker moment assumption. Employing Kesten’s extension of the strong law of large numbers, this assumption actually can be dropped completely:

(8.5) Theorem. If S_{n} → −∞, then the condition

E(log_{+}Z) < ∞

(a) is always sufficient for positive recurrence,

(b) is necessary for positive recurrence whenever E(| log Y |) < ∞.

Proof. Applying Borel–Cantelli it follows easily that

lim sup_{n→∞} \frac{1}{n} log_{+}Z_{n} \left\{{= 0 a.s. if E(log_{+}Z) < ∞, \atop = +∞ a.s. if E(log_{+}Z) = ∞.}\right\}

Applying [23], moreover, it follows from the hypothesis S_{n} → −∞ that

lim_{n→∞} \frac{1}{n} ∑_{1≤m<n} log Y_{m} \left\{{∈ ] − ∞, 0 [ a.s. if E(| log Y |) < ∞, \atop = −∞ a.s. if E(| log Y |) = ∞,}\right\}

because the trichotomy for (S_{n})_{n≥0} carries over to (S_{n}/n)_{n∈N} in the case

E(log_{−}Y) = ∞ = E(log_{+}Y).

Therefore

(1) lim sup_{n→∞} (Y_{1} … Y_{n−1}Z_{n})^{\frac{1}{n}} < 1 a.s. whenever E(log_{+}Z) < ∞,

while

(2) lim sup_{n→∞} (Y_{1} … Y_{n−1}Z_{n})^{\frac{1}{n}} = ∞ a.s. whenever E(log_{+}Z) = ∞,

if in this case E(| log Y |) < ∞ holds in addition. Clearly, (1) and (2) imply almost sure convergence and divergence of W, respectively, and the assertion follows from (8.2). □

Specialized to Y = γ ∈]0, 1[ and combined with (3.1), this result shows that even in the additive model all three possibilities – transience, null recurrence, positive recurrence – really occur.

The statement of (8.5b) is best possible in some sense. However large Z may be, Y can be made small enough for positive recurrence without attaining the value 0, even if in addition independence of Y and Z is postulated. More precisely, (2.5) has the following counterpart:

(8.6) Proposition. For any ν_{z} ∈ M_{1}(R_{+}) with ν_{z}({0}) ≠ 1 there exists ν_{y} ∈ M_{1}(R_{+}) with ν_{y}({0}) = 0 and ν_{y}({1}) ≠ 1 such that ν = ν_{y} ⊗ ν_{z} is positive recurrent.

Proof. Let Z_{n}, n ∈ N, be independent with distribution ν_{z}. Then choose sequences (z_{n})_{n∈N}, (y_{n})_{n∈N}, (p_{n})_{n∈N} satisfying

(1) ∑_{n∈N} q_{n} < ∞ with q_{n} := P(Z > z_{n}),

(2) 1 = y_{0} > y_{1} > … → 0 and ∑_{n∈N} y_{n}z_{n} < ∞, (3) 0 = p_{0} < p_{1} < … → 1 and ∑_{n∈N} p_{n}^{n−1} < ∞

(e.g. p_{n} = n^{−2/(n−1)} for n > 1). Independently of Z_{n}, n∈N, let now Y_{n}, n∈N, be independent with a distribution ν_{y} such that

P(Y > y_{n}) = p_{n} for n ≥ 0.

Then 0 < Y ≤ 1 and thus

P(Y_{1} … Y_{n−1}Z_{n} > y_{n}z_{n}) ≤ P(Y_{1}, …, Y_{n−1} > y_{n}) + P(Z_{n} > z_{n})
= p_{n}^{n−1} + q_{n} for n ∈ N.

Therefore, by the summability in (1) and (3), with probability 1

Y_{1} … Y_{n−1}Z_{n} ≤ y_{n}z_{n} for almost all n ∈ N,

hence, by the summability in (2), the assertion follows from (8.2). □

Now the close relationship between the behaviour of an affine recursion (X_{n})_{n≥0} and the associated random walk (S_{n})_{n≥0} can be summarized. Under a weak boundedness condition on Z, satisfied for instance in the multiplicative model, there is in fact a bijection:

(8.7) Theorem. With arbitrary α > 0 let one of the following two conditions be satisfied:

(a) E(Z^{α} | Y) ≤ γ for some γ < ∞,

(b) P(Y = 0) = 0 and E((\frac{Z}{Y} )^{α}) < ∞.

Then the following trichotomy holds:

S_{n} → +∞ ⟹ ν transient,
S_{n} → ±∞ ⟹ ν null recurrent,
S_{n} → −∞ ⟹ ν positive recurrent.

Proof. 1. Clearly, α ≤ 1 may be assumed and α = 1 will be considered first. Then the case S_{n} → +∞ is settled by (2.4), while the case S_{n} → ±∞ follows from (8.4). Thus it remains to consider the case S_{n} → −∞. Under condition (a) clearly E(log_{+}Z) < ∞ and (8.5a) applies, while under condition (b) similarly E(log_{+}(Z/Y)) < ∞. In view of

W = ∑_{n∈N} Y_{1} … Y_{n} \frac{Z_{n}}{Y_{n}}

the assertion follows from (8.2) as in the proof of (8.5).

2. For α < 1 the transient case is again settled by (2.4), because the passage from (Y′, Z′) = (Y^{α}, Z^{α}) to (Y, Z) does not affect the asymptotic behaviour of the associated random walk. The recurrent case follows from the inequalities

Z_{1}Y_{2} … Y_{n} + … + Z_{n} ≤ (Z′_{1}Y′_{2} … Y′_{n} + … + Z′_{n})^{\frac{1}{α}} ,
Z_{1} + … + Y_{1} … Y_{n−1}Z_{n} ≤ (Z′_{1} + … + Y′_{1} … Y′_{n−1}Z′_{n})^{\frac{1}{α}} .

Indeed, if \underline{x}′ and W′ denote the analogues of \underline{x} and W, this means

\underline{x} ≤ (\underline{x}′)^{\frac{1}{α}} and W ≤ (W′)^{\frac{1}{α}} . □

It should be mentioned that conditions (a) and (b) according to (3.4) can be simplified to

E(Z^{α}) < ∞ for some α > 0,

provided Y and Z are independent or Y is bounded away from 0.

This section will be concluded by a stability result. Related, but not comparable, conditions for continuous dependence of μ on ν can be found in [5] (see also [6], chapter 9.1). The following result strengthens (6.5):

(8.8) Proposition. Let N ∋ ν_{k} →^{w} ν and ν_{k} be positive recurrent with stationary distributions μ_{k} such that

γ := sup_{k∈N} ∫ y^{α} dν_{k} < 1 and δ := sup_{k∈N} ∫ z^{α} dν_{k} < ∞

for some α > 0. Then

(a) ν is positive recurrent,

(b) μ_{k} →^{w} μ,

where μ is the stationary distribution associated with ν.

Proof. (a) In view of the weak convergence

∫ y^{α} dν ≤ γ and ∫ z^{α} dν ≤ δ,

which by the hypotheses on γ and δ (and Jensen’s inequality) yields

−∞ ≤ ∫ log y dν < 0 and ∫ log_{+}z dν < ∞.

Thus ν is positive recurrent according to (8.5a).

(b) Since the L_{p}–norms increase with the order, clearly α ≤ 1 may be assumed. In this case

∫ x^{α} dμ_{k} = ∫ ∫ (xy + z)^{α} μ_{k}(dx) ν_{k}(dy, dz)
≤ ∫ ∫ ((xy)^{α} + z^{α}) μ_{k}(dx) ν_{k}(dy, dz)
≤ (∫ x^{α} dμ_{k}) γ + δ,

which implies

sup_{k∈N} ∫ x^{α} dμ_{k} ≤ \frac{δ}{1 − γ} < ∞.

In view of α > 0, therefore, the sequence (μ_{k})_{k∈N} is uniformly tight in M_{1}(R_{+}) and each limit point μ is excessive with respect to ν according to (4.6), because weak convergence implies vague convergence. The assertion thus follows from (5.6). □

In this result the conditions on γ and δ both can be shown to be essential. The following counterexamples resemble those in [5], represent, however, even more extreme situations. In both cases the notation P_{k} refers to ν_{k}.

(1) P_{k}(Z = \frac{k}{y^{k}}) = \frac{1}{\sqrt{k}} , P_{k}(Z = z) = 1 − \frac{1}{\sqrt{k}}

with z > 0 and Y = y ∈]0, 1[ yield positive recurrent ν_{k}, k ∈ N, such that

ν_{k} →^{w} ε_{(y,z)} and μ_{k} →^{w} ε_{∞}.

The first convergence is clear and the second one follows from

P_{k}(W ≤ k) ≤ P_{k}(Z_{i} = z for 1 ≤ i ≤ k)
= (1 − \frac{1}{\sqrt{k}})^{k} → 0.

(2) P_{k}(Y = 0) = \frac{1}{k^{3}} , P_{k}(Y = \frac{1}{k}) = 1 − \frac{1}{k}, P_{k}(Y = k^{(k^{2})}) = \frac{1}{k} − \frac{1}{k^{3}}

and Z = 1 yield positive recurrent ν_{k}, k ∈ N, such that

ν_{k} →^{w} ε_{(0,1)} and μ_{k} →^{w} ε_{∞}.

Again the first convergence is clear, while the second one follows from

P_{k}(W < k) ≤ P_{k}(Y_{1} … Y_{k^{2}} < k)
≤ P_{k}(⋃_{1≤i≤k^{2}}\{Y_{i} = 0\}) + P_{k}(⋂_{1≤i≤k^{2}}\{Y_{i} = \frac{1}{k}\})
= 1 − (1 − \frac{1}{k^{3}} )^{k^{2}} + (1 − \frac{1}{k})^{k^{2}} → 0.

9. Further ergodic theorems

The mean ergodic theorem (7.1) can be strengthened to weak convergence in the positive recurrent case, holding in an extended sense also in both the other cases. This is a consequence of more general results in [18], but for the state space R_{+} a direct proof is too simple to refer to other work. In the present framework the following holds, independently of the initial law:

(9.1) Theorem. If μ_{n} := L(X_{n}) for n ≥ 0, then

(a) μ_{n} →^{w} μ,

whenever ν is positive recurrent with stationary distribution μ,

(b) μ_{n} →^{w} ε_{∞}, i.e. μ_{n}([0, t]) → 0 for all t < ∞,

whenever ν is null recurrent or transient.

Proof. (a) By bounded convergence (2.6) implies

μ_{n}f − μf = E(∫ (f(X_{n}) − f(X_{n}^{x})) μ(dx)) → 0 for all f ∈ K(R_{+}).

(b) It follows from the representation

W = Z_{1} + … + Y_{1} … Y_{n−1}(Z_{n} + Y_{n}Z_{n+1} + …) for n ∈ N

that the event {W = ∞} is contained in (the completion of) the tail–field of (Y_{n}, Z_{n})_{n∈N}, because P(Y = 0) = 0 by (8.3). Therefore W = ∞ a.s. by (8.2) and this implies by monotonicity

μ_{n}([0, t]) ≤ P(X_{n}^{0} ≤ t)
= P(W_{n} ≤ t)
→ P(W ≤ t) = 0 for all t < ∞. □

Clearly, (9.1) strengthens (7.6) in the positive recurrent case. Moreover, the condition “X finite–valued” in (1.4b) can now be replaced by the condition P(X = ∞) ≠ 1, because convergence in probability implies weak convergence.

The pointwise ergodic theorem for the positive recurrent case can be derived from (7.4). To obtain it for as many functions as possible, it is, however, preferable to establish first ergodicity under stationarity. Actually a stronger result holds:

(9.2) Proposition. If the process (X_{n})_{n≥0} is stationary, it is mixing.

Proof. 1. Extending (Y_{n}, Z_{n}), n ∈ N, let (Y_{n}, Z_{n}), n ∈ Z, be independent with distribution ν. Then by (8.2)

X′_{n} := ∑_{−∞<m≤n} Z_{m}Y_{m+1} … Y_{n} < ∞ a.s.

and, moreover, μ = L(X′_{n}) is the stationary distribution. Since

X′_{n} = X′_{n−1}Y_{n} + Z_{n} for n ∈ N,

the processes (X_{n})_{n≥0} and (X′_{n})_{n≥0} have the same distribution and it suffices to prove the assertion for (X′_{n})_{n≥0}.

2. Denote by σ and σ′ the shift in ∏_{n∈Z} R_{+}^{2} and in ∏_{n≥0} R_{+}, respectively, and consider the mapping

τ : (y_{n}, z_{n})_{n∈Z} → (∑_{−∞<m≤n} z_{m}y_{m+1} … y_{n})_{n≥0}

from ∏_{n∈Z} R_{+}^{2} to ∏_{n≥0} R_{+}. It is compatible with σ and σ′, i.e.

τ ∘ σ = σ′ ∘ τ.

Therefore the mixing property of σ with respect to the measure ⨂_{n∈Z} ν carries over to σ′ with respect to its image by τ. Since this is the distribution of (X′_{n})_{n≥0}, the assertion follows. □

In the case P(Y = 0) > 0 it can be shown that (9.2) holds in the stronger sense of (X_{n})_{n≥0} having a trivial tail–field. This can fail extremely in the general case, as is seen by the following example:

Y = 1/2 and P(Z = 0) = 1/2 = P(Z = 1)

obviously represents the simplest nontrivial positive recurrent case. Here (X_{n})_{n≥0} is stationary, if the initial law is the uniform distribution on [0,2]. Since X_{n−1} can be reconstructed from X_{n} via

X_{n−1} = 2 (X_{n} − 1_{{X_{n}>1}}) a.s.,

the tail–field of (X_{n})_{n≥0} coincides in this case with the full σ–algebra generated by (X_{n})_{n≥0} (modulo null sets).

Now the pointwise ergodic theorem is a simple consequence. Related results in the context of Lipschitz maps can be found in [3], [10], [11]. In the present framework the following is true, again independently of the initial law:

(9.3) Theorem. Let ν be positive recurrent with stationary distribution μ and f be μ–integrable. Then the convergence

\frac{1}{n} ∑_{0≤m<n} f(X_{m}) → μf a.s.

holds under each of the following conditions:

(a) f ∈ C_{μ}(R_{+}),

(b) f uniformly continuous (with respect to Euclidean metric).

Proof. 1. If μ_{0} := L(X_{0}) equals μ, the process (X_{n})_{n≥0} is ergodic by (9.2), hence the asserted convergence holds without any further condition on f. This extends to arbitrary μ_{0} by (2.6), if f is restricted to K(R_{+}).

2. If f ∈ C_{μ}(R_{+}) and for the moment 0 ≤ f ≤ 1 is assumed, monotone approximation from K(R_{+}) yields the inequality

lim inf_{n→∞} \frac{1}{n} ∑_{0≤m<n} f(X_{m}) ≥ μf a.s.

and its counterpart for 1 − f. Both inequalities together, in view of μ1 = 1, prove the assertion under condition (a), because the assumption 0 ≤ f ≤ 1 is easily removed.

3. Under condition (b)

f(X_{n}^{x_{1}}) − f(X_{n}^{x_{2}}) → 0 a.s. for all x_{i} ∈ R_{+}

follows from

X_{n}^{x_{1}} − X_{n}^{x_{2}} = (x_{1} − x_{2}) e^{S_{n}} → 0 a.s.,

which in turn follows from (8.4). Thus the initial law μ_{0} is irrelevant for the asserted convergence. □

Applying (9.3) to a countable dense subset of the normed space K(R_{+}) yields as usual

\frac{1}{n} ∑_{0≤m<n} ε_{X_{m}} →^{w} μ a.s.,

i.e. the stationary distribution is the weak limit of the empirical distributions almost surely.

As an important special case (9.3b) yields the strong law of large numbers for the process (X_{n})_{n≥0}, stating

\frac{1}{n} ∑_{0≤m<n} X_{m} → ∫ x dμ a.s.

and holding also, if the integral is infinite.

While in the case P(Y = 0) > 0 the conditions (a) and (b) can be shown to be superfluous, in the general case (9.3) can hardly be improved. Indeed convergence can fail, if f is assumed to be μ–integrable and continuous only, as is seen by the following example:

ν = p ε_{(1/2 , 1)} + q ε_{(2 , 0)} with 0 < q < p < 1

is obviously positive recurrent with \underline{x} = 2 and \overline{x} = ∞. For μ_{0} = ε_{0} consider the random times

T_{k} := inf{n ∈ N : X_{n} ≥ 2^{k}} for k ∈ N.

Since X_{n} < 2^{k} implies X_{n+1} < 2^{k+1}, they satisfy T_{1} < T_{2} < …, both with probability 1. Choose n_{k} ∈ N such that

(1) lim sup_{k→∞} P(T_{k} ≤ n_{k}) = 1

and consider the sets

A_{k} := {x : P(T_{k} ≤ n_{k}, X_{T_{k}} = x) > 0}.

Since A_{k} is a finite subset of

B_{k} := [2^{k}, 2^{k+1}[

and the stationary distribution μ is nonatomic by (6.4), a continuous function f : R_{+} → R_{+} can be constructed such that

(2) f(x) ≥ k n_{k} for x ∈ A_{k},

(3) ∫_{B_{k}} f dμ ≤ 2^{−k} for k ∈ N.

Then by (2) the sequence

V_{n} := \frac{1}{n} ∑_{1≤m≤n} f(X_{m}) for n ∈ N

satisfies

P(lim sup_{n→∞} V_{n} = ∞) ≥ P(lim sup_{k→∞} {V_{T_{k}} ≥ k})
≥ P(lim sup_{k→∞} {T_{k} ≤ n_{k}}),

where the last inequality follows from

V_{T_{k}} ≥ \frac{1}{T_{k}} f(X_{T_{k}}) ≥ k for T_{k} ≤ n_{k}.

In view of (1) this implies

lim sup_{n→∞} V_{n} = +∞ a.s.,

while by (3) on the other hand μf ≤ 1.

The rest of this section treats mean passage times, where first the region above and below the initial level will be considered. Whether ν is recurrent or transient, the ascending ladder indices have a finite expectation:

(9.4) Proposition. Let T_{B} denote the – possibly infinite – hitting time of a set B ∈ B(R_{+}) by (X_{n})_{n≥0}. Then, for arbitrary x < \overline{x},

E^{x}(T_{[x,∞[}) < ∞.

Proof. Due to x < \overline{x} there exists n ∈ N such that

ϑ := P(X_{n}^{0} ≥ x) > 0.

Since by monotonicity

{T_{[x,∞[} > kn} ⊂ {X_{n} < x, …, X_{kn} < x}
⊂ {X_{n}^{0} < x, …, X_{kn}^{0} < x}
⊂ ⋂ _{0≤i<k} {Z_{in+1}Y_{in+2} … Y_{in+n} + … + Z_{in+n} < x},

independence implies

P(T_{[x,∞[} > kn) ≤ (P(X_{n}^{0} < x))^{k} = (1 − ϑ)^{k} for k ≥ 0.

Therefore the assertion holds for any initial distribution. □

The following counterpart of (9.4) distinguishes positive and null recurrence:

(9.5) Proposition. Let T_{B} be defined as in (9.4) and ν be recurrent. Then, for arbitrary x > \underline{x},

(a) E^{x}(T_{[0,x]}) < ∞ whenever ν is positive recurrent,

(b) E^{x}(T_{[0,x]}) = ∞ whenever ν is null recurrent.

Proof. (a) Let μ be the stationary distribution and L(X_{0}) = μ. Then it follows from the recurrence theorem by Kac [21] that

E(T_{[0,x]} | X_{0} ≤ x) = (μ([0, x]))^{−1}.

Since by (5.2a) the hitting distribution on [0, x] equals the distribution of X_{0} under the condition X_{0} ≤ x, by induction this equation can be extended to the k–th hitting time T_{k} of [0, x], i.e.

E(T_{k} | X_{0} ≤ x) = k (μ([0, x]))^{−1}.

This implies all that is needed in the sequel, namely

(1) ∫ _{{X_{0}≤x}} T_{k} dP < ∞ for all k ∈ N.

Now x < \overline{x} may be assumed, because otherwise E^{x}(T_{[0,x]}) = 1 by (1.2b). Under this assumption there exists k ∈ N such that

(2) P(X_{0} ≤ x < X_{k}) > 0.

By the inequality

T := inf{n > k : X_{n} ≤ x} ≤ T_{k+1},

with μ_{0,k} denoting the distribution of (X_{0}, X_{k}), and by monotonicity it follows that

∫ _{{X_{0}≤x}} T_{k+1} dP ≥ ∫ _{{X_{0}≤x<X_{k}}} T dP
= ∫ _{x_{0}≤x<x_{k}} (k + E^{x_{k}}(T_{[0,x]})) μ_{0,k}(dx_{0}, dx_{k})
≥ P(X_{0} ≤ x < X_{k}) E^{x}(T_{[0,x]}).

This proves the assertion in view of (1) and (2).

(b) Let μ be the invariant measure and x < t < ∞. Then

μ′(B) := (μ([0, t]))^{−1}μ(B) for B ∈ B([0, t])

by (5.2a) defines a stationary distribution with respect to ^{t}P. Now let X_{0} be distributed according to (the trivial extension of) μ′ and let T′ denote the hitting time of [0, x] by (^{t}X_{n})_{n≥0}. Then it is obvious that

T′ ≤ T_{[0,x]},

and it follows from the above–mentioned theorem by Kac that

∫ _{{X_{0}≤x}} T′dP = 1.

By monotonicity this implies

1 = ∫ _{x_{0}≤x} E^{x_{0}}(T′) μ′(dx_{0})
≤ ∫ _{x_{0}≤x} E^{x_{0}}(T_{[0,x]}) μ′(dx_{0})
≤ μ′([0, x]) E^{x}(T_{[0,x]}),

hence

μ([0, t]) ≤ μ([0, x]) E^{x}(T_{[0,x]}).

In view of μ([0, x]) < ∞ the assertion follows for t → ∞. □

Since P^{x}(T_{[0,x]} < ∞) = 1 obviously implies \underline{x} ≤ x, in the transient case the equation E^{x}(T_{[0,x]}) = ∞ holds for all x ∈ R_{+}.

The next result concerns mean recurrence times and makes again essential use of the monotonicity:

(9.6) Theorem. Let T_{B} be defined as in (9.4) and ν be recurrent with invariant measure μ. Then, for arbitrary x ∈ supp μ, ν is positive recurrent if and only if

E^{x}(T_{G}) < ∞ for all open subsets G of R_{+} containing x.

Proof. 1. Let ν be positive recurrent and consider first the case x = 0. Then G = [0, 2ε[ may be assumed, which yields by (9.5a)

E^{0}(T_{G}) ≤ E^{ε}(T_{G}) ≤ E^{ε}(T_{[0,ε]}) < ∞.

In the case x > 0 similarly G = ]x−ε, x+ε[ ⊂ R_{+} may be assumed. Choose first G′ = ]x−ε′, x+ε′[ with arbitrary ε′ ∈]0, ε[. In view of μ(G′) > 0 it follows as in the proof of (9.5a) that

(1) E^{x′}(T_{G′}) < ∞ for some x′ ∈ G′.

For fixed ω ∈ Ω consider now n ∈ N with X_{n}^{x′}(ω) ∈ G′. Then the inequality

|X_{n}^{x}(ω) − X_{n}^{x′}(ω)| = |x − x′| ∏_{1≤m≤n} Y_{m}(ω)
≤ ε′ \frac{1}{x′} (x′ ∏_{1≤m≤n} Y_{m}(ω))
< ε′ \frac{1}{x − ε′} (x + ε′)

in view of |X_{n}^{x′}(ω) − x| < ε′ implies that

|X_{n}^{x}(ω) − x| < ε′ (\frac{x + ε′}{x − ε′} + 1) = \frac{2ε′x}{x − ε′} .

Therefore by (1)

E^{x}(T_{G}) ≤ E^{x′}(T_{G′}) < ∞ for \frac{2ε′x}{x − ε′} ≤ ε,

where the last condition is satisfied for sufficiently small ε′.

2. To prove the converse suppose only

E^{x}(T_{[0,t]}) < ∞ for all t > x.

Assuming now ν not to be positive recurrent implies

(2) P(Y x + Z > t) = 0 for all t > x.

Indeed, with μ_{1} := L(X_{1}^{x}) monotonicity yields

E^{x}(T_{[0,t]}) ≥ ∫ _{s>t} E^{s}(1 + T_{[0,t]}) μ_{1}(ds)
≥ P(Y x + Z > t) E^{t}(T_{[0,t]}),

where E^{t}(T_{[0,t]}) = ∞ by (9.5b). Letting t ↓ x in (2) leads to

P(Y x + Z ≤ x) = 1,

hence by (1.2b) to \overline{x} ≤ x < ∞. This implies positive recurrence and thus a contradiction to the assumption. □

Together, (9.1) and (9.6) show that the two main characterizations of positive/null recurrence from classical Markov chain theory in essence carry over to affine recursions.

10. The contractive case

As outlined in Section 5 it is in general impossible to determine the invariant measure μ of a recurrent distribution ν explicitly. In spite of (8.2) this holds as well for the stationary distribution in the positive recurrent case (for an exception see (10.3)). This is compensated to some extent by the fact that, due to the algebraic form of the underlying recursion, the moments of μ can be easily computed from those of ν, as far as they exist. The following simple criterion for their existence extends a result by Vervaat [39]:

(10.1) Proposition. Let (X_{n})_{n≥0} be stationary and 0 < α < ∞. Then

E(X_{n}^{α}) < ∞

if and only if

E(Y^{α}) < 1 and E(Z^{α}) < ∞.

Proof. With W as defined in (8.2) it follows from

E(W^{α}) = sup_{n∈N} E((Z_{1} + … + Y_{1} … Y_{n−1}Z_{n})^{α})

by elementary inequalities that

E(W^{α}) \{ {≤ \atop ≥} \} ∑_{n∈N} (E(Y^{α}))^{n−1} E(Z^{α}) for α \{ {≤ \atop ≥} \} 1,

while on the other hand

W = sup_{n∈N} (Z_{1} + … + Y_{1} … Y_{n−1}Z_{n})

by Minkowski’s inequality implies

∥W ∥_{α} \{ {≥ \atop ≤} \} ∑_{n∈N} ∥Y ∥_{α}^{n−1} ∥Z∥_{α} for α \{ {≤ \atop ≥} \} 1.

This proves the assertion in view of E(Z^{α}) ≠ 0 resp. ∥Z∥_{α} ≠ 0. □

For α = 1 the bounds in the proof coincide and yield the equation

E(X_{n}) = E(Z) / (1 − E(Y)).

If finite, moments of any order k ∈ N can be computed from

∫ x^{i} dμ = ∫ ∫ (xy + z)^{i} μ(dx) ν(dy, dz) for 1 ≤ i ≤ k,

a system of linear equations that can be solved recursively due to ∫ y^{i} dν < 1.

Two further comments are in order:

— The existence of moments of some order is clearly related to the tail– behaviour of μ. For relevant results see the papers by Kesten [24] and Goldie [16].

— (10.1) does not extend to the case α = ∞. While ∥Y ∥_{∞} < 1 and ∥Z∥_{∞} < ∞ obviously imply \overline{x} < ∞, conversely this condition yields only ∥Y ∥_{∞} ≤ 1 and ∥Z∥_{∞} < ∞ (consider for instance the case N = {(1, 0), (0, 1)}, where μ = ε_{1} according to (1.4)).

In view of (10.1) it is of interest, under which conditions μ has an exponential moment and is thus determined by its moments of natural order. Here contractivity enters:

(10.2) Proposition. Let (X_{n})_{n≥0} be stationary. Then

E(e^{uX_{n}}) < ∞ for some u > 0

if and only if

Y ≤ 1 and E(e^{uZ}) < ∞ for some u > 0.

Proof. 1. The conditions on Y and Z are necessary, because E(X_{n}^{k}) < ∞ for all k ∈ N implies by (10.1)

∥Y ∥_{∞} = lim_{k→∞} ∥Y ∥_{k} ≤ 1,

while E(e^{uZ}) < ∞ is immediate from Z_{1} ≤ X_{1}.

2. To prove sufficiency, consider first the special case Y ≤ ϑ < 1. With W as defined in (8.2) this yields the estimate

E(e^{uW}) ≤ E(exp (u ∑_{n∈N} ϑ^{n−1}Z_{n}))
= ∑_{k≥0} \frac{u^{k}}{k!} ∥∑_{n∈N} ϑ^{n−1}Z_{n}∥_{k}^{k}

≤ ∑_{k≥0} \frac{u^{k}}{k!} (∑_{n∈N} ϑ^{n−1}∥Z_{n}∥_{k})^{k}
= ∑_{k≥0} \frac{1}{k!} (\frac{u}{1−ϑ})^{k} E(Z^{k})
= E(e^{uZ/(1−ϑ)}) for u ≥ 0,

i.e. if u is suited for Z, then (1−ϑ)u is suited for W.

3. To reduce the general case to this situation a partition into random blocks will be used, which is dual to that one used in the proof of (3.2). Applying P(Y = 1) < 1 choose ϑ < 1 satisfying P(Y > ϑ) < 1 and denote by 0 = T_{0} < T_{1} < … the random times with Y_{n} ≤ ϑ (being defined with probability 1). Now define

Y′_{k} := Y_{T_{k−1} +1} … Y_{T_{k}},
Z′_{k} := Z_{T_{k−1} +1} + … + Y_{T_{k−1} +1} … Y_{T_{k}−1}Z_{T_{k}}.

Since (T_{k})_{k≥0} is a process with independent and identically distributed increments, the random variables (Y′_{k}, Z′_{k}), k ∈ N, are independent with a distribution ν′ ∈ N, where

(1) ∑_{k∈N} Y′_{1} … Y′_{k−1}Z′_{k} = W.

With T := T_{1} they have in addition the properties

(2) Y′ ≤ ϑ,

E(e^{uZ′}) ≤ E(e^{u(Z_{1}+...+Z_{T})})
= ∑_{n∈N} E (∏_{1≤m<n} 1_{{Y_{m}>ϑ}} e^{uZ_{m}}1_{{Y_{n}≤ϑ}} e^{uZ_{n}})
= ∑_{n∈N} (ψ_{1}(u))^{n−1}ψ_{2}(u),

where

ψ_{1}(u) := E(1_{{Y >ϑ}} e^{uZ}) → P(Y > ϑ) for u → 0,
ψ_{2}(u) := E(1_{{Y ≤ϑ}} e^{uZ}) ≤ E(e^{uZ}) for all u ≥ 0.

For u_{0} > 0 with ψ_{1}(u_{0}) < 1 and ψ_{2}(u_{0}) < ∞ this yields

(3) E(e^{u_{0}Z′}) ≤ ψ_{2}(u_{0}) / (1 − ψ_{1}(u_{0})) < ∞.

By (1) – (3) the reduction to the special case is settled. □

The simplest example for the situation of (10.2) is provided by the case \overline{x} < ∞. If in addition the support N is finite, the meanwhile classical field of self–similarity is entered. Because of the extensive literature on this subject, in particular in the context of fractals, only a question concerning uniform distributions will be considered here:

(10.3) Proposition. Let ν be positive recurrent with \underline{x} < \overline{x} and

N = {(y_{i}, z_{i}) : 0 ≤ i ≤ k}

be such that 0 < y_{i} < 1 and

]\underline{x}, \overline{x}] = ⋃_{0≤i≤k} (y_{i}]\underline{x}, \overline{x}] + z_{i})

is a partition. Then the stationary distribution μ satisfies

(a) supp μ = [\underline{x}, \overline{x}],

(b) μ is the uniform distribution on [\underline{x}, \overline{x}] if and only if

ν({(y_{i}, z_{i})}) = y_{i} for 0 ≤ i ≤ k,

(c) if ν′ is any other distribution with support N, then its stationary distribution μ′ is orthogonal to μ.

Proof. (a) Since M = supp μ and N are compact, by (4.1b)

M = ⋃_{0≤i≤k} (y_{i}M + z_{i}).

By the hypothesis this equation holds as well, if M is replaced by [\underline{x}, \overline{x}], and the assertion follows from well–known uniqueness results (see e.g. [20]).

(b) With γ := \overline{x} − \underline{x} and p_{i} := ν(\{(y_{i}, z_{i})\}) the condition on μ translates via its distribution function into

∑_{0≤i≤k} p_{i} \frac{1}{γ} ⟨ \underline{x} , \frac{t − z_{i}}{y_{i}} , \overline{x} ⟩ = \frac{1}{γ} ⟨ \underline{x}, t, \overline{x} ⟩ for all t ≥ 0,

where ⟨a, b, c⟩ denotes the medium of a, b, c ∈ R. The assertion follows from the partition properties.

(c) Consider the mapping

τ : (y_{i_{n}}, z_{i_{n}})_{n∈N} → ∑_{n∈N} y_{i_{1}} … y_{i_{n−1}}z_{i_{n}}

from ∏_{n∈N} N to [\underline{x}, \overline{x}]. Under the assumption \underline{x} = z_{0}/(1 − y_{0}) it is easily seen that τ is bijective and bimeasurable, if it is restricted to sequences not terminating in the sense that i_{n} = 0 for almost all n and \underline{x} is deleted from the range. Since the exceptional sequences form a null set with respect to the orthogonal measures ⨂_{n∈N} ν and ⨂_{n∈N} ν′, orthogonality carries over to their images by τ, being μ and μ′ by (8.2). □

The simplest example for uniform distribution on [0,1] is provided by the additive model

Y = \frac{1}{k + 1} and P(Z = \frac{i}{k + 1}) = \frac{1}{k + 1} for 0 ≤ i ≤ k.

Since (10.3) extends easily to countable partitions, there are similar examples in the multiplicative model:

P(Y = 2^{−k}) = 2^{−k} for k ∈ N and Z = 1

for instance yields the uniform distribution on [1,2].

It is obvious that the hypothesis in (10.3) implies ∑_{0≤i≤k} y_{i} = 1, and it is easily seen that in the case ∑_{0≤i≤k} y_{i} < 1 the support M is a Lebesgue null set and thus the measure μ is singular with respect to Lebesgue measure. More intricate is the case ∑_{0≤i≤k} y_{i} > 1, considered in detail by Garsia [15]. Even for

N = \{(0, 1), (y, 1)\} with \frac{1}{2} < y < 1

only partial results are known, going back essentially to Erdös [13].

The rest of this section is devoted to situations not excluding weak contractions, i.e. to the case Y ≤ 1. The first result is of interest mainly in the context of (10.6), though μ occurs as limit distribution also in learning theory (see e.g. [32]) or in a problem on random walks treated by Masimov [29]. The method from [13] yields the following:

(10.4) Proposition. With 1 ≠ l ∈ N and 0 < p < 1, q = 1 − p suppose

P(Y = \frac{1}{l}) = p, P(Y = 1) = q and Z = 1.

Then ν is positive recurrent and the stationary distribution μ is singular with respect to Lebesgue measure.

Proof. Positive recurrence is immediate from (8.5a). The random times 0 = T_{0} < T_{1} < … with Y = 1/ l (being defined with probability 1) have independent and geometrically distributed increments

U_{k} := T_{k} − T_{k−1} for k ∈ N.

Since the random variable W from (8.2) has the representation

W = ∑_{k≥0} l^{−k} U_{k+1},

the Fourier transform φ of μ is therefore given by

φ(u) = ∏_{k≥0} p e^{i l^{−k}u}/ (1 − q e^{i l^{−k}u}).

In view of

|φ(u)| = ∏_{k≥0} [1 + γ (1 − cos \frac{u}{l^{k}})]^{− \frac{1}{2}} with γ := \frac{2q}{p^{2}}

it suffices to show

(1) lim inf_{n→∞} ∏_{k≥0} […] < ∞,

because then μ cannot be absolutely continuous with respect to Lebesgue measure by the Riemann–Lebesgue lemma and (6.2) applies. To verify (1) consider the values

u_{m} = 2π l^{m} → ∞ for m → ∞,

which by shifting the index k to k − m yield the constant value

∏_{k≥0} […] = ∏_{k∈N} (1 + γ (1 − cos \frac{2π}{l^{k}})).

Since 1 − cos(2π/l^{k}) is bounded by \frac{1}{2}(2π/l^{k})^{2} for almost all k and thus is summable, the latter product converges and (1) is established. □

The final result, which originally motivated the present work, requires some preparation:

(10.5) Lemma. With 0 ≤ γ < 1 and 0 < p < 1, q = 1 − p assume

Y = γ and P(Z = k) = p q^{k−1} for k ∈ N.

Then

lim sup_{n→∞} X_{n}/ log n = −1/ log q a.s.

Proof. 1. It is less cumbersome to prove instead

lim sup_{n→∞} X′_{n}/ log n = 1/δ a.s.

for a sequence (X′_{n})_{n≥0} where Y′ = γ, Z′ has an exponential distribution with parameter δ and in addition X′_{0} = 0. Then

Z = ∑_{k∈N} k 1_{{k−1≤Z′<k}}

has a geometric distribution with parameter p = 1 − e^{−δ}, while

0 ≤ X_{n} − X′_{n} ≤ X_{0} + ∑_{m≥0} γ^{m} < ∞.

Moreover, replace Z′ by δZ′ and thus X′_{n} by δX′_{n} to see that δ = 1 means no loss of generality. Finally, the superscripts will be suppressed in the sequel.

2. To show that 1 is a lower bound for the upper limit, use

(1) E(e^{uZ}) = \frac{1}{1 − u} for 0 ≤ u ≤ 1

to conclude that

∑_{n>1} P(Z_{n}/ log n > 1) = ∑_{n>1} P(e^{Z_{n}} > n) = ∞,

which by Borel–Cantelli and X_{n} ≥ Z_{n} proves one half of the equation. 3. To prove the other half, choose an arbitrary t > 1. Then

P(X_{n}/ log n > t) = P(Z_{n} > t log n − (γ^{n−1}Z_{1} + … + γ^{1}Z_{n−1}))
≤ E(exp(γ^{n−1}Z_{1} + … + γ^{1}Z_{n−1} − t log n))

for n > 1, because P(Z > z) ≤ e^{−z} holds for z ≤ 0 as well and Fubini applies due to independence. By (1) therefore

P(X_{n}/ log n > t) ≤ n^{−t} ∏_{1≤m<n} \frac{1}{1 − γ^{m}}
≤ n^{−t} / ∏_{m∈N} (1 − γ^{m}) for n > 1,

where the infinite product is strictly positive by ∑_{m∈N} γ^{m} < ∞. Thus

∑_{n>1} P(X_{n}/ log n > t) < ∞ for all t > 1,

i.e. 1 is also an upper bound. □

In conclusion the order in which an upper limit \overline{x} = ∞ is approached will be studied for the weakly contractive multiplicative model, being of particular interest in applications. While the result provides just an upper bound in the case P(Y = 1) = 0, it is exact otherwise and, somewhat surprisingly, depends only on this probability:

(10.6) Theorem. If Y ≤ 1 and Z = 1, then

lim sup_{n→∞} X_{n}/ log n = −1 / log P(Y = 1) a.s.

Proof. 1. Clearly, X_{0} = 1 can be supposed in the sequel. In proving the right–hand side to be a lower bound for the upper limit, moreover, Y may be decreased to 1_{{Y =1}}Y. Therefore in this part Y will be assumed to be 0, 1–valued, where

p := P(Y = 0) > 0.

Then the random times 0 = T_{0} < T_{1} < … with Y_{n} = 0 are defined with probability 1 and have independent and geometrically distributed increments

U_{k} := T_{k} − T_{k−1} for k ∈ N.

Thus by the strong law of large numbers

\frac{1}{k} T_{k} = \frac{1}{k} (U_{1} + … + U_{k}) → E(T_{1}) = \frac{1}{p} a.s.,

(1) log T_{k}/ log k → 1 a.s.

Therefore the equation

X_{T_{k} −1} = U_{k} for k ∈ N

yields the estimate

lim sup_{n→∞} X_{n}/ log n ≥ lim sup_{k→∞} X_{T_{k} −1} / log(T_{k} − 1)
= lim sup_{k→∞} U_{k} / log k.

Now (10.5) applies with γ = 0, in which case X_{n} and Z_{n} agree.

2. In proving the inverse inequality Y may be increased to γ on {Y ≤ γ} and to 1 on {Y > γ} for any γ < 1 satisfying P(Y ≤ γ) > 0, because a subsequent limiting procedure γ → 1 yields the desired upper bound. Therefore restrict Y to the values γ and 1 and, with 0 replaced by γ, introduce the random variables T_{k} and U_{k} as in the first part of the proof. Now for T_{k−1} ≤ n < T_{k} clearly

X_{n}/ log n ≤ X_{T_{k} −1} / log T_{k−1},

where by (1)

log T_{k−1} / log (T_{k} − 1) → 1 a.s.

Again by (1) this implies

lim sup_{n→∞} X_{n}/ log n ≤ lim sup_{k→∞} X_{T_{k} −1} / log(T_{k} − 1)
= lim sup_{k→∞} X_{T_{k} −1} / log k,

where

X_{T_{k} −1} = ∑_{1≤i≤k} γ^{k−i} U_{i} for k ∈ N.

Thus (10.5) applies again, with Z_{n} replaced by U_{n}. □

Finally, it should be mentioned that with probability 1 the limit points of the normalized sequence (X_{n}/ log n)_{n>1} exhaust the interval

I := [0, −1/ log P(Y = 1)].

Indeed, given l ∈ N and ε > 0, by \underline{x} < ∞ there exists a random time T ≥ l ∨ e^{1/ε} such that X_{T} / log T < ε, hence in view of

X_{n+1}/ log (n + 1) ≤ (X_{n} + 1)/ log n ≤ X_{n}/ log n + ε for n ≥ T

the values X_{n}/ log n, n ≥ l, are ε–dense in I.

References

1. Alpuim, M.: An extremal Markovian sequence. J. Appl. Prob. 26, 219–232 (1989)

3. Barnsley, M., Elton, J., Hardin, D.: Recurrent iterated function systems. Constr. Approx. 5, 3–31 (1989)

4. Borovkov, A.: On the ergodicity and stability of the sequence w_{n+1} = f(w_{n}, ξ_{n}). Theory Prob. Appl. 33, 595–611 (1989)

5. Brandt, A.: The stochastic equation Y_{n+1} = A_{n}Y_{n} + B_{n} with stationary coefficients. Adv. Appl. Prob. 18, 211–220 (1986)

6. Brandt, A., Franken, P., Lisek, B.: Stationary stochastic models. Chichester: Wiley 1990

7. Chamayou, J., Letac, G.: Explicit stationary distributions for compositions of random functions and products of random matrices. J. Theor. Prob. 4, 3–36 (1991)

10. Elton, J.: An ergodic theorem for iterated maps. Ergodic Theory Dyn. Syst. 7, 481–488 (1987)

11. Elton, J.: A multiplicative ergodic theorem for Lipschitz maps. Stochastic Processes Appl. 34, 39–47 (1990)

12. Elton, J., Yan, Z.: Approximation of measures by Markov processes and homogeneous affine iterated function systems. Constr. Approx. 5, 69–87 (1989)

13. Erdös, P.: On a family of symmetric Bernoulli convolutions. Am. J. Math. 61, 974–976 (1939)

15. Garsia, A.: Entropy and singularity of infinite convolutions. Pac. J. Math. 13, 1159–1169 (1963)

16. Goldie, C.: Implicit renewal theory and tails of solutions of random equations. Ann. Appl. Prob. 1, 126–166 (1991)

18. Grincevičius, A.: A random difference equation. Lith. Math. Trans. 21, 302– 306 (1982)

19. de Haan, L., Karandikar, R.: Embedding a stochastic difference equation into a continuous–time process. Stochastic Processes Appl. 32, 225–235 (1989)

20. Hutchinson, J.: Fractals and self similarity. Indiana Univ. Math. J. 30, 713– 747 (1981)

21. Kac, M.: On the notion of recurrence in discrete stochastic processes. Bull. Am. Math. Soc. 53, 1002–1010 (1947)

23. Kesten, H.: The limit points of a normalized random walk. Ann. Math. Stat. 41, 1173–1205 (1970)

24. Kesten, H.: Random difference equations and renewal theory for products of random matrices. Acta Math. 131, 207–248 (1973)

27. Lev, G.: Semi–Markov processes of multiplication with drift. Theory Prob. Appl. 17, 159–164 (1972)

29. Masimov, V.: A generalized Bernoulli scheme and its limit distribution. Theory Prob. Appl. 18, 521–530 (1973)

30. Mukherjea, A.: Recurrent random walk in nonnegative matrices: attractors of certain iterated function systems. Prob. Theory Related Fields 91, 297–306 (1992)

31. Mukherjea, A., Tserpes, N.: Measures on topological semigroups: convolution products and random walks. Lect. Notes Math. 547, Berlin–Heidelberg–New York: Springer 1976

32. Norman, M.: Limiting distributions for some random walks arising in learning models. Ann. Math. Stat. 37, 393–405 (1966)

34. Rachev, S., Samorodnitsky, G.: Limit laws for a stochastic process and random recursion arising in probability modelling. Preprint (1992)

39. Vervaat, W.: On a stochastic difference equation and a representation of non– negative infinitely divisible random variables. Adv. Appl. Prob. 11, 750–783 (1979)

40. Wolfe, S.: On a continuous analogue of the stochastic difference equation X_{n} = ϱX_{n−1} + B_{n}. Stochastic Processes Appl. 12, 301–312 (1982)