Ergodic Behaviour of Affine Recursions I

Criteria for Recurrence and Transience

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_{+}. This results in quite natural notions of (topological) recurrence and transience and allows for rather explicit criteria to distinguish between both cases.

1991 Mathematics Subject Classification. Primary 60H25, 60J05; Secondary 54H20.

Introduction

A discrete–time Markov process (X_{n})_{n≥0} with a decent (say, Polish) state space E can be given the form of a “stochastically recursive sequence” (in the sense of Borovkov [4])

X_{n} = g_{n}(X_{n−1}) for n ∈ N,

where g_{n}, n ∈ N, is a sequence of independent and identically distributed random mappings from E to E which is independent of the initial variable X_{0}.

A first systematic treatment under this aspect goes back to Dubins and Freedman [9], who, for E = [0, 1], considered in particular two cases: (C) regarding the metric structure of E, they restricted the mappings g_{n} to the class of contractions; (A) specializing further, they limited these mappings to the class of affinities.

Generalizations of (C) from [0,1] to a complete metric space E attracted much interest during the last decade, mainly in the context of fractals. Under the heading “iterated function systems” Barnsley, Elton and others considered questions concerning stationary distributions, weak convergence, recurrence, ergodicity etc. Crucial for their results is an “average contractivity” (see [2], [3], [10], [11], [12]).

Extensions of (A) from the compact interval [0,1] to R occur first in papers by Lev [27] and Masimov [29]. More comprehensive are independent treatments by Grincevičius [17] and Vervaat [39]. Explicitly, affine recursions on R have the form of a stochastic difference equation

(∗) X_{n} = Y_{n}X_{n−1} + Z_{n} for n ∈ N

(which is somewhat more general than X_{n} = Y_{n} (X_{n−1} + Z_{n})). Here, X_{0} is a real random variable, independent of a sequence (Y_{n}, Z_{n})_{n∈N} of independent identically distributed R^{2}-valued random variables.

These affine recursions include as degenerate cases random walks (Y_{n} = 1) and infinite products (Z_{n} = 0). Of particular interest are the “additive model”, where

X_{n} = yX_{n−1} + Z_{n} with constant y ∈ R

(the simplest case of an autoregressive process), and the “multiplicative model”, where

X_{n} = Y_{n}X_{n−1} + z with constant z ∈ R.

Both models can be subsumed under the case where Y_{n} and Z_{n} are independent.

Due to the particular role of 0 with respect to multiplication, the situation is especially simple for P(Y = 0) > 0. This “regenerative” case can be studied in a more general context (see e.g. Nummelin [33]). Another particular situation is provided by the “contractive” case, where in the weak version |Y_{n}| ≤ 1 and in the strong version |Y_{n}| ≤ ϑ < 1.

To conclude the historical remarks, two central results concerning the general case have to be mentioned:

— If an affine recursion has a stationary distribution, it is unique and the laws L(X_{n}) converge weakly to it, independently of the initial law L(X_{0}).

— Conditions on the existence of a stationary distribution can be formulated via logarithmic moments of Y_{n} and Z_{n}.

The present work originates in the observation that most applications in economics, biology, physics etc. (see the long list of references in [39]) in fact work in the state space R_{+}, and thus the case X_{0} ≥ 0 and Y_{n}, Z_{n} ≥ 0 is of special importance. From the mathematical point of view this restriction is supported by the fact that a state space R_{+} allows only one kind of divergence to infinity and the assumption Y_{n}, Z_{n} ≥ 0 entails additional monotonicity properties of the associated transition kernel.

In the existing literature these aspects do not find much attention. Apart from an approach by Lamperti [25], [26], too general for affine recursions, there are only two exceptions: a recent paper by Mukherjea [30], coupling in the context of nonnegative matrices the sequence (X_{n})_{n≥0} with the partial products of (Y_{n})_{n∈N}, and a preprint by Rachev [34], concentrating on central limit theorems for suitably normalized variables X_{n} in the divergent case.

To summarize the main feature of the present work before going into details: affine recursions on R_{+} seem to provide one of the best suited models for extending classical Markov chain theory to an uncountable state space. Since the Harris theory (see e.g. [35]) is easily seen not to be adequate, the study has to be based on the topological structure. This, in general, leads to various notions of irreducibility and aperiodicity, of (positive or null) recurrence and transience (see the papers by Rosenblatt [37] and Tweedie [38]). In the present case, however, these notions merge into very natural definitions satisfying the classical criteria.

This allows for a rather complete theory, developed in the sections:

1. Lower and upper limit

2. Recurrence and transience

3. Recurrence criteria

4. Excessive and invariant measures

5. Existence and uniqueness of invariant measures

6. Main properties of the invariant measure

7. Ratio ergodic theorems

8. Positive and null recurrence

9. Further ergodic theorems

10. The contractive case

Thus the paper divides into three parts: Sections 1–3 classify affine recursions on R_{+} according to recurrence and transience, Sections 4–7 treat existence and uniqueness of invariant measures as well as ergodic theorems, Sections 8–10 continue to classify the recurrent case by introducing the notions of positive recurrence and null recurrence. Part II and III will appear in … and …; the contents of Part I are summarized below.

Section 1. Since convergence of an affine recursion, even in probability, occurs only in an exceptional case (1.4), the lower and upper limit are of interest. It is a crucial consequence of restricting the state space to R_{+} that these limits are constants \underline{x} and \overline{x}, independent of the initial law L(X_{0}) (1.1). Wherever starting, the sequence (X_{n})_{n≥0} approaches the interval [\underline{x}, \overline{x}] monotonically (1.2). While the upper limit only depends on the support of the joint law L(Y_{n}, Z_{n}), this in general fails for the lower limit. In fact, it is not surprising that even in the simple example

