RANDOM DYNAMICAL SYSTEMS ON ORDERED TOPOLOGICAL SPACES

Hans G. Kellerer

University of Munich

June 30, 2002

Let (X_{n}, n ≥ 0) be a random dynamical system and its state space be endowed with a reasonable topology. Instead of completing the structure as common by some linearity, this study stresses – motivated in particular by economic applications – order aspects. If the underlying random transformations are supposed to be order-preserving, this results in a fairly complete theory. First of all, the classical notions of and familiar criteria for recurrence and transience can be extended from discrete Markov chain theory. The most important fact is provided by existence and uniqueness of a locally finite invariant measure for recurrent systems. It allows to derive ergodic theorems as well as to introduce an attractor in a natural way. 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. For positive recurrent systems, moreover, strengthened versions of weak convergence as well as generalized laws of large numbers are available.

Introduction. The random dynamical systems studied in this paper evolve in one-sided discrete time with independent and stationary increments. Therefore the formalism needed for more general models (see the monographs by Kifer [26] or Arnold [2]) is dispensable, and the process (X_{n}, n ≥ 0) can be introduced as an “ iterated function system ”

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

where (H_{n}, n ∈ N) is a sequence of i. i. d. transformations of the state space E, independent of the initial E–valued variable X_{0}. If no specific structure in E has to be taken into account, this is just another way to introduce a homogeneous Markov chain on E (see von Weizsäcker [39]).

If, however, state space and mappings are supposed to have appropriate linearity (or smoothness) properties, the multiplicative ergodic theorem yields additional insight, provided the relevant integrability conditions are satisfied. Another common model – studied in particular by Barnsley and Elton (see e.g. [6, 5, 14]) – supposes E to be a complete metric space and the mappings H_{n} to satisfy an average contractivity. But in both cases research concerns primarily existence resp. uniqueness of an equilibrium and consequences on the long-term behaviour of the system. In both cases, too, the required moment conditions are by no means necessary.

To exemplify the problems left open, choose E = R_{+} and restrict H_{n} to affine maps, i.e. consider the “ autoregressive model ”

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

2000 Mathematics Subject Classifications. Primary 60J05, 60H25; secondary 54H20, 54F05.

with a sequence of i. i. d. R_{+}^{2}–valued variables (U_{n}, V_{n}). If (S_{n}, n ≥ 0) denotes the random walk with increments log U_{n} ( ≥ −∞), then – without any moment conditions on U_{n} and under weak boundedness conditions on V_{n} – the following trichotomy is established in the preprint [24]:

(a) if S_{n} → −∞, then (X_{n}, n ≥ 0) is “ positive recurrent ”,

(b) if (S_{n}, n ≥ 0) oscillates, then (X_{n}, n ≥ 0) is “ null recurrent ”,

(c) if S_{n} → +∞, then (X_{n}, n ≥ 0) is “ transient ”.

In the existing literature (see in particular the surveys by Vervaat [38] and by Embrechts/Goldie [15] and Goldie/Maller [20]) there is nearly no distinction between cases (b) and (c), though a common treatment of cases (a) and (b) is in fact much more adequate. But it is not the affine (and topological) structure that allows a natural extension of classical notions and central criteria from discrete Markov chain theory to an uncountable state space. While under a topological structure alone there is a variety of definitions for transience and (null or positive) recurrence (see e.g. the various notions in Tweedie [37] and Meyn/Tweedie [32]), the results obtained in the preprint [25] prove that order and topology combined provide an ideal framework for a fairly complete theory of random dynamical systems as considered in this paper.

To cover, however, autoregressive models of higher dimension or stochastic recursions of higher order, assuming E to be totally ordered, as is the case in [24] or [25], is too restrictive. In the sequel, therefore, these preprints are disregarded, and the state space is supposed to be any (partially) ordered topological space. In essence, there is only one restriction: E is supposed to be bounded from below, a condition that is largely in accordance with theory as well as with applications. Indeed, to give only two typical examples: most work on products of i. i. d. matrices is actually restricted to nonnegative matrices (see e.g. Högnäs/Mukherjea [22, Chapter 4]), while economic processes, modeling dams, insurance risk, queues, storage, traffic etc. (see e.g. Asmussen [3, Part C]) in general have 0 as natural lower bound. These and other examples, moreover, justify the restriction to mappings H_{n} that respect the structure of E, i.e. are order-preserving and continuous.

The precise assumptions on the state space E are collected at the beginning of Section 0. They are met not only in the classical case E = R_{+}^{d}, but as well, for instance, by (rooted) tree models. The significance of the order is reflected by the singular role of order convex sets and functions of bounded variation, leading to the basic classes 𝔙(E) and V(E), respectively. The extension of these notions from total to partial order is straightforward, apart from the fact that monotone sets or functions need not be measurable in the general case. But the arising problems, as some less common notions and facts concerning ordered topological spaces, are postponed to the final section. Random is introduced by specifying an element ν in the space N[E] of distributions on the space H[E] of order-preserving continuous transformations of E. This defines a (coupled) family of homogeneous Markov chains (X_{n}^{x}, n ≥ 0), depending on the initial state x ∈ E.

If the interest is not limited to stationary distributions and more generally recurrence properties are studied, the existence of not necessarily finite invariant measures for the underlying transition kernel is just as interesting. To assure uniqueness, being essential for ergodic theorems, restriction to suitably “ irreducible ” systems is inevitable. As it turns out, the adequate notion – introduced at the beginning of Section 1 – employs the order instead of the topology of E. It has to be emphasized here that this, as all subsequent notions, is invariant under conjugation, i.e. under order-preserving homeomorphisms (not distinguishing, for instance, state spaces R_{+} and [0, 1[). Since in general no natural metric is available in E, to answer the basic question of asymptotic equivalence of two processes (X_{n}^{x}, n ≥ 0) and (X_{n}^{y}, n ≥ 0) translations f : E → R must be used. Again, topology has to be replaced by order: while the differences |f(X_{n}^{x}) − f(X_{n}^{y})| need not converge to zero for bounded continuous functions f, they even are summable, if f is of bounded variation. The fundamental inequality (1.4) and its corollaries are crucial in the sequel.

A first consequence is the zero-one law (2.1), applying to all sets in the algebra 𝔙(E) and concerning the probability of an infinite number of visits by the process (X_{n}, n ≥ 0). Since this value is independent of the initial law, the definition of recurrence resp. transience in Section 2 is straightforward, if restricted to these sets. Then it is quite natural to introduce recurrent systems by employing the topological structure and requiring the existence of a compact recurrent set K. As can be shown only in (4.5), K may actually be replaced by an interval [0, y] (where 0 stands for min E). Transient systems are characterized in (2.6) in two different ways: by almost sure divergence of the process (X_{n}, n ≥ 0) to infinity (in the Alexandrov compactification) or, equivalently, by convergence of the associated potential kernel for all compact sets.

The main result of Section 3 is fundamental for all what follows: whenever the process (X_{n}, n ≥ 0) does not diverge to infinity, there is a unique invariant measure μ for the associated Markov kernel. The easy part is the existence proof, being based on the topological properties of the state space. To establish uniqueness, E is exhausted by an increasing sequence of compact sets, and the classical ergodic theorem is applied to the associated embedded systems. The main tool, however, are the summability results from (1.5). An example at the end of the section shows that the uniqueness result in fact requires a restriction to measures compatible with the topological structure, i.e. to Radon measures. The only results related to (3.4), known so far, are due to Babillot et al. [4], who study order-preserving affine systems of a special structure and under suitable moment conditions (see the remarks following (9.3)). In addition, they derive a limit theorem for occupation times as considered in the next section.

Without postulating the invariant measure to be finite, the ergodic theorems in Section 4 have to concern ratios, regarding bounded functions with compact support. While the version for means in (4.2) is restricted to functions in K(E), the pointwise version in (4.3) can be established for functions of bounded variation and their uniform limits, defining a class R(E) that in general is much larger than K(E). As a consequence recurrent sets can simply be described as those having positive invariant measure. More generally, (4.4) characterizes recurrence resp. transience of a given system through hitting probabilities as well as through the potential kernel – in complete analogy to the well-known criteria for discrete Markov chains. The section concludes by deriving a strong version of irreducibility and aperiodicity in the recurrent case.

From the above description of recurrent sets it is easily deduced that, with probability 1, the set of limit points of a recurrent system equals the support M of the invariant measure μ, independently of the initial law. By (5.2) it is justified to call M the “ attractor ” of the system, whether μ is finite or not. Since M need not be compact, to state its self-similarity in general involves a passage to the closure. Nevertheless it allows to characterize the attractor as the smallest nonempty closed set that is mapped into itself by the mappings H_{n} with probability 1. A more explicit characterization of the attractor is established at the end of Section 5: M can be identified with the set of constants in the closed semigroup generated by the mappings that define the system, i.e. that are contained in the support N of ν. If the state space is only partially ordered, actually “ local boundedness ” of E has to be supposed here (see the final section).

As mentioned above, the existing literature concerns almost exclusively positive recurrent systems, i.e. the case of a finite invariant measure, as treated in Section 6. There are numerous studies considering E = R_{+} with its total order and random transformations preserving this order as, for instance, Alpuim/Athayde [1], Goldie [19], Helland/Nilsen [21], Lund et al. [30], Yahav [40]. There is, moreover, a number of papers dealing also with only partially ordered state spaces as Bougerol/Picard [10], Diaconis/Freedman [12, Section 3], Glasserman/Yao [18], Jarner/Tweedie [23], Mairesse [31], Rachev/Samorodnitsky [34], Rachev/Todorovic [35], and in particular Brandt et al. [11, Section 1.3] (where, however, a metric compatible with the order is postulated). The full benefit from order and monotonicity turns out under time reversal, i.e. replacing left by right composition of the underlying random transformations. The resulting (non-Markovian) “ dual process ” (Y_{n}^{0}, n ≥ 0) increases pointwise, and its limit Y satisfies a zero-one law, distinguishing positive and null recurrence, where in the positive recurrent case (6.7) reveals the stationary distribution as the law of Y. Combined with the asymptotic behaviour of the original process (X_{n}^{0}, n ≥ 0) this yields the criterion (6.8) and the unified characterization of positive recurrence, null recurrence, and transience at the end of the section.

Another criterion for positive resp. null recurrence can be established by considering the hitting times T_{B} of sets B that are determined by the order. While for increasing intervals [x, ·] it is shown already in (1.2) that E(T_{[x, ·]}), regardless of the initial law, is always finite, (7.1) exhibits a different behaviour for decreasing intervals [0, x]. Now, with T_{B}^{y} denoting the hitting time of B for the process starting at y, for any x ∈ M the mean passage time E(T_{[0,x]}^{x}) is finite if and only if the system is positive recurrent. The main tool in the proof is (a slight extension of) the recurrence theorem of Kac. Section 7 concludes by the topological analogue (7.3) of the classical result on mean passage times for discrete Markov chains (here again local boundedness enters).

In Section 8 the ratio ergodic theorems are considerably strengthened for positive recurrent systems. In this case the laws μ_{n} = L(Y_{n}^{0}) of the dual process, hence also the laws L(X_{n}^{0}) = μ_{n}, are easily seen to converge weakly to the stationary distribution μ. By (1.6) this extends to arbitrary initial laws and from functions in C(E) to those in the class R(E). The resulting convergence for all decreasing sets suggests the introduction of a metric d for distributions on the space E (lacking any metric structure) such that metric convergence is strictly stronger than weak convergence. Employing an idea in Dubins/Freedman [13] (apparently the first treatment of iterated function systems, though restricted to the case E = [0, 1]), it is then possible to verify even d(μ_{n}, μ) → 0 in (8.3) – with geometric convergence whenever the state space is bounded. The section concludes by proving the mixing property for the stationary version (X_{n}, n ≥ 0) and deriving from it in (8.5) a fairly general law of large numbers, again independent of the initial law.

Basic assumption throughout the preceding sections is – apart from the existence of min E – the irreducibility of the system. Under a total ordering this means in fact no real restriction: simply reduce the state space to those elements that can be reached from 0 in the sense of (1.1). But this procedure need not work in general, as is demonstrated in Section 9. The arising problems, however, can be settled as above, whenever the system is strictly order-preserving. This is a familiar hypothesis in affine models, for instance, where it concerns the occurrence of zero entries in the associated random matrix. For strictly order-preserving systems the reduction works as in the totally ordered case and leads to a state space that is in addition locally bounded (as required for one half of (5.7) and (7.3)).

The concluding Section 10 collects the necessary material on ordered topological spaces. The fundamental fact needed here is the existence of an open base consisting of order convex sets. This is a simple consequence of Nachbin’s extension theorem, i.e. of Tietze’s extension theorem carried over to ordered topological spaces. Results not to be found in the standard reference [33] concern the Alexandrov compactification of ordered topological spaces with a lower bound in (10.5), its consequences for the approximation by nonnegative decreasing functions from K(E) in (10.6) and (10.7), and finally the explicit representation of sets in the algebra 𝔙(E) resp. of functions in the vector lattice V(E) seen from the viewpoint of universal measurability in (10.8).

0. Preliminaries. Throughout Sections 1 – 9 the state space E is an ordered topological space (the definition being recalled in Section 10), where regarding the topology it is sufficient to suppose that

(E1) E is locally compact and second countable,

while regarding the order it is necessary to suppose that

(E2) E has a lower bound, denoted by 0.

If E^{∗} = E ∪{∞} is the Alexandrov compactification of E (∞ being an isolated point if E is compact), the order is extended from E to E^{∗} in accordance with (E2) by letting ∞ be an upper bound of E^{∗}. This makes E^{∗} again an ordered topological space if and only if (see (10.5))

(E3) the decreasing hull of a compact subset of E is compact,

entailing compactness in particular for each interval [0, x]. In the sequel conditions (E1) – (E3) will be taken for granted, calling E admissible in this case.

The topological notations are as usual: 𝔊(E) / 𝔉(E) / 𝔎(E) / 𝔅(E) denote, respectively, the class of open / closed / compact / Borel subsets of E, while C(E) / K(E) / B(E) stand, respectively, for the class of bounded continuous / compactly supported continuous / Borel functions f : E → R.

The following notations refer to the order: If A is a subset of E, then A^{↓} and A^{↑} denote, respectively, its decreasing and increasing hull, i.e.

A^{↓} = ⋃_{x∈A} [0, x] and A^{↑} = ⋃_{x∈A} [x, ·] .

A is called (order) convex if A ∋ x ≤ y ∈ A implies [x, y] ⊂ A or, equivalently, if A = A^{↓} ∩ A^{↑}. Arrows are also used to denote, for instance, by 𝔊^{↓}(E) the class of decreasing sets in 𝔊(E) or by B^{↑}(E) the class of increasing functions in B(E).

To extend the notion of bounded variation from total to partial order, let V(E) be the class of functions f ∈ B(E) satisfying

sup { ∑_{k∈N} |f(x_{k+1}) − f(x_{k})| : x_{1} ≤ x_{2} ≤ … } < ∞

and 𝔙(E) the class of sets B ∈ 𝔅(E) with 1_{B} ∈ V(E). Universal null sets disregarded, V(E) is the linear space generated by the bounded monotone functions, while 𝔙(E) is the algebra generated by the convex sets (see (10.8)). The closure of V(E) with respect to the uniform norm, yielding the class of regular functions (having finite limits from left and right everywhere on E^{∗}) under a total ordering and including K(E) in the general case (see (10.6)), is denoted by R(E).

M(E) denotes the class of all locally finite measures on 𝔅(E), which due to (E1) are Radon measures and can be identified with the positive linear functionals on K(E). If μf denotes the μ−integral of a function f, then M(E) is endowed with the vague (weak*) topology, generated by the mappings μ ↦ μf, f ∈ K(E); the corresponding convergence is denoted by →_{v} . On the subspace M_{1}(E) of probability measures this induces the weak (narrow) topology, generated by the mappings μ ↦ μf, f ∈ C(E); the corresponding convergence is denoted by →_{w} .

The space C[E] := C(E, E) of continuous mappings from E to E, endowed with the compact-open topology, is a Polish space due to (E1), and this carries over to the closed subspace H[E] of order-preserving continuous mappings h : E → E, being a central object of this paper. Under composition H[E] is a subsemigroup of C[E], where composition is continuous by the local compactness of E and thus measurable by the second countability of C[E].

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], making this space a semigroup itself. Occuring powers are denoted by ν^{n}, hence

∫ _{H[E]} f(h(x)) ν^{n}(dh) = ∫ _{H[E]} … ∫ _{H[E]} 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 identy map. Since H[E] is second countable, the support N is well-defined for ν ∈ N[E].

Now the stochastic model can be formally introduced. Let be given an admissible space E and, on some probability space (Ω, 𝔄, P),

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

– 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} = H_{n}(X_{n−1}) for n ∈ N .

