Order-preserving Random Dynamical Systems

Hans G. Kellerer

Mathematisches Institut der Universität München Theresienstrasse 39, D–80333 München, Germany

June 30, 1995

Summary. This paper is concerned with stochastic recursions X_{n} = H_{n}(X_{n−1}) for n ∈ N, where (H_{n})_{n∈N} is a sequence of i.i.d. random transformations in R_{+} independent of the initial variable X_{0}. If the transformations are supposed to be continuous and order-preserving, this results in quite natural notions of (topological) recurrence and transience. In the recurrent case existence and uniqueness of an invariant measure as well as mean and pointwise ergodic theorems are established. Moreover, the associated attractor is investigated. The classification is completed by distinguishing positive and null recurrence corresponding, respectively, to the case of a finite or infinite invariant measure. Equivalently, this amounts to finite or infinite mean passage times.

Mathematics Subject Classifications (1991): Primary 60J05, 60H25; Secondary 58F11, 54H20.

Introduction

In this paper random dynamical systems are studied under the following assumptions on space and time: the evolution is supposed to develop in the space of reals and to proceed in discrete time starting at zero. Thus the process is given by a sequence (X_{n})_{n≥0} satisfying the recursion

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

where X_{0} is a real-valued random variable and H_{n}, n ∈ N are random transformations from R to R. To obtain the Markov property the variables X_{0}, H_{1}, H_{2}, … are supposed to be independent, to obtain a stationary transition kernel the variables H_{1}, H_{2}, … are supposed to be identically distributed. If their common distribution ν is carried by a finite family of transformations, this results in an “iterated function system”, made popular during the past decade by Barnsley, Elton and others (see e.g. [2, 3, 8, 9]). On the other hand, it is shown, for instance, by Kifer in Theorem 1.1 of [18] that, without restricting the support of ν, the model above provides just another possibility to introduce any Markov chain with state space R.

In applications, such a representation arises often quite naturally as is exhibited by the following examples (see also [1, 24, 25]):

(1) The simplest queuing process is given by

X_{n} = (X_{n−1} + U_{n})^{+} for n ∈ N

with i.i.d. variables U_{n}, n ∈ N. Here, X_{n−1} denotes the waiting time of customer n − 1 and U_{n} = S_{n−1} − (T_{n} − T_{n−1}) is the balance between his service time and the arrival times of customers n − 1 and n.

(2) A “savings process” is defined by

X_{n} = U_{n}X_{n−1} + V_{n} for n ∈ N

with i.i.d. variables (U_{n}, V_{n}), n ∈ N. Here, X_{n−1} denotes the balance of a savings account at time n − 1, U_{n} the interest / inflation rate during period n and V_{n} the deposit made at time n (this and a survey of other affine recursions in biology, economics, physics etc. can be found in Vervaat [29]).

(3) An “exchange process” is defined by

X_{n} = (X_{n−1} − U_{n}) ∨ V_{n} for n ∈ N

with i.i.d. variables (U_{n}, V_{n}), n ∈ N. Here, X_{n−1} is the utility of some equipment in use at time n − 1, U_{n} its loss in utility during period n, and V_{n} the utility of a new equipment available at time n (for this and related examples see, for instance, Helland and Nilsen [13]).

The first example differs from the second and the third one by a particular characteristic: the state 0 is a regeneration point, and thus the queuing process fits into the Doeblin-Harris theory for not necessarily discrete Markov chains.

Since the dominating measure, whose existence is postulated in this theory, fails to exist in general, there are attempts, for instance by Rosenblatt [27] or Tweedie [28], to classify Markov chains by stressing the topological structure of the state space. Even under continuity assumptions on the underlying kernel, however, this results in a variety of notions of transience and null or positive recurrence, being thus less convincing than the classical notions for discrete Markov chains. The present paper, therefore, emphasizes the order structure of the state space, motivated by two observations holding for various applications. First, the transformations h : x → (x + u)^{+}, h : x → ux + v, and h : x → (x − u) ∨ v appearing in the examples above are all order-preserving (observing U_{n} ≥ 0 in (2)). Second, in these examples the proper state space is R_{+} (observing V_{n} ≥ 0 in (2) and (3)). As it turns out, accepting these two restrictions presents an appropriate compromise in order to obtain a satisfying theory as well as substantial applications.

While there exists an extensive literature based on the metric structure of the state space by requiring, for instance, an “average contractivity” of the underlying transformations, there are only a few papers with special emphasis on the order structure. The earliest one dates back to Dubins and Freedman [7], who limit, however, their investigations to the compact state space [0,1]. This restriction is given up in Yahav [30], who studies concave increasing mappings from R_{+} to R_{+}. Extending the state space further to R, Bhattacharaya and Waymire in Section II.14 of [4] take up a “splitting” condition from [7]. In all this treatments the main interest concerns the existence and uniqueness of stationary distributions. This holds as well for Brandt et al., who consider in Section 1.3 of [5] order-preserving mappings in partially ordered Polish spaces requiring, however, appropriate compactness and contraction properties.

To see fluctuation aspects to be as interesting as equilibrium results, consider an exchange process with deterministic loss of utility, say U_{n} = 1. Then it is easily established that a (unique) stationary distribution exists if and only if the utility V_{n} of the substitute has a finite expectation. This fails, for instance, if V_{n} has the density

f_{1}(x) = (x + 1)^{−2} or f_{2}(x) = 2x(x + 1)^{−3} for x ≥ 0 .

Due to f_{1}(x) ≤ f_{2}(x) ≤ 2f_{1}(x) for x ≥ 1, in both cases V_{n} behaves similarly as far as it concerns the existence of moments. Nevertheless, there is a significant difference: while in the second case (X_{n})_{n≥0} escapes to infinity, the process is uniformly distributed on R_{+} in the first case (this example appears in the context of (2.4), (6.3)−(6.4), (9.7)).

A detailed survey of the principal results of the present paper appears dispensable, because the headings of the different sections provide a first information about the contents. Instead, the main feature will be summarized as follows: the order-preserving random dynamical systems as considered here represent one of the best suited models for extending discrete Markov chain theory to an uncountable state space. That is because the fundamental criteria for positive / null recurrence or transience − by means of the n-step transition kernels resp. the potential kernel, by means of hitting probabilities resp. mean passage times, or by means of a unique invariant measure − all find their counterpart in the present paper (for a first orientation see the remarks following (6.5), (9.8), (10.1) and preceding (11.4)).

Finally, a historical remark is in order. This work originated from a threepart paper devoted to the special case of recursions

X_{n} = U_{n}X_{n−1} + V_{n} with U_{n}, V_{n} ≥ 0 for n ∈ N .

