Deterministically driven random walks on a finite state space

Abstract

We introduce the concept of a deterministic walk. Confining our attention to the finite state case, we establish hypotheses that ensure that the deterministic walk is transitive, and show that this property is in some sense robust. We also establish conditions that ensure the existence of asymptotic occupation times.

Keywords:

• ergodic theory and dynamical systems
• probability theory
• zero-one laws
• statistical limit laws

1. Introduction

Our purpose is to provide a foundational background for the study of deterministically driven random walks on a finite state space. In particular, we are concerned to generalize properties of Markov chains to settings in which the dynamics governing the behaviour of the walk is deterministic, and where the Markov property does not necessarily hold.

We define the deterministic walk as follows.

Definition 1.1:

Let T be a measurable transformation of a probability space (X, m), and suppose that associated to each i ∈ S is a measurable function f_i: X → S. We call each f_i a transition function, and we call the collection (f_k)_{k ∈ S} an environment on S.

Define the skew-product transformation T_f: X × S → X × S by (1.1) Define the deterministic walk on S in the environment (f_k)_{k ∈ S} to be (1.2) where π₂(x, y) := y.

An important feature of the above is that random updates are highly dependent on the current position of the walk. While there is a considerable wealth of dynamical system literature devoted to the study of systems in which transformations are applied randomly to a common state space, these predominantly deal with the situation where random updates are state-independent. A classic example of such systems is that of a random transformation R of a probability space (Y, ν). Given a finite set of measurable transformations of a probability space (Y, ν), and an independent and identically distributed sequence (T_n)_{n ≥ 1} of random variables taking values in , the random transformation R of (Y, ν) is defined such that for all n ≥ 1, Rⁿ := T_n○⋅⋅⋅○T₁. An equivalent, deterministic, representation of R uses the skew-product T_f: Σ⁺ × X → Σ⁺ × X such that , where Σ := {1, … , K}, and σ: Σ⁺ → Σ⁺ is the fullshift. In particular, for all n ≥ 1, (1.3) The ergodic theory of such systems was studied extensively in [1]. Among the many areas in which the model given by Equation (1.3(1.3) ) (and generalizations thereof) plays an important role are the theory of products of random matrices (which goes back to the work of Furstenberg and Kesten [2]), and the theory of random iterated function systems (in which the properties of fractals generated by random applications of contractive maps to a complete metric space are studied – see [3,4] for early developments in this field). For a relatively recent study of position-dependent case, see [5].

While systems described by Equation (1.3(1.3) ) enjoy the Markov property, we are interested in understanding the asymptotic behaviour of deterministic walks that are non-Markov.

Focusing on the finite state case, we establish recurrence properties under relatively mild assumptions. Notably, no mixing assumptions are required on the underlying dynamics. We also note that while distortion properties play an important role in the infinite state case (see [6]), such assumptions are not required for establishing recurrence in the finite state case.

In Section 2, we formally introduce the central notions of recurrence, transience and transitivity of a deterministic walk, and motivate these ideas by considering simple examples. We then establish (in Theorem 2.8) conditions for which a deterministic walk on a finite state space is transitive, and show that this property is in some sense robust.

In Section 3, we establish (in Theorem 3.6) conditions under which a deterministic walk on a finite state space admits asymptotic occupation times.

2. Transitivity of a deterministic walk on a finite state space

The following properties of a deterministic walk are fundamental to the exposition of our main results.

Definition 2.1:

Given a deterministic walk on a state space S in an environment (f_k)_{k ∈ S}, we say that a state i ∈ S is recurrent, if We say that a state i is transient, if it is not recurrent.

We say that the deterministic walk is transitive on S, if for all i, j ∈ S,

Proposition 2.2:

If S consists of two states, m({x ∈ X: f_i(x) = i}) < 1 for each i ∈ S, and T is measure-preserving and ergodic, then the deterministic walk is transitive on S.

Proof:

Since m({x ∈ X: f_i(x) = i}) < 1 for each i ∈ S, and T is measure-preserving and ergodic, it follows from Birkhoff's ergodic theorem that m(∩^∞_{n = 0}T^{− n}{x ∈ X: f_i(x) = i}) = 0. Hence, for i, j ∈ S, m({x: U_{i, n}(x) = j for some n ≥ 1}) = 1.□