(E) X_{n} = Y_{n}X_{n−1} + 1 with Y_{n} = 2^{−1} or 2^{+1}

the asymptotic behaviour depends essentially on the probabilities

p_{−} = P(Y_{n} = 2^{−1}) and p_{+} = P(Y_{n} = 2^{+1}).

Provided, however, \underline{x} and \overline{x} are finite, a simple characterization by means of the support is available (1.3).

Section 2. Clearly, (X_{n})_{n≥0} has to be called “transient” in the case \underline{x} = ∞. It is less clear – and one of the central questions in the sequel –, whether the sequence may be called “recurrent” in the case \underline{x} < ∞. A first justification is supplied by an equivalent characterization through the associated potential kernel: the mean time spent in a bounded interval [0, t] is finite in the transient case and infinite in the recurrent case, provided t > \underline{x} (2.2). Examples for both situations are easily established: the affine recursion is certainly recurrent in the regenerative case P(Y_{n} = 0) > 0 (2.3), and it is transient whenever the associated random walk (S_{n})_{n≥0} with increments log Y_{n} diverges to +∞ (2.4). Though both conditions depend on the “primary” variable Y_{n} only, the “secondary” variable Z_{n} may be essential as well. In fact, however small Y_{n} is, a sufficiently large Z_{n} yields transience (2.5).

Section 3. In the additive model a nearly complete characterization of recurrence or transience by the asymptotic behaviour of t P(log Z_{n} > t) for t → ∞ can be derived, which extends to the case where Y_{n} is bounded away from 1 or 0 (3.1). The situation is less clear in the multiplicative model. It is not surprising that in example (E) above p_{−} < p_{+} implies transience and p_{−} > p_{+} implies recurrence. It is a nontrivial problem, however, to decide the balanced case p_{−} = p_{+}. Clearly the related multiplicative random walk, where

X_{0} = 1 and X_{n} = Y_{n}X_{n−1} for n ∈ N,

oscillates through the values 2^{k}, k ∈ Z. But it requires Spitzer’s combinatorial identity to prove the drift term +1 not to change recurrence into transience. The relevant recurrence criterion settles the multiplicative model completely and extends in fact to the case where Z_{n} is only bounded (3.3). Assuming Y_{n} and Z_{n} to be independent, even finiteness of the expectation of Z_{n} ensures recurrence (3.4).

0. Preliminaries

Throughout the paper (X_{n})_{n≥0} is a fixed affine recursion on R_{+}, given by the stochastic difference equation (∗) of the introduction. Thus the distribution of (X_{n})_{n≥0} is completely determined by the laws μ_{0} = L(X_{0}) and ν = L(Y, Z). Here, Y and Z is briefly written instead of Y_{n} and Z_{n}, as will be done whenever n ∈ N plays no role.

The initial law μ_{0}, as usual, is largely of only secondary significance. If in particular μ_{0} is a unit measure ε_{x}, this will be expressed by the notation (X_{n}^{x})_{n≥0}, i.e.

X_{n}^{x} := xY_{1}Y_{2} … Y_{n} + Z_{1}Y_{2} … Y_{n} + … + Z_{n} for x ∈ R_{+} and n ≥ 0.

Thus conditional probability and expectation are simply given by

P^{x}((X_{n}, n ≥ 0) ∈ B) = P((X_{n}^{x}, n ≥ 0) ∈ B),

E^{x}(g(X_{n}, n ≥ 0)) = E(g(X_{n}^{x}, n ≥ 0)).

Roughly speaking, what follows is a theory of distributions ν on R_{+}^{2}. Here an essential role will be played by their support, for which the notation N will be fixed. Since nothing new can be expected in the special cases Y = 1 resp. Z = 0, for simplification

N ∩ {(y, z) : y ≠ 1} ≠ ∅ ≠ N ∩ {(y, z) : z ≠ 0}

is always assumed. The symbol N will throughout refer to the class of distributions ν on R_{+}^{2} that are admissible in this sense.

As is clear from the introduction, the ergodic behaviour of (X_{n})_{n≥0} is intimately related to the random walk

S_{n} := ∑_{1≤m≤n} log Y_{m} for n ≥ 0,

generalized in the sense that it may attain the (absorbing) value −∞. Due to P(Y = 1) < 1 there are only three possibilities for the asymptotic behaviour of this random walk:

(1) S_{n} → +∞ a.s.,

(2) S_{n} → ±∞ a.s.,

(3) S_{n} → −∞ a.s.,

where the symbol in (2) serves as a short notation for

P(lim inf_{n→∞} S_{n} = −∞, lim sup_{n→∞} S_{n} = +∞) = 1.

Another process closely related to (X_{n})_{n≥0} arises if, in the notation at the beginning of the introduction, the random variables g_{n}∘…∘g_{1}(X_{0}) are replaced by g_{1} ∘ … ∘ g_{n}(X_{0}). Especially for X_{0} = 0 this yields

W_{n} := Z_{1} + Y_{1}Z_{2} + … + Y_{1} … Y_{n−1}Z_{n} for n ≥ 0.

The sequence (W_{n})_{n≥0} is no longer a Markov process, however, due to the exchangeability of (Y_{1}, Z_{1}), …, (Y_{n}, Z_{n}), satisfies

L(W_{n}) = L(X_{n}^{0}) for n ≥ 0,

an equation, which will be important later on.

The transition kernel of the Markov process (X_{n})_{n≥0} will always be denoted byP. Thus the kernel P transforms a nonnegative function f into the function P f given by