Therefore the distribution of (X_{n}, n ≥ 0) is completely determined by ν and the initial law μ_{0} = L(X_{0}). 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 analogous equation for conditional expectations.

As usual, the initial law is largely of secondary importance, and the primary component is the distribution ν. Therefore, whenever possible, it will be briefly referred to the (dynamical ) system (E, ν) . All notions to be defined in Sections 1 – 9 will depend on ν, but this dependence will be suppressed in related notations (as for the support N above), because ν is supposed to be fixed.

Clearly, (X_{n}, n ≥ 0) is a homogeneous Markov chain. Its transition kernel P transforms (nonnegative) functions f ∈ B(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 ∈ 𝔅(E) ,

which in the σ−finite case equals

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

P is a Feller kernel, which in addition transforms increasing functions into functions of the same type. By (E2) this implies in particular:

(0.1) Lemma The sequence (ε_{0} P^{n}, n ≥ 0) is stochastically increasing, i.e.

E(f(X_{n−1}^{0})) ≤ E(f(X_{n}^{0})) for 0 ≤ f ∈ B^{↑}(E) .

Proof. This is immediate from the equations

E(f(X_{n−1}^{0})) = ∫ _{E} P^{n−1}f (0) P (0; dx) ,
E(f(X_{n}^{0})) = ∫ _{E} P^{n−1}f (x) P (0; dx) .  □

Finally, it has to be mentioned that the passage from the distribution ν to the kernel P in general is not injective.

1. Irreducible systems. Let (E, ν) be a dynamical system as introduced in the preceding section. Then, to classify it as recurrent or transient, requires some communication structure to prevent the state space from splitting into different classes. It turns out to be sufficient that, starting from the minimal state 0, each state x with positive probability can be reached or exceeded in the following sense:

(1.1) Definition The system (E, ν) is called “ (upwards) irreducible ”, if for any x ∈ E there is some n ∈ N such that

P^{n}(0; [x, ·]) = P(X_{n}^{0} ≥ x) = ν^{n}(h(0) ≥ x) > 0 .

It is immediate from (0.1) that the system (E, ν^{n}) is irreducible for all n ∈ N, whenever this holds for one n ∈ N.

The question, whether irreducibility can be accomplished by suitably reducing the state space, is postponed to Section 9. As an example consider the “ Cantor system ”, assigning mass ν(\{h_{i}\}) = \frac{1}{2} to the two mappings h_{1} : x ↦ x/3 and h_{2} : x ↦ x/3 + 2/3 : the adequate state space in the present setting is E = [0, 1[.

In spite of its weak appearance, the condition in (1.1) has strong recurrence implications for increasing intervals:

(1.2) Proposition If the system (E, ν) is irreducible, then for arbitrary initial law and all x ∈ E

(a)  P(lim sup_{n→∞} {X_{n} ≥ x}) = 1 ,
(b)  E(T_{[x, ·]}) < ∞ ,

where T_{B} := inf {n ∈ N : X_{n} ∈ B} (≤ ∞) for B ∈ 𝔅(E).

Proof. By assumption ϑ := ν^{n}(h(0) ≥ x) > 0 for some n, which yields by monotonicity and independence

P(T_{[x, ·]} > kn) ≤ P^{0}(T_{[x, ·]} > kn)
≤ ∏_{0≤i<k} (1 − P(H_{(i+1)n} ∘ … ∘ H_{in+1} (0) ≥ x))
= (1 − ϑ)^{k} for all k ∈ N.

This settles (b), which in turn implies (a) by the Markov property. □

Under a total ordering the state space of an irreducible system, due to (E1), is a countable union of intervals [0, y_{n}]. Somewhat surprisingly, this result extends to the general case:

(1.3) Proposition If the system (E, ν) is irreducible, then there is a countable subset A of E such that E = A^{↓}.

Proof. If (Y_{n}^{0}, n ≥ 0) is an independent copy of (X_{n}^{0}, n ≥ 0), then (1.2a) implies

P( ⋂_{m∈N} ⋃_{n∈N} {x_{m} ≤ Y_{n}^{0}}) = 1 for all (x_{n}, n ∈ N) ∈ E^{N} .

Applying Fubini to the product of the distributions of (X_{n}^{0}, n ≥ 0) and (Y_{n}^{0}, n ≥ 0) twice, it follows that

P( ⋂_{m∈N} ⋃_{n∈N} {X_{m}^{0} ≤ y_{n}}) = 1 for some (y_{n}, n ∈ N) ∈ E^{N} .

For any x ∈ E and l ∈ N satisfying P(X_{l}^{0} ≥ x) > 0 therefore

{X_{l}^{0} ≥ x} ∩ ( ⋂_{m∈N} ⋃_{n∈N} {X_{m}^{0} ≤ y_{n}}) ≠ ∅ ,

hence for m = l in particular

{X_{l}^{0} ≥ x} ∩ ( ⋃_{n∈N} {X_{l}^{0} ≤ y_{n}}) ≠ ∅ .

This implies x ∈ A^{↓} for A := {y_{n} : n ∈ N}. □

The following inequality is the crucial tool in the sequel:

(1.4) Theorem Let the system (E, ν) be irreducible and suppose 0 ≤ f ∈ B^{↑}(E). Then for all x ∈ E

∑_{n≥0} E(f(X_{n}^{x}) − f(X_{n}^{0})) ≤ E(T_{[x, ·]}^{0}) sup_{n≥0} E(f(X_{n}^{0})) ,

where T_{B}^{y} := inf {n ∈ N : X_{n}^{y} ∈ B} (≤ ∞) for y ∈ E and B ∈ 𝔅(E).

Proof. If f is replaced by f ∧ k, k ∈ N, then the corresponding differences on the left-hand side increase for k → ∞ to the difference in question, i.e. f may be assumed to be bounded. In addition, by (1.2b) the stopping time T := T_{[x, ·]}^{0} may be assumed to be finite everywhere. Then, with the notation A_{l} := {T ≤ l}, for n ≥ 0 fixed and m ≤ n arbitrary

(∗) E(1_{A_{n−m}} f(X_{T +m}^{0})) = E(1_{A_{n−m}} f(H_{T +m} ∘ … ∘ H_{T +1} (X_{T}^{0} )))

≥ E(1_{A_{n−m}} f(H_{T +m} ∘ … ∘ H_{T +1} (x)))
= P(A_{n−m}) E(f(X_{m}^{x})) ,

where the inequality is a consequence of f being increasing, while the final equality uses the fact that (H_{T +1}, …, H_{T +m}) is independent of T and distributed as (H_{1}, …, H_{m}). But, f is nonnegative and thus

∑_{0≤m≤n} f(X_{m}^{0}) ≥ ∑_{0≤m, T +m≤n} f(X_{T +m}^{0}) = ∑_{0≤m≤n} 1_{A_{n−m}} f(X_{T +m}^{0}) .

This leads by integration and inserting from (∗) to

∑_{0≤m≤n} E(f(X_{m}^{x}) − f(X_{m}^{0}))
≤ ∑_{0≤m≤n} E(f(X_{m}^{x})) − ∑_{0≤m≤n} P(A_{n−m}) E(f(X_{m}^{x}))
= ∑_{0≤m≤n} (1 − P(A_{n−m})) (E(f(X_{m}^{x}) − f(X_{m}^{0})) + E(f(X_{m}^{0}))) ,

which by (0.1) implies

∑_{0≤m≤n} P(T ≤ n − m) E(f(X_{m}^{x}) − f(X_{m}^{0}))
≤ ∑_{0≤m≤n} P(T > n − m) E(f(X_{m}^{0}))
≤ E(T) E(f(X_{n}^{0})) .

Since P(T ≤ n − m) ↑ 1 for n → ∞, the assertion follows. □

Apart from arising measurability problems the preceding result can be easily extended to a larger class of functions:

(1.5) Proposition Let the system (E, ν) be irreducible and suppose f ∈ V(E). Then for all x ∈ E

(a)  ∑_{n≥0} E(|f(X_{n}^{x}) − f(X_{n}^{0})|) < ∞ ,

and for arbitrary initial law

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

Proof. According to (10.8) there are bounded increasing and universally measurable functions f_{i} ≥ 0 such that f = f_{1} − f_{2}. Since the variables X_{n}^{x} : Ω → E are universally measurable as well, provided the underlying probability space (Ω, 𝔄, P) is assumed to be complete, the proof of (1.4) works for f_{i}, too. In view of (1.2b) this proves assertion (a), which by Fubini implies assertion (b). □

For some applications, where summability of the differences may be replaced by convergence to zero, the class of admissible functions can be enlarged once more:

(1.6) Proposition Let the system (E, ν) be irreducible and suppose f ∈ R(E). Then for arbitrary initial law

f(X_{n}) − f(X_{n}^{0}) → 0 a.s. .

Proof. This is immediate from (1.5b) and the definition of R(E). □

It has to be emphasized that, even under a total ordering, the last result may fail for functions f ∈ C(E). To construct a nondegenerate (i.e. recurrent) counterexample consider the following system: on E = R_{+} let the support N of ν consist of the fractional linear mappings

h_{1} : x ↦ x + 1 and h_{2} : x ↦ x / (x + 1) .

Starting with n_{0} := 0 choose a sequence (n_{k}, k ≥ 0) such that

lim sup_{k→∞} P(A_{k}) = 1 with A_{k} := ⋃_{n_{k−1}<n≤n_{k}} {X_{n}^{0} ≥ k} ,

as is possible in view of (1.2). Denote the finite support of L(X_{n}^{x}) by B_{n}^{x} and define the discrete sets

B^{x} := ⋃_{k∈N} (( ⋃_{n_{k−1}<n≤n_{k}} B_{n}^{x}) ∩ [k, ∞[ ) for x ∈ E .

Then the sets B^{0} and B^{y} are disjoint for fixed irrational y, due to h_{i}^{−1}[Q_{+}] = Q_{+} for i = 1, 2. Thus there is a function f ∈ C(E) with 0 ≤ f ≤ 1, satisfying f(x) = 0 for x ∈ B^{0} and f(x) = 1 for x ∈ B^{y}. Then on A_{k} almost surely

max_{n_{k−1}<n≤n_{k}}(f(X_{n}^{y}) − f(X_{n}^{0})) = 1 ,

hence in view of P(lim sup_{k→∞} A_{k}) = 1 finally

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

2. Recurrence and transience. In general, the probability that the process (X_{n}^{x}, n ≥ 0) visits a set B ∈ 𝔅(E) infinitely often neither obeys a zero-one law nor is independent of the starting point x ∈ E – as can be seen, for instance, by the Cantor system even for appropriate countable sets. But an application of the final result of Section 1 yields:

(2.1) Theorem Let the system (E, ν) be irreducible and suppose B ∈ 𝔙(E). Then

P( lim sup_{n→∞} {X_{n} ∈ B}) = 0 or 1 ,

where the value is independent of the initial law.

Proof. Choosing f = 1_{B} ∈ V(E) in (1.6) proves

lim sup_{n→∞} {X_{n} ∈ B} = lim sup_{n→∞} {X_{n}^{0} ∈ B} =: A^{0} a.s. .

Applying this result to the distribution of X_{1}^{0} as initial law and the shifted sequence (H_{n}, n > 1) yields

A^{0} = lim sup_{n→∞} {H_{n} ∘ … ∘ H_{2} (0) ∈ B} a.s. .

Repeating the argument shows A^{0} to be contained in the completed tail σ−field of (H_{n}, n ∈ N), and the assertion follows. □

The preceding result justifies:

(2.2) Definition Let the system (E, ν) be irreducible. Then B ∈ 𝔙(E) is called “ recurrent ”, if

P( lim sup_{n→∞} {X_{n}^{x} ∈ B}) = 1 for one (or all) x ∈ E ,

and “ transient ” otherwise.

The following consequence of recurrence will be needed:

(2.3) Lemma Let the system (E, ν) be irreducible and B ∈ 𝔙(E) be recurrent. Then for any finite subset A of E there exists some n ∈ N such that

P(X_{n}^{x} ∈ B for all x ∈ A) > 0 .

Proof. According to (1.6)

1_{B}(X_{n}^{x}) − 1_{B}(X_{n}^{0}) → 0 a.s. for all x ∈ A .

Since A is finite and B is recurrent, this implies

lim sup_{n→∞} {X_{n}^{x} ∈ B for all x ∈ A} = lim sup_{n→∞} {X_{n}^{0} ∈ B} = Ω a.s. .

Therefore the probabilities in question even sum up to ∞. □

It is immediate from (1.2) that each increasing set B ≠ ∅ is recurrent. For decreasing sets the following criterion is available:

(2.4) Proposition Let the system (E, ν) be irreducible. Then for arbitrary initial law a set B ∈ 𝔅^{↓}(E) is recurrent if and only if ∑_{n≥0} P(X_{n} ∈ B) = ∞.

Proof. Due to (2.1), the condition is certainly necessary. To prove its sufficiency, let B be transient and assume without restriction X_{0} = 0. Therefore the variable Z := ∑_{n∈N} 1_{B}(X_{n}^{0}) satisfies ϑ := P(Z ≥ l) < 1 for suitable l ∈ N. Using the stopping time

T := inf {n ∈ N : ∑_{1≤m≤n} 1_{B}(X_{m}^{0}) = l}

with respect to (H_{n}, n ∈ N), it follows as in the proof of (1.4) that

P(Z ≥ k l) = P(T < ∞ , ∑_{n∈N} 1_{B} (H_{T +n} ∘ … ∘ H_{T +1} (X_{T}^{0} )) ≥ (k − 1) l)
≤ P(T < ∞ , ∑_{n∈N} 1_{B} (H_{T +n} ∘ … ∘ H_{T +1} (0)) ≥ (k − 1) l)
= P(Z ≥ l) P(Z ≥ (k − 1) l) .

Therefore

P(Z ≥ k l) ≤ ϑ^{k} for all k ∈ N

and thus indeed E(Z) < ∞. □

The topological structure enters in the central classification:

(2.5) Definition An irreducible system (E, ν) (or the process (X_{n}, n ≥ 0) or the kernel P) is called “ recurrent ”, if 𝔙(E) contains a compact recurrent set K, and “ transient ” otherwise.

In Section 4, using the invariant measure, it will be shown that the set K required in this definition may in fact be postulated to be an interval [0, y].

The assumption (E3), connecting compactness and order in Section 0, is essential for the following criterion:

(2.6) Theorem Let the system (E, ν) be irreducible. Then for arbitrary initial law the following conditions are equivalent:

(1)  (E, ν) is transient ,
(2)  X_{n} → ∞ a.s. ,
(3)  ∑_{n≥0} P(X_{n} ∈ K) < ∞ for all K ∈ 𝔎(E) .

Proof. The equivalence (1) ⇔ (2) follows from the existence of a sequence of sets K_{l} ∈ 𝔎(E) such that each K ∈ 𝔎(E) is included in some K_{l}. The implication (1) ⇒ (3) is a consequence of (2.4), because the compact set K, due to (E3), may be assumed to be decreasing. The final implication (3) ⇒ (1) is straightforward. □

Restricting condition (3) to decreasing sets K, it follows by (0.1) that the system (E, ν^{n}) is recurrent for all n ∈ N, whenever this holds for one n ∈ N.

For an application consider an “ exchange process ” as has been studied in [21] and in its best accessible form is given by the recursion

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

with a sequence of i. i. d. variables U_{n} ≥ 0. Here, X_{n−1} is the utility of some equipment in use at time n − 1, losing one unit during period n, and U_{n} the utility of a new equipment available at time n. The corresponding mappings h : x ↦ (x−1)∨u, restricted to the state space

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

belong to H[E] for all u ∈ E. With ν ∈ N[E] being the associated distribution, the system (E, ν) is obviously irreducible. The explicit representation

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

implies by independence

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

where F denotes the common distribution function of U_{n}, n ∈ N. Therefore (2.6) yields recurrence whenever E is bounded, because the summands P(X_{n}^{0} ≤ y) are strictly positive and eventually constant for any y ∈ E satisfying P(U_{n} ≤ y) > 0. For E = R_{+} both cases are possible:

(1) if U_{n}, n ∈ N, have the common density f_{1}(x) = (x + 1)^{−2}, then F (y) = \frac{y}{y + 1}

implies

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

i.e. the process is recurrent;

(2) if the density is replaced by f_{2}(x) = 2x(x + 1)^{−3}, then F (y) = (\frac{y}{y + 1})^{2}, and it

follows similarly that the process is transient.

It should be noted that – in spite of the contrasting asymptotic behaviour – the variables U_{n} behave similarly in both cases as far as it concerns the existence of moments, due to f_{1}(x) ≤ f_{2}(x) ≤ 2f_{1}(x) for x ≥ 1 (for a continuation see Sections 3, 4, and 6).

In general, as in discrete Markov chain theory, it may demand some effort to decide whether a system (E, ν) is recurrent or transient. For an example consider E = [0, 1[ with ν assigning mass \frac{1}{2} to the mappings defined by h_{1}(x) = (x + 1)/2 and h_{2}(x) = x^{2} (solvable by conjugation).

3. Invariant measures. As in discrete Markov chain theory, a central question concerns the existence and uniqueness of invariant measures in the recurrent case. In accordance with the topological assumptions, this question will – and must – be treated within the class M(E) of locally finite measures. The easy task here is existence, where general results by Foguel [17] apply. Since the arguments can be simplified, due to monotonicity, the proof of the following assertion is outlined:

(3.1) Proposition Let the system (E, ν) be irreducible and suppose

0 ≤ g ∈ K^{↓}(E) with ∑_{n≥0} E(g(X_{n}^{0})) = ∞ .

Then the measures ϱ_{n} ∈ M(E) defined by

ϱ_{n}(f) := ∑_{0≤m<n} E(f(X_{m}^{0})) / ∑_{0≤m<n} E(g(X_{m}^{0})) for f ∈ K(E)

for all n ≥ n_{0} (say) satisfy

(a) the sequence (ϱ_{n}, n ≥ n_{0}) is relatively compact,

(b) each limit point μ ∈ M(E) is a nontrivial invariant measure for (E, ν) (i.e. for the kernel P).

Proof. (a) By assumption and (1.5a) the functions

s_{n} := ∑_{0≤m<n} P^{m}g ∈ C(E) for n ∈ N

increase to infinity for all x ∈ E. Therefore for fixed f ∈ K(E) there exists l ∈ N with f ≤ s_{l}, which by (0.1) implies

P^{m}f (0) ≤ P^{m}s_{l} (0) ≤ l P^{m}g (0) for all m ≥ 0 .

Thus the sequence (ϱ_{n}(f), n ≥ n_{0}) is bounded for all f ∈ K(E), i.e. the sequence (ϱ_{n}, n ≥ n_{0}) is uniformly locally finite, which proves (a).

(b) If ϱ_{n_{k}} →_{v} μ ∈ M(E), then μg = 1 and thus μ is indeed nontrivial. To prove its invariance consider 0 ≤ f ∈ K(E) and approximate 0 ≤ P f ∈ C(E) from below by functions from K(E). This yields

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

because s_{n_{k}}(0) → ∞ and P^{n_{k}}f (0) is bounded by max f. Applying the resulting inequality μP ≤ μ to s_{l} − f ≥ 0, with f and l chosen as in the proof of (a), yields

μf − μP f ≤ μs_{l} − μP s_{l} ≤ μg =: γ .

Disregarding the middle term, this implies

μf − μP f ≤ γ for all f ∈ K(E) ,

and – replacing f by multiples – proves the invariance of μ. □

Uniqueness of the invariant measure is established by a localization, which requires an elementary result from probabilistic potential theory:

(3.2) Lemma Let the system (E, ν) be irreducible and K ∈ 𝔎^{↓}(E) be recurrent. With the almost surely finite hitting time T_{K} define the Markov kernel ^{K}P by

KP (x; B) := P^{x}(X_{T_{K}} ∈ B) for x ∈ K and B ∈ 𝔅(K) .

If a measure μ ∈ M(E) is invariant for P, then its restriction ^{K}μ ∈ M(K) is invariant for ^{K}P.

Proof. μP ≤ μ implies ^{K}μ^{K}P ≤ ^{K}μ (see e.g. Proposition 2.2.6 in [36]). Since Kμ is a finite measure and ^{K}P is a stochastic kernel, in fact equality has to hold in this inequality. □

For the main step towards uniqueness the results from Section 1 are crucial:

(3.3) Proposition Let the system (E, ν) be irreducible and K ∈ 𝔎^{↓}(E) be recurrent. Moreover, let μ ∈ M(E) be invariant for (E, ν) and satisfy μ(K) > 0. Then for 0 ≤ f ∈ B^{↓}(E) with supp f ⊂ K and all x ∈ E

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

Proof. 1. The variables

\underline{Q}^{x} := lim inf_{n→∞} ( ∑_{0≤m<n} f(X_{m}^{x}) / ∑_{0≤m<n} 1_{K}(X_{m}^{x})) for x ∈ E

are almost surely independent of x. Indeed:

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

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

tends to 1 almost surely by (1.5b) and the recurrence of K.

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

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

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

tends to 0 almost surely for the same reasons.

Neglecting single summands and applying Fubini, it follows as in the proof of (2.1) that in fact \underline{Q}^{x} equals some constant \underline{q} almost surely.

2. Because of 0 < μ(K) < ∞ the restriction ^{K}μ of μ to K may be assumed to be normalized, hence by (3.2) to be a stationary distribution for the Markov kernel ^{K}P. Let (^{K}X_{n}, n ≥ 0) denote the corresponding “ embedded process ” of (X_{n}, n ≥ 0), where X_{0} is distributed according to (the trivial extension of) ^{K}μ. Since f is bounded, the classical ergodic theorem applies to the stationary process (^{K}X_{n}, n ≥ 0), i.e. the limit

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

exists almost surely and in view of supp f ⊂ K satisfies

E(Q) = E(f(^{K}X_{0})) = μf .

But on \{X_{0} = x\} the sequence of quotients defining \underline{Q}^{x} arises from the successive means of (f(^{K}X_{n}), n ≥ 0) through “ extension to the right by constancy ” in an evident sense. Therefore, applying Fubini once more, it turns out that the variable Q and the constant \underline{q} agree almost surely and thus \underline{q} = μf. Since the argument carries over to the upper limit, the assertion is established. □

Now one of the main results of this paper can be stated:

(3.4) Theorem For any recurrent system (E, ν) there exists one and – up to multiples – only one nontrivial invariant measure μ ∈ M(E).

Proof. 1. If K ∈ 𝔎^{↓}(E) is recurrent and g_{l} ∈ K^{↓}(E) with g_{l} ≥ 1_{K} is chosen according to (10.7), then the condition in (3.1) is satisfied for g = g_{l} by (2.4), and the existence of μ is established.

2. To prove uniqueness, let μ′ ∈ M(E) be another nontrivial invariant measure for (E, ν) and exhaust E by an increasing sequence of sets K_{l} ∈ 𝔎^{↓}(E), where μ(K_{l}) > 0 and μ′(K_{l}) > 0 and in addition recurrence of K_{l} may be assumed. Then an application of (3.3) yields constants γ_{l} such that

μ′(1_{K_{l}}f) = γ_{l} μ(1_{K_{l}}f) for 0 ≤ f ∈ B^{↓}(E) .

Inserting f = 1_{K_{m}}, m ≠ l, proves γ_{l} to be a constant γ independent of l and thus, with K_{0} as defined in (10.6a),

μ′(1_{K_{l}}f) = γ μ(1_{K_{l}}f) for f ∈ K_{0} .

This equation extends to f ∈ K(E), because the uniform approximation of f by a sequence (f_{k}, k ∈ N) from K_{0} according to (10.6a) can be carried out with all functions vanishing outside a fixed compact set (otherwise multiply by some g_{l} from (10.7)). The assertion follows for l → ∞. □

As usual the actually one-dimensional family of invariant measures μ ∈ M(E) will be briefly called the invariant measure in the sequel.

It has to be emphasized that, even under a total ordering, the uniqueness statement in (3.4) concerns locally finite measures only. To exhibit a counterexample, choose E = [0, 1[ and let ν assign mass \frac{1}{2} to the piecewise affine maps defined by

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

Then (E, ν) is clearly irreducible, and the uniform distribution μ on E is easily checked to be a finite invariant measure. With μ as initial law the series ∑_{n≥0} P(X_{n} ≤ y) diverges for all y > 0, and thus (E, ν) is recurrent by (2.6). 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. Incidentally, the existence of both a finite and an infinite, but σ−finite, invariant measure in this example proves the Doeblin-Harris theory of recurrent Markov chains on an abstract state space to be inadequate in the present setting.

Finally, it has to be mentioned that, again even under a total ordering, there is no converse of (3.4), i.e. there are transient systems with a unique nontrivial and locally finite invariant measure. For an example consider the transient case (2) of the exchange process from Section 2. It is easily seen that a measure μ ∈ M(E) is invariant if and only if the function Φ(y) := μ([0, y]) satisfies

Φ(y) = Φ(y + 1) F (y) = Φ(y + 1) (\frac{y}{y + 1})^{2} for y ≥ 0 .

Therefore Φ_{0}(y) = y^{2} defines a solution, while for any other solution Φ by iteration

Φ(y) = Φ(y + n) (\frac{y}{y + n})^{2} for y ≥ 0 and n ∈ N .

For 0 ≤ y ≤ m ∈ N this provides by monotonicity the bounds

Φ(y) = Φ(y + n) (\frac{y}{y + n})^{2} ≥ Φ( 0 + n) (\frac{y}{y + n})^{2} = Φ(1) y^{2} ( \frac{n}{y + n} )^{2} ,

Φ(y) = Φ(y + n) (\frac{y}{y + n})^{2} ≤ Φ(m + n) (\frac{y}{y + n})^{2} = Φ(1) y^{2} (\frac{m + n}{y + n})^{2} ,

which for n → ∞ lead to Φ(y) = Φ(1) y^{2} and thus to the asserted uniqueness.

4. Ergodic theorems. The first theorem in this section requires some preparation, concerning again asymptotic independence of the initial law:

(4.1) Proposition Let the system (E, ν) be recurrent with invariant measure μ and suppose 0 ≤ f ∈ B^{↓}(E) with μf > 0. Then for arbitrary initial law

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

Proof. With the abbreviation

s_{n}^{x} := ∑_{0≤m<n} E(f(X_{m}^{x})) for x ∈ E

an application of (1.4) to the increasing function f′ := f(0) − f ≥ 0 yields by (1.2b)

0 ≤ s_{n}^{0} − s_{n}^{x} ≤ E(T_{[x, ·]}^{0}) f(0) < ∞ .

If K ∈ 𝔎^{↓}(E) is a recurrent set with ∫_{K} f dμ > 0, then (3.3) implies

∑_{0≤m<n} 1_{K}f(X_{n}^{0}) → ∞ a.s. ,

because the analogous result for 1_{K} replacing 1_{K}f follows from the recurrence of K. Therefore s_{n}^{0} → ∞ and thus the quotients s_{n}^{x}/s_{n}^{0} converge to 1. Since this convergence is dominated by the constant 1, it continues to hold when integrated by the initial law. □

Now a mean ergodic theorem can be established:

(4.2) Theorem Let the system (E, ν) be recurrent with invariant measure μ and suppose f, g ∈ K(E). Then for arbitrary initial law

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

whenever the quotient on the right-hand side makes sense.

Proof. 1. First, the problem will be simplified in four steps:

(1) By comparing both the nominator and the denominator with the corresponding sum for a third function it is seen that 0 ≤ g ∈ K^{↓}(E) with μg > 0 may be assumed in the sequel.

(2) Since the uniform approximation of f by a sequence (f_{k}, k ∈ N) from K_{0} according to (10.6a) can be carried out from below and above with all functions vanishing outside a fixed compact set (otherwise multiply by some g_{l} from (10.7)), f may be restricted to K_{0}.

(3) Therefore it is sufficient to consider the case 0 ≤ f ∈ K^{↓}(E), where in addition μf > 0 may be assumed (otherwise replace f by f + g).

(4) Thus f and g both satisfy the assumptions of (4.1), which justifies finally the restriction to the initial law ε_{0}.

2. Now the relative compactness from (3.1a) and the uniqueness of the invariant measure yield a constant γ such that

∑_{0≤m<n} E(f(X_{m}^{0})) / ∑_{0≤m<n} E(g(X_{m}^{0})) → γ μf

with an analogous relation for g replacing f. This shows γ = 1/μg and concludes the proof. □

It has to be mentioned that the question, whether the convergence in (4.2) extends from f, g ∈ K(E) to functions in R(E) with compact support, poses an open problem. An affirmative answer is possible under a total ordering (see Theorem 6.3 in [25]) as well as concerning the following pointwise ergodic theorem:

(4.3) Theorem Let the system (E, ν) be recurrent with invariant measure μ and the functions f, g ∈ R(E) have compact support. Then for arbitrary initial law

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

whenever the quotient on the right-hand side makes sense.

Proof. Assume X_{0} = x, as is justified by Fubini, and simplify the problem as in step (1) of the proof of (4.2) by considering g = 1_{K} with supp f ⊂ K ∈ 𝔎^{↓}(E) and μ(K) > 0. Then proceed as follows:

(1) For f ∈ V(E) choose a representation f = f_{1} − f_{2} according to (10.8) and a constant γ ≥ f_{1}(0) ∨ f_{2}(0), so that f = f′_{1} − f′_{2} with universally measurable decreasing functions f′_{1} := γ − f_{2} ≥ 0 and f′_{2} := γ − f_{1} ≥ 0. If in addition supp f′_{i} ⊂ K, as can be achieved by multipying with 1_{K}, then it follows as in the proof of (1.5a) that the arguments for (3.3) work as well for the functions f′_{i}.

(2) For f ∈ R(E) approximate uniformly by a sequence (f_{k}, k ∈ N) from V(E), which can be carried out from below and above with supp f_{k} ⊂ K for all k ∈ N (otherwise multiply again by 1_{K}). □

As a first application of these ergodic theorems consider the recurrent case (1) of the exchange process from Section 2. Here P(X_{n}^{0} ≤ y) = \frac{y}{y + n} implies

E(f(X_{n}^{0})) = \frac{1}{n} ∫_{0}^{∞} f(y) (\frac{y}{n} + 1)^{−2} dy for n ∈ N

and thus

E(f(X_{n}^{0})) / E(g(X_{n}^{0})) → ∫_{0}^{∞} f(y) dy / ∫_{0}^{∞} g(y) dy for f, g ∈ K(R_{+}) .

Since this convergence carries over to the corresponding quotients in (4.2), the invariant measure is simply the Lebesgue measure λ restricted to R_{+}. By (4.3) this implies that, regardless of the initial law, the process (X_{n}, n ≥ 0) is “ equidistributed ” on R_{+}, i.e.

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

for subintervals I_{k} of R_{+} of positive and finite length.

By means of (4.3) recurrence of a set B ∈ 𝔙(E) can be seen to be simply equivalent to μ(B) > 0. More generally, extending (2.1) and (2.4) and replacing sets by functions, the following dichotomy holds:

(4.4) Theorem Let the system (E, ν) be recurrent with invariant measure μ. Then for 0 ≤ f ∈ V(E) and any x ∈ E

(a) μf > 0 implies

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

(b) μf = 0 implies

∑_{n≥0} f(X_{n}^{x}) < ∞ a.s. and ∑_{n≥0} E(f(X_{n}^{x})) < ∞ .

Proof. (a) Choose K ∈ 𝔎^{↓}(E) with ∫_{K} f dμ > 0 and apply (4.3) to the functions 1_{K}f and 1_{K} in V(E). This yields the first (and second) assertion.

(b) Use the invariance of μ to obtain

∫ _{E} ( ∑_{n≥0} E(f(X_{n}^{x}))) μ(dx) = ∑_{n≥0} μP^{n}f = 0 .

Therefore the integrand vanishes μ−almost everywhere and thus by (1.5a) is finite for all x ∈ E. This proves the second (and first) assertion. □

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

(1) If (E, ν) is recurrent, then for x ∈ supp μ the assertion

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

hence

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

holds, whenever G is an open neighborhood of x.

(2) If ν is transient, then for arbitrary x ∈ E the assertion

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

hence

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

holds, whenever K is a compact subset of E.

Clearly, under a total ordering the compact recurrent set in (2.5) can be required to be an interval. Now it is possible to extend this simplification to the general case:

(4.5) Theorem Let the system (E, ν) be recurrent. Then there exists y ∈ E such that K = [0, y] is recurrent.

Proof. Since (1.3) provides y ∈ E with invariant measure μ([0, y]) > 0, the assertion is an immediate consequence of (4.4a). □

Explicitly, this proves an irreducible system (E, ν) to be recurrent if and only if

∑_{n≥0} P(X_{n}^{0} ≤ y) = ∞ for some y ∈ E .

As another consequence of (4.4), a recurrent system can be shown to be irreducible and aperiodic in a very strong sense. The essential step concerns decreasing intervals:

(4.6) Lemma Let the system (E, ν) be recurrent with invariant measure μ. Then any y ∈ E with μ([0, y]) > 0 satisfies

P(X_{n}^{y} ≤ y) > 0 for almost all n ≥ 0 .

Proof. The Markov property and monotonicity imply that

D := {n ≥ 0 : P(X_{n}^{y} ≤ y) > 0}

is an additive semigroup. Therefore it is sufficient to prove d = 1 for the greatest common divisor d of D. Now the assumption d > 1 yields P(X_{nd+1}^{y} ≤ y) = 0 for all n ≥ 0 and thus by (1.5a)

∑_{n≥0} P(X_{nd+1}^{0} ≤ y) < ∞ .

But this leads to a contradiction, because the probabilities P(X_{n}^{0} ≤ y) decrease by (0.1) and sum up to infinity by (4.4a). □

It has to be added that under a total ordering μ([0, y]) > 0 in fact implies P(X_{n}^{y} ≤ y) > 0 for all n ≥ 0. Indeed: the assumption ν(h(y) > y) = 1 yields P(X_{n}^{y} > y) = 1 for all n ∈ N, while μ([0, y]) > 0 implies X_{n}^{y} ≤ y infinitely often with probability 1.

Now (4.6) can be considerably extended:

(4.7) Proposition Let the system (E, ν) be recurrent with invariant measure μ. Then for convex sets B ∈ 𝔅(E) with μ(B) > 0 and arbitrary initial law

P(X_{n} ∈ B) > 0 for almost all n ≥ 0 .

Proof. Fix first y ∈ E with μ([0, y]) > 0, as is justified by (1.3). Then apply (4.4a) and (4.1) to get k ∈ N such that

(1)  P(X_{k} ≤ y) > 0 .

Next, use (4.6) to obtain l ∈ N such that

(2)  P(X_{n}^{y} ≤ y) > 0 for n ≥ l .

Finally, apply (4.4a) to f = 1_{B} and (2.3) to A = {0, y} to find m ∈ N such that

(3)  P(X_{m}^{z} ∈ B for all z ≤ y) > 0 .

Combining (1) – (3) it follows easily that

P(X_{n}^{x} ∈ B) > 0 for n ≥ k + l + m .  □

5. The attractor. The following notation will be used in the sequel:

(5.1) Definition Let the system (E, ν) be recurrent with invariant measure μ. Then the closed set M := supp μ is called the “ attractor ” of (E, ν).

This terminology is readily justified:

(5.2) Theorem Let the system (E, ν) be recurrent with invariant measure μ. Then for arbitrary initial law the random set

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

equals the attractor M with probability 1.

Proof. According to (10.4) the second countable space E has a base consisting of convex open sets G_{k}, k ∈ N, which in addition may be assumed to be relatively compact (otherwise choose functions g_{l}, l ∈ N, according to (10.7) and take intersections with the sets {g_{l} > 0}). Then the inclusion M ⊂ L(ω) is obviously equivalent to

(1)  ∑_{n≥0} 1_{G_{k}}(X_{n}(ω)) = ∞ whenever G_{k} ∩ M ≠ ∅ ,

and it is easily checked that the inclusion L(ω) ⊂ M is equivalent to

(2)  ∑_{n≥0} 1_{G_{k}}(X_{n}(ω)) < ∞ whenever \overline{G}_{k} ∩ M = ∅ ,

where \overline{A} denotes the closure of a subset A of E. Now it follows from (1.5b) that X_{n} in (1) and (2) can be replaced by X_{n}^{0} without changing probabilities. Then (4.4) applies: the series in (1) diverges almost surely because of μ(G_{k}) > 0 for G_{k}∩M ≠ ∅, while the series in (2) converges almost surely because of μ(G_{k}) = 0 otherwise. □

The following properties of μ and M will be needed in the sequel:

(5.3) Proposition Let the system (E, ν) be recurrent with invariant measure μ and attractor M. Then for each x ∈ E there exists y ≥ x such that μ([x, y]) > 0 and M ∩ [x, y] ≠ ∅.

Proof. The interval [x, ·] is recurrent by (1.2a), hence satisfies μ([x, ·]) > 0 by (4.4b). Now (1.3) provides y ∈ E with μ([x, y]) > 0, which implies the second assertion due to μ(E \ M) = 0. □

The self-similarity of the attractor is a direct consequence of the topological assumptions. Since M need not be compact, however, it involves a passage to the closure:

(5.4) Proposition Let the system (E, ν) be recurrent with invariant measure μ. Then its attractor M satisfies

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

Proof. Since the spaces E and H[E] both are second countable, the product μ ⊗ ν is again a Radon mesure, and its support is given by M × N. In view of the continuity of the mapping φ : (x, h) ↦ h(x) the image of μ ⊗ ν under φ is easily checked to have as its support the closure of φ[M × N]. But this image equals μ, and thus the assertion is established. □

Now M can be characterized as is familiar from elementary models:

(5.5) Proposition Let the system (E, ν) be recurrent with invariant measure μ. Then its attractor M is the smallest nonempty set F ∈ 𝔉(E) satisfying the condition

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

or, equivalently, the condition

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

Proof. Since the mappings h ↦ h(x), x ∈ F, are continuous, the set of mappings h ∈ H[E] with h[F] ⊂ F is closed, and thus both conditions are clearly equivalent. Since, moreover, (5.4) shows that (2) is satisfied for F = M, it remains only to prove F ⊃ M for any nonempty set F ∈ 𝔉(E) satisfying (1). But this condition clearly continues to be satisfied, if ν is replaced by ν^{n}. 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) has with probability 1 all its limit points in F. Therefore the inclusion M ⊂ F is a consequence of (5.2). □

It is immediate from version (2) that the attractor depends on the distribution ν only through its support N.

Another application concerns the special case of a totally ordered state space. Here z := min M exists and by (5.5) satisfies h(z) ∈ M, hence h(z) ≥ z for all h ∈ N, while on the other hand by (5.2) any x ∈ E with h(x) ≥ x for all h ∈ N yields M ⊂ [x, ·], hence z ≥ x. Put together, this means

min M = max {x ∈ E : h(x) ≥ x for all h ∈ N } .

The term “ attractor ” does not mean that, regardless of the initial law, the event “ X_{n} ∈ M eventually ” has probability 1 – as can be seen, for instance, by the Cantor system (E, ν), where h_{i} [E \ M] ⊂ E \ M for i = 1, 2. In the present setting there is a substitute:

(5.6) Proposition If the system (E, ν) is recurrent with attractor M, then for arbitrary initial law

P(X_{n} ∈ M^{↑} for almost all n ≥ 0) = 1 .

Proof. To settle first the necessary measurability, note that M is σ−compact and thus M^{↑} = ⋃_{l∈N} Kl^{↑} with K_{l} ⊂ 𝔎(E), hence Kl^{↑} ∈ 𝔉(E) as follows by sequential compactness of E. Therefore M^{↑} is in fact of type F_{σ}. Since (5.5) implies

h[M^{↑}] ⊂ (h[M])^{↑} ⊂ M^{↑} for all h ∈ N ,

the process (X_{n}, n ≥ 0) stays in M^{↑} almost surely whenever entering this set. But by (1.2a) this entrance occurs with probability 1. □

For a final characterization of M let N^{∘} (\overline{N^{∘}}) denote the (closed) semigroup generated by N. Then the following criterion holds:

(5.7) Proposition Let the system (E, ν) be recurrent with invariant measure μ and denote by j the canonical injection of E into H[E]. Then the attractor M satisfies

(a) j(x) ∈ \overline{N^{∘}} ⇒ x ∈ M,

(b) j(x) ∈ \overline{N^{∘}} ⇐ x ∈ M, provided E is locally bounded (see (10.2)).

Proof. (a) By (5.5) the inclusion h[M] ⊂ M holds for h ∈ N, hence for h ∈ \overline{N^{∘}}. Thus the assertion follows from h[M] = {x} for h = j(x).

(b) By definition of the topology in H[E] it has to be shown that

{h ∈ N^{∘} : h[K] ⊂ G} ≠ ∅

for G ∈ 𝔊(E) containing x, hence satisfying μ(G) > 0, and arbitrary K ∈ 𝔎(E). Since E is locally bounded, K can be covered by a finite number of bounded open sets and thus K ⊂ A^{↓} for some finite subset A of E. Since, moreover, 0 can be included in A and G can be supposed to be convex by (10.4), it is sufficient to prove

{h ∈ N^{∘} : h(y) ∈ G for all y ∈ A} ≠ ∅ .

But translated into probabilities this is implied by

P(X_{n}^{y} ∈ G for all y ∈ A) > 0 for some n ∈ N ,

which follows indeed from (4.4a) and (2.3). □

Since a totally ordered space is locally bounded, in this case by (5.7) simply M = j^{−1}[ \overline{N^{∘}}]. Whether this equation extends to the general case, remains an open problem (see, however, (9.5)). It has to be mentioned here that the assumption j^{−1}[ \overline{N^{∘}}] ≠ ∅ is the starting point of the PhD thesis [7], which tries to carry over methods and results from [24] and [25] to random dynamical systems defined by contractions of a complete metric space.

6. Positive recurrence and null recurrence. As usual two kinds of recurrence have to be distinguished:

(6.1) Definition A recurrent system (E, ν) with invariant measure μ is called “ positive recurrent ” if μ is finite and “ null recurrent ” otherwise.

By (2.6) recurrence resp. transience of the system (E, ν^{n}) was seen to be independent of n ∈ N; this extends to the present classification, because the invariant measures for these systems agree.

Nontrivial and locally finite invariant measures may exist also in the transient case, as is shown at the end of Section 3. Therefore the following fact has to be confirmed explicitly:

(6.2) Proposition If the system (E, ν) is irreducible, positive recurrence is equivalent to the existence of a stationary distribution μ.

Proof. It is sufficient to deduce recurrence from the existence of μ. But choosing μ as initial law and K ∈ 𝔎(E) with μ(K) > 0, this is immediate from (2.6). □

Clearly, compactness of the state space always implies positive recurrence; more generally:

(6.3) Proposition An irreducible system (E, ν) is positive recurrent under each of the following conditions:

(a) ν(h[E] is relatively compact ) > 0,

(b) E contains a maximal element y.

Proof. (a) Choose a sequence of sets K_{l} ∈ 𝔎(E) such that each K ∈ 𝔎(E) is included in some K_{l}. Then the assumption concerns the union of the sets {h ∈ H[E] : h[E] ⊂ K_{l}}, which due to E and K_{l} being of type K_{σ} and G_{δ}, respectively, are again of type G_{δ}. This settles the question of measurability and ensures γ := ν(h[E] ⊂ K_{m}) > 0 for some m, which in view of the estimate

P(X_{n} ∈ K_{m}) ≥ P(H_{n}(x) ∈ K_{m} for all x ∈ E) = γ for all n ∈ N

proves the recurrence of (E, ν) by (2.6). Invariance of μ, moreover, implies

μ(K_{m}) = ∫ _{E} ν(h(x) ∈ K_{m}) μ(dx) ≥ γ μ(E)

and thus μ(E) < ∞ as asserted.

(b) The maximality of x and the monotonicity of h ∈ H[E] prove h(0) ≥ x and h[E] = {x} to be equivalent statements. Since ν^{n}(h(0) ≥ x) > 0 for some n ∈ N, by (a) the system (E, ν^{n}) – and thus also (E, ν) – is positive recurrent. □

It is a consequence of (6.3a) and (6.2) that the examples following (1.6) and (3.4) both are even positive recurrent counterexamples; on the other hand the latter one proves neither condition in (6.3) to be necessary for positive recurrence.

To obtain a necessary and sufficient condition ideas from queuing theory will be taken up that can be traced back to [28, 29] and lead to the following notion:

(6.4) Definition Let (H_{n}, n ∈ N) be the generating sequence of the system (E, ν). Then the random variables

Y_{n}^{x} := H_{1} ∘ … ∘ H_{n} (x) for n ≥ 0

define the “ dual process ” belonging to x ∈ E.

Clearly, the distributions of X_{n}^{x} and Y_{n}^{x} agree for fixed n, but (Y_{n}^{x}, n ≥ 0) need not be a Markov chain. Moreover, while the joint distribution of the process (X_{n}^{x}, n ≥ 0) depends only on the kernel P and not on the underlying distribution ν, this fails in general for the process (Y_{n}^{x}, n ≥ 0).

Considered in the compactification E^{∗} of E all dual processes converge to a common limit:

(6.5) Proposition If the system (E, ν) is irreducible, there is a random variable Y : Ω → E^{∗} such that

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

Proof. (a) Since the ordered topological space E^{∗} is sequentially compact and the sequence (Y_{n}^{0}(ω), n ≥ 0) is increasing, it converges in view of (10.4) to a limit Y (ω) for each ω. Since, moreover, E^{∗} is metrizable, the mapping Y : Ω → E^{∗} is measurable.

(b) Whenever Y (ω) = ∞, monotonicity yields Y_{n}^{x}(ω) → ∞ for all x, too. Otherwise choose a countable base of E , which may be assumed to consist of convex sets G_{k}, k ∈ N, by (10.4). Since (1.5a) – and thus (1.5b) – carries over from (X_{n}^{x}, n ≥ 0) to (Y_{n}^{x}, n ≥ 0), due to L(X_{n}^{x}) = L(Y_{n}^{x}), this implies

1_{G_{k}}(Y_{n}^{x}) − 1_{G_{k}}(Y_{n}^{0}) → 0 a.s. for all k ∈ N .

Therefore Y_{n}^{x}(ω) → Y (ω) for almost all ω satisfying Y (ω) ≠ ∞. □

The variable Y obeys a zero-one law characterizing the type of recurrence:

(6.6) Proposition Let the system (E, ν) be irreducible. Then, with Y being defined by (6.5),

(a) P(Y = ∞) = 0 if (E, ν) is positive recurrent,

(b) P(Y = ∞) = 1 otherwise.

Proof. (a) Let μ be the stationary distribution and choose functions g_{l}, l ∈ N, according to (10.7). Identifying g_{l} with its continuous extension to E^{∗} yields by (6.5b) and the invariance of μ

E(g_{l}(Y)) = lim_{n→∞} ∫ _{E} E(g_{l}(Y_{n}^{x})) μ(dx)
= lim_{n→∞} ∫ _{E} E(g_{l}(X_{n}^{x})) μ(dx)
= μ g_{l} for all l ∈ N .

The assertion follows by the passage l → ∞.

(b1) If (E, ν) is null recurrent and μ is the invariant measure, it follows similarly, now applying Fatou,

E(g_{l}(Y))μ(E) ≤ lim inf_{n→∞} ∫ _{E} E(g_{l}(Y_{n}^{x})) μ(dx)
= lim inf_{n→∞} ∫ _{E} E(g_{l}(X_{n}^{x})) μ(dx)
= μ g_{l} < ∞ for all l ∈ N .

In view of μ(E) = ∞ therefore E(g_{l}(Y)) = 0 for all l ∈ N, and the assertion follows again for l → ∞.

(b2) If finally (E, ν) is transient, then (6.5a) and (2.6) imply

P(Y ∈ K) = lim_{n→∞} P(Y_{n}^{0} ∈ K) = lim_{n→∞} P(X_{n}^{0} ∈ K) = 0 for K ∈ 𝔎^{↓}(E) ,

hence for all K ∈ 𝔎(E). □

For an application of this criterion consider once more the exchange process from Section 2, denoting again by F the relevant distribution function. The explicit representation

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

shows that

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

if and only if F (y) > 0 and the series ∑_{n≥0} (1 − F (y + n)) converges. Therefore the system (E, ν) is positive recurrent if and only if the variables U_{n}, n ∈ N, have a finite expectation (for extensions see [22]).

The following result is related to a “ contraction principle ” in [27]:

(6.7) Theorem If the system (E, ν) is positive recurrent, its stationary distribution is given by L(Y), with Y being defined by (6.5).

Proof. Application of (6.5) and (6.6) to the sequence (H_{n}, n > 1) yields a variable Y′ such that

H_{2} ∘ … ∘ H_{n} (0) ↑ Y′ and P(Y′ = ∞) = 0 .

Therefore, by the continuity of the mappings H_{1}(ω), the variables Y and H_{1}(Y′) agree almost surely. Since Y′ is independent of H_{1} and distributed as Y, this common law is indeed a stationary distribution. □

Finally, the criterion (2.6) for recurrence resp. transience can be completed:

(6.8) Theorem Let the system (E, ν) be recurrent. Then for arbitrary initial law the following conditions are equivalent:

(1)  (E, ν) is null recurrent ,
(2)  P(X_{n} ∈ K) → 0 for all K ∈ 𝔎(E) .

Proof. 1. In establishing that (1) implies (2) clearly K ∈ 𝔎^{↓}(E) may be assumed. By (6.5) this yields

P(X_{n} ∈ K) ≤ P(X_{n}^{0} ∈ K) = P(Y_{n}^{0} ∈ K) → P(Y ∈ K)

with P(Y ∈ K) = 0 by (6.6).

2. Conversely, let condition (2) be satisfied. Then the estimate

P(X_{n} ∈ K) ≥ P(X_{0} ≤ x) P(X_{n}^{x} ∈ K) for K ∈ 𝔎^{↓}(E) ,

with P(X_{0} ≤ x) > 0 for some x ∈ E by (1.3), yields

P(Y_{n}^{x} ∈ K) = P(X_{n}^{x} ∈ K) → 0 for K ∈ 𝔎^{↓}(E) ,

hence for all K ∈ 𝔎(E). Again by (6.5) and (6.6), this verifies (1). □

Now the results of (2.6) and (6.8) can be summarized as follows:

(E, ν) positive recurrent ⇔ P(X_{n}^{0} → ∞) = 0 and P(Y_{n}^{0} → ∞) = 0,

(E, ν) null recurrent ⇔ P(X_{n}^{0} → ∞) = 0 and P(Y_{n}^{0} → ∞) = 1,

(E, ν) transient ⇔ P(X_{n}^{0} → ∞) = 1 and P(Y_{n}^{0} → ∞) = 1.

7. Mean passage times. As stated in (1.2), the expected time to enter an increasing interval is finite in any case. In contrast, decreasing intervals can serve to distinguish positive from null recurrence. This relies on the well-known recurrence theorem of Kac, which is mostly stated under unnecessary restrictions. In the present setting the following dichotomy can be established:

(7.1) Theorem Let the system (E, ν) be recurrent with invariant measure μ. Then, with the notations T_{B} and T_{B}^{x} as defined in Section 1,

(a) E(T_{[0,x]}^{x}) < ∞, if (E, ν) is positive recurrent and μ([0, x]) > 0,

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

Proof. (a) Consider first the case that x is a maximal element of E. Then by (1.2b)

E(T_{[0,x]}^{x}) ≤ E(T_{{x}}^{x}) = E(T_{[x, ·]}^{x}) < ∞ .

Otherwise choose y ∈ [x, ·] \ {x} and m ∈ N such that P(X_{m}^{0} ≥ y) > 0. If (X_{n}, n ≥ 0) is the stationary process belonging to (E, ν), then it follows from μ([0, x]) > 0 by the Markov property and monotonicity that

P(X_{0} ≤ x, X_{m} ≥ y) > 0 .

If m is chosen minimal with respect to this inequality, then

P(X_{0} ≤ x, X_{l} ≤ x, X_{m} ≥ y) = 0 for 0 < l < m ,

because otherwise, due to the stationarity, m could be replaced by m − l. Therefore P(A) > 0 for the event

A := {X_{0} ≤ x, X_{l} ∉ [0, x] for 0 < l < m, X_{m} ≥ y} ⊂ {T_{[0,x]} > m} .

With the increasing function

g(z) := E(T_{[0,x]}^{z}) for z ∈ E

the recurrence theorem of Kac in its familiar version and the Markov property imply

P(T_{[0,x]} < ∞) = ∫ _{{X_{0}≤x}} T_{[0,x]} dP
≥ ∫ _{A} T_{[0,x]} dP
= ∫ _{A} (m + g(X_{m})) dP
≥ P(A) (m + g(x)) .

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

(b) The extended version of the recurrence theorem of Kac needed here concerns the infinite measure ϱ := μ ⊗ P ⊗ P ⊗ … on ⨂_{n≥0} 𝔅(E), which is shift invariant by the invariance of μ. Now the standard proof in the case of probability measures is easily checked to work as well for ϱ, resulting in

∫ _{B} E(T_{B}^{y}) μ(dy) = ∫ _{E} P(T_{B}^{y} < ∞) μ(dy) for all B ∈ 𝔅(E) .

In applying this equation to B = [0, x] it means no restriction to assume again μ([0, x]) > 0, because otherwise an application of (4.4b) to f = 1_{[0,x]} and the Markov property yield P(T_{[0,x]}^{x} = ∞) > 0. Under this assumption, now in view of (4.4a), P(T_{[0,x]}^{y} < ∞) = 1 for all y ∈ E and thus by monotonicity

E(T_{[0,x]}^{x}) μ([0, x]) ≥ ∫ _{[0,x]} E(T_{[0,x]}^{y}) μ(dy)
= ∫ _{E} P(T_{[0,x]}^{y} < ∞) μ(dy)
= μ(E)

with μ([0, x]) < ∞ = μ(E). □

It is trivial that assertion (b) extends to transient systems, because in this case again P(T_{[0,x]}^{x} = ∞) > 0.

The final result of this section requires a uniform version of (7.1a), not restricted to decreasing intervals:

(7.2) Proposition Let the system (E, ν) be positive recurrent with stationary distribution μ. Let moreover B ∈ 𝔅(E) be convex with μ(B) > 0 and y ∈ E be fixed. Then the stopping time

T := inf{n ∈ N : X_{n}^{x} ∈ B for 0 ≤ x ≤ y}

has a finite expectation.

Proof. Since B is recurrent by (4.4a), an application of (2.3) with A = {0, y} yields m ∈ N such that

ϑ := P(X_{m}^{x} ∈ B for 0 ≤ x ≤ y) > 0 .

Since the system (E, ν′) with ν′ = ν^{m} meets the assumptions as well and the corresponding stopping time T′ satisfies T ≤ m T′, the notation can be simplified by supposing m = 1. In view of (5.3), moreover, μ([0, y]) > 0 may be assumed in the sequel. Then the recursion

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

defines a sequence of stopping times with respect to (H_{n}, n ∈ N), which by (4.4a) may be assumed to be finite. By (7.1a) it follows as in the proof of (1.4) that

(1)  E(S_{k} − S_{k−1}) = E(T_{[0,y]}^{y}) < ∞ for k ∈ N .

Moreover, the events

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

by the convention m = 1 satisfy

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

By construction the variables 1_{A_{0}}, …, 1_{A_{k−1}}, S_{k+1} − S_{k} are independent for fixed k. Finally, the estimate

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

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

E(T) ≤ ϑ^{−1} E(T_{[0,y]}^{y}) + 1 < ∞ .  □

Now the familiar criterion for positive resp. null recurrence by mean passage times carries over from discrete Markov chain theory to the present setting in the following form:

(7.3) Theorem Let the system (E, ν) be recurrent with attractor M.

(a) If (E, ν) is positive recurrent and x ∈ M, then

E(T_{G}^{x}) < ∞ for all G ∈ 𝔊(E) with x ∈ G;

(b) if (E, ν) is null recurrent and x ∈ E arbitrary, then

E(T_{G}^{x}) = ∞ for some G ∈ 𝔊(E) with x ∈ G ,

provided E is locally bounded (see (10.2)).

Proof. (a) Since G by (10.4) may be assumed to be convex, this is a special case of (7.2).

(b) By the local boundedness there exist G_{0} ∈ 𝔊(E) and y ∈ E such that x ∈ G_{0} ⊂ [0, y], where y ≠ x may be assumed, because otherwise by (7.1b)

E(T_{G_{0}}^{x}) ≥ E(T_{[0.x]}^{x}) = ∞ .

But then G_{0} ∩ [y, ·] = ∅ may be assumed as well, because otherwise G_{0} can be decreased to G_{0} \ [y, ·]. Now let m ∈ N satisfy ϑ := P(X_{m}^{x} ≥ y) > 0. If m is chosen minimal, then

P(X_{l}^{x} = x, X_{m}^{x} ≥ y) ≤ P(X_{m−l}^{x} ≥ y) = 0 for 0 < l < m .

Therefore outer regularity of L(X_{l}^{x}) provides G_{l} ∈ 𝔊(E) with x ∈ G_{l} and

∑_{0<l<m} P(X_{l}^{x} ∈ G_{l}, X_{m}^{x} ≥ y) < ϑ .

Then x ∈ G := ⋂_{0≤l<m} G_{l} ∈ 𝔊(E) and P(A) > 0 for the event

A := {X_{l}^{x} ∉ G for 0 < l < m, X_{m}^{x} ≥ y} .

Since G_{0} ∩ [y, ·] = ∅ implies T_{G}^{x} > m on A, the Markov property and monotonicity, again by (7.1b), yield

E(T_{G}^{x}) ≥ P(A) (m + E(T_{[0,y]}^{y})) = ∞ .  □

As in the context of (5.7) it is an open problem, whether local boundedness is essential for assertion (b) (see, however, (9.5)). Moreover, assertion (b) extends again to transient systems, because in this case P(T_{G}^{x} = ∞) > 0 whenever G is relatively compact.

8. Further limit theorems. From the results of Section 6 it is easily derived that the distributions of X_{n}, n ≥ 0, converge in the positive recurrent case weakly to the stationary distribution (and otherwise vaguely to 0). Actually, the class of functions, for which convergence holds, is considerably larger:

(8.1) Proposition Let the system (E, ν) be positive recurrent with stationary distribution μ. Then, for arbitrary initial law μ_{0} and with μ_{n} := μ_{0} P^{n},

μ_{n}f → μf for all f ∈ R(E) .

Proof. Since f is bounded, application of (1.6) with initial variable 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 .  □

This result implies in particular that

P(X_{n} = x) → μ({x}) for all x ∈ E .

Under a total ordering this fact is easily seen to imply uniform convergence of the distribution functions F_{n}(y) := P(X_{n} ≤ y) to the limit F (y) := μ([0, y]). To extend this result to the general setting, an appropriate metric on M_{1}(E) is needed:

(8.2) Proposition The definition

d(μ_{1}, μ_{2}) := sup {|μ_{1}(B) − μ_{2}(B)| : B ∈ 𝔅^{↓}(E)}

yields a metric on M_{1}(E) with the following properties:

(a)  d(μ_{1}, μ_{2}) = sup {|μ_{1}f − μ_{2}f| : f ∈ B^{↓}(E) with 0 ≤ f ≤ 1} ,
(b)  d(μ_{n}, μ) → 0 implies μ_{n} →_{w} μ ,
(c)  the mapping μ ↦ μP is a contraction .

Proof. (a) This follows from μ_{i}f = ∫_{[0,1]} μ_{i}(f(x) > y) dy.

(b) By (a)

μ_{n}f → μf for f ∈ B^{↓}(E) with 0 ≤ f ≤ 1 ,

which implies convergence for f ∈ K_{0} and thus for f ∈ K(E) according to (10.6a). Besides μ_{n} →_{w} μ this proves d to be indeed a metric.

(c) By (a) this follows from μP f = ∫_{H[E]} μ(f ∘ h) ν(dh). □

An application of (10.3) to E^{∗} yields d(ε_{x}, ε_{y}) = 1 for x ≠ y, showing metric convergence in general to be much stronger than weak convergence. Using the notion of a “ splitting point ” (see z in the following proof), as introduced by Dubins/Freedman [13] for E = [0, 1] and extended by Bhattacharya/Majumdar [8, 9] to higher dimension, the weak convergence from (8.1) can be strengthened to metric convergence:

(8.3) Theorem If the system (E, ν) is positive recurrent with stationary distribution μ, then

d(μ_{0} P^{n}, μ) → 0 for all μ_{0} ∈ M_{1}(E) .

Proof. 1. Applying (1.3), choose z with μ([0, z]) > 0 and, applying (5.3), choose δ > 0 such that

μ([0, z]) ∧ μ([z, ·]) > δ .

Then, for given ε > 0 and with μ_{n} := μ_{0} P^{n}, there exists a finite subset A of E satisfying

μ(E \ A^{↓}) ≤ δ ε and μ_{n}(E \ A^{↓}) ≤ δ ε for all n ∈ N ,

as follows from (1.3) and (8.1), applied to f = 1_{A^{↓}}. Moreover, again by (8.1), there exists k ∈ N such that

P(X_{k}^{x} ≤ z for all x ∈ A^{↓}) ≥ δ and P(X_{k}^{0} ≥ z) ≥ δ ,

where the first inequality uses the fact that by (1.5a)

P({X_{n}^{0} ≤ z} \ ( ⋂_{x∈A^{↓}} {X_{n}^{x} ≤ z})) ≤ ∑_{x∈A} (P(X_{n}^{0} ≤ z) − P(X_{n}^{x} ≤ z)) → 0 .

Since the values d(μ_{n}, μ) = d(μ_{n−1}P, μP) by (8.2c) form a decreasing sequence, it is sufficient to prove d(μ_{kn}, μ) → 0. Therefore, passing from ν to ν^{k}, the notation can be simplified by assuming k = 1 in the sequel.

2. For arbitrary B ∈ 𝔅^{↓}(E) there are now two possibilities:

(1) In the case z ∈ B, i.e. [0, z] ⊂ B, consider

H_{∗} := {h ∈ H[E] : h[A^{↓}] ⊂ [0, z]} ,

satisfying A^{↓} ⊂ h^{−1}[B] ∈ 𝔅^{↓}(E) for h ∈ H_{∗}. Therefore

|μ_{n}(B) − μ(B)| ≤ ∫ _{H[E]} |μ_{n−1}(h^{−1}[B]) − μ(h^{−1}[B])| ν(dh)
≤ (1 − δ) d(μ_{n−1}, μ) + δ ε for all n ∈ N ,

because by the first part ν(H[E] \ H_{∗}) ≤ 1 − δ and on H_{∗} the integrand is bounded by δ ε.

(2) In the case z ∉ B, i.e. [z, ·] ⊂ E \ B, replace H_{∗} by

H^{∗} := {h ∈ H[E] : h(0) ≥ z} ,

satisfying h^{−1}[B] = ∅ for h ∈ H^{∗}. Then it follows similarly, in fact somewhat simpler, that

|μ_{n}(B) − μ(B)| ≤ (1 − δ) d(μ_{n−1}, μ) for all n ∈ N .

Combining both cases and putting γ := 1 − δ this yields

d(μ_{n}, μ) ≤ γ d(μ_{n−1}, μ) + δ ε

and thus by recursion

d(μ_{n}, μ) < γ^{n} d(μ_{0}, μ) + ε for all n ∈ N .

In view of γ < 1 and d ≤ 1 this proves the assertion. □

In case the state space is bounded (or at least of the form E = A^{↓} with A finite), the proof is easily checked to work with ε = 0, i.e. there is geometric convergence, which in addition is uniform in μ_{0}.

To conclude this section by a law of large numbers, ergodicity of the stationary version of the process (X_{n}, n ≥ 0) is essential. Actually, by means of the dual process from Section 6, a stronger result can be established:

(8.4) Proposition Let the system (E, ν) be positive recurrent with stationary distribution μ. Then the process (X_{n}, n ≥ 0) with initial law μ is mixing.

Proof. Extending H_{n}, n ∈ N, let H_{n}, n ∈ Z, be independent random variables with distribution ν. Then by (6.5) and (6.6)

X′_{n} := lim_{n≥m→−∞} H_{n} ∘ … ∘ H_{m} (0) ∈ E a.s. .

The continuity of the mappings H_{n}(ω) yields

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

Since X′_{0} is independent of (H_{n}, n ∈ N) and L(X′_{0}) = μ by (6.7), the processes (X_{n}, n ≥ 0) and (X′_{n}, n ≥ 0) have the same distribution, and thus it is sufficient to prove the assertion for (X′_{n}, n ≥ 0). To this end denote by σ and σ′ the shift in W := ∏_{n∈Z} H[E] and W′ := ∏_{n≥0} E^{∗}, respectively, and consider the mapping

τ : (h_{n}, n ∈ Z) ↦ ( lim_{n≥m→−∞} h_{n} ∘ … ∘ h_{m} (0), n ≥ 0)

from W to W′, which is easily checked to be measurable, due to the topological properties of E^{∗}. Then the mappings σ and σ′ are conjugate under τ, i.e. satisfy τ ∘ σ = σ′ ∘ τ. Therefore the mixing property of σ with respect to the product measure ⨂_{n∈Z} ν carries over to σ′ with respect to its image by τ. Since this obviously is the distribution of (X′_{n}, n ≥ 0), the assertion follows. □

To be complete, it has to be mentioned that in general the tail σ−field of (X_{n}, n ≥ 0), even under stationarity, need not be trivial. A counterexample is provided by the Cantor system, where X_{n−1} can be reconstructed from X_{n} with probability 1, and thus the tail σ−field of (X_{n}, n ≥ 0) coincides with the full σ−field generated by the process up to sets of probability 0.

Now a fairly general law of large numbers can be derived:

(8.5) Theorem Let the system (E, ν) be positive recurrent with stationary distribution μ. Then for arbitrary initial law

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

whenever f ∈ R(E) or f ∈ C(E).

Proof. If X_{0} is replaced by X′_{0} with L(X′_{0}) = μ, the resulting copy (X′_{n}, n ≥ 0) of (X_{n}, n ≥ 0) is ergodic by (8.4), hence satisfies

\frac{1}{n} ∑_{0≤m<n} f(X′_{m}) → μf a.s. for all bounded f ∈ 𝔅(E) .

(1) In the case f ∈ R(E) this convergence carries over to the process (X_{n}, n ≥ 0), because (1.6) implies f(X_{n}) − f(X′_{n}) → 0 almost surely.

(2) In the case f ∈ C(E) assume without restriction 0 ≤ f ≤ 1 and approximate f from below by functions from K(E). Since these functions by (10.6b) belong to R(E), they satisfy the assertion and thus

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

Repeating the argument for 1 − f proves the assertion. □

A further extension of (8.5) from continuous to semicontinuous functions fails in general, as can be seen, for instance, by the Cantor system (E, ν). Here, for fixed x ∈ E, there exists a countable subset B of E such that P(X_{n}^{x} ∈ B) = 1 for all n ≥ 0. Since the stationary distribution μ is nonatomic, this yields a set F ∈ 𝔉(E) with B ∩ F = ∅ and μ(F) > 0. Then the initial law ε_{x} and the function f = 1_{F} are suited for a counterexample.

9. Strictly order-preserving systems. Throughout Sections 1 – 8 the system (E, ν) has always been supposed to be irreducible. To see the crucial role of this assumption consider the example following (3.4). If in this case the state space is enlarged from [0, 1[ to [0, 1] (extending the mappings h_{i} continuously), the definition μ = ε_{1} yields another invariant measure. This observation suggests a restriction of the original state space:

(9.1) Definition For an arbitrary system (E, ν) the “ reduced state space ” is given by the subspace

Ê := {x ∈ E : P(X_{n}^{0} ≥ x) > 0 for some n ∈ N} .

If E is totally ordered, Ê is obviously an open or closed decreasing subset of E and thus again admissible in the sense of Section 0. Moreover, it makes sense to restrict the mappings h to Ê, because

(∗)  h[Ê] ⊂ Ê for ν−almost all h ∈ H[E] .

Indeed, fix x_{0} ∈ Ê with P(X_{n}^{0} ≥ x_{0}) > 0 and consider h_{0} ∈ H[E] with h_{0}(x_{0}) ∉ Ê. Then necessarily ν(h(x_{0}) ≥ h_{0}(x_{0})) = 0, because otherwise by independence

P(X_{n+1}^{0} ≥ h_{0}(x_{0})) ≥ P(X_{n}^{0} ≥ x_{0}) P(H_{n+1}(x_{0}) ≥ h_{0}(x_{0})) > 0 .

Therefore, with the notation

H(y) := {h ∈ H[E] : h(x_{0}) ≥ y} for y ∈ E ,

each h_{0} ∈ H[E] with h_{0}(x_{0}) ∉ Ê is contained in the union of all sets H(y) with ν(H(y)) = 0. Since the sets H(y) decrease for increasing y, this union can be replaced by a countable one, due to (E1), and thus is a ν−null set itself. Therefore h_{0}(x_{0}) ∈ Ê for ν−almost all h_{0} ∈ H[E] and, replacing x_{0} by a sequence (x_{k}, k ∈ N) with [0, x_{k}] ↑ Ê, this settles (∗).

As this consideration shows, to treat only irreducible systems means no real restriction under a total ordering. This, however, does not hold for a general state space, as the following examples show. Choose E = R_{+}^{2} and let ν be supported by constant mappings (resulting in independent variables X_{n}, n ≥ 0), taking their values in the totally disordered subset D := {x ∈ E : x_{1} + x_{2} = 1} only. If ν assigns positive mass to each constant in a dense subset of D, the reduced state space Ê is easily seen to be no longer locally compact. If on the other hand ν has no point masses at all, obviously

h[Ê] ∩ Ê = ∅ for ν−almost all h ∈ H[E] .

This observation is the motivation to investigate systems (E, ν) that are not necessarily irreducible but strictly order-preserving. Before introducing this notion the necessary measurability has to be settled:

(9.2) Proposition The subspace J [E] consisting of all mappings h ∈ H[E] such that

h(x_{1}) < h(x_{2}) whenever x_{1} < x_{2}

is of type G_{δ} (i.e. a Polish space).

Proof. Denote by S the open set of all pairs (x_{1}, x_{2}) with x_{1} < x_{2}. Since E is locally compact and second countable, it follows that

S = ⋃_{l∈N} (K_{1}^{l} × K_{2}^{l}) with K_{i}^{l} ∈ 𝔎(E) .

Therefore it is sufficient to prove

H_{l} := {h ∈ H[E] : h[K_{1}^{l}] × h[K_{2}^{l}] ⊂ S}

to be open for all l ∈ N. In view of h[K_{i}^{l}] ∈ 𝔎(E) a theorem of Wallace (see e.g. [16]) applies, i.e. h ∈ H_{l} is equivalent to the existence of sets G_{i} ∈ 𝔊(E) satisfying h[K_{i}^{l}] ⊂ G_{i} and G_{1} × G_{2} ⊂ S. Since the sets {h ∈ H[E] : h[K_{i}^{l}] ⊂ G_{i}} are open, the assertion is established, □

Now the central assumption for this section can be made precise:

(9.3) Definition The system (E, ν) is called “ strictly order-preserving ”, if the following two conditions are satisfied:

(a)  ν(J [E]) = 1 ,
(b)  ν^{n}(h(0) > 0) > 0 for some n ∈ N .

Clearly, condition (a) is of relevance only in conjunction with condition (b). To discuss briefly an important special case, consider generalized autoregressive

models on E = R_{+}^{d}, where ν is supported by affine maps h : x ↦ Ax + b. If A and b are composed of the (nonnegative) variables a_{ik} and b_{i}, respectively, then conditions (a) and (b) are satisfied as soon as

(a′)  P(a_{i1} + … + a_{id} > 0) = 1 for 1 ≤ i ≤ d ,
(b′)  P(b_{1} … b_{d} > 0) > 0 .

This example should be compared with the model in [4]. While the state space there is enlarged to E = R^{d}, only mappings h : x ↦ ax + b with strictly positive scalar factors a are admitted, imposing in addition strong moment conditions on the variables a and b.

The notions in (9.1) and (9.3) are related by the following facts:

(9.4) Lemma If the system (E, ν) is strictly order-preserving, then any x ∈ Ê satisfies

(a)  P(X_{n}^{0} > x) > 0 for some n ∈ N ,

(b)  x < y for some y ∈ Ê ,
(c)  h(x) ∈ Ê for all h ∈ N ∩ J [E] .

Proof. Since J [E] is stable under composition, ν(J [E]) = 1 implies ν^{k}(J [E]) = 1 for all k ∈ N. In the sequel denote the support of ν^{k} by N^{k} and its elements by h_{k}.

(a) By the assumptions on x and (E, ν) there are l ∈ N and m ∈ N such that

ν^{l}(h_{l}(0) ≥ x) > 0 and ν^{m}(h_{m}(0) > 0) > 0 .

With n = l + m and

J_{a} := {(h_{l}, h_{m}) : h_{l} ∘ h_{m} (0) > x}

this implies

ν^{n}(h_{n}(0) > x) = ν^{l} ⊗ ν^{m} (J_{a}) ≥ ν^{l} ⊗ ν^{m} (h_{l}(0) ≥ x, h_{m}(0) > 0) > 0 .

(b) By (a) there are h_{m}^{0} ∈ N^{m} with h_{m}^{0}(0) > 0 and h_{n}^{0} ∈ N^{n} ∩ J [E] with y := h_{n}^{0}(0) > x. Then h_{n}^{0} ∘ h_{m}^{0} (0) > y and thus

J_{b} := {(h_{n}, h_{m}) : h_{n} ∘ h_{m} (0) > y}

defines an open subset of H[E]×H[E] intersecting the support of ν^{n}⊗ν^{m}. Therefore

ν^{n+m}(h_{n+m}(0) > y) = ν^{n} ⊗ ν^{m} (J_{b}) > 0 ,

hence in particular y ∈ Ê.

(c) Choose h_{1}^{0} = h and h_{n}^{0} as in (b). Then h_{1}^{0} ∘ h_{n}^{0} (0) > h(x), and it follows as above, considering now

J_{c} := {(h_{1}, h_{n}) : h_{1} ∘ h_{n} (0) > h(x)} ,

that h(x) ∈ Ê. □

The crucial properties of the reduced state space follow readily:

(9.5) Proposition If the system (E, ν) is strictly order-preserving, then

(a)  Ê is locally compact ,
(b)  h[Ê] ⊂ Ê for ν−almost all h ∈ H[E] ,
(c)  Ê is locally bounded .

Proof. (a) Ê is a decreasing subset of E, hence by (9.4b) open in E and thus again locally compact.

(b) Since Ê is second countable and by (9.4b) covered by the family of open sets {x ∈ Ê : x < y}, y ∈ Ê, there are y_{k} ∈ Ê such that Ê = ⋃_{k∈N} [0, y_{k}]. Therefore h[Ê] ⊂ Ê if and only if h(y_{k}) ∈ Ê for all k ∈ N, as holds indeed by (9.4c) for all h ∈ N ∩ J [E].

(c) Local boundedness is immediate from (9.4b). □

Since the assumptions (E2) and (E3) clearly carry over from E to Ê, too, the reduced state space is again admissible in the sense of Section 0. Therefore the reduction of a strictly order-preserving system (E, ν) can be summarized as follows: Disregarding the ν−null set of mappings with h[Ê] ⊄ Ê, let ν̂ be the image of ν under the (continuous) mapping that assigns to h ∈ H[E] its restriction ĥ ∈ H[Ê]. Then the system (Ê, ν̂) is irreducible, and an associated process (X̂_{n}, n ≥ 0) behaves as (X_{n}, n ≥ 0), whenever the initial law is supported by Ê. By (9.5c), moreover, the results (5.7) and (7.3) on attractor and mean passage time simplify for the reduced system.

10. Order and topology. A set is called an ordered topological space (OTS), if its topology and (partial) order are compatible, i.e.

R := {(x_{1}, x_{2}) : x_{1} ≤ x_{2}} ∈ 𝔉(E × E) .

By symmetry this holds as well for the inverse ordering, hence the diagonal is a closed subset of E × E, and thus each OTS is a Hausdorff space. Moreover, each subspace with the induced ordering and each product space with the product ordering yield again an OTS.

The simplest example of an OTS is provided by a totally ordered set E, the topology being generated by the “ open intervals ” E \[x, ·] and E \[ · , x]. While the meaning of a strict inequality “ x_{1} < x_{2} ” is clear in this case, more care is necessary in the general case:

(10.1) Definition Let E be an arbitrary OTS. Then “ x_{1} < x_{2} ” means existence of disjoint neighborhoods G_{i} of x_{i} such that

(a)  G_{1} ∈ 𝔊^{↓}(E) and G_{2} ∈ 𝔊^{↑}(E) ,
(b)  y_{1} ≤ y_{2} for y_{i} ∈ G_{i} .

This implies in particular

S := {(x_{1}, x_{2}) : x_{1} < x_{2}} ∈ 𝔊(E × E)

and the transitivity law

x_{1} < x_{3} whenever x_{1} < x_{2} ≤ x_{3} or x_{1} ≤ x_{2} < x_{3} .

Another notion combining order and topology appears in Sections 5 and 7:

(10.2) Definition Let E be an arbitrary OTS. Then E is “ locally bounded ”, if any x ∈ E has a bounded neighborhood.

While this condition is clearly satisfied under a total ordering, it may well be violated in the general case: consider, for instance, the subspace

E = {(x_{1}, x_{2}) ∈ R_{+}^{2} : x_{1} + x_{2} ≤ 1} .

The deepest result on order and topology used here is the analogue of Tietze’s extension theorem, due to Nachbin:

(10.3) Proposition Let E be a compact OTS and E_{0} be a closed subspace. Then any function f_{0} ∈ C^{↑}(E_{0}) can be extended to a function f ∈ C^{↑}(E).

Proof. See [33, Corollary 3.4 and Theorem 3.6]. □

The following fact is an immediate consequence of (10.3) and therefore supplied with its simple proof:

(10.4) Proposition Let E be (a subspace of) a compact OTS. Then the class of convex open sets is a base of the topology.

Proof. Assume E to be compact and apply (10.3) to E_{0} = {x_{1}, x_{2}} with x_{1} ≠ x_{2} to see that C^{↑}(E) separates the points of E. Therefore C^{↑}(E) induces a Hausdorff topology in E coarser than the underlying compact topology, and thus both topologies agree. Since sets {x ∈ E : a < f(x) < b} are convex for f ∈ C^{↑}(E) and a, b ∈ R and convexity is stable under intersection, the assertion follows. □

The next result is crucial for the introduction of admissible state spaces E in Section 0:

(10.5) Proposition Let E be a locally compact OTS and E^{∗} = E ∪ {∞} its Alexandrov compactification. Then, defining x ≤ ∞ for all x ∈ E makes E^{∗} again an OTS if and only if

(∗)  K^{↓} ∈ 𝔎(E) for all K ∈ 𝔎(E) .

Proof. 1. Let first E^{∗} be an OTS and consider a set K ∈ 𝔎(E) ⊂ 𝔎(E^{∗}). Then denoting by R^{∗} the order graph of E^{∗} and by p_{1} the projection of E^{∗} × E^{∗} onto its first factor leads to

K^{↓} = p_{1}[ (E^{∗} × K) ∩ R^{∗}] ∈ 𝔎(E^{∗}) ,

where ∞ ∉ K^{↓} and thus indeed K^{↓} ∈ 𝔎(E).

2. Let conversely condition (∗) be satisfied and R^{∗} be defined as above. Then, to prove (E^{∗} × E^{∗}) \ R^{∗} to be open, choose any (x_{1}, x_{2}) in this set.

(1) If {x_{1}, x_{2}} ⊂ E, then there are G_{i} ∈ 𝔊(E) ⊂ 𝔊(E^{∗}) such that

x_{i} ∈ G_{i} and G_{1} × G_{2} ⊂ (E × E) \ R ⊂ (E^{∗} × E^{∗}) \ R^{∗} .

(2) If {x_{1}, x_{2}} ⊄ E, then x_{1} = ∞ and x_{2} ∈ E. Since E is locally compact, there is a neighborhood G_{2} ∈ 𝔊(E) ⊂ 𝔊(E^{∗}) of x_{2} with closure K ∈ 𝔎(E). By condition (∗), therefore, K^{↓} ∈ 𝔎(E) as well, and thus G_{1} := E^{∗} \ K^{↓} ∈ 𝔊(E^{∗}) is a neighborhood of x_{1}. Then it is easily checked that (G_{1} × G_{2}) ∩ R^{∗} = ∅. □

Now an appropriate version of Stone’s theorem can be established:

(10.6) Proposition Let E be a locally compact OTS satisfying condition (∗) of (10.5). Then

(a)  K_{0} := {f_{1} − f_{2} : 0 ≤ f_{i} ∈ K^{↓}(E)}

is a dense subspace of K(E) with respect to the uniform norm,

(b)  K(E) ⊂ R(E) .

Proof. Since E^{∗} according to (10.5) is a compact OTS, it follows as in the proof of (10.4) that

C_{0}^{∗} := {f_{1}^{∗} − f_{2}^{∗} : 0 ≤ f_{i}^{∗} ∈ C^{↓}(E^{∗})}

separates the points of E^{∗}. All further conditions in Stone’s theorem are obviously satisfied, and thus C_{0}^{∗} is dense in C(E^{∗}). Let now f ∈ K(E) be given and f^{∗} be its trivial extension to E^{∗}. Then there are nonnegative functions f_{ik}^{∗} ∈ C^{↓}(E^{∗}) with

∥f_{k}^{∗} − f^{∗}∥ → 0 for f_{k}^{∗} := f_{1k}^{∗} − f_{2k}^{∗} ,

where by adding suitable constants f_{ik}^{∗}(∞) = 0 can be achieved. The restriction of (f_{ik}^{∗} − 1/k)^{+} to E yields nonnegative functions f_{ik} ∈ C(E) such that

∥f_{k} − f∥ → 0 for f_{k} := f_{1k} − f_{2k} .

Since the support of f_{ik} is a subset of {f_{ik}^{∗} ≥ 1/k} and this set is compact in view of f_{ik}^{∗}(∞) = 0, the functions f_{ik} are in fact contained in K(E). This proves (a) and, due to K_{0} ⊂ V(E), also (b). □

The next result requires some countability:

(10.7) Proposition Let E be a locally compact and second countable OTS satisfying condition (∗) of (10.5). Then there are functions g_{l} ∈ K^{↓}(E) such that

(1)  0 ≤ g_{1} ≤ g_{2} ≤ … → 1 ,
(2)  each K ∈ K(E) is included in {g_{l} = 1} for some l .

Proof. By the topological properties of E there is a sequence of sets K_{l} ∈ 𝔎^{↓}(E) such that each K ∈ 𝔎(E) is included in some K_{l}. Since E^{∗} according to (10.5) is a compact OTS, (10.3) applies and yields functions f_{l}^{∗} ∈ C^{↓}(E^{∗}) with f_{l}^{∗}|Kl^{↓} = 1 and f_{l}^{∗}(∞) = −1. If f_{l} denotes the restriction of f_{l}^{∗} to E, the functions

g_{l} := (f_{1}^{+} ∨ … ∨ f_{l}^{+}) ∧ 1 for l ∈ N

meet all requirements. □

The final result concerns the classes V(E) and 𝔙(E) introduced in Section 0. Clearly, V(E) includes the linear space of all differences f_{1} − f_{2} with bounded functions f_{i} ∈ B^{↑}(E), and thus 𝔙(E) includes the algebra of all finite unions of sets B_{1} \ B_{2} with B_{i} ∈ 𝔅^{↑}(E). Conversely:

(10.8) Proposition Let E be a locally compact and second countable OTS with lower bound 0. If U(E) and 𝔘(E) denote the class of universally measurable functions on and subsets of E, respectively, then

(a) each f ∈ V(E) is a difference f_{1} − f_{2} with bounded functions 0 ≤ f_{i} ∈ U^{↑}(E),

(b) each B ∈ 𝔙(E) is a finite union of sets B_{1} \ B_{2} with B_{i} ∈ 𝔘^{↑}(E).

Proof. (a) Assume without restriction f(0) = 0. As under a total ordering f can then be represented as f = f^{+} − f^{−} with bounded increasing functions f^{σ} ≥ 0, σ ∈ {−, +}, defined by

f^{σ}(x) := sup { ∑_{k∈N} (f(x_{k+1}) − f(x_{k}))^{σ} : x_{1} ≤ x_{2} ≤ … ≤ x } .

To verify f^{σ} ∈ U(E), consider the Borel measurable function

g^{σ}(x_{1}, x_{2}, …; x) := 1_{{x_{1}≤x_{2}≤...≤x}} ∑_{k∈N} (f(x_{k+1}) − f(x_{k}))^{σ}

on the Suslin space E^{N} × E. Then the set of x ∈ E satisfying an inequality f^{σ}(x) > γ equals the projection of the set of (x_{1}, x_{2}, …; x) ∈ E^{N} × E satisfying g^{σ}(x_{1}, x_{2}, …; x) > γ onto the second factor and is therefore a Suslin, hence universally measurable, set for all γ ≥ 0.

(b) In the special case f = 1_{B} the functions f^{σ} are integer-valued. This yields the representation

B = ⋃_{k∈N} ({f^{+} ≥ k} \ {f^{−} ≥ k}) ,

where the right-hand side is in fact a finite union. □

It has to be mentioned that no null sets intervene under a total ordering, because in this case increasing functions are Borel measurable.

REFERENCES

[1] Alpuim, M., Athayde, E. (1990). On the stationary distribution of some extremal Markovian sequences. J. Appl. Prob. 27, 291–302.

[2] Arnold, L. (1998). Random dynamical systems. Springer, New York.

[3] Asmussen, S. (1987). Applied probability and queues. Wiley, New York.

[4] Babillot, M., Bougerol, P., Elie, L. (1997). The random difference equation X_{n} = A_{n}X_{n−1} +B_{n} in the critical case. Ann. Probab. 25, 478–493.

[5] Barnsley, M. (1993). Fractals everywhere, 2nd edition. Academic Press, London.

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

[7] Benda, M. (1998). Schwach kontraktive stochastische dynamische Systeme. PhD thesis, University of Munich.

[8] Bhattacharya, R., Majumdar, M. (1999). On a theorem of Dubins and Freedman. J. Theor. Prob. 1067–1087.

[9] Bhattacharya, R., Majumdar, M. (1999). Convergence to equilibrium of random dynamical systems generated by i. i. d. monotone maps, with applications to economics. Statist. Textbooks Monogr. 158, 713–741. Dekker, New York.

[10] Bougerol, P., Picard, N. (1992). Stationarity of GARCH processes and of some nonnegative time series. J. Econ. 52, 115–127.

[11] Brandt, A., Franken, P., Lisek, B. (1990). Stationary stochastic models. Wiley, New York.

[12] Diaconis, P., Freedman, D. (1999). Iterated random functions. SIAM Rev. 41, 45–76.

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

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

[15] Embrechts, P., Goldie, C. (1994). Perpetuities and random equations. Asymptotic statistics (Prague 1993), 75–86. Physica, Heidelberg.

[16] Engelking, R. (1989). General topology, 2nd edition. Polish Scientific Publishers, Warzawa.

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

[18] Glasserman, P., Yao, D. (1995). Stochastic vector difference equations with stationary coefficients. J. Appl. Prob. 32, 851–866.

[19] Goldie, C. (1991). Implicit renewal theory and tails of solutions of random equations. Ann. Appl. Probab. 1, 126–166.

[20] Goldie, C., Maller, R. (2000). Stability of perpetuities. Ann. Probab. 28, 1195–1218.

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

[22] Högnäs, G., Muhkerjea, A. (1995). Probability measures on semigroups. Plenum Press, London.

[23] Jarner, S., Tweedie, R. (2001). Locally contracting iterated functions and stability of Markov chains. J. Appl. Prob. 38, 494–507.

[24] Kellerer, H. (1992). Ergodic behaviour of affine recursions I, II, III. Preprints, University of Munich (http://www.mathematik.uni-muenchen.de/∼kellerer).

[25] Kellerer, H. (1995). Order-preserving random dynamical systems. Preprint, University of Munich (http://www.mathematik.uni-muenchen.de/∼kellerer).

[26] Kifer, Y. (1986). Ergodic theory of random transformations. Birkhäuser, Basel.

[27] Letac, G. (1986). A contraction principle for certain Markov chains and its applications. Contemp. Math. 50, 263–273.

[28] Lindley, D. (1952). The theory of a queue with a single server. Proc. Camb. Philos. Soc. 48, 277–289.

[29] Loynes, R. (1962). The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Philos. Soc. 58, 497–520.

[30] Lund, B., Meyn, P., Tweedie, R. (1996). Computable exponential convergence rates for stochastically ordered Markov processes. Ann. Appl. Probab. 6, 218–237.

[31] Mairesse, J. (1997). Products of irreducible random matrices in the (max,+) algebra. Adv. Appl. Prob. 29, 444–477.

[32] Meyn, P., Tweedie, R. (1993). Markov chains and stochastic stability. Springer, New York.

[33] Nachbin, L. (1965). Topology and order. Van Nostrand, Princeton.

[34] Rachev, S., Samorodnitsky, G. (1995). Limit laws for a stochastic process and random recursion arising in probability modelling. Adv. Appl. Prob. 27, 185–202.

[35] Rachev, S., Todorovic, P. (1990). On the rate of convergence of some functionals of a stochastic process. J. Appl. Prob. 27, 805–814.

[36] Revuz, D. (1984). Markov chains, 2nd edition. North-Holland, Amsterdam.

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

[38] Vervaat, W. (1979). On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables. Adv. Appl. Prob. 11, 750–783.

[39] von Weizsäcker, H. (1974). Zur Gleichwertigkeit zweier Arten der Randomisierung. Manuscr. Math. 11, 91–94.

[40] Yahav, J. (1975). On a fixed point theorem and its stochastic equivalent. J. Appl. Prob. 12, 605–611.