Example 2.3:

In light of Proposition 2.1, it might be hoped that if S is finite, T is measure-preserving and ergodic, and m({x ∈ X: f_i(x) = j}) > 0 for all i, j ∈ S, then (U_n)_{n ≥ 0} is necessarily transitive. As the following counter-example shows, this is not the case. Consider the deterministic walk on the state space S = {0, 1, 2} driven by the transformation T: [0, 1] → [0, 1], where Tx := 2x mod 1, and with transition functions f₀, f₁ and  f₂ given by and Defining , by inspection, we see that the skew-product T_f: [0, 1] × S → [0, 1] × S decomposes the product state space β × S into two closed communication classes given by and .

Since the first communication class does not project onto the whole fibre S (in particular, the state 0 is not represented in this class), it follows that the deterministic walk is not transitive on S. In fact, it is easy to show that T_f induces a Markov chain on the state space β × S (with respect to the product measure Lebesgue × counting measure), and it follows that any walk started in the second communication class necessarily visits all three states infinitely often.

Definition 2.4:

Recall that a non-singular transformation T of a measure space (X, m) is said to be Markov, with a measurable Markov partition β of X, if

(1)	for all a ∈ β, T(a) is the union of elements of β,
(2)	T|a: a → T(a) is a bijection.

Given a Markov map T with Markov partition β, for all n ≥ 1 and all sequences a₀, … , a_{n − 1} ∈ β, we call the set [a₀, …, a_{n − 1}] ≔ ∩^{n − 1}_{j = 0}T^{− j}a_j a cylinder set of rank n or an n-cylinder.

For a given cylinder set a, we let |a| denote its rank.

We denote by β_n the collection of all n-cylinders.

We say that a cylinder set a is admissible, if m(a) > 0.

We introduce concepts for Markov maps that are analogous to the related concepts for Markov chains.

Definition 2.5:

Let T be a Markov transformation of a measure space (X, m) with Markov partition β. Given a, b ∈ β, we say that a communicates with b, if Given a, b ∈ β, we say that a and b intercommunicate, if a communicates with b and b communicates with a.

Given a ∈ β, we define the communication class of a to be the set of all b ∈ β with which it intercommunicates. (We observe that intercommunication is an equivalence relation.)

We say that a communication class is closed, if for all and all b ∈ β, a communicates with b, only if b communicates with a. (When β is finite, the existence of closed communication classes is automatic.)

We say that β is irreducible, if β is itself a communication class under T.

2.1. Standing hypotheses for the deterministic walk

We assume that a deterministic walk on a finite state space S is driven by a Markov transformation T of a probability space (X, m), with Markov partition β. In proving the main result of this section (Theorem 2.8), it is convenient to assume that transition functions are constant on elements of β, but as we observe later, this assumption is not entirely necessary.

Definition 2.6:

Define the probability measure .

The following proposition is an easy consequence of the standing hypotheses. (The routine details are written out in [7, Proposition 4.1].)

Define .

Proposition 2.7:

The skew-product T_f: X × S → X × S is a Markov transformation of the probability space (X × S, μ) with Markov partition .

Theorem 2.8:

Suppose that the base map T is measure-preserving and ergodic with finite Markov partition β. Then, the deterministic walk is transitive on S, if and only if every closed communication class in projects onto the whole of S.

Proof:

By Proposition 2.7, T_f: X × S → X × S is a Markov map with Markov partition . We observe that the ‘only if’ direction of the proof is trivial, in that if there exists a closed communication class that does not project onto the whole of S, then, clearly, the deterministic walk cannot be transitive. In proving the ‘if’ part of the result, we in fact prove something stronger:

(1)	Tf is transitive on closed communication classes in .
(2)	If a partition element does not lie in a closed communication class, then .

Since S and β are finite, so is , and it follows from (1) and (2) that with probability 1, an orbit under the skew-product dynamics must eventually end up in a closed communication class on which the orbit is transitive thereafter. Hence, the deterministic walk is transitive on S provided that every closed communication class projects onto the whole of S.