(P f)(x) = ∫ f(yx + z) ν(dy, dz)

and a measure μ on the Borel σ–algebra B(R_{+}) into the measure μP given by

(μP)(B) = ∫ ν({(y, z) : yx + z ∈ B}) μ(dx).

If μ is σ–finite, the last equation amounts to

(μP)(B) = (μ ⊗ ν)({(x; y, z) : yx + z ∈ B}).

In accordance with the notations P f and μP the μ–integral of a function f sometimes is simply denoted by μf.

The kernel P enjoys two important properties. First it is clearly a Feller kernel, transforming bounded continuous functions into the same type. Moreover, due to Y ≥ 0, it is monotone in the sense that it transforms bounded increasing functions into the same type, too.

If E is a locally compact space with a countable base, the following concepts from topological measure theory will be used:

— C(E) denotes the space of bounded continuous functions f : E → R and K(E) the subspace consisting of functions f ∈ C(E) with compact support.

— If μ is any measure on B(E), then C_{μ}(E) denotes the space of bounded Borel–measurable functions f : E → R that are μ–almost everywhere continuous and K_{μ}(E) the corresponding subspace.

— The class M(E) of locally finite measures on E is endowed with the vague (weak*) topology, i.e. the initial topology with respect to the mappings

μ → μf, f ∈ K(E).

In this topology convergence will be denoted by →^{v}.

— The class M_{1}(E) of probability measures on E is endowed with the weak (narrow) topology, i.e. the initial topology with respect to the mappings

μ → μf, f ∈ C(E).

In this topology convergence will be denoted by →^{w}.

Finally it has to be emphasized that statements concerning random variables in case of doubt are always understood modulo P–null sets. Thus the supplement “almost surely”, as in the trichotomy concerning (S_{n})_{n≥0}, will frequently be deleted.

1. Lower and upper limit

As outlined in the introduction, the following observation is of central importance throughout the paper:

(1.1) Theorem. The random variables

\underline{X} := lim inf_{n→∞} X_{n} and \overline{X} := lim sup_{n→∞} X_{n}

are almost surely constant and independent of the initial value X_{0}, i.e. there exist constants 0 ≤ \underline{x} ≤ \overline{x} ≤ ∞, depending only on ν, such that

P(\underline{X} = \underline{x}) = 1 and P(\overline{X} = \overline{x}) = 1.

Proof. 1. The following fact will be needed:

(1) sup_{n≥0} S_{n} = +∞ implies sup_{n≥0} X_{n} = ∞ a.s.

Indeed, since

sup_{m∈N} Z_{m} > 0 a.s. and sup_{n≥m} e^{S_{n}−S_{m}} = ∞ a.s.,

the assertion is a consequence of

sup_{n≥0} X_{n} ≥ sup_{m∈N} (Z_{m} sup_{n≥m} e^{S_{n}−S_{m}}).

2. Let \underline{X}^{x} and \overline{X}^{x} be defined in analogy to X_{n}^{x}. Then

\underline{X}^{0} ≥ lim inf_{n→∞} (Z_{m}Y_{m+1} … Y_{n} + … + Z_{m+n}) =: \underline{X}_{m}^{0},

where L(\underline{X}^{0}) and L(\underline{X}_{m}^{0}) are identical. This implies

\underline{X}^{0} = \underline{X}_{m}^{0} a.s. for all m ∈ N,

i.e. \underline{X}^{0} is measurable with respect to (the completion of) the tail–field of (Y_{n}, Z_{n})_{n∈N}. Thus \underline{X}^{0} – and similarly \overline{X}^{0} – are almost surely constant. Therefore it suffices to show that \underline{X}^{x} and \overline{X}^{x} are in fact independent of x ∈ R_{+}. Here sup_{n≥0} S_{n} = +∞ may be assumed, because otherwise

X_{n}^{x} − X_{n}^{0} = x e^{S_{n}} → 0 a.s.

3. To treat the lower limit first, consider the random time

T := inf{n ≥ 0 : X_{n}^{0} ≥ x}, which is finite almost surely by (1). Then

\underline{X}^{x} ≥ \underline{X}^{0}
≥ lim inf_{n→∞} (X_{T}^{0} Y_{T +1} … Y_{T +n} + … + Z_{T +n})
≥ lim inf_{n→∞} (x Y_{T +1} … Y_{T +n} + … + Z_{T +n})
=: \underline{X}_{T}^{x} ,

where L(\underline{X}^{x}) and L(\underline{X}_{T}^{x}) are identical, because T is a stopping time with respect to (Y_{n}, Z_{n})_{n∈N}. Thus, indeed

\underline{X}^{x} = \underline{X}^{0} a.s. for all x ∈ R_{+}.

The corresponding result for the upper limit is another consequence of (1), which yields

\overline{X}^{x} ≥ \overline{X}^{0} = ∞ a.s. for all x ∈ R_{+}. □

The notation \underline{x} and \overline{x} will be used in the sequel without further reference. The interval defined by these limits attracts the sequence (X_{n})_{n≥0} in a strong sense:

(1.2) Proposition. Whenever finite, the constants \underline{x} and \overline{x} are determined by the equivalences

(a) x ≤ \underline{x} if and only if P(Y x + Z ≥ x) = 1,

(b) x ≥ \overline{x} if and only if P(Y x + Z ≤ x) = 1;

moreover the “if–part” holds without the finiteness assumption.

Proof. 1. The implication from right to left is an immediate consequence of (1.1), because e.g. the assumption

Y x + Z ≥ x a.s.

obviously implies

{X_{n−1} ≥ x} ⊂ {X_{n} ≥ x} a.s.,

which in turn yields