This affine model, which for constant U_{n} contains in particular first-order autoregressive processes, is of special importance, because it may serve to approximate more complex situations by linearization. During the refereeing process of [16], however, it became clear that most results rely on the topological and order structure of the state space only and make no use of the linear structure. Moreover, it turned out that within a more general framework not only several proofs could be simplified but also several theorems could be strengthened. This led to the decision to develop first the general theory in the present paper and to deal with the special features of affine recursions in a subsequent paper. As it is to be expected, there are, for instance, stronger criteria for positive / null recurrence or transience, if the underlying mappings are compatible with the linear structure. To state just one of the main results of [17], let (S_{n})_{n≥0} be the random walk with increments log U_{n} (≥ −∞). Then, under a weak boundedness condition on V_{n} (and excluding the degenerate case of a common fixed point of the underlying mappings), the following trichotomy holds: the process (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 between −∞ and +∞ resp. diverges to +∞.

Preliminaries

Throughout the paper the state space E is a subinterval of R satisfying min E = 0 and endowed with its Borel σ-algebra B(E). As usual, C(E) denotes the space of bounded continuous functions f : E → R and K(E) the subspace consisting of functions with compact support. Employing the order structure, R(E) denotes the space of (“regular”) functions f : E → R having limits within R from the right and from the left everywhere (including sup E) and V(E) the subspace consisting of functions of bounded variation.

Let the space of continuous mappings from E to E be endowed with the compact open topology. Then the closed subspace H[E] of order-preserving mappings inherits a Polish topology, which is also the initial topology with respect to the evaluation maps h → h(x), x ∈ E. Since H[E] is stable with respect to composition and composition is continuous, H[E] is a topological semigroup. Since E can be embedded into H[E], the mapping (x, h) → h(x) is continuous, too.

M(E) denotes the class of locally finite measures on E and M_{1}(E) the subclass consisting of probability measures. If μf denotes the μ−integral of a function f, then M(E) is endowed with the vague (weak^{∗}) topology, i.e. the initial topology with respect to the mappings μ → μf, f ∈ K(E); the corresponding convergence is denoted by →_{v} . On the subspace M_{1}(E) this induces the weak (narrow) topology, i.e. the initial topology with respect to the mappings μ → μf, f ∈ C(E); the corresponding convergence is denoted by →_{w} .

The main object of this paper is the space N [E] of distributions ν on H[E]. The semigroup structure of H[E] induces a convolution in N [E] and makes this space a topological semigroup itself. Corresponding powers are simply denoted by ν^{n}, i.e.

∫ f(h(x))ν^{n}(dh) = ∫ … ∫ f(h_{1} ∘ … ∘ h_{n}(x)) ν(dh_{1}) … ν(dh_{n})

for x ∈ E, f ∈ C(E) and n ∈ N, while ν^{0} is the unit measure ε_{h} with h being the identity map. Since H[E] is again a Polish space, in particular the support N is well-defined for ν ∈ N [E].

Now the stochastic model can be precisely introduced. Let be given, on some probability space (Ω, A, P),

(1) a sequence of independent random variables H_{n} : Ω → H[E] with identical distribution ν ∈ N [E],

(2) a random variable X_{0} : Ω → E that is independent of (H_{n})_{n∈N}.

This defines an “order-preserving random dynamical system” by

X_{n} = ψ(X_{n−1}, H_{n}) with ψ(x, h) = h(x) ,

which in the sequel will be briefly written as

X_{n} = H_{n}(X_{n−1}) for n ∈ N .

Thus the distribution of (X_{n})_{n≥0} is completely determined by ν ∈ N [E] and the initial law μ_{0} = L(X_{0}). Here, the primary component is ν, and all notions to be defined will depend on that distribution. This dependence will, however, be suppressed in the related notations, because ν is supposed to be fixed.

As usual, the initial law is largely of secondary importance only. If in particular X_{0} = x, this will be expressed by the notation (X_{n}^{x})_{n≥0}, i.e.

X_{n}^{x} = H_{n} ∘ … ∘ H_{1}(x) for x ∈ E and n ≥ 0 .

Thus for general μ_{0} conditional probabilities are given by

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

with an anologous equation for conditional expectations.

Clearly, (X_{n})_{n≥0} is a homogeneous Markov process. Its transition kernel, always denoted by P, transforms a function f on E into P f given by

P f(x) = ∫_{H[E]} f(h(x)) ν(dh) for x ∈ E

and a measure μ on E into μP given by

μP (B) = ∫_{E} ν(h(x) ∈ B) μ(dx) for B ∈ B(E) ,

which for a σ−finite measure μ by Fubini equals

μP (B) = ∫_{H[E]} μ(h(x) ∈ B) ν(dh) for B ∈ B(E) .

The kernel P belongs to the class P[E] of Markov kernels from E to E satisfying the following two conditions:

(1) P transforms C(E) into itself,

(2) P transforms bounded increasing functions into functions of the same type.

It has to be mentioned here that the mapping ν → P from N [E] to P[E] is neither injective nor surjective.

Finally, it has to be pointed out that, in contrast to topology and order, the algebraic structure of the state space is not taken into account. Thus distributions ν ∈ N [E] and ν′ ∈ N [E′] are called “conjugate” and have to be classified in the same way, if there is an order-preserving homeomorphism g : E′ → E such that ν′ is the image of ν under the mapping h → g^{−1} ∘ h ∘ g.

For an example in the case E = R_{+} = E′ let h_{+} ∈ H[E] be strictly increasing with h_{+}(x) > x for all x ∈ E and define h_{−} ∈ H[E] by h_{−}(x) = 0 for x ≤ h_{+}(0) and h_{−}(x) = h_{+}^{−1}(x) otherwise. Then a distribution ν ∈ N [E] with support N = {h_{−}, h_{+}} is conjugate to the distribution ν′ ∈ N [E′] belonging to the queuing process

X_{n} = (X_{n−1} + U_{n})^{+} for n ∈ N

with independent variables U_{n}, n ∈ N, satisfying

P(U_{n} = −1) = ν({h_{−}}) and P(U_{n} = +1) = ν({h_{+}}).

Indeed, it is easily checked that any strictly increasing function g ∈ C([0, 1]) with g(0) = 0 and g(1) = h_{+}(0) can be extended to an appropriate homeomorphism by the definition

g(x + n) = h_{+}^{n}(g(x)) for 0 ≤ x ≤ 1 and n ∈ N.

1. Lower and upper limit

As in discrete Markov chain theory, the first question to be settled concerns the appropriate decomposition of the state space E. For some t ∈ E it may split into two intervals E_{1} = [0, t[ and E_{2} = E \ E_{1} such that h[E_{i}] ⊂ E_{i} for ν−almost all h ∈ H[E] and i = 1, 2. With 0 = min E as reference state the corresponding “class” can be characterized explitely as well as implicitly:

(1.1) Proposition For ν ∈ N [E] the set

E_{0} := ⋃_{n∈N} {x ∈ E : P(X_{n}^{0} ≥ x) > 0}

is the smallest subinterval I of E satisfying the conditions

(a)  0 ∈ I ,
(b)  ν(h[I] ⊂ I) = 1 .

Proof. 1. Since any − open or closed − interval I in E containing 0 can be represented as a countable union of intervals [0, x_{k}], the subset of H[E] occurring in (b) is apparently of type G_{δ} (or even closed) and thus in particular measurable. Since this representation applies to I = E_{0} itself, in establishing (b) it suffices to show that, x = x_{k} being fixed, h(x) ∈ E_{0} for ν−almost all h ∈ H[E].

2. To this end choose n ∈ N with P(X_{n}^{0} ≥ x) > 0 and define

H_{t} := {h ∈ H[E] : h(x) ≥ t} for t ∈ E .

Then the independence of X_{n}^{0} and H_{n+1} yields

{h ∈ H[E] : h(x) ∈ E_{0}} ⊃ {h ∈ H[E] : P(X_{n+1}^{0} ≥ h(x)) > 0}
⊃ {h ∈ H[E] : P(X_{n}^{0} ≥ x, H_{n+1}(x) ≥ h(x)) > 0}
= {h ∈ H[E] : P(H_{n+1}(x)) ≥ h(x)) > 0}
= {h ∈ H[E] : ν(H_{h(x)}) > 0} .

Due to h ∈ H_{h(x)} this implies

{h ∈ H[E] : h(x) ∉ E_{0}} ⊂ {h ∈ H[E] : ν(H_{h(x)}) = 0}
⊂ ⋃ {H_{h(x)} : h ∈ H[E] with ν(H_{h(x)}) = 0} .

Since the sets H_{t} decrease for increasing t, this union can be replaced by a countable one and is thus itself a null set with respect to ν, as had to be shown.

3. Finally, let the subinterval I of E satisfy (a) and (b). Then iteration yields the equation ν^{n}(h[I] ⊂ I) = 1 and thus in particular

P(X_{n}^{0} ∈ I) = ν^{n}(h(0) ∈ I) = 1 for all n ∈ N .

For x ∈ E satisfying the condition P(X_{n}^{0} ≥ x) > 0 this implies x ∈ I, thus proving E_{0} to be minimal. □

The interval E_{0} can be an open or closed subset of E as it may happen already in the following two trivial examples:

(1) the “deterministic system” (E, h), where ν = ε_{h} for some mapping h ∈ H[E], yielding deterministic variables X_{n}, n ∈ N, whenever X_{0} is a constant;

(2) the “independent system” (E, μ), where ν is the image of some measure μ ∈ M_{1}(E) with respect to the canonical injection j of E into H[E], yielding independent variables X_{n}, n ∈ N, with distribution μ.

If the interval E_{0} is a proper subset of E, its upper endpoint is easily identified:

(1.2) Proposition The supremum \overline{x} of the set E_{0} defined by (1.1) is given by

\overline{x} = min\{x ∈ E : h(x) ≤_{ν} x\} whenever \overline{x} ∈ E .

Proof. For each x ∈ E with h(x) ≤_{ν} x the interval I = [0, x] satisfies the condition in (1.1) and thus contains E_{0}, which implies \overline{x} ≤ x. On the other hand, the definition of E_{0} yields h(x) ≤_{ν} \overline{x} for x < \overline{x}, which by the continuity of h ∈ H[E] implies h(\overline{x}) ≤_{ν} \overline{x} whenever the condition \overline{x} ∈ E is satisfied. □

The assumption \overline{x} ∈ E is no real restriction, because E being replaced by \overline{E} := E ∪ \{\overline{x}\} mappings h ∈ H[E] have unique extensions \overline{h} ∈ H[\overline{E}], where possibly ∞ has to be adjoined to R_{+}. Moreover, if \overline{x} ∈ E and the support N of ν is finite, \overline{x} clearly is a fixed point of some h ∈ N.

The implicit description of E_{0} suggests the following notion:

(1.3) Definition The distribution ν ∈ N [E] is called “irreducible”, if the set E_{0} defined by (1.1) coincides with the state space E.

Irreducibility apparently can always be achieved, replacing mappings h ∈ H[E] by their restrictions h_{0} ∈ H[E_{0}]. Moreover, since irreducibility is clearly invariant under conjugation, it suffices in principle, neglecting the trivial case E = {0}, to treat exclusively the two cases E = [0, 1] and E = R_{+} − at the expense, however, of permanent repetitions.

The notion of irreducibility is also compatible with convolution powers:

(1.4) Proposition If ν^{k} ∈ N [E] is irreducible for one k ∈ N, this holds for all k ∈ N.

Proof. The assertion is an immediate consequence of the fact that, for arbitrary x ∈ E, the sequence (P(X_{n}^{0} ≥ x))_{n≥0} increases due to

P(X_{n}^{0} ≥ x) = P(H_{n} ∘ … ∘ H_{1}(0) ≥ x)
= P(H_{1} ∘ … ∘ H_{n}(0) ≥ x) . □

The following two theorems are of central importance in the sequel. Due to the assumptions concerning the consistency with the order structure, lower and upper limit of the process (X_{n})_{n≥0} turn out to be constants, which in addition do not depend on the initial variable X_{0}. The first result is easily established: (1.5) Theorem If ν ∈ N [E] is irreducible, the constant \overline{x} = sup E satisfies

lim sup_{n→∞} X_{n} = \overline{x} a.s. ,

regardless of the initial law. Proof. For x ∈ E there exists l ∈ N such that

P(H_{l} ∘ … ∘ H_{1}(0) ≥ x) > 0 .

Then by monotonicity and independence

P(X_{n} ≥ x infinitely often) ≥ P(lim sup_{k→∞} {H_{(k+1)l} ∘ … ∘ H_{1}(0) ≥ x})
≥ P(lim sup_{k→∞} {H_{(k+1)l} ∘ … ∘ H_{kl+1}(0) ≥ x})
= 1.

Since x ∈ E is arbitrary, lim sup_{n→∞} X_{n} ≥ \overline{x} holds almost surely, while the inverse inequality is obvious. □

The second result is less immediate: (1.6) Theorem If ν ∈ N [E] is irreducible, there is a constant \underline{x} ≤ \overline{x} satisfying

lim inf_{n→∞} X_{n} = \underline{x} a.s. ,

regardless of the initial law. Proof. 1. For x ∈ E and n ≥ 0 define

\underline{X}_{n}^{x} := lim inf_{k→∞} H_{n+k} ∘ … ∘ H_{n+1}(x) .

Then the inequality

\underline{X}_{0}^{0} = lim inf_{k→∞} H_{n+k} ∘ … ∘ H_{n+1}(X_{n}^{0})
≥ lim inf_{k→∞} H_{n+k} ∘ … ∘ H_{n+1}(0) = \underline{X}_{n}^{0}

combined with the equation L(\underline{X}_{0}^{0}) = L(\underline{X}_{n}^{0}) yields

\underline{X}_{0}^{0} = \underline{X}_{n}^{0} a.s. for all n ≥ 0 ,

hence \underline{X}_{0}^{0} is measurable with respect to the completed tail σ-field of (H_{n})_{n∈N}. Thus there is a constant \underline{x} satisfying

(1)  \underline{X}_{0}^{0} = \underline{x} a.s. .

2. For fixed x ∈ E choose n ∈ N such that P(A) > 0 for A := {X_{n}^{0} ≥ x}. With the notation μ_{n} := L(X_{n}^{0}) it follows from (1) that

1 = P((\underline{X}_{0}^{0} ≤ \underline{x})
= ∫_{E} P(\underline{X}_{n}^{y} ≤ \underline{x}) μ_{n}(dy)
≤ ∫_{y≥x} P(\underline{X}_{n}^{x} ≤ \underline{x}) μ_{n}(dy) + ∫_{y<x} P(\underline{X}_{n}^{x} ≤ \underline{x}) μ_{n}(dy)
≤ P(A) P(\underline{X}_{n}^{x} ≤ \underline{x}) + P(Ω \ A) .

In view of P(A) > 0 and the equation L(\underline{X}_{0}^{x}) = L(\underline{X}_{n}^{x}) this implies

(2)  \underline{X}_{0}^{x} ≤ \underline{x} a.s. for all x ∈ E .

3. Together, (1) and (2) yield

\underline{x} = \underline{X}_{0}^{0} ≤ \underline{X}_{0}^{x} ≤ \underline{x} a.s. for all x ∈ E ,

and the assertion follows by applying Fubini. □

The preceding results suggest the following terminology:

(1.7) Definition If ν ∈ N [E] is irreducible, the constants \underline{x} and \overline{x} in (1.5) and (1.6) are called “lower limit” and “upper limit” of ν, respectively.

Now a counterpart of (1.2) can be derived:

(1.8) Proposition If ν ∈ N [E] is irreducible, its lower limit \underline{x} is given by

\underline{x} = max\{x ∈ E : h(x) ≥_{ν} x\} whenever \underline{x} ∈ E .

Proof. For each x ∈ E with h(x) ≥_{ν} x iteration yields X_{n}^{x} ≥ x a.s. for all n ∈ N, which by (1.6) implies \underline{x} ≥ x. On the other hand, whenever \underline{x} ∈ E, choose x > \underline{x} in the case \underline{x} < \overline{x} and x = \underline{x} in the case \underline{x} = \overline{x}. In both cases the hitting times T_{1} < T_{2} < … of [0, x] by (X_{n}^{0})_{n≥0} are defined almost surely, where again by (1.6)

\underline{x} = lim inf_{n→∞} X_{n}^{0}
≤ lim inf_{k→∞} X_{T_{k}+1}^{0}
≤ lim inf_{k→∞} H_{T_{k}+1}(x) .

Since T_{k}, k ∈ N, are stopping times with respect to (H_{n})_{n∈N}, the variables H_{T_{k}+1}, k ∈ N, are again independent with distribution ν. Thus H_{T_{k}+1}(x) ≥ \underline{x} a.s., or equivalently, h(x) ≥_{ν} \underline{x}, which for x ↓ \underline{x} (if necessary) implies h(\underline{x}) ≥_{ν} \underline{x} by the continuity of h ∈ H[E]. □

As stated for the upper limit, if \underline{x} ∈ E and the support N of ν is finite, \underline{x} clearly is a fixed point of some h ∈ N.

The upper limit of an irreducible distribution ν is always uniquely determined by its support N; indeed:

\overline{x} = sup\{h_{n} ∘ … ∘ h_{1}(0) : n ∈ N and h_{i} ∈ N\} .

A corresponding result for the lower limit fails to hold; in fact, even the alternative \underline{x} ∈ E or \underline{x} ∉ E is not a question on N alone, but will lead to the basic distinction between recurrence and transience of ν.

Proper convergence of the process (X_{n})_{n≥0}, even if weakened to convergence in probability, is limited to a degenerate case:

(1.9) Proposition If ν ∈ N [E] is irreducible, then for arbitrary initial law the following assertions are equivalent:

(a)  \underline{x} = x = \overline{x} for some x ∈ E ,
(b)  (X_{n})_{n≥0} converges in E in probability ,
(c)  h(x) =_{ν} x for some x ∈ E .

Proof. 1. The implication (a) ⇒ (b) is immediate from (1.5) and (1.6).

2. Assume now X_{n} → X in probability with μ = L(X) ∈ M_{1}(E) and let d be a bounded metric inducing the topology of E. Then integration over Ω × H[E] by P ⊗ ν yields

∫ ∫ d(X, h(X)) dP dν ≤ ∫ ∫ d(X, X_{n}) dP dν
+ ∫ ∫ d(X_{n}, h(X_{n})) dP dν
+ ∫ ∫ d(h(X_{n}), h(X)) dP dν .

For n → ∞ the three summands on the right-hand side tend to 0: the first one because of the assumption; the second one, because it equals E(d(X_{n}, X_{n+1})) due to the independence of X_{n} and H_{n+1}; the third one, because h(X_{n}) → h(X) in probability due to the continuity of h ∈ H[E]. Therefore

d(x, h(x)) = 0 for μ ⊗ ν−almost all (x, h) ,

hence by applying Fubini

h(x) =_{ν} x for μ−almost all x ∈ E .

3. The implication (c) ⇒ (a) is a consequence of (1.2), yielding \overline{x} ≤ x, and (1.8), yielding \underline{x} ≥ x. □

2. Recurrence and transience

Besides the proper convergence \underline{x} = \overline{x} ∈ E considered in (1.9) there is an improper convergence \underline{x} = \overline{x} ∉ E, generalizing the almost sure divergence of the process (X_{n})_{n≥0} to ∞ in the special case E = R_{+}. This is a first motivation for the following notion, used similarly in [19] in related context:

(2.1) Definition If ν ∈ N [E] is irreducible, the distribution ν (or the kernel P or the process (X_{n})_{n≥0}) is called

(a) “recurrent” if \underline{x} ∈ E,

(b) “transient” if \underline{x} ∉ E.

To begin with the simplest example, a deterministic system (E, h) is easily seen to be recurrent if and only if E = [0, \overline{x}] with \overline{x} being the maximum of the increasing sequence (h^{n}(0))_{n≥0}. Thus choosing E = [0, 1[ and h(x) = (x+1)/2 provides an example for transience due to \underline{x} = 1 = \overline{x}. This appears only logical, observing that the classification in (2.1) is clearly compatible with conjugacy and (E, h) is conjugate to the deterministic process (E′, h′) with E′ = R_{+} and h′(x′) = x′ + 1. Indeed, an appropriate order-preserving homeomorphism g : E′ → E is given by g(x′) = 1 − 2^{−x′}.

By definition an irreducible distribution ν ∈ N [E] is recurrent whenever \overline{x} ∈ E. This is a special case of a more general sufficient condition that often applies:

(2.2) Proposition If ν ∈ N [E] is irreducible and satisfies

ν(sup_{x∈E} h(x) ∈ E) > 0 ,

then ν is recurrent.

Proof. First, the subset of H[E] occurring in the condition is apparently of type F_{σ} and thus in particular measurable. To prove this condition to imply recurrence, choose t ∈ E with ν(sup_{x∈E} h(x) ≤ t) > 0. Then for arbitrary initial law by independence

P(X_{n} ≤ t infinitely often) ≥ P(lim sup_{n→∞} {sup_{x∈E} H_{n}(x) ≤ t}) = 1

and thus \underline{x} ≤ t ∈ E. □

As a trivial example consider an independent system (E, μ), where by definition sup_{x∈E} h(x) ∈ E for ν−almost all h ∈ H[E]. To see that the condition in (2.2) is far from being necessary, consider the queuing process

X_{n} = (X_{n−1} + U_{n})^{+} for n ∈ N ,

where the i.i.d. variables U_{n}, n ∈ N, are arbitrary. With state space E = R_{+} the corresponding distribution ν is carried by the mappings h : x → (x + u)^{+}, u ∈ R, and thus irreducible whenever P(U_{n} > 0) > 0. In this case the condition in (2.2) is not satisfied, while it is well-known that X_{n} → ∞ a.s. if and only if the random walk with increments U_{n} does not diverge to + ∞.

In the case of transience the process (X_{n})_{n≥0} diverges exponentially fast in the following sense:

(2.3) Proposition If ν ∈ N [E] is transient, the random cardinality

Z := |{n ≥ 0 : X_{n} ≤ t}|

for arbitrary initial law and every t ∈ E satisfies

E(exp(uZ)) < ∞ for some u > 0 .

Proof. Define recursively

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

Then by transience

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} < ∞) for x ∈ E

the Markov property 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} < ∞) for k ≥ 0 .

This yields the bound

P^{0}(T_{kl} < ∞) ≤ ϑ^{k}

and thus by monotonicity

P(Z ≥ kl) ≤ P^{0}(T_{kl} < ∞)
≤ ϑ^{k} for k ≥ 0 .

Partial integration shows that each u < −\frac{1}{l} log ϑ satisfies the assertion. □

It is a fundamental consequence of (2.3) that recurrence and transience can be characterized by applying the potential kernel G := ∑_{n≥0} P^{n} to intervals [0, t] with the right endpoints:

(2.4) Theorem If ν ∈ N [E] is irreducible, the following dichotomy holds for arbitrary initial law:

(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 < \overline{x} .

Proof. Both assertions follow by taking the expectation of

Z = ∑_{n≥0} 1_{[0,t]}(X_{n}) ,

which in case (a) is almost surely infinite and in case (b) is integrable by (2.3). □

For an application consider an exchange process with U_{n} = 1, i.e.

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

where the i.i.d. variables V_{n}, n ∈ N, are nonnegative. With state space

E = {x ≥ 0 : P(V_{n} ≥ x) > 0}

the corresponding distribution ν is carried by the mappings h : x → (x−1)∨v, v ∈ E, and thus irreducible by (1.1). Moreover it is recurrent in the case \overline{x} < ∞. Indeed, in this case

sup_{x∈E} ((x − 1) ∨ v) = (\overline{x} − 1) ∨ v ∈ E for v ∈ E

and thus (2.2) applies. As already indicated in the introduction, recurrence as well as transience can occur in the case \overline{x} = ∞. To exhibit appropriate examples, denote by F the common distribution function of V_{n}, n ∈ N. Then the explicit representation

X_{n}^{0} = (V_{1} − (n − 1)) ∨ … ∨ (V_{n−1} − 1) ∨ V_{n} for n ∈ N

yields by independence

P(X_{n}^{0} ≤ t) = ∏_{0≤m<n} F (t + m) .

Now (2.4) applies:

(1) if V_{n}, n ∈ N, have the common density f(x) = (x+1)^{−2}, then F (t) = \frac{t}{t + 1} implies

∑_{n≥0} P(X_{n}^{0} ≤ t) = ∑_{n≥0} \frac{t}{t + n} = ∞ for all t > 0 ,

i.e. the process is recurrent;

(2) if the density is replaced by the function f(x) = 2x(x + 1)^{−3}, then

F (t) = (\frac{t}{t + 1})^{2}, and it follows similarly that the process is transient.

More profound criteria for recurrence and transience can be derived by linearization, i.e. comparing the underlying mappings with affine ones. As already mentioned in the introduction, however, this topic is postponed to [17].

This section concludes with a consequence of (2.4) by which some proofs can be simplified:

(2.5) Proposition If ν^{k} ∈ N [E] is recurrent for one k ∈ N, this holds for all k ∈ N. Moreover, the associated limits \underline{x}_{k} and \overline{x}_{k} are independent of k.

Proof. The case \underline{x} = \overline{x} is settled by (1.4), because X_{n} → X a.s. implies X_{kn} → X a.s. and thus \underline{x}_{k} = \underline{x} = \overline{x} = \overline{x}_{k}. To settle the case \underline{x} < \overline{x}, it is sufficient to apply (2.4) with X_{0} = 0, because it follows as in the proof of (1.4) that the sequence (P(X_{n}^{0} ≤ t))_{n≥0} decreases. □

3. A fundamental inequality

The following result will play a key role in deriving the main results in Sections 4 and 6:

(3.1) Lemma If ν ∈ N [E] is irreducible, there exists an increasing function c : E → R_{+} such that

∑_{n≥0} E(f(X_{n}^{x}) − f(X_{n}^{0})) ≤ c(x) sup_{n≥0} E(f(X_{n}^{0}))

for each increasing function f : E → R_{+} and every x ∈ E.

Proof. First of all, the left-hand side is well-defined, because the differences f(X_{n}^{x}) − f(X_{n}^{0}) are nonnegative. Now, fix x ∈ E and choose k ∈ N such that

H′ := {h′ ∈ H[E] : h′(0) ≥ x}

satisfies the condition

γ := ν^{k}(H′) = P(X_{k}^{0} ≥ x) > 0 .

With the abbreviation H := H[E] this yields the bound

E(f(X_{n}^{x}) − f(X_{n}^{0})) = ∫_{H}[f(h(x)) − f(h(0))] ν^{n}(dh)
= γ^{−1}∫_{h′∈H′} ∫_{h∈H}[…] ν^{n}(dh) ν^{k}(dh′)
≤ γ^{−1}∫_{h′∈H′} ∫_{h∈H}[f(h ∘ h′(0)) − f(h(0))] ν^{n}(dh) ν^{k}(dh′)
≤ γ^{−1}∫_{h′∈H} ∫_{h∈H}[…] ν^{n}(dh) ν^{k}(dh′)
= γ^{−1} E(f(X_{n+k}^{0}) − f(X_{n}^{0})) for n ≥ 0 ,

where the first inequality follows from

f(h ∘ h′(0)) ≥ f(h(x)) for h ∈ H, h′ ∈ H′

and the second one from

f(h ∘ h′(0)) ≥ f(h(0)) for h ∈ H, h′ ∈ H \ H′ .

By summing up, cancelling on the right-hand side, and omitting the term ∑_{0≤l<k} f(X_{l}^{0}) ≥ 0 this yields

∑_{0≤l<m} E(f(X_{l}^{x}) − f(X_{l}^{0})) ≤ γ^{−1} ∑_{m≤l<m+k} E(f(X_{l}^{0}))
≤ kγ^{−1} sup_{n≥0} E(f(X_{n}^{0})) for all m ∈ N .

According to the choice of k and the definition of γ, therefore,

c(x) := ( sup_{k∈N} \frac{1}{k} P(X_{k}^{0} ≥ x))^{−1} for x ∈ E

defines an increasing function as desired. □

The next result is an immediate consequence:

(3.2) Lemma If ν ∈ N [E] is irreducible, then for arbitrary initial law and each increasing function f : E → R_{+} the condition

sup_{n≥0} E(f(X_{n}^{0})) < ∞

implies

(a)  ∑_{n≥0} (f(X_{n}) − f(X_{n}^{0})) < ∞ a.s. ,
(b)  f(X_{n}) − f(X_{n}^{0}) → 0 a.s. .

Proof. The second assertion follows from the first one, which in turn follows in the special case X_{0} = x from (3.1), interchanging the order of summation and integration, and in the general case by applying Fubini. □

Actually, the preceding results extend to larger classes of functions:

(3.3) Theorem If ν ∈ N [E] is irreducible, then for arbitrary initial law

(a)  ∑_{n≥0} |f(X_{n}) − f(X_{n}^{0})| < ∞ a.s. for f ∈ V(E) ,
(b)  f(X_{n}) − f(X_{n}^{0}) → 0 a.s. for f ∈ R(E) .

Proof. (a) A function f ∈ V(E) has a representation f = f_{1} − f_{2} with increasing and bounded functions f_{i} : E → R_{+}, for which (3.2a) applies.

(b) The assertion follows for step functions f from (a) and for functions f ∈ R(E) by uniform approximation. □

By inspecting the proof it is easily noticed that in both statements the convergence is uniform on compact subsets of E, i.e. for instance

sup_{0≤x≤t} |f(X_{n}^{x}) − f(X_{n}^{0})| → 0 a.s. for f ∈ R(E) and t ∈ E .

Assertion (b) cannot be extended to functions f ∈ C(E), as is seen in the transient case already by the deterministic system (E, h) with E = R_{+} and h(x) = x + 1, which is obviously irreducible: if f(x) denotes the euclidean distance of x from the set {0, 2, 4, …}, then |f(X_{n}^{1}) − f(X_{n}^{0})| = 1 for all n ≥ 0.

To exhibit a counterexample in the recurrent case, a more elaborate construction is required. To this end consider the autoregressive process

X_{n} = \frac{1}{2}X_{n−1} + V_{n} for n ∈ N ,

where the i.i.d. variables V_{n}, n ∈ N, attain the values 0 and \frac{1}{2} each with probability \frac{1}{2}. With E = [0, 1[ as state space the corresponding distribution ν is supported by the two mappings h_{0} : x → x/2 and h_{1} : x → (x + 1)/2. It is clearly irreducible and by (2.2) recurrent, where \underline{x} = 0 by (1.8). Denote by (t_{k})_{k≥0} a strictly increasing sequence in E with sup_{k≥0} t_{k} = 1, to be specified later, and define

T_{k} := inf{n ≥ 0 : X_{n}^{0} ≥ t_{k}} for k ≥ 0 .

Since these random times are almost surely finite, there exist n_{k} ∈ N such that

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

Moreover, since the support N of ν is finite, there exist finite sets B_{k} ⊂ [t_{k}, 1[ such that

(2)  P(T_{k} ≤ n_{k}, X_{T_{k}}^{0} ∉ B_{k}) = 0 for k ≥ 0 .

Finally, since the mappings h_{i} leave the set D of dyadic numbers in E and its complement invariant, for fixed x ∈ E \ D there exist finite sets C_{k} ⊂ [t_{k}, 1[ such that

(3)  P(T_{k} ≤ n_{k}, X_{T_{k}}^{x} ∉ C_{k}) = 0 for k ≥ 0 ,

satisfying in addition B_{k} ∩ C_{k} = ∅. Now, starting with t_{0} = 0, choose the levels t_{k} recursively under the constraints t_{k} > max C_{k−1} for k ∈ N. Then the finite sets B_{k} and C_{k} are disjoint subsets of the successive intervals [t_{k}, t_{k+1}[, k ≥ 0, with union E. Thus there exists a function f ∈ C(E) with 0 ≤ f ≤ 1, satisfying f(y) = 0 for y ∈ ⋃_{k≥0} B_{k} and f(y) = 1 for y ∈ ⋃_{k≥0} C_{k}. By (2) and (3) this implies

lim sup_{k→∞} {T_{k} ≤ n_{k}} ⊂ {lim sup_{n→∞} |f(X_{n}^{x}) − f(X_{n}^{0})| = 1}

almost surely, which by (1) yields

lim sup_{n→∞} |f(X_{n}^{x}) − f(X_{n}^{0})| = 1 a.s. ,

providing the desired counterexample.

As a corollary assertion (b) of (3.3) yields a result on functions f that are regular with respect to P, i.e. satisfy 0 ≤ f = P f: in the irreducible case such a function, provided it is contained in R(E), has to be constant. Indeed, the equation P^{n}f = f for n ≥ 0 and the boundedness of f combine by (3.3b) to

f(x) − f(0) = E(f(X_{n}^{x})) − E(f(X_{n}^{0}))
= E(f(X_{n}^{x}) − f(X_{n}^{0}))
→ 0 for all x ∈ E .

To see that outside R(E) there may exist regular functions that are bounded and not constant, consider the autoregressive process from above. Since in this case the requirement f = P f amounts to the equation

f(x) = \frac{1}{2}(f(\frac{x}{2}) + f(\frac{x + 1}{2})) for x ∈ E ,

for instance f = 1_{D} with D again denoting the set of dyadic numbers in E is a solution that is not constant.

This section is concluded by a technical result that will be important in the sequel. It implies in particular for intervals I ⊂ E, visited from 0 infinitely often almost surely, and compact subsets K of E the existence of n ∈ N such that for x ∈ K the hitting probabilities P(X_{n}^{x} ∈ I) are bounded away from 0. Actually, this result can be strengthened and extended to functions:

(3.4) Lemma Let ν ∈ N [E] be irreducible and f ∈ V(E) satisfy

f ≥ 0 and ∑_{n≥0} E(f(X_{n}^{0})) = ∞ .

Then for every t ∈ E there exists m ∈ N such that

E( inf_{0≤x≤t} f(X_{m}^{x})) > 0 .

Proof. First, measurability is ensured, because it suffices to extend the infimum over a countable dense subset of [0, t], containing the countably many points of discontinuity of f. A representation f = f_{1} − f_{2} with increasing and bounded functions f_{i} : E → R_{+} yields the estimate

E( inf_{0≤x≤t} f(X_{n}^{x})) ≥ E(f_{1}(X_{n}^{0})) − E(f_{2}(X_{n}^{t})) =: δ_{n} .

Now the identity

δ_{n} = E(f(X_{n}^{0})) − (E(f_{2}(X_{n}^{t})) − E(f_{2}(X_{n}^{0})))

ensures the existence of some m ∈ N with δ_{m} > 0, because otherwise by (3.1)

∑_{n≥0} E(f(X_{n}^{0})) ≤ ∑_{n≥0} (E(f_{2}(X_{n}^{t})) − E(f_{2}(X_{n}^{0}))) < ∞ ,

contradicting the assumption on f. □

4. Existence and uniqueness of invariant measures

To deal with not necessarily finite invariant measures, the following “localization” is essential:

(4.1) Definition Let ν ∈ N [E] be recurrent and fix t ∈ E with t > \underline{x} or t = \overline{x}. Then:

(a) ^{t}P denotes the “hitting kernel” belonging to ν and [0, t], i.e.

tP (x; B) := P^{x}(X_{T} ∈ B) for x ∈ [0, t] and B ∈ B([0, t]) ,

where

T := inf{n ∈ N : X_{n} ∈ [0, t]};

(b) for arbitrary initial law (^{t}X_{n})_{n≥0} denotes the “embedded process” belonging to (X_{n})_{n≥0} and [0, t], i.e.

tX_{n} := X_{T_{n}} for n ≥ 0 ,

where T_{0} < T_{1} < … are the random times when (X_{n})_{n≥0} is in [0, t].

To include the case t = \overline{x} ∈ E, where ^{t}P = P and no localization is necessary, is convenient for a unified treatment. To assume T_{n} < ∞ in (b) is no real restriction.

For easy reference the required facts from probabilistic potential theory are stated explicitly:

(4.2) Lemma Let ν ∈ N [E] be recurrent and μ ∈ M(E) be excessive with respect to P. If ^{t}μ denotes the restriction of μ to [0, t], then

(a) ^{t}μ is invariant with respect to ^{t}P for t ∈ E with t > \underline{x} or t = \overline{x},

(b) μ is invariant with respect to P.

Proof. (a) If I_{A} for A ∈ B(E) denotes the kernel

I_{A}(x; ·) := 1_{A}(x) ε_{x} for x ∈ E ,

the crucial point is the inequality

μI_{A} ∑_{n≥0} (P I_{E\A})^{n}P ≤ μP

for excessive measures, which follows as the dual result for excessive functions (see e.g. Proposition 2.2.6 in [26]). Applied to A = [0, t] this inequality concerns ^{t}P and implies

(∗)  (^{t}μ^{t}P)(B) ≤ (μP)(B) for B ∈ B([0, t]) .

Therefore μP ≤ μ yields ^{t}μ^{t}P ≤ ^{t}μ proving (a), because ^{t}μ is a finite measure and ^{t}P is a stochastic kernel.

(b) For 0 ≤ f ∈ K(E) choose t ∈ E with t > \underline{x} or t = \overline{x} and supp f ⊂ [0, t] and denote the restriction of f to [0, t] by ^{t}f. Then (a) and (∗) together imply

μf = ^{t}μ^{t}f = (^{t}μ^{t}P)^{t}f ≤ (μP)f .

By varying f this yields the inequality μ ≤ μP required for (b). □

Now the existence of an invariant measure for ν (i.e. for P) can be established as in [10], under some simplification due to the monotonicity. More generally, the following version will be needed in Section 6:

(4.3) Proposition Let ν ∈ N [E] be recurrent and fix t ∈ E with t > \underline{x} or t = \overline{x}. Then for arbitrary initial law the measures

ϱ_{n}(B) := ∑_{0≤m<n} P(X_{m} ∈ B) / ∑_{0≤m<n} P(X_{m} ≤ t) for B ∈ B(E) ,

defined for n ≥ n_{0} according to (2.4a), satisfy:

(a) {ϱ_{n} : n ≥ n_{0}} is a sequentially compact subset of M(E),

(b) each limit point μ ∈ M(E) of the sequence (ϱ_{n})_{n≥n_{0}} is a nontrivial invariant measure for ν.

Proof. (a) For arbitrary s ∈ E choose l ∈ N such that ϑ := P(X_{l}^{s} ≤ t) > 0, which is possible due to the assumption on t. With μ_{m} := L(X_{m}) this implies by monotonicity

P(X_{m+l} ≤ t) ≥ ∫_{x≤s} P(X_{l}^{x} ≤ t) μ_{m}(dx)
≥ ∫_{x≤s} P(X_{l}^{s} ≤ t) μ_{m}(dx)
= ϑ P(X_{m} ≤ s) for m ≥ 0 .

With the norming constants

r_{n} := ∑_{0≤m<n} P(X_{m} ≤ t) for n ≥ 0

this provides the estimate

∑_{0≤m<n} P(X_{m} ≤ s) ≤ ϑ^{−1} ∑_{0≤m<n} P(X_{m+l} ≤ t)
≤ ϑ^{−1} (r_{n} + l) .

Since r_{n} → ∞ by (2.4a), this yields

lim sup_{n→∞} ϱ_{n}([0, s]) ≤ ϑ^{−1} < ∞ .

This being true for all s ∈ E, the measures ϱ_{n}, n ≥ n_{0}, are uniformly locally finite. The asserted compactness follows by considering the associated linear functionals on K(E) and applying the Riesz representation theorem.

(b) The assumption ϱ_{n_{k}} →_{v} μ yields μ ≠ 0, because

μ([0, t]) ≥ lim sup_{k→∞} ϱ_{n_{k}}([0, t]) = 1 .

With μ_{0} := L(X_{0}), moreover,

ϱ_{n_{k}}f = r_{n_{k}}^{−1} ∑_{0≤m<n_{k}} μ_{0} P^{m}f for 0 ≤ f ∈ K(E) .

By approximation of P f ∈ C(E) from below this yields

μ P f ≤ lim inf_{k→∞} ϱ_{n_{k}} P f
= lim inf_{k→∞} r_{n_{k}}^{−1} ∑_{0<m≤n_{k}} μ_{0}P^{m}f
= lim inf_{k→∞} r_{n_{k}}^{−1} ∑_{0≤m<n_{k}} μ_{0}P^{m}f
= μf for 0 ≤ f ∈ K(E) ,

because r_{n_{k}} → ∞ and μ_{0}P^{m}f is bounded by max f. Therefore μ is excessive and thus invariant by (4.2b). □

The following property of the support of invariant measures will be required before its thorough study in Section 7:

(4.4) Theorem Let ν ∈ N [E] be recurrent and μ ∈ M(E) be a nontrivial invariant measure for ν. Then M := supp μ satisfies

inf M = \underline{x} and sup M = \overline{x} .

Proof. 1. Since μ = μP^{n} by assumption, \underline{m} := inf M satisfies

0 = μ([0, \underline{m} [) = ∫_{E} P(X_{n}^{x} < \underline{m}) μ(dx) ,

which for fixed n ≥ 0 implies

P(X_{n}^{x} ≥ \underline{m}) = 1 for μ−almost all x ∈ E .

For any x satisfying this equation simultaneously for all n ≥ 0, by (1.6)

\underline{x} = lim inf_{n→∞} X_{n}^{x} ≥ \underline{m} (a.s.) .

2. To prove the inverse inequality, observe first

P(X_{n}^{x} < \underline{x}) = ν^{n}(h(x) < \underline{x}) = 0 for x ≥ \underline{x} and n ∈ N

according to (2.5) and (1.8). Therefore

μ([0, t]) = ∫_{E} ν^{n}(h(x) ≤ t) μ(dx)
= ∫_{x<\underline{x}} ν^{n}(h(x) ≤ t) μ(dx) for t < \underline{x} .

Since μ is locally finite, the dual form of Fatou’s lemma applies and leads to

μ([0, t]) = (lim sup_{n→∞}) ∫_{x<\underline{x}} P(X_{n}^{x} ≤ t) μ(dx)
≤ ∫_{x<\underline{x}} lim sup_{n→∞} P(X_{n}^{x} ≤ t) μ(dx)
≤ ∫_{x<\underline{x}} P(lim sup_{n→∞} \{X_{n}^{x} ≤ t\}) μ(dx)
≤ ∫_{x<\underline{x}} P(lim inf_{n→∞} X_{n}^{x} ≤ t) μ(dx)
= 0 for t < \underline{x} .

For t ↑ \underline{x} this implies \underline{m} ≥ \underline{x}.

3. The inequality \overline{m} ≥ \overline{x} for \overline{m} := sup M follows as in part 1 of the proof, replacing (1.6) by (1.5), while the inverse inequality holds by the definition of \overline{x}. □

Now uniqueness of the invariant measure can be established. At the first step (3.3) is crucial:

(4.5) Lemma Let ν ∈ N [E] be recurrent and fix t ∈ E with t > \underline{x} or t = \overline{x}. For f ∈ V(E) with supp f ⊂ [0, t] and g = 1_{[0,t]} define

Q_{n}^{x}(f, g) := ∑_{0≤m<n} f(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{x}) for x ∈ E .

Then there exist constants \underline{q}(f, g) and \overline{q}(f, g) such that

lim inf_{n→∞} Q_{n}^{x}(f, g) = \underline{q}(f, g) a.s. and
lim sup_{n→∞} Q_{n}^{x}(f, g) = \overline{q}(f, g) a.s. for every x ∈ E .

Proof. 1. The limits on the left-hand side are well-defined according to the choice of t. Moreover, they are independent of x. Indeed:

(1) In the denominator x may be replaced by 0, because the quotient

∑_{0≤m<n} g(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{0}) = 1 + ( ∑_{0≤m<n} (g(X_{m}^{x})−g(X_{m}^{0})) / ∑_{0≤m<n} g(X_{m}^{0}))

tends to 1 almost surely by (3.3a) and the assumption on t.

(2) In the nominator x may be replaced by 0, because the difference

∑_{0≤m<n} f(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{0}) − ∑_{0≤m<n} f(X_{m}^{0}) / ∑_{0≤m<n} g(X_{m}^{0})

= ∑_{0≤m<n} (f(X_{m}^{x}) − f(X_{m}^{0})) / ∑_{0≤m<n} g(X_{m}^{0})

tends to 0 almost surely for the same reason.

2. Since the summands with m = 0 may be neglected, using the abbreviation

[…] := H_{m} ∘ … ∘ H_{2}(H_{1}(0)) ,

the lower limit equals

lim inf_{n→∞} Q_{n}^{0}(f, g) = lim inf_{n→∞} ∑_{1≤m<n} f([…]) / ∑_{1≤m<n} g([…]) .

Therefore by part 1 of the proof, applying Fubini, the arguments […] of f and g can be replaced by H_{m} ∘ … ∘ H_{2}(0) up to a set of probability 0. Continuing, it follows that the lower limit is measurable with respect to the completed tail σ-field of (H_{n})_{n∈N}. Thus it is almost surely a constant − and the same holds for the upper limit. □

At the next step the pointwise ergodic theorem enters:

(4.6) Lemma Let ν ∈ N [E] be recurrent and μ ∈ M(E) be a nontrivial invariant measure for ν. Then, in continuation of (4.5),

\underline{q}(f, g) = ∫_{E} f dμ / μ([0, t]) = \overline{q}(f, g) .

Proof. Since μ([0, t]) is finite and by (4.4) strictly positive, the restriction ^{t}μ of μ to [0, t] may be assumed to be normalized, hence by (4.2a) to be a stationary distribution for ^{t}P. If now X_{0} is distributed according to (the trivial extension of) ^{t}μ, then (^{t}X_{n})_{n≥0} is a stationary process. Since f is bounded, the classical ergodic theorem therefore ensures that

Q(f, g) := lim_{n→∞} \frac{1}{n} ∑_{0≤m<n} f(^{t}X_{m})

exists almost surely. Now on {X_{0} = x} the sequence (Q_{n}^{x}(f, g))_{n≥0} arises from the successive means of (f(^{t}X_{n}))_{n≥0} through “extension to the right by constancy” in an evident sense. Therefore by (4.5), applying once more Fubini,

\underline{q}(f, g) = Q(f, g) = \overline{q}(f, g) a.s. .

Again the stationarity of (^{t}X_{n})_{n≥0} and the boundedness of f imply

E(Q(f, g)) = ∫_{E} f dμ ,

and the assertion follows. □

Now one of the principal results can be established:

(4.7) Theorem For each recurrent distribution ν ∈ N [E] there exists a nontrivial invariant measure μ ∈ M(E) such that every excessive measure μ′ ∈ M(E) is a multiple of μ.

Proof. Choose μ according to (4.3) and let μ′ ∈ M(E) be another nontrivial excessive, hence by (4.2b) invariant, measure. Then for t and f, g satisfying the assumptions of (4.5), according to (4.6),

∫_{E} f dμ / μ([0, t]) = ∫_{E} f dμ′ / μ′([0, t]) .

Specialized to f = 1_{[0,s]} , s ≤ t, this provides a constant γ_{t} such that

μ′(B) = γ_{t} μ(B) for B ∈ B([0, t]) ,

where in fact γ_{t}, due to μ′([0, t]) ≠ 0, is independent of t. □

The measure μ that this theorem assigns to a recurrent distribution ν actually stands for a one-dimensional family. Nevertheless it will be called “the invariant measure” in the sequel.

At this point it has to be emphasized that the uniqueness statement in (4.7) concerns locally finite measures only. To exhibit an example, choose E = [0, 1[ and let ν assign mass \frac{1}{2} to the two mappings defined by

h_{1}(x) = \frac{1}{3} (2x + 1) and h_{2}(x) = \frac{1}{2} x ∨ (2x − 1) .

Then ν is clearly irreducible and the uniform distribution μ on E is easily seen to be a finite invariant measure. With μ as initial law the series ∑_{n≥0} P(X_{n} ≤ t) diverges for all t > 0 and thus ν is recurrent by (2.4b). On the other hand, it is not hard to check that

μ′ := ∑_{x∈D} x ε_{x} with D := E ∩ Q

defines another invariant measure, which, however, is σ-finite only.

Finally, it has to be mentioned that − as in discrete Markov chain theory − neither existence nor uniqueness of nontrivial locally finite invariant measures carry over to the transient case.

5. The regenerative case

Clearly, a process (X_{n})_{n≥0} transient according to (2.1) cannot be recurrent in the sense of Harris, due to X_{n} → \overline{x} ∉ E a.s.. The counterexample at the end of the preceding section implies, on the other hand, that a process (X_{n})_{n≥0} recurrent according to (2.1) need not be recurrent in the restricted sense, because in this case there is always an − up to a constant factor − unique σ-finite invariant measure (see e.g. [23, 26]). There is, however, a particular situation that fits into this framework and will be needed in the following section. This “regenerative case” makes no use of the topological structure and arises, if the invariant measure contains atoms. The crucial consequence of this assumption is the following fact:

(5.1) Lemma Let ν ∈ N [E] be recurrent with invariant measure μ. Then μ({z}) > 0 implies for arbitrary initial law

P(X_{n} = z infinitely often) = 1 .

Proof. An application of (4.5) and (4.6) to t = z and f = 1_{{z}} yields

∑_{0≤m<n} 1_{{z}}(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{x}) → μ({z})/μ([0, z]) a.s.

for every x ∈ E, which verifies the assertion by applying Fubini. □

A question left aside in the preceding section is how to determine the invariant measure μ for a recurrent distribution ν. There is, in general, no chance to solve the integral equation

μ(B) = ∫_{E} μ(h(x) ∈ B) ν(dh) for B ∈ B(E)

explicitly. An exception, however, is provided by the regenerative case as can be deduced from the Harris theory. Since in the order context the proof of the relevant result is especially simple, it is carried out:

(5.2) Theorem Let ν ∈ N [E] be recurrent with invariant measure μ. Then μ({z}) > 0 implies

μ(B) = μ({z}) E^{z}( ∑_{0≤n<T_{z}} 1_{B}(X_{n})) for B ∈ B(E) ,

where T_{z} denotes the hitting time of z by (X_{n})_{n≥0}.

Proof. 1. To establish first the invariance of the measure μ′ defined by the expectation on the right-hand side, choose f = 1_{[0,t]} with t ∈ E. Since T_{z} by (5.1) is almost surely finite, the condition X_{0} = z yields

μ′P f = E^{z}( ∑_{0≤n<T_{z}} f(X_{n+1}))
= E^{z}( ∑_{0<n≤T_{z}} f(X_{n}))
= E^{z}( ∑_{0≤n<T_{z}} f(X_{n})) = μ′f .

Since t ∈ E is arbitrary, this implies μ′P = μ′. In view of (4.7) and μ′(B) = 1 for B = {z} it remains to show μ′ to be locally finite.

2. To this end consider the function f = 1_{{z}} and observe that by (5.1) the condition ∑_{n≥0} E(f(X_{n}^{0})) = ∞ in (3.4) is satisfied. Thus for z ≤ t ∈ E there exists n ∈ N such that

ϑ := inf_{0≤x≤t} P(X_{m}^{x} = z) > 0 .

By the Markov property this implies

μ′([0, t]) = E^{z}( ∑_{n≥0} 1_{{T_{z}>n}}1_{[0,t]} (X_{n}))
= ∑_{n≥0} P^{z}(^{t}X_{k} ≠ z for 0 < k ≤ n)
≤ m ∑_{l≥0} P^{z}(^{t}X_{k} ≠ z for 0 < k ≤ lm)
≤ m ∑_{l≥0} P^{z}(^{t}X_{km} ≠ z for 0 < k ≤ l)
≤ m ∑_{l≥0} (1 − ϑ)^{l} < ∞ ,

i.e. the measure μ′ is locally finite. □

In the regenerative case the initial law disappears in a strong sense:

(5.3) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ. Then μ({z}) > 0 implies for arbitrary initial law

P(X_{n} = X_{n}^{0} eventually) = 1 .

Proof. Application of (3.3b) to f = 1_{{z}} yields

P(1_{{z}}(X_{n}) = 1_{{z}}(X_{n}^{0}) eventually) = 1 .

Combined with (5.1) this implies that the random time

T := inf{n ∈ N : X_{n} = X_{n}^{0} = z}

is almost surely finite, where clearly X_{n} = X_{n}^{0} for n ≥ T. □

A first consequence of this result concerns the tail events:

(5.4) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ and μ({z}) > 0. Then for arbitrary initial law the tail σ-field of (X_{n})_{n≥0} is trivial.

Proof. Let B be a Borel subset of ∏_{n≥0} E, not depending on any finite number of coordinates. Then an application of (5.3) to n ∈ N as starting time shows that the two events

A := {(X_{0}, X_{1}, …) ∈ B} = {(X_{0}, …, X_{n}, H_{n+1}(X_{n}), …) ∈ B}

and

A′ := {(0, …, 0, H_{n+1}(0), …) ∈ B}

agree almost surely, hence A is contained in the completed tail σ-field of (H_{n})_{n∈N} as well and thus has probability 0 or 1. □

Another consequence of (3.4) is the following aperiodicity:

(5.5) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ and μ({z}) > 0. Then there exists n_{0} ∈ N such that

P(X_{n}^{z} = z) > 0 for n ≥ n_{0} .

Proof. As in the proof of (5.2) choose m ∈ N satisfying

ϑ := inf_{0≤x≤z} P(X_{m}^{x} = z) > 0 .

With μ_{1} := L(X_{1}^{z}) it follows that

P(X_{m+1}^{z} = z) ≥ ∫_{x≤z} P(X_{m}^{z} = z) μ_{1}(dx)
≥ ϑ P(X_{1}^{z} ≤ z) > 0 ,

because P(X_{1}^{z} ≤ z) = 0 by iteration would lead to X_{n}^{z} > z for all n ∈ N almost surely, contradicting (5.1). From P(X_{n}^{z} = z) > 0 for n = m, m + 1 it follows, combining k periods of length m and l periods of length m + 1, that

P(X_{n}^{z} = z) > 0 for n = km + l(m + 1) ,

hence n_{0} = (m − 1)m satisfies the assertion. □

This result implies in particular that z is a fixed point of some h in the semigroup generated by the support N of ν. While this property is clearly not sufficient for μ({z}) > 0, the following criterion holds:

(5.6) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ. Then for t ∈ E with t > \underline{x} or t = \overline{x} the following assertions are equivalent:

(a)  μ({z}) > 0 ,
(b)  P(X_{n}^{x} = z for 0 ≤ x ≤ t) > 0 for some n ∈ N .

Proof. 1. If (a) is satisfied, combination of (5.1) and (5.3) provides n ∈ N such that

P(X_{n}^{0} = z = X_{n}^{t}) > 0 ,

which by monotonicity agrees with the probability in (b).

2. If (b) is satisfied, then the estimate

μ({z}) = ∫_{E} P(X_{n}^{x} = z) μ(dx)
≥ P(X_{n}^{x} = z for 0 ≤ x ≤ t) μ([0, t])

yields μ({z}) > 0, because μ([0, t]) > 0 by (4.4). □

It is a consequence of this equivalence that \overline{x} ∈ E implies μ(\{\overline{x}\}) > 0. Indeed, in this case ν is recurrent and by definition there exists n ∈ N such that P(X_{n}^{0} = \overline{x}) > 0, hence due to X_{n}^{0} ≤ X_{n}^{x} ≤ \overline{x} for all x ∈ E condition (b) is satisfied.

For the boundary values the criterion (5.6) simplifies:

(5.7) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ and assume \underline{x} < \overline{x}. Then

(a) μ(\{\underline{x}\}) > 0 if and only if ν(h(x) = \underline{x}) > 0 for some x > \underline{x} ,

(b) μ(\{\overline{x}\}) > 0 if and only if ν(h(x) = \overline{x}) > 0 for some x < \overline{x} .

Proof. (a) The function

g(x) := ν(h(x) = \underline{x}) for x ∈ E

decreases for x ≥ \underline{x}, because h(\underline{x}) ≥_{ν} \underline{x} by (1.8), and satisfies g(\underline{x}) < 1, because otherwise \underline{x} = \overline{x} by (1.9). Moreover, by (4.4)

μ(\{\underline{x}\}) = ∫_{x≥\underline{x}} g(x) μ(dx) .

Thus μ(\{\underline{x}\}) > 0 implies g(x) > 0 for some x > \underline{x}, while μ(\{\underline{x}\}) = 0 implies g(x) = 0 for μ−almost all x > \underline{x}, hence for all x > \underline{x} by (4.4).

(b) Under each condition \overline{x} belongs to E, because ν(h(x) = \overline{x}) > 0 for some x < \overline{x} implies \overline{x} ∈ E by (1.1). Therefore − with obvious modifications − the proof of (a) carries over to (b). □

A typical example for (a) is the queuing process, where in case of recurrence always \underline{x} = 0 and μ(\{\underline{x}\}) > 0.

6. Ratio ergodic theorems

To derive ergodic theorems that are not restricted to continuous functions of the process (X_{n})_{n≥0}, some preparations are necessary:

(6.1) Lemma If ν ∈ N [E] is recurrent, then for \underline{x} < t ∈ E and arbitrary initial law

∑_{0≤m<n} P(X_{m} ≤ t) / ∑_{0≤m<n} P(X_{m}^{0} ≤ t) → 1 .

Proof. 1. With the notations g := 1_{[0,t]} and f := 1 − g the assertion holds in the case X_{0} = s, because

∑_{0≤m<n} P(X_{m}^{s} ≤ t) / ∑_{0≤m<n} P(X_{m}^{0} ≤ t)

= 1 − ( ∑_{0≤m<n} (E(f(X_{m}^{s})) − E(f(X_{m}^{0}))) / ∑_{0≤m<n} P(X_{m}^{0} ≤ t)) ,

where the last quotient tends to 0 by (3.1) and (2.4a).

2. For arbitrary μ_{0} := L(X_{0}) and s ∈ E the estimate

E(g(X_{m}^{0})) ≥ E(g(X_{m})) ≥ E(g(X_{m}^{s})) μ_{0}([0, s])

holds, because the function g decreases. Summation over 0 ≤ m < n and division yields for the ratios r_{n} under consideration the bounds

(1)  lim sup_{n→∞} r_{n} ≤ 1 ,
(2)  lim inf_{n→∞} r_{n} ≥ μ_{0}([0, s]) ,

where (1) uses part 1 of the proof. The assertion now follows for s ↑ \overline{x} (or s = \overline{x}). □

The next step relies on results for the regenerative case:

(6.2) Lemma Let ν ∈ N [E] be recurrent with invariant measure μ and μ(\{z\}) > 0. Then for \underline{x} < t ∈ E and arbitrary initial law

∑_{0≤m<n} P(X_{m} = z) / ∑_{0≤m<n} P(X_{m} ≤ t) → μ({z})/μ([0, t]) .

Proof. 1. It suffices to consider the case X_{0} = z. Indeed:

(1) In the nominator X_{m} may be replaced by X_{m}^{z} in view of (6.1).

(2) To extend this to the denominator, introduce the hitting time T_{z} of z by (X_{n})_{n≥0} and define

p_{k} := P(X_{k}^{z} = z) for k ≥ 0 .

Conditioning with respect to {X_{0} ≠ z} shows that P(X_{0} = z) = 0 may be assumed. Then decomposition according to the first stay in z yields

∑_{0≤m<n} P(X_{m} = z) / ∑_{0≤m<n} P(X_{m}^{z} = z)

= ∑_{0≤m<n} ( ∑_{0≤k<m} P(T_{z} = m − k) p_{k}) / ∑_{0≤k<n} p_{k}
= ∑_{0≤k<n} p_{k} P(T_{z} < n − k) / ∑_{0≤k<n} p_{k}
→ lim_{n→∞} P(T_{z} < n) = 1 ,

because ∑_{k≥0} p_{k} = ∞ and P(T_{z} < ∞) = 1 by (5.1).

2. To verify the assertion in the case X_{0} = z, define

q_{k} := P(X_{k}^{z} ≤ t and T_{z} > k) for k ≥ 0 .

Then decomposition according to the last stay in z yields

∑_{0≤m<n} P(X_{m}^{z} ≤ t) / ∑_{0≤m<n} P(X_{m}^{z} = z)

= ∑_{0≤m<n} ∑_{0≤k≤m} p_{k} q_{m−k} / ∑_{0≤k<n} p_{k}
= ∑_{0≤k<n} p_{k} E^{z}( ∑_{0≤l<T_{z}∧(n−k)} 1_{[0,t]}(X_{l})) / ∑_{0≤k<n} p_{k}
→ lim_{n→∞} E^{z}( ∑_{0≤l<T_{z}∧(n−k)} 1_{[0,t]}(X_{l}))
= E^{z}( ∑_{0≤l<T_{z}} 1_{[0,t]}(X_{l})) ,

again due to ∑_{k≥0} p_{k} = ∞, and the assertion follows by (5.2). □

Now a first information on the fluctuation of a recurrent process (X_{n})_{n≥0} by means of its invariant measure can be obtained. In its general form it concerns one sequence (H_{n})_{n∈N}, but two possibly different initial variables:

(6.3) Theorem Let ν ∈ N [E] be recurrent with invariant measure μ and denote by (X′_{n})_{n≥0} a copy of (X_{n})_{n≥0} with X′_{0} replacing X_{0}. Then for functions f, g ∈ R(E) with compact support

∑_{0≤m<n} E(f(X_{m})) / ∑_{0≤m<n} E(g(X′_{m})) → μf/μg ,

provided μf ≠ 0 or μg ≠ 0.

Proof. 1. By comparing both the denominator and the nominator with the corresponding sum for 1_{[0,t]} the situation can be simplified to the case g = 1_{[0,t]}, where t ∈ E with t > \underline{x} or t = \overline{x}. Moreover, μ(\{t\}) = 0 may be supposed unless t = \overline{x}. Finally, the assumption X′_{0} = X_{0} means no real restriction in view of (6.1).

2. Now consider the measures ϱ_{n} defined in (4.3). If ϱ_{n_{k}} →_{v} ϱ ∈ M(E) is any convergent subsequence, (4.3b) and the uniqueness of the invariant measure imply ϱ = γ μ. Since g is μ−almost continuous, the constant γ satisfies

γ μ([0, t]) = lim_{k→∞} ϱ_{n_{k}}([0, t]) = 1 ,

hence is independent of the subsequence, and thus by (4.3b)

ϱ_{n}f → ϱf = μf/μg for all f ∈ K(E) .

3. For a, b ∈ E with a ≤ b, approximating by K(E) from below and above, part 2 of the proof yields

(1)  lim inf_{n→∞} ϱ_{n}(]a, b[) ≥ ϱ(]a, b[) ,

(2)  lim sup_{n→∞} ϱ_{n}([a, b]) ≤ ϱ([a, b]) .

In particular, (2) implies that the convergence ϱ_{n}({z}) → ϱ({z}), established in (6.2) for the case μ({z}) > 0, extends to the case μ({z}) = 0. Together with (1) this leads to

lim inf_{n→∞} ϱ_{n}([a, b]) = lim inf_{n→∞} (ϱ_{n}(]a, b[) + ϱ_{n}({a}) + ϱ_{n}({b}))
= lim inf_{n→∞} ϱ_{n}(]a, b[) + ϱ({a}) + ϱ({b})
≥ ϱ(]a, b[) + ϱ({a}) + ϱ({b}) ,

hence to

(3)  lim inf_{n→∞} ϱ_{n}([a, b]) ≥ ϱ([a, b]) .

4. Combined, equations (2) and (3) yield

ϱ_{n}f → ϱf = μf/μg for all f = 1_{[a,b]} ∈ R(E) .

Therefore the assertion holds for all step functions f with compact support. Thus, approximating a function f ∈ R(E) with compact support by such functions from below and above, the proof is completed. □

As a first application of this ergodic theorem consider the exchange process (X_{n})_{n≥0} studied in Section 2. If it is recurrent (which can be tested by (2.4)) and t > \underline{x} (which can be determined by (1.8)), then the sequence of ratios

P(X_{n}^{0} ≤ s) / P(X_{n}^{0} ≤ t) = ∏_{0≤m<n} F (s + m)/F (t + m)

converges for every s ∈ E to a limit G(s) ≤ ∞, because the right-hand side decreases for s ≤ t and increases for s ≥ t. Then even more

∑_{0≤m<n} P(X_{n}^{0} ≤ s) / ∑_{0≤m<n} P(X_{n}^{0} ≤ t) → G(s) ,

hence by (6.3) the function G is finite and the invariant measure μ is given by

μ([0, s]) = ∏_{n≥0} F (s + n)/F (t + n) for all s ∈ E .

Applied in particular to the recurrent case (1) with F (t) = \frac{t}{t + 1}, it turns out that \underline{x} = 0 and μ is simply the Lebesgue measure on R_{+}.

In stating the pointwise analogue of the mean version (6.3) more care has to be taken of (X_{0}, X′_{0}):

(6.4) Theorem Let the assumptions of (6.3) be satisfied and in addition (X_{0}, X′_{0}) and (H_{n})_{n∈N} be independent. Then for functions f, g ∈ R(E) with compact support

∑_{0≤m<n} f(X_{m}) / ∑_{0≤m<n} g(X′_{m}) → μf/μg a.s. ,

provided μf ≠ 0 or μg ≠ 0.

Proof. By applying Fubini it follows that X_{0} and X′_{0} may be assumed to be constant. Moreover, as in the proof of (6.3), the situation can be simplified to the case g = 1_{[0,t]}, where t ∈ E with t > \underline{x} or t = \overline{x}. Since in a self-explanatory notation

\frac{S(f, x)}{S(g, y)} = \frac{S(f, x)}{S(g, x)} \frac{S(g, x)}{S(g, 0)} \frac{S(g, 0)}{S(g, y)} ,

only the following two assertions have to be verified:

(1)  ∑_{0≤m<n} f(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{x}) → μf/μg a.s. ,
(2)  ∑_{0≤m<n} g(X_{m}^{x}) / ∑_{0≤m<n} g(X_{m}^{0}) → 1 a.s. .

Concerning (1), this follows from (4.5) and (4.6) in the case of step functions f and by approximation from below and above in the case f ∈ R(E). Concerning (2), this in fact has been derived already in part 1 of the proof of (4.5). □

Applied to the exchange process preceding this theorem, with λ denoting the Lebesgue measure, it follows for subintervals I_{k} of R_{+} of positive and finite length that

∑_{0≤m<n} 1_{I_{1}}(X_{m}) / ∑_{0≤m<n} 1_{I_{2}}(X_{m}) → λ(I_{1})/λ(I_{2}) a.s. ,

regardless of the initial law.

The next result concerns the orbits of the process themselves. In view of (4.4) it provides a simultaneous generalization of (1.5) and (1.6):

(6.5) Theorem Let ν ∈ N [E] be recurrent with invariant measure μ and define the random set

L(ω) := {x ∈ E : x is limit point of (X_{n}(ω))_{n≥0}} .

Then with probability 1

L(ω) = supp μ ,

regardless of the initial law.

Proof. 1. Let I_{k}, k ∈ N, be a countable base for E consisting of bounded open subintervals of E. Then the inclusion L(ω) ⊃ supp μ holds if and only if

∑_{n≥0} 1_{I_{k}}(X_{n}(ω)) = ∞ whenever μ(I_{k}) > 0 .

Applying (6.4) to f = 1_{I_{k}} and g = 1_{[0,t]}, where t ∈ E with t > \underline{x} or t = \overline{x}, shows that this holds indeed with probability 1.

2. To prove the inverse inclusion, denote by L_{t}(ω) the analogue of L(ω) for the process (^{t}X_{n})_{n≥0}. Moreover, let D consist of \overline{x} in the case \overline{x} ∈ E and of a countable subset of \{t ∈ E : t > \underline{x}\} with sup D = \overline{x} otherwise. Then clearly

L(ω) = ⋃_{t∈D} L_{t}(ω) ,

hence it suffices to verify that with probability 1

L_{t}(ω) ⊂ supp μ for t ∈ D .

To this end let X_{0} first be distributed according to (the trivial extension of) the normalized restriction of μ to [0, t]. Then (^{t}X_{n})_{n≥0} is stationary by (4.2a) and thus

(∗)  P(^{t}X_{n} ∉ I_{k} eventually) = 1 whenever I_{k} ∩ supp μ = ∅ ,

as desired. Finally, an application of (3.3b) to f = 1_{I_{k}} shows that the distribution of X_{0} in fact is irrelevant for (∗). □

Together, (2.4) and (6.5) imply that the two familiar criteria for recurrence / transience from discrete Markov chain theory carry over to the present setting in the following form:

(1) If ν is recurrent, then for x ∈ supp μ always

P^{x}(X_{n} ∈ G infinitely often) = 1 ,

hence

E^{x}(|{n ≥ 0 : X_{n} ∈ G}|) = ∞ ,

provided G is an open neighborhood of x.

(2) If ν is transient, then for x ∈ E always

E^{x}(|{n ≥ 0 : X_{n} ∈ K}|) < ∞ ,

hence

P^{x}(X_{n} ∈ K infinitely often) = 0 ,

provided K is a compact subset of E.

The final result of this section is related to (5.5) and (5.6):

(6.6) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ. Then for each open subset G of E satisfying μ(G) > 0 and every t ∈ E there exists n_{0} ∈ N such that

P(X_{n}^{x} ∈ G for 0 ≤ x ≤ t) > 0 for n ≥ n_{0} .

Proof. Since G may be assumed to be a bounded interval, f = 1_{G} in view of (6.3) satisfies all conditions in (3.4). Accordingly there exists m ∈ N such that

ϑ := P(X_{m}^{x} ∈ G for 0 ≤ x ≤ t) > 0 ,

where the assumption t > \underline{x} or t = \overline{x} means no loss of generality. By applying Fubini it follows that

P(X_{l+m}^{x} ∈ G for 0 ≤ x ≤ t) = ∫_{H[E]} P(X_{m}^{h(x)} ∈ G for 0 ≤ x ≤ t) ν^{l}(dh)
≥ ϑ ν^{l}(h(t) ≤ t) for l ∈ N ,

because x ≤ t and h(t) ≤ t imply h(x) ≤ t. Now ν^{l}(h(t) ≤ t) > 0 follows from (2.5) and (1.8) in the case t > \underline{x} and is trivial in the case t = \overline{x}. Therefore n_{0} = m satisfies the assertion. □

7. Properties of the attractor

While in the transient case \overline{x} attracts the process (X_{n})_{n≥0}, in the recurrent case (6.5) suggests the following terminology:

(7.1) Definition If ν ∈ N [E] is recurrent with invariant measure μ, the set M := supp μ is called the “attractor” of ν.

As a first information (4.4) yields

inf M = \underline{x} and sup M = \overline{x} ,

where \underline{x} ∈ M in any case, while \overline{x} ∈ M only in the case \overline{x} ∈ E.

Similarly to (1.1), there is an implicit characterization:

(7.2) Theorem If ν ∈ N [E] is recurrent, its attractor is the smallest nonempty closed subset F of E satisfying the condition

(a)  ν(h[F] ⊂ F) = 1 ,

or, equivalently, the condition

(b)  h[F] ⊂ F for all h ∈ N .

Proof. 1. Since the set of mappings h ∈ H[E] with h[F] ⊂ F is closed, both conditions are clearly equivalent. Moreover, any nonempty closed set F ⊂ E satisfying (a) satisfies the corresponding condition with respect to ν^{n} as well. For any x ∈ F this implies P(X_{n}^{x} ∈ F) = 1 for all n ≥ 0, and thus the process (X_{n}^{x})_{n≥0} with probability 1 has all its limit points in F. Therefore the inclusion M ⊂ F is a consequence of (6.5).

2. It remains to verify that (b) is satisfied for F = M. To this end consider x = h_{0}(x_{0}) with x_{0} ∈ M and h_{0} ∈ N, and let G ⊂ E be any open neigborhood of x. Then, due to the continuity of the mapping (x, h) → h(x), there are open sets G_{0} ⊂ E and H_{0} ⊂ H[E] such that

(x_{0}, h_{0}) ∈ G_{0} × H_{0} and h(x) ∈ G for x ∈ G_{0}, h ∈ H_{0} .

By the invariance of μ this yields

μ(G) = (μ ⊗ ν){(x, h) : h(x) ∈ G}
≥ (μ ⊗ ν) (G_{0} × H_{0}) > 0 .

Therefore x has to be contained in the support of μ. □

It is a consequence of (b) that the attractor of a recurrent distribution ν depends on it only through its support N.

In the following two propositions \overline{B} denotes the closure of a subset B of E. Then M and N are related by an equation that is basic in the context of selfsimilar sets (see e.g. [12, 14]):

(7.3) Proposition If ν ∈ N [E] is recurrent, its attractor M satisfies

M = \overline{⋃_{h∈N} h[M]} .

Proof. If F denotes the set on the right-hand side, the inclusion F ⊂ M follows from . Conversely, the continuity of h ∈ H[E] yields

h[F] ⊂ \overline{h[ ⋃_{h′∈N} h′[M]]} ,

where for h′ ∈ N, again by (7.2), h′[M] ⊂ M. Therefore

h[F] ⊂ \overline{h[M]} ⊂ F for all h ∈ N ,

and the inclusion M ⊂ F follows, once more from (7.2). □

Whenever both M and N are compact, due to the continuity of the mapping (x, h) → h(x), this result holds without taking the closure. To see that, without assuming M to be compact, this may fail even if N is finite, consider the autoregressive process

X_{n} = \frac{1}{3}X_{n−1} + V_{n} for n ∈ N ,

where the i.i.d. variables V_{n}, n ∈ N, attain the values 0 and \frac{2}{3} with probability \frac{1}{2}. With E = [0, 1[ as state space the corresponding distribution ν is supported by the two mappings h_{1} : x → x/3 and h_{2} : x → (x + 2)/3. It is clearly irreducible and by (2.2) recurrent. In view of sup M = 1 by (7.2) also \frac{1}{3} = sup h_{1}[M] ∈ M, while on the other hand \frac{1}{3} ∉ h_{1}[E] ∪ h_{2}[E].

Next, M will be described by means of the semigroup N^{∗} generated by N:

(7.4) Proposition If ν ∈ N [E] is recurrent, its attractor M satisfies

M = \overline{\{h(x) : h ∈ N^{∗}\}} for every x ∈ M .

Proof. If F denotes the set on the right-hand side, the inclusion F ⊂ M follows from (7.2). Conversely, as in the proof of (7.3),

h[F] ⊂ \overline{\{h ∘ h′(x) : h′ ∈ N^{∗}\}}
⊂ \overline{\{h′′(x) : h′′ ∈ N^{∗}\}}
= F for all h ∈ N ,

and the inclusion M ⊂ F follows again from (7.2). □

The assumption x ∈ M is clearly essential for the inclusion F ⊂ M, while the proof shows that the inclusion M ⊂ F holds for any x ∈ E.

The most explicit characterization of M uses the closure N^{∗∗} of N^{∗}:

(7.5) Theorem If ν ∈ N [E] is recurrent, its attractor M satisfies

x ∈ M if and only if j(x) ∈ N^{∗∗} ,

where j is the canonical injection of E into H[E].

Proof. 1. To prove the condition to be necessary, consider h_{0} = j(x_{0}) with x_{0} ∈ M. By definition of the topology in H[E] it has to be shown that

{h ∈ N^{∗} : h(x) ∈ G_{0} for 0 ≤ x ≤ t} ≠ ∅

for arbitrary t ∈ E and open sets G_{0} ⊂ E containing x_{0}. Since x_{0} ∈ M implies μ(G_{0}) > 0 for these sets, (6.6) applies and provides n ∈ N with

P(X_{n}^{x} ∈ G_{0} for 0 ≤ x ≤ t) > 0 .

Thus there exist h_{1}, …, h_{n} ∈ N such that

h_{n} ∘ … ∘ h_{1}(x) ∈ G_{0} for 0 ≤ x ≤ t ,

as had to be shown.

2. To prove the converse, let h_{n} ∈ N^{∗} converge to h_{0} = j(x_{0}) and apply (7.4) to x = \underline{x} ∈ M, leading to

x_{0} = h_{0}(\underline{x}) = lim_{n→∞} h_{n}(\underline{x}) ∈ M . □

It is a consequence of this result, that the fixed points of the mappings h ∈ N^{∗} are dense in M. Indeed, since this is trivial for \underline{x} = \overline{x}, assume

M ∩]s, t[ ≠ ∅ with \underline{x} < s < t < \overline{x} .

Then any h ∈ N^{∗} with s < h(x) < t for 0 ≤ x ≤ t satisfies s < h(s) ≤ h(t) < t and thus by its continuity h(x) = x for some x ∈]s, t[.

On the other hand, fixed points of mappings in N^{∗} need not belong to M. This is seen, for instance, replacing ν by ν′ = (ν + ν_{0})/2, where ν_{0} is concentrated on the identity map; for it is obvious that, passing from ν to ν′, neither recurrence nor invariant measure are concerned. It is, however, true that a fixed point x of a mapping h ∈ N^{∗} belongs to M, if it is minimal under the condition x ≥ \underline{x}. Indeed, in this case the increasing sequence (h^{n}(\underline{x}))_{n≥0} converges to x and (7.4) applies.

The rest of this section concerns conditions under which the attractor is an interval. The first one is quite natural:

(7.6) Proposition If ν ∈ N [E] is recurrent, its attractor M is connected whenever N is connected.

Proof. Fix some y ∈ M and assume \underline{x} < \underline{y} < \overline{y} < \overline{x}. Then, according to (4.4) and (6.6), there exists n ∈ N such that

P(X_{n}^{y} < \underline{y}) > 0 and P(X_{n}^{y} > \overline{y}) > 0 .

Thus the set

B := {h_{n} ∘ … ∘ h_{1}(y) : h_{1}, … h_{n} ∈ N}

is a subset of M by (7.2) and contains elements x < \underline{y} and x > \overline{y}. Moreover it is connected, because in H[E] composition and evaluation are continuous. Therefore [\underline{y}, \overline{y}] ⊂ M, as had to be shown. □

The connectedness of N is by no means necessary for that of M as is seen, for instance, by the autoregressive process following (3.3), where the invariant measure is the uniform distribution on [0,1[.

To exhibit a nontrivial example with disconnected attractor, choose E = [0, 1[ and let N consist of the two mappings defined by

h_{1}(x) = \frac{x}{3} ∨ (x − \frac{2}{5}) and h_{2}(x) = (x + \frac{2}{5}) ∧ \frac{x + 2}{3} ,

satisfying the symmetry condition h_{2}(1 − x) = 1 − h_{1}(x). The corresponding distribution ν is recurrent by (2.2) with \underline{x} = 0 by (1.8), and a simple sketch shows that the open set G =]\frac{1}{5}, \frac{2}{5}[ ∪]\frac{3}{5}, \frac{4}{5}[ satisfies h_{i}[E \G] ⊂ E \G for i = 1, 2. By (7.2) this implies M ⊂ E \ G, hence M is disconnected, even though the mappings h_{i} are nonexpansive and the images h_{1}[E] and h_{2}[E] cover E.

The final result of this section is related to (2.2) and of interest in Section 9:

(7.7) Proposition If ν ∈ N [E] is recurrent, its attractor M is connected whenever the following two conditions are satisfied:

(a)  ν(sup h ∈ E) = 0 ,
(b)  M ⊃ ] t, \overline{x} [ for some t ∈ E .

Proof. 1. The crucial point is the implication

(∗)  [s, t] ⊂ M if s < t satisfies ν(h(t) < s) > 0 .

To derive it, consider a nonempty open subset G of ]s, t[. Then condition (a) and the assumption ν(h(t) < s) > 0 yield

ν(H_{s}) > 0 for H_{s} := {h ∈ H[E] : h(t) < s < t < sup h} .

For h ∈ H_{s}, due to the continuity, h^{−1}[G] is a nonempty open subset of ]t, \overline{x} [, hence the invariant measure satisfies μ(h^{−1}[G]) > 0. Therefore

μ(G) = ∫_{H[E]} μ(h(x) ∈ G) ν(dh)
≥ ∫_{H_{s}} μ(h^{−1}[G]) ν(dh) > 0 ,

as had to be shown.

2. Now let t in condition (b) be chosen minimal. Then by (∗)

ν(h(t) < s) = 0 for s < t ,

hence s ↑ t yields h(t) ≥_{ν} t, which by (1.8) implies t ≤ \underline{x}. □

To see condition (a) to be essential for this result, consider the independent system (E, μ), where the invariant measure coincides with μ.

8. Properties of the invariant measure

Since an explicit determination of the invariant measure in general is out of reach, at least a qualitative description is desirable. Some basic facts concerning the case E = [0, 1] can be found in [7]. A rather general result can be derived from the mean ergodic theorem:

(8.1) Theorem Let ν ∈ N [E] be recurrent with invariant measure μ and exclude the case E = {0}. Then μ is nonatomic whenever

(∗)  ν(h(x_{1}) = z = h(x_{2})) = 0 for x_{i}, z ∈ E with x_{1} < x_{2} .

Proof. 1. If D is a countable dense subset of E, application of (∗) to all pairs x_{1} < x_{2} with x_{i} ∈ D yields

|h^{−1}[{z}]| ≤ 1 for ν−almost all h ∈ H[E] .

Consequently, the kernel P transforms nonatomic measures ϱ ∈ M_{1}(E) into measures of the same type, because

ϱP ({z}) = ∫_{H[E]} ϱ(h(x) = z) ν(dh) ,

where the integrand vanishes for ν−almost all h ∈ H[E].

2. Starting with any nonatomic initial law μ_{0} on E ≠ {0}, it follows from part 1 of the proof that μ_{n} := L(X_{n}) is nonatomic for all n ∈ N. An application of (6.3) to f = 1_{{z}} and an admissible function g with μg ≠ 0 under X_{0} = X′_{0} yields

μ({z})/μg = lim_{n→∞} ∑_{0≤m<n} μ_{m}({z}) / ∑_{0≤m<n} μ_{m}g

and thus μ({z}) = 0 for all z ∈ E. □

Since condition (∗) is apparently satisfied whenever the underlying mappings h are injective, the regenerative case may rightly be considered as an exception. This holds even more, as (∗) is not a necessary condition. To see this, consider the example following (7.6), where the invariant measure μ is nonatomic by (8.1). A slight modification of the mappings h_{i} on the set G due to μ(G) = 0 does not affect the equation defining μ.

The next result is of interest primarily for affine recursions, the distinguished measure being the Lebesgue measure. In its simplest form the argument can be traced back to [15]. Since Lebesgue null sets are not invariant under conjugation, the proper version is as follows:

(8.2) Proposition Let ν ∈ N [E] be recurrent with invariant measure μ and let ϱ ∈ M[E] satisfy (h(ϱ) denoting the image of ϱ under h)

ν( h(ϱ) absolutely continuous with respect to ϱ) = 1 .

Then μ is either absolutely continuous or singular with respect to ϱ.

Proof. 1. First, measurability of the set

H_{0} := {h ∈ H[E] : h(ϱ) ≪ ϱ}

has to be settled, where the symbol “≪” stands for absolute continuity and ϱ may be assumed to be a finite measure. Using the ε, δ−criterion for h(ϱ) ≪ ϱ and approximating B ∈ B(E) from outside by open sets and h^{−1}[B] from inside by compact sets, it is no problem to verify the representation

H[E] \ H_{0} = ⋃_{k∈N} ⋂_{l∈N} ⋃ {h ∈ H[E] : h[K] ⊂ G} ,

where the inner union is extended over all pairs of compact sets K with ϱ(K) > 1/k and open sets G with ϱ(G) < 1/l, hence is an open subset of H[E]. Therefore H_{0} itself is of type F_{σδ}.

2. Let now μ be decomposed into its absolutely continuous part μ_{c} and its singular part μ_{s} with respect to ϱ. Then the equation

μ_{c}P (B) = ∫_{H_{0}} μ_{c}(h^{−1}[B]) ν(dh) for B ∈ B(E)

implies μ_{c}P ≪ ϱ, hence the equation

μ_{c}P + μ_{s}P = μP = μ = μ_{c} + μ_{s}

implies μ_{c}P ≪ μ_{c}. By the uniqueness of the invariant measure, therefore, μ_{c} = γ_{c}μ with some constant γ_{c}, hence μ_{s} = γ_{s}μ with some constant γ_{s}. Now μ_{c} ∧ μ_{s} = 0 implies γ_{c} ∧ γ_{s} = 0 and proves the assertion. □

In general, there is no further information available about the alternative in this proposition. An obvious exception is the case, where the common distribution of the variables H_{n}(x), n ∈ N, is absolutely continuous with respect to ϱ for all x ∈ E, because in this case the equation

μ(B) = ∫_{E} P(H_{n}(x) ∈ B) μ(dx) for B ∈ B(E)

implies μ ≪ ϱ.

The rest of this section is devoted to stability results. This requires some preparation:

(8.3) Lemma If ν_{k}, ν ∈ N [E] and μ_{k}, μ ∈ M(E) satisfy

(a)  μ_{k} is excessive for ν_{k} ,
(b)  ν_{k} →_{w} ν and μ_{k} →_{v} μ ,

then μ is excessive for ν.

Proof. Let g ∈ K(E) satisfy 0 ≤ g ≤ 1 and define ϱ_{k}, ϱ ∈ M(E) by

dϱ_{k}/dμ_{k} = g = dϱ/dμ .

Since f ∈ C(E) implies fg ∈ K(E), the vague convergence in (b) yields ϱ_{k} →_{w} ϱ. Together with the weak convergence in (b) this leads to

ϱ_{k} ⊗ ν_{k} →_{w} ϱ ⊗ ν ,

because the multiplication of measures is continuous in the weak topology. Now for 0 ≤ f ∈ K(E) the mapping (x, h) → f(h(x)) is continuous, hence

∫_{E} ∫_{H[E]} f(h(x))g(x) μ(dx) ν(dh) = lim_{k→∞} ∫_{E} ∫_{H[E]} f(h(x))g(x) μ_{k}(dx) ν_{k}(dh)
≤ lim inf_{k→∞} ∫_{E} ∫_{H[E]} f(h(x)) μ_{k}(dx) ν_{k}(dh)
≤ lim inf_{k→∞} ∫_{E} f dμ_{k}
= ∫_{E} f dμ ,

where the second inequality uses (a). By letting g increase to 1, therefore

μP f ≤ μf for 0 ≤ f ∈ K(E) ,

as had to be shown. □

If ν_{k}, ν ∈ N [E] satisfy ν_{k} →_{w} ν, all that can be said about their restrictions in the sense of (1.1) is the inequality

lim inf_{k→∞} \overline{x}_{k} ≥ \overline{x}

for the respective upper limits. For simplicity, therefore, in the sequel all occurring distributions will be assumed to be irreducible with respect to the same state space. Then the following stability criterion holds:

(8.4) Theorem Let ν_{k}, ν ∈ N [E] be recurrent with invariant measures μ_{k}, μ and denote the respective lower limits by \underline{x}_{k}, \underline{x}. Then the convergence ν_{k} →_{w} ν implies the existence of norming constants γ_{k} with γ_{k}μ_{k} →_{v} μ if and only if

(∗)  lim sup_{k→∞} \underline{x}_{k} ≤ \underline{x} .

Proof. 1. In verifying the condition (∗) to be necessary \underline{x} < \overline{x} may be assumed, because otherwise \underline{x}_{k} ≤ \underline{x} for all k ∈ N. For any t ∈ E with t > \underline{x} the convergence γ_{k}μ_{k} →_{v} μ yields

lim inf_{k→∞} γ_{k}μ_{k}([0, t[) ≥ μ([0, t[) > 0 ,

hence \underline{x}_{k} ≤ t for almost all k ∈ N by (4.4), as had to be shown.

2. To prove sufficiency, choose t ∈ E with t > \underline{x} or t = \overline{x} and assume μ(\{t\}) = 0 unless t = \overline{x}. Then (4.4) and the inequality (∗) yield μ([0, t]) > 0 and μ_{k}([0, t]) > 0 for almost all k ∈ N. Therefore it means no loss of generality to assume

(1)  μ_{k}([0, t]) = μ([0, t]) = 1 for all k ∈ N .

From this it will be derived in part 3 of the proof that

(2)  sup_{k∈N} μ_{k}([0, s]) < ∞ for all s ∈ E ,

i.e. the measures μ_{k}, k ∈ N, are uniformly locally finite. It follows as in the proof of (4.3) that {μ_{k} : k ∈ N} is a sequentially compact subset of M(E). If (μ′_{k})_{k∈N} is any convergent subsequence, its limit by (8.3) is excessive and thus by (4.7) is of the form γμ. Since 1_{[0,t]} is μ−almost continuous, the constant γ satisfies by (1)

γ = γ μ([0, t]) = lim_{k→∞} μ′_{k}([0, t]) = 1 .

Thus the sequence (μ_{k})_{k∈N} itself satisfies μ_{k} →_{v} μ.

3. Since (2) is implied by (1) in the case t = \overline{x}, in the sequel t > \underline{x} may be assumed. Thus there exists n ∈ N with ν^{n}(h(s) < t) > 0. Since ν_{k} →_{w} ν implies ν_{k}^{n} →_{w} ν^{n}, therefore

lim inf_{k→∞} ν_{k}^{n}(h(s) < t) ≥ ν^{n}(h(s) < t) > 0 ,

and thus it is no real restriction to assume

ϑ := inf_{k∈N} ν_{k}^{n}(h(s) < t) > 0 .

Since μ_{k} is invariant for ν_{k}^{n} as well, this yields

μ_{k}([0, s]) ≤ ϑ^{−1} μ_{k}([0, s]) ν_{k}^{n}(h(s) < t)
≤ ϑ^{−1} (μ_{k} ⊗ ν_{k}^{n}) ({(x, h) : h(x) < t})
= ϑ^{−1} μ_{k}([0, t[)
≤ ϑ^{−1} for all k ∈ N ,

and the proof is completed. □

As an example violating the condition (∗) consider on E = [0, 1[ the mappings defined by

h_{1}(x) = \frac{1}{2} (x + 1) , h_{2}(x) = x ∧ \frac{1}{2} and h_{2}^{k}(x) = (1 − \frac{1}{k}) x ∧ \frac{1}{2} .

If ν_{k} and ν assign mass \frac{1}{2} to h_{1}, h_{2}^{k} and h_{1}, h_{2}, respectively, then clearly ν_{k} →_{w} ν. Moreover, ν_{k} and ν are recurrent by (2.2), their lower limits, however, are \underline{x}_{k} = 0 and \underline{x} = \frac{1}{2} by (1.8).

For an application of (8.4) let ν_{0} be concentrated on the constant mapping h = 0 and approximate a recurrent distribution ν by

ν_{k} := (1 − \frac{1}{k}) ν + \frac{1}{k} ν_{0} for n ∈ N .

For the same reasons as above these distributions are recurrent with \underline{x}_{k} = 0, hence the corresponding invariant measures, suitably normalized, satisfy μ_{k} →_{v} μ. In this case μ_{k}({0}) > 0 by (5.6) or (5.7), and thus μ_{k} has a representation according to (5.2).

Finally, the special case \overline{x} ∈ E has to be mentioned, where the invariant measures can be normalized to μ_{k}, μ ∈ M_{1}(E). Since in this case vague and weak convergence coincide, the constants γ_{k} are needless and thus μ_{k} →_{w} μ. That this convergence in the case \overline{x} ∉ E and μ_{k}, μ ∈ M_{1}(E) may fail, will be seen in the next section.

9. Positive recurrence and null recurrence

The following classification is adopted from the discrete situation:

(9.1) Definition If ν ∈N [E] is recurrent with invariant measure μ, the distribution ν (or the kernel P or the process (X_{n})_{n≥0}) is called

(a) “positive recurrent” if μ(E) <∞,

(b) “null recurrent” if μ(E) = ∞.

As the alternative recurrent / transient, considered in (2.5), this classification is invariant under a passage from ν to ν^{n}, because this does not affect the invariant measure.

The following criterion, where again ν is identified with the corresponding kernel P, includes the transient case:

(9.2) Proposition The irreducible distribution ν ∈ N [E] is positive recurrent if and only if there exists a stationary distribution μ ∈ M_{1}(E) for ν.

Proof. It suffices to deduce recurrence of ν, if μ is stationary for ν. Otherwise, with μ as initial law, (2.4b) would yield

∑_{n≥0} μ([0, t]) = ∑_{n≥0} P(X_{n} ≤ t) < ∞ for all t < \overline{x} ,

hence μ([0, t]) = 0, implying \overline{x} ∈ E and contradicting transience by (2.2). □

Next, the result of (2.2) can be strengthened:

(9.3) Proposition If ν ∈ N [E] is irreducible and satisfies

ν(sup_{x∈E} h(x) ∈ E) > 0 ,

then ν is positive recurrent.

Proof. Let μ be the invariant measure for ν that is ensured by (2.2) and choose t ∈ E satisfying

ϑ := ν(sup_{x∈E} h(x) ≤ t) > 0 .

Then the invariance of μ implies

μ([0, t]) = ∫_{E} ν(h(x) ≤ t) μ(dx) ≥ ϑ μ(E) .

Since the left-hand side is finite, the assertion follows. □

That the sufficient condition in this proposition fails to be necessary is seen by the queuing process. It is well-known to possess a stationary distribution if and only if the associated random walk diverges to −∞.

At this point it can be clarified what measures μ ∈ M(E) arise as invariant measure of some recurrent distribution ν ∈ N [E]. The independent system (E, μ) shows that the only condition to be satisfied in the case of a measure μ ∈ M_{1}(E) is given by

μ({x ∈ E : x ≥ t}) > 0 for all t ∈ E .

In the case of an infinite measure μ, however, this condition fails to be sufficient, because for a null recurrent distribution ν−almost all h ∈ H[E] are unbounded in E by (9.3) and thus (7.7) applies.

In the sequel − suggested by ideas from queuing theory (see e.g. [21, 22]) − the “dual process” (H_{1} ∘ … ∘ H_{n}(0))_{n∈N} will be investigated. Though it fails, in general, to be a Markov process, it is of particular interest for distinguishing positive and null recurrence. To this end an improper random variable taking its values in the (possibly) enlarged state space \overline{E} = E ∪ \{\overline{x}\} has to be introduced:

(9.4) Definition For irreducible ν ∈ N [E] the random variable

Y := sup_{n∈N} H_{1} ∘ … ∘ H_{n}(0)

is called the “dual limit” of ν.

Often, Y can be given in an explicit form, for instance

(1) if (X_{n})_{n≥0} is the queuing process, then

Y = sup_{n≥0} (U_{1} + … + U_{n}) ,

(2) if (X_{n})_{n≥0} is an exchange process with U_{n} = 1, then

Y = sup_{n∈N} (V_{n} − (n − 1)) ,

(3) if (X_{n})_{n≥0} is an affine recursion as in the introduction, then

Y = ∑_{n∈N} U_{1} … U_{n−1}V_{n} .

By means of the results in Section 3 the terminology in (9.4) can be justified:

(9.5) Proposition If ν ∈ N [E] is irreducible, the sequence

Y_{n}^{x} := H_{1} ∘ … ∘ H_{n}(x) for n ∈ N

satisfies

(a)  Y_{n}^{x} ↑ Y a.s. for x = 0 ,
(b)  Y_{n}^{x} → Y a.s. for every x ∈ E .

Proof. (a) This is immediate from the monotonicity of h ∈ H[E].

(b) Since the distributions of Y_{n}^{x} and X_{n}^{x} agree, the fundamental inequality (3.1) implies as well

∑_{n≥0} E(f(Y_{n}^{x}) − f(Y_{n}^{0})) < ∞

for each bounded increasing function f : E → R_{+}. In complete analogy to the derivation of (3.3b) this leads to

1_{I}(Y_{n}^{x}) − 1_{I}(Y_{n}^{0}) → 0 a.s.

for every subinterval I of E. If I runs through a countable base of E, therefore,

(b) is a consequence of (a). □

The uniform convergence on compact sets carries over from Section 3, i.e.

sup_{0≤x≤t} |f(Y_{n}^{x}) − f(Y_{n}^{0})| → 0 a.s. for f ∈ R(E) and t ∈ E .

If \overline{x} ∈ E, moreover, (a) can be complemented by Y_{n}^{x} ↓ Y a.s. for x = \overline{x}. There is a zero-one law for the (possibly) improper random variable Y:

(9.6) Proposition If ν ∈ N [E] is irreducible, its dual limit satisfies

P(Y ∈ E) = 0 or 1 .

Proof. 1. Consider first the case that

P(sup_{x∈E} H_{n}(x) ≤ t) > 0 for some t ∈ E .

Then the random time

T := inf{n > 1 : sup_{x∈E} H_{n}(x) ≤ t}

is almost surely finite and satisfies

Y ≤ H_{1} ∘ … ∘ H_{T −1}(t) ∈ E a.s. .

2. Otherwise H_{1} is almost surely unbounded in E, hence

{sup_{n∈N} H_{1}(H_{2} ∘ … ∘ H_{n}(0)) ∈ E} = {sup_{n>1} H_{2} ∘ … ∘ H_{n}(0) ∈ E} a.s. .

Continuing, it follows that the event {Y ∈ E} is contained in the completed tail σ-field of (H_{n})_{n∈N} and thus has probability 0 or 1. □

Now the dual limit can be shown to play the same role in singling out positive recurrence as the lower limit does for recurrence. The first result is related to a “principle” in [20]:

(9.7) Theorem The irreducible distribution ν ∈ N [E] is positive recurrent if and only if P(Y ∈ E) = 1. In this case

(a) μ := L(Y) is the unique stationary distribution,

(b) L(X_{n}) →_{w} μ for arbitrary initial law.

Proof. 1. If ν is positive recurrent with stationary distribution μ, then

μ([0, t]) = (lim inf_{n→∞}) ∫_{E} P(X_{n}^{x} ≤ t) μ(dx)
≤ lim inf_{n→∞} ∫_{E} P(X_{n}^{0} ≤ t) μ(dx)
= lim inf_{n→∞} P(Y_{n}^{0} ≤ t)
= P(Y ≤ t)
≤ P(Y ∈ E) for all t ∈ E

by (9.5a). Thus t ↑ \overline{x} (or t = \overline{x}) implies P(Y ∈ E) = 1.

2. If conversely Y ∈ E almost surely, then

Y = H_{1}(Y′) a.s. with Y′ := sup_{n>1} H_{2} ∘ … ∘ H_{n}(0) ,

where H_{1} and Y′ are independent and in addition Y and Y′ have the same distribution. Thus μ = L(Y) is a stationary distribution, hence ν is positive recurrent by (9.2), and (a) is established.

3. Finally, if μ_{0} := L(X_{0}) is arbitrary, then

E(f(X_{n})) = ∫_{E} E(f(X_{n}^{x})) μ_{0}(dx)
= ∫_{E} E(f(Y_{n}^{x})) μ_{0}(dx)
→ E(f(Y)) for all f ∈ C(E)

by (9.5b), and (b) is established. □

As a simple application consider the exchange process studied in Sections 2 and 6. The representation following (9.4) implies P(Y ∈ E) = 1 in the case \overline{x} < ∞, because then the supremum is in fact a maximum. In the case \overline{x} = ∞ choose any t satisfying F (t) > 0 for the underlying distribution function. Then

P(Y ≤ t) = ∏_{n≥0} F (t + n) > 0

if and only if the series ∑_{n≥0} (1 − F (t + n)) converges. Therefore the process (X_{n})_{n≥0} is positive recurrent if and only if the variables V_{n}, n ∈ N, have a finite expectation (for extensions see [13]).

Instead of presenting further examples (as can be found in [6, 11, 20]), the fractal character of stationary distributions and their support will briefly be discussed. To this end choose E = [0, 1[ and let the support of ν ∈ N [E] consist of two injective, but not necessarily contractive, mappings h_{0}, h_{1} ∈ H[E] satisfying

h_{0}(x) < x < h_{1}(x) for 0 < x < 1 and sup_{x∈E} h_{0}(x) < h_{1}(0) .

Then ν is positive recurrent by (9.3) with \underline{x} = 0 (and \overline{x} = 1). Now endow the space J := {0, 1}^{N} with the product topology and define

φ : (j_{n})_{n∈N} → sup_{n∈N} h_{j_{1}} ∘ … ∘ h_{j_{n}}(0) .

It follows that φ is an embedding of J into [0,1] (see e.g. [12, 14]). Moreover, the stationary distribution μ is the image under φ of the product measure ϱ with factors ν({h_{0}}) ε_{0} + ν({h_{1}}) ε_{1}. Since supp ϱ = J, the support M of μ equals φ[J] ∩ E and is thus, as J, totally disconnected. Finally, since the measures ϱ belonging to different ν are pairwise orthogonal, this holds for the corresponding distributions μ as well.

Before establishing the counterpart of (9.7) the stability problem mentioned at the end of the preceding section will be settled. To this end choose E = R_{+} and let ν correspond to a positive recurrent exchange process as above, satisfying P(V_{n} = 0) > 0 and thus \underline{x} = 0. Now consider the perturbed distributions

ν_{k} := (1 − \frac{1}{k}) ν + \frac{1}{k} ν′_{k} for k ∈ N ,

where ν′_{k} is concentrated on the constant mapping h_{k} = k^{2}. Then ν_{k} is again positive recurrent by (9.3), with lower limit 0 by (1.8). Thus (8.4) applies, i.e. the corresponding stationary distributions μ_{k} and μ satisfy γ_{k}μ_{k} →_{v} μ for suitable constants γ_{k}. If P_{k} refers to ν_{k}, however, h(x) ≥ x − 1 for ν−almost all h ∈ H[E] implies

P_{k}(sup_{n∈N} H_{1} ∘ … ∘ H_{n}(0) ≤ l) ≤ P_{k}(H_{m} ≠ h_{k} for 1 ≤ m ≤ k^{2} − l)
= (1 − \frac{1}{k})^{k^{2}−l}
→ 0 for all l ∈ N ,

hence μ_{k} →_{w} ε\overline{x} on \overline{E} = E ∪ \{\overline{x}\} by (9.7).

This improper convergence appears again in the following criterion:

(9.8) Theorem The irreducible distribution ν ∈ N [E] is null recurrent or transient if and only if P(Y ∈ E) = 0. In this case for arbitrary initial law

L(X_{n}) →_{w} ε\overline{x} on \overline{E} = E ∪ \{\overline{x}\} .

Proof. The asserted equivalence is immediate from (9.6) and (9.7). The asserted convergence follows from

lim sup_{n→∞} P(X_{n} ≤ t) ≤ lim sup_{n→∞} P(X_{n}^{0} ≤ t)
= lim sup_{n→∞} P(Y_{n}^{0} ≤ t)
= P(Y ≤ t)
= 0 for all t ∈ E . □

The results concerning the classification can now be summarized as follows:

(1) if ν is positive recurrent, then lim inf_{n→∞} X_{n}^{0} ∈ E a.s. and lim_{n→∞} Y_{n}^{0} ∈ E a.s. ,

(2) if ν is null recurrent, then lim inf_{n→∞} X_{n}^{0} ∈ E a.s. and lim_{n→∞} Y_{n}^{0} ∉ E a.s. ,

(3) if ν is transient, then lim inf_{n→∞} X_{n}^{0} ∉ E a.s. and lim_{n→∞} Y_{n}^{0} ∉ E a.s. .

10. Further ergodic theorems The convergence in (9.7) is unnecessarily restricted to functions f ∈ C(E): (10.1) Theorem Let ν ∈ N [E] be positive recurrent with stationary distribution μ. Then the convergence

μ_{n}f → μf with μ_{n} := L(X_{n})

holds in each of the following cases:

(a) f ∈ R(E),

(b) f : E → R_{+} increasing and supp μ_{0} compact. Proof. (a) Since f is bounded, application of (3.3b) with initial variables X_{0} = x_{0} resp. X_{0} = x yields

μ_{n}f − μf = ∫_{E} ∫_{E} E(f(X_{n}^{x_{0}}) − f(X_{n}^{x})) μ_{0}(dx_{0}) μ(dx) → 0 .

(b) Application of (a) to f ∧ k with k → ∞ leads to

lim inf_{n→∞} μ_{n}f ≥ μf ,

establishing the case μf = ∞. Otherwise, (9.5a) and (9.7) imply

(∗)  E(f(X_{n}^{0})) = E(f(Y_{n}^{0})) ≤ μf < ∞ for all n ≥ 0 .

If t ∈ E satisfies supp μ_{0} ⊂ [0, t], therefore

μ_{n}f ≤ E(f(X_{n}^{t}))
≤ μf + (E(f(X_{n}^{t})) − E(f(X_{n}^{0}))) .

In view of (∗) the fundamental inequality (3.1) yields

lim sup_{n→∞} μ_{n}f ≤ μf . □

To see the regularity condition in case (a) to be essential, consider the autoregressive process following (3.3). It is positive recurrent with the uniform distribution on [0,1[ as stationary distribution. Here, the convergence μ_{n}f → μf fails, for instance, if X_{0} = x_{0} ∈ D and f = 1_{D} with D denoting the set of dyadic numbers in E.

The compactness condition in case (b) is essential as well. Indeed, consider an exchange process with E = R_{+} and E(V_{n}) < ∞, proved to be positive recurrent by (9.7). Assume in addition ∫_{E} x dμ < ∞ for its stationary distribution μ − a condition that can be checked to amount to ∏_{n>\underline{x}} (F (n))^{n} > 0 for the underlying distribution function. Then E(X_{0}) = ∞ by X_{n} ≥ X_{n−1}−1 implies E(X_{n}) = ∞ for all n ∈ N.

Application of (10.1) yields in particular pointwise convergence of the associated distribution functions. Together with (2.4) this implies that the familiar classification from discrete Markov chain theory for \underline{x} < t ∈ E carries over in the following form:

(1) ν positive recurrent ⇔ lim_{n→∞} P(X_{n} ≤ t)> 0,

(2) ν null recurrent ⇔ lim_{n→∞} P(X_{n} ≤ t) = 0 and ∑_{n≥0} P(X_{n} ≤ t) = ∞,

while in the transient case ∑_{n≥0} P(X_{n} ≤ t) <∞ for all t ∈ E.

To prove a law of large numbers not restricted to functions f ∈ C(E), ergodicity will be established first. More generally the following holds:

(10.2) Theorem Let ν ∈ N [E] be positive recurrent with stationary distribution μ. Then the process (X_{n})_{n≥0} with L(X_{0}) = μ is mixing.

Proof. 1. Extending H_{n}, n ∈ N, let H_{n}, n ∈ Z, be independent variables with distribution ν. Then by (9.7)

X′_{n} := sup_{m≤n} H_{n} ∘ … ∘ H_{m}(0) ∈ E a.s.

and, moreover, L(X′_{n}) = μ for n ∈ Z. The continuity of h ∈ H[E] yields

X′_{n} = H_{n}(X′_{n−1}) a.s. for n ∈ N .

Since X′_{0} is independent of (H_{n})_{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 σ resp. σ′ the shift in W := ∏_{n∈Z} H[E] resp. W′ := ∏_{n≥0} \overline{E} with \overline{E} = E ∪ \{\overline{x}\} and consider the (measurable) mapping

τ : (h_{n})_{n∈Z} → ( sup_{m≤n} h_{n} ∘ … ∘ h_{m}(0))_{n≥0}

from W to W′. It is compatible with σ and σ′, i.e. τ ∘ σ = σ′ ∘ τ. Therefore the mixing property of σ with respect to the product measure ⨂_{n∈Z} ν carries over to σ′ with respect to its image by τ. Since this apparently is the distribution of (X′_{n})_{n≥0}, the assertion follows. □

In contrast to the result of (5.4), in general the tail σ-field of (X_{n})_{n≥0}, even under stationarity, need not be trivial. A counterexample is provided by any distribution ν ∈ N [E], whose support consists of two injective mappings h_{0}, h_{1} ∈ H[E] with disjoint images h_{i}[E], as considered in Section 9. Since in this case X_{n−1} can be reconstructed from X_{n} with probability 1, the tail σ-field of (X_{n})_{n≥0} coincides with the full σ-field generated by the process up to sets of probability 0.

If the underlying mappings h ∈ H[E] satisfy a Lipschitz condition, laws of large numbers regarding functions f ∈ C(E) can be found in [3, 9]. In the order context more general results are available:

(10.3) Theorem Let ν ∈ N [E] be positive recurrent with stationary distribution μ. Then for arbitrary initial law the convergence

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

holds in each of the following cases:

(a) f ∈ R(E),

(b) f : E → R_{+} increasing.

Proof. (a) Let (X′_{n})_{n≥0} be a copy of (X_{n})_{n≥0} as in (6.3) and assume L(X′_{0}) = μ. Then the process (X′_{n})_{n≥0} is ergodic by (10.2), hence

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

This convergence carries over to (X_{n})_{n≥0}, because f(X_{n}) − f(X′_{n}) → 0 a.s. by (3.3b).

(b) It follows from (a) as in the proof of (10.1b) that it is no real restriction to assume μf < ∞. In this case it follows, again as in the proof of (10.1b), that sup_{n≥0} E(f(X_{n}^{0})) < ∞. Therefore, (3.2b) can replace (3.3b) to continue the proof as in (a). □

Case (b) implies in particular the classical law of large numbers

\frac{1}{n} ∑_{0≤m<n} X_{m} → ∫_{E} x μ(dx) a.s. ,

holding regardless of initial law and proper existence of the integral.

Case (a) cannot dispense with the regularity condition on f as follows by the same counterexample as considered for (10.1a). Moreover, even under continuity, boundedness of f cannot be replaced by integrability with respect to the stationary distribution. To exhibit an appropriate counterexample requires a recursive construction as in the context of (3.3). Choose E = R_{+} and let the support of ν consist of the two mappings defined by h_{1}(x) = x + 1 and h_{2}(x) = x/(x + 1). Then ν is positive recurrent by (9.3) with \underline{x} = 0 (and \overline{x} = ∞). For X_{0} = 0 consider the random times

T_{k} := inf{n ≥ 0 : X_{n} ≥ k} for k ≥ 0 .

Due to X_{n} ≤ X_{n+1}−1 they satisfy T_{0} < T_{1} < … almost surely. As in Section 3 choose now n_{k} ∈ N such that

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

and finite subsets B_{k} of [k, k + 1[ such that

(2)  P(T_{k} ≤ n_{k}, X_{T_{k}} ∉ B_{k}) = 0 for k ≥ 0 .

Since the stationary distribution μ is nonatomic by (8.1), a continuous function f : R_{+} → R_{+} can be found satisfying the conditions

(3)  f(x) ≥ k n_{k} for x ∈ B_{k} ,
(4)  ∫_{[k,k+1[} f dμ < 2^{−k} for k ∈ N .

Then the sequence

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

satisfies

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

where the last inequality holds, because (2) and (3) yield

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

In view of (1) this implies

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

while in view of (4) on the other hand μf ≤ 1.

11. Mean passage times

In accordance with the order structure of the state space the hitting times for regions above or below some level are of special interest. The first result in this direction follows from (2.3) in the transient case, but holds as well in the recurrent case:

(11.1) Theorem Let ν ∈ N [E] be irreducible and fix t ∈ E. Then the hitting time T^{t} of {x ∈ E : x ≥ t} by (X_{n})_{n≥0} satisfies:

E^{0}(exp(uT^{t})) < ∞ for some u > 0 ,

hence in particular E^{0}(T^{t}) < ∞.

Proof. Choose l ∈ N such that ϑ := P(X_{l}^{0} ≥ t) > 0. Then monotonicity and independence imply

P^{0}(T^{t} > kl) ≤ P(H_{(i+1)l} ∘ … ∘ H_{il+1}(0) < t for 0 ≤ i < k)
= (1 − ϑ)^{k} for all k ≥ 0 .

Partial integration shows that each u < −\frac{1}{l} log(1 − ϑ) satisfies the assertion. □

The following counterpart of (11.1) separates the two kinds of recurrence:

(11.2) Theorem Let ν ∈ N [E] be recurrent and fix t ∈ E with t > \underline{x}. Then the hitting time T_{t} of {x ∈ E : x ≤ t} by (X_{n})_{n≥0} satisfies

(a) E^{x}(T_{t}) < ∞ for all x ∈ E whenever ν is positive recurrent,

(b) E^{x}(T_{t}) = ∞ for t ≤ x ∈ E whenever ν is null recurrent.

Proof. (a) Clearly, the process (X_{n})_{n≥0} may be assumed to be stationary. Moreover, the assumption x > t means no loss of generality, because the assertion is trivial in the case t = \overline{x}. Since P(X_{0} ≤ t) > 0 by (4.4), any n ∈ N with P(X_{n}^{0} ≥ x) > 0 satisfies

(∗)  P(X_{0} ≤ t, X_{n} ≥ x) > 0 .

If n is chosen minimal with respect to (∗), then

P(X_{0} ≤ t, X_{m} ≤ t, X_{n} ≥ x) = 0 for 0 < m < n ,

because otherwise by stationarity n − m would satisfy (∗) as well. Thus P(A) > 0 for the event

A := {X_{0} ≤ t, X_{1} > t, …, X_{n−1} > t, X_{n} ≥ x} ⊂ {T_{t} > n} .

With the increasing function

g(y) := E^{y}(T_{t}) for y ∈ E

the recurrence theorem by Kac and the Markov property imply

P(T_{t} < ∞) = ∫_{{X_{0}≤t}} T_{t} dP
≥ ∫_{A} T_{t} dP
= ∫_{A}(n + g(X_{n})) dP
≥ P(A) (n + g(x)) .

Therefore g(x) < ∞, as had to be shown.

(b) If μ is the invariant measure and t < y ∈ E, then

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

by (4.2a) and (4.4) defines a stationary distribution with respect to ^{y}P. Now let X_{0} be distributed according to (the trivial extension of) μ′ and let T′_{t} denote the hitting time of [0, t] by (^{y}X_{n})_{n≥0}. Then it is obvious that T′_{t} ≤ T_{t}, and it follows, again from the recurrence theorem by Kac, that

P(T′_{t} < ∞) = ∫_{{^{y}X_{0}≤t}} T′_{t} dP
= ∫_{x_{0}≤t} E^{x_{0}}(T′_{t}) μ′(dx_{0})
≤ ∫_{x_{0}≤t} E^{x_{0}}(T_{t}) μ′(dx_{0})
≤ μ′([0, t]) E^{t}(T_{t}) .

Since T′_{t} is almost surely finite, therefore

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

Letting y increase to \overline{x} in view of μ([0, t]) < ∞ yields E^{t}(T_{t}) = ∞, hence E^{x}(T_{t}) = ∞ for all x ∈ E with x ≥ t. □

Since P^{t}(T_{t} < ∞) = 1 clearly implies \underline{x} ≤ t, in the transient case the equation E^{t}(T_{t}) = ∞ holds for all t ∈ E.

Next, the topological structure of the state space is taken into account:

(11.3) Proposition Let ν ∈ N [E] be positive recurrent with stationary distribution μ. Then for each open subset G of E satisfying μ(G) > 0 and every t ∈ E the stopping time

T := inf{n ∈ N : X_{n}^{x} ∈ G for 0 ≤ x ≤ t}

has a finite expectation.

Proof. 1. By (6.6) there exists n ∈ N such that

ϑ := P(X_{n}^{x} ∈ G for 0 ≤ x ≤ t) > 0 .

If T′ denotes the analogous stopping time with respect to ν′ = ν^{n}, then apparently T ≤ nT′, hence n = 1 may be assumed in view of (2.5).

2. Moreover, t > \underline{x} or t = \overline{x} means no loss of generality. Then

S_{0} := 0 and S_{k+1} := inf{n > S_{k} : H_{n} ∘ … ∘ H_{S_{k}+1}(t) ≤ t}

are almost surely finite stopping times with respect to (H_{n})_{n∈N}, which by (11.2a) satisfy

(1)  E(S_{k} − S_{k−1}) = E^{t}(T_{t}) < ∞ for k ∈ N .

Finally, the events

A_{k} := {H_{S_{k}+1}(x) ∈ G for 0 ≤ x ≤ t}

by the assumption n = 1 satisfy

(2)  P(A_{k}) = ϑ > 0 for k ≥ 0 .

3. By construction the variables 1_{A_{0}}, …, 1_{A_{k−1}}, S_{k+1} − S_{k} are independent for each k ≥ 0. Moreover, the estimate

T ≤ 1 + ∑_{k≥0} ∏_{i≤k} (1 − 1_{A_{i}}) (S_{k+1} − S_{k})

holds, because the right-hand side for fixed ω ∈ Ω equals S_{k}(ω) + 1, if k is the first index with ω ∈ A_{k}, and is infinite, if there is no such index. If for each k the factor with i = k is cancelled, the bound for T is increased and the summands are composed of independent factors. By (1) and (2) this yields

E(T) ≤ 1 + ϑ^{−1} E^{t}(T_{t}) < ∞ . □

If in particular \overline{x} ∈ E, this result implies sup_{x∈E} E^{x}(T_{G}) < ∞, where T_{G} denotes the hitting time of G by (X_{n})_{n≥0}. With this notation the familiar criterion for positive / null recurrence by mean passage times carries over from discrete Markov chain theory in the following form:

(11.4) Theorem Let ν ∈ N [E] be recurrent with attractor M and fix x ∈ M. Then ν is positive recurrent if and only if

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

Proof. According to (11.3) only the sufficiency of the condition has to be established. To this end assume ν to be null recurrent. Then \overline{x} ∉ E by (9.3), hence x < \overline{x} and thus ν(h(x) > x) > 0 by (1.1). This implies the existence of t ∈ E with t > x such that ϑ := ν(h(x) > t) > 0. With the notation μ_{1} := L(X_{1}^{x}) an application of (11.2b) yields

E^{x}(T_{t}) = (1 − ϑ) + ∫_{y>t}(1 + E^{y}(T_{t})) μ_{1}(dy)
≥ ∫_{y>t} E^{t}(T_{t}) μ_{1}(dy)
= ϑ E^{t}(T_{t}) = ∞ ,

i.e. the condition is violated for G = [0, t[ ∋ x. □

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] Bhattacharya, R., Waymire, E.: Stochastic processes with applications. New York: Wiley 1990

[5] Brandt, A., Franken, P., Lisek, B.: Stationary stochastic models. Chichester: Wiley 1990

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

[7] Dubins, L., Freedman, D.: Invariant probabilities for certain Markov processes. Ann. Math. Stat. 37, 837−848 (1966)

[8] Elton, J.: An ergodic theorem for iterated maps. Ergodic Theory Dyn. Syst. 7, 481−488 (1987)

[9] Elton, J.: A multiplicative ergodic theorem for Lipschitz maps. Stochastic Processes Appl. 34, 39−47 (1990)

[10] Foguel, S.: The ergodic theory of positive operators on continuous functions. Ann. Sc. Norm. Super. Pisa 27, 19−51 (1973)

[11] Goldie, C.: Implicit renewal theory and tails of solutions of random equations. Ann. Appl. Prob. 1, 126−166 (1991)

[12] Hata, M.: On the structure of self-similar sets. Japan J. Appl. Math. 2, 381−414 (1985)

[13] Helland, I., Nilsen, T.: On a general random exchange model. J. Appl. Prob. 13, 781−790 (1976)

[14] Hutchinson, J.: Fractals and self similarity. Indiana Univ. Math. J. 30, 713−747 (1981)

[15] Karlin, S.: Random walks arising in learning models. Pac. J. Math. 3, 725−756 (1953)

[16] Kellerer, H.: Ergodic behaviour of affine recursions I, II, III. Preprints (1992)

[17] Kellerer, H.: Order-preserving random dynamical systems: the affine case. To appear

[18] Kifer, Y.: Ergodic theory of random transformations. Boston Basel Stuttgart: Birkhäuser 1986

[19] Lamperti, J.: Criteria for the recurrence or transience of stochastic processes. J. Math. Anal. Appl. 1, 314−330 (1960)

[20] Letac, G.: A contraction principle for certain Markov chains and its applications. Contemp. Math. 50, 263−273 (1986)

[21] Lindley, D.: The theory of a queue with a single server. Proc. Camb. Philos. Soc. 48, 277−289 (1952)

[22] Loynes, R.: The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Philos. Soc. 58, 497−520 (1962)

[23] Nummelin, E.: General irreducible Markov chains and non-negative operators. Cambridge: University Press 1984

[24] Rachev, S., Samorodnitsky, G.: Limit laws for a stochastic process and random recursion arising in probability modelling. Adv. Appl. Prob. 27, 185−202 (1995)

[25] Rachev, S., Todorovic, P.: On the rate of convergence of some functionals of a stochastic process. J. Appl. Prob. 27, 805−814 (1990)

[26] Revuz, D.: Markov chains, 2nd edition. Amsterdam NewYork: North-Holland 1984

[27] Rosenblatt, M.: Recurrent points and transition functions acting on continuous functions. Z. Wahrscheinlichkeitstheorie Verw. Geb. 30, 173−183 (1974)

[28] Tweedie, R.: Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737−771 (1976)

[29] Vervaat, W.: On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables. Adv. Appl. Prob. 11, 750−783 (1979)

[30] Yahav, J.: On a Markov process generated by non-decreasing concave functions. Stochastic Processes Appl. 4, 41−54 (1976)