Proof of (1): Since T is Markov with Markov partition β, and the environment of transition functions (f_i)_{i ∈ S} are constant on elements of β, it follows that for all n ≥ 1, every admissible n-cylinder x := [x₀, … , x_{n − 1}], and all r₀ ∈ S, there is a unique itinerary on S: such that for i = 0, … , n − 2. We thus define Fix such that both lie in the same closed communication class . Let (2.1) be enumerations of all elements in whose β-coordinates are a and b, respectively. Since T is measure-preserving and ergodic, such collections are non-empty. We show that if we start in the communication class , then we must eventually visit b × {k}.

Since b × {i₁}, … , b × {i_n} all lie in the closed communication class , then, for each s = 1, … , n, there exists a cylinder w(i_s) of the form [x₁, x₂, … , b] such that (2.2) and [b, w(i_s)] is admissible (where in an abuse of notation we have written [b, w(i_s)] as shorthand for [b, x₁, x₂, … , b]). Equation (2.2(2.2) ) says that if the skew-product visits the set [b, w(i_s)] × {i_s}, then it must eventually visit the partition element b × {k}.

Since , there exists an admissible cylinder E₁ of the form [a, … , b] such that For r = 1, … , l − 1, we may inductively define admissible cylinders (2.3) For each r = 1, … , l, the cylinder E_r is of the form [a, … , b]. Thus, t(E_r, j_{r + 1}) is the S-coordinate at time |E_r| − 1 of every point in E_r × {j_{r + 1}}. Hence, every point in E_r × {j_{r + 1}} visits the partition element b × {t(E_r, j_{r + 1})} at time |E_r| − 1. It follows by construction that every point in the set E_{r + 1} × {j_{r + 1}} as defined in Equation (2.3(2.3) ) will visit the partition element b × {k} at time |E_{r + 1}| − 1.

Since m(E_l) > 0, it follows from Birkhoff's ergodic theorem that the base dynamics must eventually visit E_l. Since we are in the closed communication class , and since E_l ⊂ a, it follows that when the base dynamics visit the set E_l, the deterministic walk visits one of the states j₁, … , j_l. However, since E_l ⊂ E_{l − 1} ⊂ ⋅⋅⋅ ⊂ E₁, it follows that we must eventually visit the partition element b × {k}. This completes the proof of (1).

Proof of (2): Fix a × {i} lying in a communication class that is not closed, and let a × {i₁}, … , a × {i_l} be all the other partition elements in whose β-coordinate is a. Fix with which a × {i} communicates, but which does not communicate with a × {i}. Let A denote the set of partition elements that intercommunicate with a × {i} whose β-coordinate is b. Also, let A′ denote the set of partition elements whose β-coordinate is b, with which a × {i} communicates, but that do not communicate with a × {i}. Clearly, b × {k} ∈ A′.

By a similar argument to that given in the proof of part (1), for all b × {j} ∈ A, there exists a cylinder w(j) = [x₁, x₂, … , b] such that b × {t([b, w(j)], j)} ∈ A′.

Since a × {i} communicates with b × {k}, there exists an admissible cylinder E₀ of the form [a, … , b], such that For r = 0, … , l − 1, we may inductively define admissible cylinders (2.4) Let a × {s₁}, … , a × {s_t} be the set of all partition elements in whose β-coordinate is a, and with which a × {i} communicates, but which do not communicate with a × {i}.

Assuming that the skew-product dynamics start in a × {i}, then by Birkhoff's ergodic theorem, the base dynamics must (with probability 1) eventually make a first visit to the set E_l ⊂ a, at which point, the deterministic walk must be in one of the states i, i₁, … , i_l, s₁, … , s_t. If it is one of the s_i (for i = 1, … , t), then we cannot return to a × {i} by assumption. If, instead, it is in one of the states i, i₀, … , i_l, then, since E_l ⊆ E_{l − 1} ⊆ ⋅⋅⋅ ⊆ E₀, by the same argument as in part (1), it must either eventually visit the state b × {k} or some other element of the set A′. By definition, it cannot return from any of these partition elements to the partition element a × {i}. This completes the proof of (2).□

2.2. Robustness of transitivity