\underline{x} = lim inf_{n→∞} X_{n}^{x} ≥ inf_{n≥0} X_{n}^{x} ≥ x.

2. To prove the converse, consider first assertion (a). Fix an arbitrary x′ ∈ ]\underline{x}, ∞[ and let T_{1} < T_{2} … denote the hitting times of [0, x′] by the sequence (X_{n}^{0})_{n≥0} (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

(Y′_{k}, Z′_{k}) := (Y_{T_{k} +1}, Z_{T_{k} +1}) for k ∈ N

are again independent and distributed according to ν. Therefore

\underline{x} ≤ lim inf_{k→∞} X_{T_{k} +1}^{0}
= lim inf_{k→∞} (Y_{T_{k} +1}X_{T_{k}}^{0} + Z_{T_{k} +1})
≤ lim inf_{k→∞} (Y′_{k} x′ + Z′_{k})
≤ yx′ + z for (y, z) ∈ N,

because (Y′_{k}, Z′_{k})_{k∈N} visits each neighborhood of (y, z) infinitely often with probability 1. Letting x′ tend to \underline{x} leads to

(1) \underline{x} ≤ y\underline{x} + z for (y, z) ∈ N. This inequality holds as well with 0 replacing \underline{x}, hence

(2) x ≤ yx + z for (y, z) ∈ N and x ≤ \underline{x}, which is equivalent to the assertion

x ≤ Y x + Z a.s. for x ≤ \underline{x}.

3. The corresponding proof for \overline{x} requires only minor changes: choose now x′ ∈ [0, \overline{x}[ , which is possible due to

(3) \overline{x} ≥ lim sup_{n→∞} Z_{n} > 0, replace the interval [0, x′] by [x′, ∞[, and use \overline{x} > 0 once more for the passage between (the counterparts of) (1) and (2). □

From (1.2) it is easily deduced that for finite values \underline{x} and \overline{x}

X_{n−1} ∧ \underline{x} ≤ X_{n} ≤ X_{n−1} ∨ \overline{x} a.s. for all n ∈ N. Now the constants \underline{x} and \overline{x} – except for a crucial ambiguity – can be

evaluated explicitly, using a decomposition of the support N by its contractive and expansive part. With an asymmetry due to the different roles of 0 and ∞, the following holds: (1.3) Proposition. With the notations

N_{c} := {(y, z) ∈ N : y < 1},

N_{e} := {(y, z) ∈ N : y ≥ 1 and (y, z) ≠ (1, 0)} the constants \underline{x} and \overline{x} satisfy

(a) \underline{x} = inf\{\frac{z}{1 − y} : (y, z) ∈ N_{c}\}

or \underline{x} = ∞,

(b) \overline{x} = sup\{\frac{z}{1 − y} : (y, z) ∈ N_{c}\} if N_{e} = ∅,

and \overline{x} = ∞ otherwise.

Proof. (a) If \underline{x} is finite, according to (1.2a) it is the largest value x such that

x ≤ yx + z for all (y, z) ∈ N.

Since this inequality is trivially satisfied for y ≥ 1, it amounts indeed to

x ≤ \frac{z}{1 − y} for (y, z) ∈ N_{c}.

(b) If \overline{x} is finite, according to (1.2b) it satisfies

\overline{x} ≥ \overline{x}y + z for all (y, z) ∈ N.

In view of \overline{x} > 0 (see (3) in the proof of (1.2)) this yields N_{e} = ∅. Since (y, z) = (1, 0) can be disregarded, \overline{x} is the smallest value x such that

x ≥ xy + z for (y, z) ∈ N_{c}. □

It is a trivial consequence of this result that X_{n} → ∞ a.s. whenever N_{c} is empty. Otherwise \underline{x} – unlike \overline{x} – may depend on the distribution ν not only through its support N. If, however, \underline{x} resp. \overline{x} is finite, it can be obtained graphically: (0, \underline{x}) resp. (0, \overline{x}) is that point where the lower resp. upper tangent from (1,0) to N_{c} intersects the z–axis. This implies in particular that the infimum or supremum in (1.3) need not be attained.

In contrast to the possibility X_{n} → ∞ a.s., convergence of (X_{n})_{n≥0} within R_{+} can occur only in a degenerate case, even if weakened to convergence in probability:

(1.4) Proposition. The following assertions are equivalent:

(a) \underline{x} = γ = \overline{x} with 0 < γ < ∞,

(b) the sequence (X_{n})_{n≥0} converges in probability to a finite–valued random variable X,

(c) Y ≤ 1 and Z = γ(1 − Y) with 0 < γ < ∞.

Proof. 1. The implication (a) ⇒ (b) is trivial.

2. Assume now (b) and let d be a bounded metric on R_{+}. Then (yX_{n}+z)_{n≥0} converges in probability to yX + z, hence

(1) E (d (yX_{n} + z, yX + z)) → 0 for all (y, z) ∈ R_{+}^{2}.

Since X_{n} and (Y_{n+1}, Z_{n+1}) are independent, moreover

∫ E (d (yX_{n} + z, X_{n})) dν = E (d (X_{n+1}, X_{n})) → 0.

Thus there is a subsequence (X_{n_{k}})_{k≥0} such that

(2) E (d (yX_{n_{k}} + z, X_{n_{k}})) → 0 for ν–almost all (y, z) ∈ R_{+}^{2}. When combined with the restriction of (1) to this subsequence, applied to (y, z) as well as to (1,0), (2) yields

E (d (yX + z, X)) = 0 for ν–almost all (y, z) ∈ R_{+}^{2}. With μ := L(X) this implies

yx + z =^{μ} x for ν–almost all (y, z) ∈ R_{+}^{2}; therefore, by Fubini,

yx + z =^{ν} x for μ–almost all x ∈ R_{+}. Thus there exists indeed γ ∈ R_{+} such that

Z = γ(1 − Y), where γ ≠ 0 (since otherwise Z = 0) and Y ≤ 1 (because of Z ≥ 0).

3. The implication (c) ⇒ (a) is immediate from (1.2). □

Clearly, the constant γ is a common fixed point of the underlying affine maps almost surely.

2. Recurrence and transience

In view of X_{n} ≥ 0 the first classification is very natural: (2.1) Definition. The distribution ν (or the kernel P or the process (X_{n})_{n≥0}) is called

(a) “recurrent” if \underline{x} < ∞,

(b) “transient” if \underline{x} = ∞.

Both cases can be distinguished as well by the associated potential kernel G := ∑_{n≥0} P^{n}, independently of the initial law: (2.2) Theorem. The following dichotomy holds:

(a) if ν is recurrent, then ∑_{n≥0} P(X_{n} ≤ t) = ∞ for t > \underline{x};

(b) if ν is transient, then ∑_{n≥0} P(X_{n} ≤ t) < ∞ for t < ∞.

Proof. (a) This is an immediate consequence of P(X_{n} ≤ t infinitely often) = 1.

(b) Define recursively

T_{0} := 0 and T_{k} := inf{n > T_{k−1} : X_{n} ≤ t} (≤ ∞). Then in particular

0 = P^{0}(X_{n} ≤ t infinitely often) = lim_{k→∞} P^{0}(T_{k} < ∞), hence there exists l ∈ N such that

ϑ := P^{0}(T_{l} < ∞) < 1. With the decreasing function

g(x) := P^{x}(T_{l} < ∞) this implies

P^{0}(T_{(k+1) l} < ∞) = ∫ _{{T_{kl}<∞}} g(X_{T_{kl}}) dP^{0}
≤ ∫ _{{T_{kl}<∞}} g(0) dP^{0}
= ϑ P^{0}(T_{kl} < ∞).

Therefore

P^{0}(T_{kl} < ∞) ≤ ϑ^{k} for all k ≥ 0, and again by monotonicity this yields

∑_{n≥0} P(X_{n} ≤ t) ≤ ∑_{n≥0} P^{0}(X_{n} ≤ t)
= E^{0}(|{n ≥ 0 : X_{n} ≤ t}|)
= ∑_{i≥0} P^{0}(T_{i} < ∞)
≤ l ∑_{k≥0} P^{0}(T_{kl} < ∞)
≤ l ∑_{k≥0} ϑ^{k} < ∞. □

The next result is a simple consequence of (2.2) (and needed before a stronger version will be available): (2.3) Proposition. ν is recurrent whenever P(Y = 0) > 0. Proof. For any t < ∞ satisfying

P(Y = 0, Z ≤ t) > 0 the assertion follows from (2.2a) in view of

∑_{n≥0} P(X_{n} ≤ t) ≥ ∑_{n∈N} P(Y_{n} = 0, Z_{n} ≤ t). □ Equally simple is the following counterpart:

(2.4) Proposition. ν is transient whenever S_{n} → +∞.

Proof. Since

T := inf{n ∈ N : Z_{n} > 0}

defines an (almost surely finite) stopping time with respect to (Z_{n})_{n∈N}, by the hypothesis

S_{n} − S_{T} → ∞ a.s.

Thus the assertion is a consequence of

X_{n} ≥ Z_{T} e^{S_{n}−S_{T}} for n ≥ T. □

That the converse of (2.4) does not hold in general can be demonstrated by a somewhat surprising result. However small the primary variable Y, in view of (2.3) only supposed to be strictly positive, may be, the secondary variable Z can be made large enough for transience, even if in addition independence of Y and Z is postulated. More precisely, in terms of distributions:

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

Proof. Let Y_{n}, n ∈ N, be independent with distribution ν_{y} and assume without loss of generality Y < 1. Then choose a sequence (c_{n})_{n≥0} satisfying

(1) 0 < c_{0} < c_{1} < … → 1,

(2) ∑_{n≥0} c_{1} … c_{n} < ∞

(e.g. c_{n} = (\frac{n}{n+1})^{2} for n ∈ N) and a sequence (ε_{n})_{n∈N} satisfying

(3) 1 > ε_{1} > ε_{2} > … → 0,

(4) b_{n} := P(Y_{1} … Y_{n−1} ≤ ε_{n}) ≤ 2^{−n} c_{1} … c_{n} for n ∈ N,

where the assumption P(Y = 0) = 0 enters. Independently of Y_{n}, n ∈ N, let Z_{n}, n ∈ N, be independent with a distribution ν_{z} such that

P(Z = 0) = c_{0} and P(Z = 1/ε_{n}) = c_{n} − c_{n−1} for n ∈ N,

hence in particular

P(Z ≤ 1/ε_{n}) = c_{n} for n ∈ N.

With the dual sequence (W_{n})_{n≥0}, defined in Section 0, consider now the events

A_{n} := {W_{n} ≤ 1},
B_{n} := {Y_{1} … Y_{n−1} ≤ ε_{n}},
C_{n} := {Z_{n} ≤ 1/ε_{n}},

which obviously satisfy

A_{n} ⊂ A_{n−1} ∩ (B_{n} ∪ C_{n}) ⊂ (A_{n−1} ∩ C_{n}) ∪ B_{n} for n ∈ N.

With the notation a_{n} := P(A_{n}) this yields by independence the inequality

a_{n} ≤ a_{n−1} c_{n} + b_{n} for n ∈ N,

which by induction, using (4), leads to

a_{n} ≤ (1 + … + 2^{−n}) c_{1} … c_{n} for n ≥ 0.

By (2), therefore

∑_{n≥0} P(X_{n}^{0} ≤ 1) = ∑_{n≥0} P(W_{n} ≤ 1)
≤ 2 ∑_{n≥0} c_{1} … c_{n} < ∞.

According to (1.3a) the lower limit \underline{x}, due to P(Y < 1, Z = 0) > 0, can only take the values 0 or ∞. But the first possibility is ruled out by (2.2a), and thus ν = ν_{y} ⊗ ν_{z} is transient. □

The final result of this section is a consequence of the monotonicity and will be crucial in Sections 5 and 7:

(2.6) Lemma. If f ∈ K(R_{+}), then

f(X_{n}) − f(X_{n}^{x}) → 0 a.s. for all x ∈ R_{+}.

Proof. 1. It suffices to prove the assertion under the hypothesis X_{0} = x_{0} ∈ R_{+}, because its general validity then follows by integration. Comparing f(X_{n}^{x_{0}}) and f(X_{n}^{x}) with f(X_{n}^{0}) shows that in fact x_{0} = 0 may be assumed. Since the assertion is obviously true in the transient case, moreover recurrence will be assumed in the sequel. According to (2.4) the random walk (S_{n})_{n≥0} then hits the interval [−∞, −γ] infinitely often with probability 1, where γ will be chosen at the end of the proof. If T_{1} < T_{2} < … are the corresponding hitting times, the random variables

(Y′_{k}, Z′_{k}) := (Y_{T_{k} +1}, Z_{T_{k} +1}) for k ∈ N

are again independent and distributed according to ν.

2. Next, in view of

0 < P(Z > 0) = lim_{m→∞} P(Y < mZ)

there exists l ∈ N such that

ϑ := P(Y < lZ) > 0.

Therefore, by part 1 of the proof, the random time

T := inf{T_{k} : Y_{T_{k} +1} < l Z_{T_{k} +1}}

may be assumed to be finite for all ω ∈ Ω.

3. Now for fixed ω ∈ Ω and n > T (ω) obviously

X_{n}^{x}(ω) − X_{n}^{0}(ω) = x ∏_{0<m≤T (ω)} Y_{m}(ω) ∏_{T (ω)<m≤n} Y_{m}(ω), where the two products ∏_{1} and ∏_{2} can be estimated by

∏_{1} = e^{S_{T (ω)}(ω)} ≤ e^{−γ},

∏_{2} ≤ l Z_{T (ω)+1}(ω) ∏_{T (ω)+1<m≤n} Y_{m}(ω) ≤ l X_{n}^{0}(ω).

Together this yields

(1) 0 ≤ X_{n}^{x}(ω) − X_{n}^{0}(ω) ≤ x e^{−γ} l t whenever X_{n}^{0}(ω) ≤ t.

4. Finally, fix t satisfying the requirement

supp f ⊂ [0, t] and, given an arbitrary ε > 0, choose δ > 0 such that

|f(t_{1}) − f(t_{2})| < ε for |t_{1} − t_{2}| < δ. This yields

f(X_{n}^{x}(ω)) − f(X_{n}^{0}(ω)) = 0 for X_{n}^{0}(ω) > t, in view of X_{n}^{x}(ω) ≥ X_{n}^{0}(ω), and

|f(X_{n}^{x}(ω)) − f(X_{n}^{0}(ω))| < ε for X_{n}^{0}(ω) ≤ t, if in addition

|X_{n}^{x}(ω) − X_{n}^{0}(ω)| < δ. By (1) this condition is satisfied for x e^{−γ} l t < δ, i.e. if γ is chosen sufficiently large. □

3. Recurrence criteria The sufficient conditions for recurrence and transience, given in (2.3) and (2.4), apply only to extreme cases. To deal with concrete situations stronger criteria are necessary. The first relevant result concerns essentially the additive model. A slight generalization yields: (3.1) Theorem. For 0 < γ < 1 the following dichotomy holds:

(a) ν is transient, if

Y ≥ γ and lim inf_{t→∞} t P(log Z > t) > log \frac{1}{γ} ,

(b) ν is recurrent, if

Y ≤ γ and lim sup_{t→∞} t P(log Z > t) < log \frac{1}{γ} .

Proof. (a) Clearly, Y = γ may be assumed. By the hypothesis

lim inf_{t→∞} t P(log Z > s + t) > log \frac{1}{γ} for all s ≥ 0,

which for fixed s implies the existence of α > 1 and l ∈ N such that

m log \frac{1}{γ} P(log Z > s + m log \frac{1}{γ}) ≥ α log \frac{1}{γ} for m ≥ l.

Therefore, by independence,

P(X_{n} ≤ e^{s}) ≤ P(⋂ _{l≤m<n} {γ^{m}Z_{n−m} ≤ e^{s}})
= ∏ _{l≤m<n} P(log Z ≤ s + m log \frac{1}{γ})
≤ ∏ _{l≤m<n} (1 − \frac{α}{m})
≤ ∏ _{l≤m<n} (1 − \frac{1}{m})^{α}
= (\frac{l − 1}{n − 1})^{α} for n > l,

where the last inequality makes use of α ≥ 1, implying

(1 − x)^{α} ≥ 1 − αx for 0 ≤ x ≤ 1.

Summation over n yields

∑_{n≥0} P(X_{n} ≤ e^{s}) ≤ (l + 1) + (l − 1)^{α} ∑_{n≥l} \frac{1}{n^{α}} < ∞,

and the transience follows from (2.2a), because s is arbitrary.

(b) Again, Y = γ may be assumed. In addition Z may be replaced by 0 on the set {Z ≤ z} for fixed z < ∞, because this is irrelevant for the hypothesis and changes the values of X_{n} by z/(1 − γ) at most. By an appropriate choice of α < 1 and z < ∞, therefore, the following conditions can be satisfied (in the given order):

(1) t P(log Z > t) ≤ α log \frac{1}{γ} for all t ≥ 0,

(2) P(Z = 0) ≥ δ := γ^{1−α}.

With the abbreviation

m_{n} := log n/ log \frac{1}{γ} + 2 for n ∈ N

this yields by independence

P(X_{n}^{0} ≤ 1) ≥ P(⋂ _{0≤m<n} \{γ^{m}Z_{n−m} ≤ \frac{1}{n}\})
≥ ∏ _{0≤m≤m_{n}} P(Z = 0) ∏ _{m_{n}<m<n} P(Z ≤ \frac{1}{n}γ^{−m}).

In view of (2) and (1) the two products ∏_{1} and ∏_{2} can be estimated by

∏ 1 ≥ δ^{m_{n} +1} = δ^{3} n^{α−1},
∏ 2 = ∏_{m_{n}<m<n} (1 − P(log Z > [m log \frac{1}{γ} − log n]))

≥ ∏_{m_{n}<m<n} (1 − α log \frac{1}{γ} / [m log \frac{1}{γ} − log n]),

because for m > m_{n} the difference […] satisfies the conditions

[…] > 0 and α log \frac{1}{γ} / […] ≤ 1.

The estimation of ∏_{2} can be continued by

∏ 2 ≥ ∏_{m_{n}<m<n} (1 − α / (m − (m_{n} − 2)))
≥ ∏_{0<l<n} (1 − \frac{α}{l + 1})
≥ ∏_{0<l<n} (1 − \frac{1}{l + 1})^{α}
= n^{−α},

where the last inequality makes use of 0 ≤ α ≤ 1, implying

(1 − x)^{α} ≤ 1 − αx for 0 ≤ x ≤ 1.

Together the bounds for ∏_{1} and ∏_{2} yield

∑_{n≥0} P(X_{n}^{0} ≤ 1) ≥ ∑_{n∈N} δ^{3} n^{α−1}n^{−α} = ∞,

and the recurrence follows from (2.2b). □

Two comments on this result are in order:

— The sufficient condition for transience is strictly stronger than the condition E(log_{+} Z) = ∞, while the sufficient condition for recurrence is strictly stronger than the condition E((log_{+} Z)^{1−ε}) < ∞ for all ε > 0.

— If t P(log Z > t) → ∞, then the sequence (X_{n})_{n≥0} is transient whenever Y = γ > 0; if t P(log Z > t) → 0, then it is recurrent whenever Y = γ < 1.

The rest of this section is devoted to recurrence criteria for the case that the underlying affine maps are not necessarily contractions. Here the possibility S_{n} → +∞ is ruled out by (2.4), i.e. inf_{n≥0} S_{n} = −∞ has to be assumed.

Then the following auxiliary result can be obtained by a partition into random blocks:

(3.2) Lemma. If inf_{n≥0} S_{n} = −∞ and

E(X_{T}^{0}) < ∞ for T := inf{n ∈ N : S_{n} < 0},

then ν is recurrent.

Proof. 1. In view of (2.3) the hypothesis P(Y = 0) = 0 can be used in the sequel. Set T_{0} := 0 and let T = T_{1} < T_{2} < … denote the strictly descending ladder indices of the random walk (S_{n})_{n≥0} (being defined with probability 1). Moreover, define

Y′_{k} := Y_{T_{k−1} +1} … Y_{T_{k}},
Z′_{k} := Z_{T_{k−1} +1} Y_{T_{k−1} +2} … Y_{T_{k}} + … + 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 such that

γ := E(Y′_{k}) = E(e^{S_{T}}) < 1,
δ := E(Z′_{k}) = E(X_{T}^{0}) < ∞.

2. Let now (X′_{k})_{k≥0} denote the sequence associated with (Y′_{k}, Z′_{k})_{k∈N}, and the initial value X′_{0} = 0. Then, clearly

X′_{k} = X_{T_{k}}^{0} for k ≥ 0,

and this implies by Fatou

\underline{x} = E(lim inf_{n→∞} X_{n}^{0})
≤ E(lim inf_{k→∞} X′_{k})
≤ lim inf_{k→∞} E(X′_{k})
= lim inf_{k→∞} (δγ^{k−1} + … + δ)
= δ / (1 − γ) < ∞. □

Now the two main recurrence criteria can be derived simultaneously:

(3.3) Theorem. If inf_{n≥0} S_{n} = −∞, then ν is recurrent in each of the following cases:

(a) E(Z | Y) ≤ γ for some γ < ∞,

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

Proof. 1. In view of (2.3) the hypothesis P(Y = 0) = 0 can be used in both cases. Moreover, the assumptions γ ≤ 1 in (a) and E(Z/Y) ≤ 1 in (b) are admissible simplifications, because a scalar multiplication has the same effect on X_{n}^{0}, n ≥ 0, as on Z_{n}, n ∈ N.

2. Consider now first case (a). Then, with T as in (3.2),

E(1_{{T =n}}Z_{m}Y_{m+1} … Y_{n}) = E(E(… | Y_{1}, …, Y_{n}))
= E(1_{{T =n}}Y_{m+1} … Y_{n} E(Z_{m} | Y_{m}))
≤ E(1_{{T =n}}Y_{m+1} … Y_{n}) for 1 ≤ m ≤ n,

where the last equation uses that {T = n} is measurable with respect to Y_{1}, …, Y_{n} and (Y_{m}, Z_{m}) is independent of Y_{l}, l ≠ m. In view of Y_{1} … Y_{n} ≤ 1 on {T = n} this yields

E(X_{T}^{0}) = ∑_{n∈N} ∑_{1≤m≤n} E(1_{{T =n}}Z_{m}Y_{m+1} … Y_{n})
≤ ∑_{m∈N} ∑_{n>m} E(1_{{T =n}}Y_{m+1} … Y_{n}) + 1
≤ ∑_{m∈N} ∑_{n>m} E(1_{\{T =n\}} \frac{1}{Y_{1}} … \frac{1}{Y_{m}}) + 1

= ∑_{m≥0} E(1_{\{T >m\}} \frac{1}{Y_{1}} … \frac{1}{Y_{m}}),

where the summand 1 stands first for ∑_{n∈N} E(1_{{T =n}}) and then for E(1_{{T >0}}). The final result can be rewritten as

(1) E(X_{T}^{0}) ≤ E(∑_{0≤m<T} e^{−S_{m}}).

3. This inequality extends to case (b). Indeed, here

E(X_{T}^{0}) = ∑_{m∈N} ∑_{n≥m} E(1_{\{T =n\}} \frac{Z_{m}}{Y_{m}} Y_{m} … Y_{n})

≤ ∑_{m∈N} ∑_{n≥m} E(1_{\{T =n\}} \frac{1}{Y_{1}} … \frac{1}{Y_{m−1}} \frac{Z_{m}}{Y_{m}})

= ∑_{m∈N} E(1_{\{T >m−1\}} \frac{1}{Y_{1}} … \frac{1}{Y_{m−1}} ) E(\frac{Z_{m}}{Y_{m}} )

≤ ∑_{m≥0} E(1_{\{T >m\}} \frac{1}{Y_{1}} … \frac{1}{Y_{m}}),

where the last equation uses that {T > m − 1} is measurable with respect to Y_{1}, …, Y_{m−1} and Z_{m}/Y_{m} is independent of Y_{1}, …, Y_{m−1}.

4. Now the proof can be jointly completed. The essential tool is Spitzer’s identity, which will be applied in its real form (see e.g. [28], p.395). Letting there t ↑ 1 leads to

(2) E(∑_{0≤m<T} e^{−S_{m}}) = exp (∑_{n∈N} \frac{1}{n} E(1_{\{S_{n}≥0\}}e^{−S_{n}})).

Moreover, a result by Rosén [36] provides δ < ∞ such that

(3) P(x ≤ S_{n} < x + 1) ≤ δ \frac{1}{\sqrt{n}} for all n ∈ N and x ∈ R.

Combination of (1) – (3) yields

log E(X_{T}^{0}) ≤ ∑_{n∈N} \frac{1}{n} ∑_{k≥0} P(k ≤ S_{n} < k + 1) e^{−k}
≤ δ ∑_{n∈N} n^{−3/2} ∑_{k≥0} e^{−k} < ∞

and, in view of (3.2), establishes the assertion. □

The main application of (3.3a) concerns the multiplicative model. More generally: if only (S_{n})_{n≥0} does not converge to +∞, boundedness of Z ensures recurrence. Version (3.3b) is better adapted to a model where the role of multiplication and addition is interchanged, i.e. to the recursion

X′_{n} = Y′_{n}(X′_{n−1} + Z′_{n}) for n ∈ N;

in obvious notation: if only (S′_{n})_{n≥0} does not converge to +∞, the existence of E(Z′) already ensures recurrence (the additional hypothesis P(Y′ = 0) = 0 is no real restriction because of (2.3)).

It is an open problem, however, whether the conditional expectation in (3.3a) may be replaced simply by E(Z). Only a partial answer is possible:

(3.4) Proposition. If inf_{n≥0} S_{n} = −∞ and E(Z) < ∞, then ν is recurrent in each of the following cases:

(a) Y and Z independent,

(b) Y ≥ γ for some γ > 0.

Proof. Both assertions are immediate consequences of their counterparts in (3.3). □

References

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

2. Barnsley, M., Elton, J.: A new class of Markov processes for image encoding. Adv. Appl. Prob. 20, 14–32 (1988)

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)

9. Dubins, L., Freedman, D.: Invariant probabilities for certain Markov processes. Ann. Math. Stat. 37, 837–848 (1966)

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)

17. Grincevičius, A.: On the continuity of the distribution of a sum of dependent variables connected with independent walks on lines. Theory Prob. Appl. 19, 163–168 (1974)

25. Lamperti, J.: Criteria for the recurrence or transience of stochastic processes I. J. Math. Anal. Appl. 1, 314–330 (1960)

26. Lamperti, J.: Criteria for stochastic processes II: passage–time moments. J. Math. Anal. Appl. 7, 127–145 (1963)

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

28. Loève, M.: Probability theory I, 4th edition. New York–Heidelberg–Berlin: Springer 1977

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)

33. Nummelin, E.: General irreducible Markov chains and non–negative operators. Cambridge: University Press 1984

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

35. Revuz, D.: Markov chains, 2nd edition. Amsterdam–New York: North–Holland 1984

36. Rosén, B.: On the asymptotic distribution of sums of independent identically distributed random variables. Ark. Mat. 4, 323–332 (1961)

37. Rosenblatt, M.: Recurrent points and transition functions acting on continuous functions. Z. Wahrscheinlichkeitstheorie Verw. Geb. 30, 173–183 (1974)

38. Tweedie, R.: Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771 (1976)

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)