We call a set A ⊂ X transitive if for all i ∈ S and all x ∈ A, the orbit of the associated deterministic walk (U_{i, n}(x))^∞_{n = 0} visits every state in S at least once. Under the hypotheses of Theorem 2.8, it is immediate that if the deterministic walk is transitive on the state space S, then there must exist a transitive cylinder set a of positive measure. Any perturbation (f′_i)_{i ∈ S} of the environment (f_i)_{i ∈ S} of transition functions that preserves the existence of a transitive positive measure subset a′ ⊂ a will, by Birkhoff's ergodic theorem, preserve the transitivity of the deterministic walk. Therefore, we may say that the transitivity of the deterministic walk on a finite fibre is robust to perturbations of the environment. It follows that the hypothesis that transition functions are constant on elements of the Markov partition is not a necessary condition for the deterministic walk to be transitive on a finite state space.

3. Asymptotic occupation times for a deterministic walk on a finite state space

In this section, we continue to assume that the standing hypotheses hold and we establish conditions for the existence of asymptotic occupation times of a deterministic walk on a finite state space.

Definition 3.1:

Let T: X → X be a Markov transformation of a probability space (X, m), with Markov partition β. By the non-singularity of T, for all n ≥ 1 and all a ∈ β_n, we may define the Radon–Nikodym derivative such that for every measurable set B, .

We say that T has the strong distortion property, with distortion constant D ≥ 1, if for all n ≥ 1 and for all a ∈ β_n, and for a.e. x, y ∈ Tⁿa, .

Example 3.2:

We call a C² piecewise uniformly expanding Markov transformation T: [0, 1] → [0, 1] of the probability space ([0, 1], Lebesgue), an Adler transformation if (1) it has Markov partition β consisting of intervals, such that for all a ∈ β, T_|a is strictly monotonic and extends to a C² function on , (2) T′(x) ≠ 0 for all x ∈ [0, 1] and (3) . It can be shown that Adler transformations have the strong distortion property (see [8]).

The following proposition is an easy consequence of the standing hypotheses. (The routine details are written out in [7, Proposition 4.3].)

Proposition 3.3:

Suppose that the map T has the strong distortion property. Then, the skew-product T_f: X × S → X × S has the strong distortion property with respect to the measure μ.

Definition 3.4:

We say that a Markov transformation T of probability space (X, m), with Markov partition β, has finite images, if .

The following result combines Lemma 4.4.1 and Theorem 4.6.3 in [9]. (We note that [9] uses the term topologically transitive instead of irreducible.)

Proposition 3.5:

Let T be an irreducible Markov transformation of a probability space (X, m), with Markov partition β, satisfying strong distortion and finite images. Then, there exists an invariant and ergodic probability measure m′ equivalent to m.

We may now state the main result of this section.

Theorem 3.6:

Suppose that the state space S is finite and that the transformation T is a Markov map, with Markov partition β, that has strong distortion and finite images. Also,suppose that is irreducible under T_f. Then, there exists a distribution (π_i)_{i ∈ S} such that for all i, j ∈ S, (3.1)

Proof:

Since T has finite images and since S is finite, it follows that T_f also has finite images.

By Proposition 3.3, T_f has the strong distortion property with respect to μ.

By assumption, is irreducible under T_f, and it follows from Proposition 3.5 that T_f has an invariant and ergodic probability measure μ′ equivalent to μ. Thus, if for each i ∈ S, we define π_i := μ′(X × {i}), it follows from Birkhoff's ergodic theorem that (3.2) Equation (3.1(3.1) ) now follows from Equation (3.2(3.2) ).□

4. Concluding remarks

It is natural to consider how Theorem 2.8 might generalize to (1) situations where the Markov partition β is infinite and (2) situations where the base map T is non-Markov.

It follows from results presented in [6] that generalizing Theorem 2.8 to the situation where the Markov partition is infinite requires much stronger assumptions relating to the distortion properties of T and the combinatorial properties of the skew-product T_f. We refer the reader to Theorem 4.8 of [6] for further details.

Generalizing our main results to the non-Markov case entails identifying conditions under which the ergodic components of the skew-product T_f project onto the whole of S. In the absence of a Markov structure, alternative methods to the combinatoric arguments used above are required. A natural starting point for results in this direction would be to identify conditions under which the skew-product T_f admits an invariant and ergodic measure ν that is equivalent to μ, thus establishing both the transitivity of the walk and the existence of asymptotic occupation times.

Acknowledgements

I am indebted to Ian Melbourne for his advice during the development of this research.

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

The study was funded by the ESRC International Centre for Lifecourse Studies in Society and Health [award number RES-596-28-0001], [award number ES/J019119/1].