Introduction to Markov Chains

Witold Bednorz

Chapter 1

Definition of a Markov Chain

1.1 Stochastic Process

A Markov chain is a collection of random variables X = (X_{n})_{n∈T}, where T is a countable time-set. It is customary to write T as ℤ_{+} := {0, 1, 2, ...}, and we will do this henceforth. We require that each X_{i} takes values in (X , B(X)) (some measurable space which we call state space for X). There are three different types of state space:

1. The state space X is called countable if X is discrete with a finite or countable number of elements, and with B(X) the σ-field of all subsets of X.

2. The state space X is called general if it is equipped with a countably generated σ-field B(X).

3. The state space X is called topological if it is equipped with a locally compact, separable, metrizable topology with B(X) as the Borel σ-field.

Whenever we consider the Markov chain as an entity we regard values of the whole chain X itself as lying in the sequence or path space formed by a countable product Ω = X^{∞} = ∏_{i=0}^{∞} X_{i} where each X_{i} is a copy of X equipped with a copy of B(X). To make the definition precise (so that X_{i} is a random variable) we define a σ-field F as the smallest that contains B(X_{i}) in projection (i.e. we require that projections on each coordinate are measurable). Finally, for each x ∈ X we there will be a measure P_{x} such that the probability of the event {X ∈ A} is well defined for any A ∈ F; the initial condition requires of course that P_{x}(X_{0} = x) = 1. The triple (Ω, F, P_{x}) thus defines a stochastic process, since Ω = {ω_{0}, ω_{1}, ... : ω_{i} ∈ X_{i}} has the product structure to enable the projections ω_{n} at time n to be well defined realizations of the random variables X_{n}. Heuristically the critical aspect of a Markov process, as opposed to any other set of random variables, is that it is forgetful of all but its most immediate past. The precise meaning of this requirement for the evolution of Markov chain in time, is that the future of the process is independent of the past given only its present value.

1.2 Markov Chain on Countable Space

Definition 1 The process X = (X_{0}, X_{1}, ...) taking values in (Ω, F, P) is a Markov chain if for every n, and any sequence of states {x_{0}, x_{1}, x_{2}, ..., x_{n}},

P_{μ}(X_{0} = x_{0}, X_{1} = x_{1}, ..., X_{n} = x_{n}) = μ(x_{0})P_{x_{0}}(X_{1} = x_{1})...P_{x_{n−1}}(X_{1} = x_{n})  (1.1)

The probability measure μ is called the initial distribution of the chain. The process X is a time homogeneous Markov chain if the probabilities P_{x_{j}}(X_{1} = x_{j+1}) depend on the values x_{j}, x_{j+1} and are independent of the time points j.

If X is a time homogeneous Markov chain, we write

P (x, y) := P_{x}(X_{1} = y);

then the definition (1.1) can be rewritten

P_{μ}(X_{0} = x_{0}, X_{1} = x_{1}, ..., X_{n} = x_{n}) = μ(x_{0})P (x_{0}, x_{1})P (x_{1}, x_{2})...P (x_{n−1}, x_{n}).  (1.2)

or equivalently in terms of the conditional probabilities of the process X,

P_{μ}(X_{n+1} = x_{n+1}|X_{n} = x_{n}, ..., X_{0} = x_{0}) = P (x_{n}, x_{n+1}).

In applications we almost always define P_{x_{0}} for a fixed x_{0} by defining the one step transition probabilities for the process and building the overall distribution using (1.2). This is done by using the Transition Probability matrix.

Definition 2 The matrix P = {P (x, y), x, y ∈ X } is called a Markov transition matrix if

P (x, y) ⩾ 0, ∑_{z∈X} P (x, z) = 1, x, y ∈ X  (1.3)

We define the usual matrix iterates P^{n} = {P^{n}(x, y), x, y ∈ X } by setting P^{0} = Id, the identity matrix and then taking inductively

P^{n}(x, y) = ∑_{y∈X} P (x, y)P^{n−1}(y, z).

Theorem 1 If X is countable, and

μ = {μ(x), x ∈ X }, P = {P (x, y), x, y ∈ X}

are an initial measure on X and a Markov transition matrix satisfying (1.3) then there exists a Markov chain X on (Ω, F) with probability law P_{μ} satisfying

P_{μ}(X_{n+1} = y|X_{n} = x, ..., X_{0} = x_{0}) = P (x, y).

1.3 General State space Definition

We let X be a general set and B(X) denote a countably generated σ-field on X: when X is topological, then B(X) will be taken as the Borel σ-field, but otherwise it may be arbitrary.

Definition 3 If P = {P (x, A), x ∈ X , A ∈ B(X)} is such that 1. for each A ∈ B(X), P (·, A) is a non negative measurable function on X

2. for each x ∈ X, P (x, ·) is a probability measure on B(X)

then we call P a transition probability or Markov transition function.

To extend the definition from the countable space case to the general one we first define a finite sequence {X_{0}, X_{1}, ..., X_{n}} of random variables on the product space X^{n+1} = ∏_{i=0}^{n} X_{i} equipped with the product σ-field F_{n} generated by B(X_{i}). For any measurable sets A_{i} ⊂ X_{i} we develop the set function P_{x}^{n}(·) on X^{n+1} by setting, for a fixed point x ∈ X and for the ’cylinder sets’ A_{1} × ... × A_{n}

P_{x}^{1}(A_{1}) = P (x, A_{1}),
P_{x}^{2}(A_{1} × A_{2}) = ∫_{A_{1}} P (x, dy_{1})P (y_{1}, A_{2}),  ...
P_{x}^{n}(A_{1} × ... × A_{n}) = ∫_{A_{1}} P (x, dy_{1}) ∫_{A_{2}} P (y_{1}, dy_{2})...P (y_{n−1}, A_{n}).

These are well-defined by the this procedure for increasing n, we find

Theorem 2 For any initial measure μ on B(X), and any transition probability kernel P = {P (x, A), x ∈ X , A ∈ B(X)}, there exists a stochastic process X = {X_{0}, X_{1}, ...} on Ω = ∏_{i=0}^{∞} measurable with respect to F (generated by B(X_{i})) and a probability measure P_{μ} on F such that P_{μ}(B) is the probability of the event {X ∈ B} for B ∈ F, and for measurable A_{i} ⊂ X_{i}, i = 0, ..., n and any n

P_{μ}(X_{0} ∈ A_{0}, X_{1} ∈ A_{1}, ..., X_{n} ∈ A_{n}) = ∫_{A_{0}} ... ∫_{A_{n}} μ(dy_{0})P (y_{0}, dy_{1})...P (y_{n−1}, A_{n}).  (1.4)

Definition 4 The stochastic process X defined on (Ω, F) is called a time-homogeneous Markov chain with transition probability kernel P (x, A) and initial distribution μ if the finite dimensional distributions of X satisfy (1.4).

As on countable spaces the n-step transition probability kernel is defined iteratively. We set P^{0}(x, A) − δ_{x}(A), the Dirac measure defined by

δ_{x}(A) = \{ \begin{matrix}1 & x ∈ A \\ 0 & x ∉ A, \end{matrix}

and for n ⩾ 1, we define inductively

P^{n}(x, A) = ∫_{X} P (x, dy)P^{n−1}(y, A), x ∈ X , A ∈ B(X),

We write P^{n} for the n-step transition probability kernel {P^{n}(x, A), x ∈ X , A ∈ B(X)}, note that P^{n} is defined analogously to the n-step transition probability matrix for the countable space case.

Theorem 3 Chapman-Kolmogorov equations. For any m with 0 ⩽ m ⩽ n,

P^{n}(x, A) = ∫_{X} P^{m}(x, dy)P^{n−m}(y, A), x ∈ X , A ∈ B(X).  (1.5)

We interpret (1.5) as saying that, as X moves from x into A is n steps, at any intermediate time m it must take some value y ∈ X and that being a Markov chain it forgets the past at that time m and moves the succeeding (n − m) steps with the law appropriate to starting afresh at y. We can write equation (1.5) alternatively as

P_{x}(X_{n} ∈ A) = ∫_{X} P_{x}(X_{m} ∈ dy)P_{y}(X_{n−m}).

Exactly as the one-step transition probability kernel describes a chain X, the m-step kernel satisfies the definition of a transition kernel, and thus defines a Markov chain X^{m} = {X_{n}^{m}} with transition probabilities

P_{x}(x_{n}^{m} ∈ A) = P^{nm}(x, A).  (1.6)

Definition 5 The chain X^{m} with transition law (1.6) is called the m-skeleton of the chain X. The resolvent K_{a} is defined for 0 < ε < 1 by

K_{ε}(x, A) = (1 − ε) ∑_{i=0}^{∞} ε^{i}P^{i}(x, A), x ∈ X, A ∈ B(X).

The Markov chain with transition function K_{ε} is called the K_{ε}-chain.

1.4 Semigroup

In the general case the kernel P^{n} operates on quite different entities from the left and the right. As an operator P^{n} acts on both bounded measurable functions f on X and on σ-finite measures μ on B(X) via

P^{n}f(x) = ∫_{X} P^{n}(x, dy)f(y), μP^{n}(A) = ∫_{X} μ(dx)P^{n}(x, A),

and we shall use the notation P^{n}f, μP^{n} to denote these operations. We shall also write

P^{n}(x, f) := ∫_{X} P^{n}(x, dy)f(f) := δ_{x}P^{n}f

if it is notationally convenient. In general, the functional notation is more compact: for example we can rewrite the Chapman-Kolmogorov equations as

P^{m+n} = P^{n}P^{m}, m, n ∈ ℤ_{+}.

On many occasions, though where we feel that the argument is more transparent when written in full form we shall revert to the more detailed presentation.

1.5 Some basic properties

Proposition 1 If X is a Markov chain on (Ω, F), with initial measure μ, and h : Ω → ℝ is bounded and measurable, then

E_{μ}(h(X_{n+1}, X_{n+2}, ...)|X_{0}, ..., X_{n}; X_{n} = x) = E_{x}h(X_{1}, X_{2}, ...).

The formulation of the Markov concept is made much simpler if we develop more systematic notation for the information encompassed in the past of the process, and if we introduce the shift operator on the space Ω. For a given initial distribution, define the σ-field

F_{n}^{X} := σ(X_{0}, ..., X_{n}) ⊂ B(X^{n+1}).

which is the smallest σ-field for which the random variable {X_{0}, ..., X_{n}} is measurable. In many cases, F_{n}^{X} will coincide with B(X^{n}), although this depends in particular on the initial measure μ chosen for a particular chain. the shift operator θ is defined to be the mapping on Ω defined by

θ({x_{0}, x_{1}, ...}) = {x_{1}, x_{2}, ...}.

We write θ^{k} for the k-th iterate of the mapping θ, defined inductively by

θ^{1} = θ, θ^{k+1} = θ · θ^{k}, k ⩾ 1.

The shifts θ^{k} define operators on random variables H on (Ω, F, P_{μ}) by

(θ^{k}H)(ω) = H · θ^{k}(ω).

It is obvious that X_{n} · θ^{k}(ω) = X_{n+k}. Hence if the random variable H is of the form H = h(X_{0}, X_{1}, ...) for a measurable function h on the sequence Ω then

θ^{k}H = h(X_{k}, X_{k+1}, ...).

Since the expectation E_{x}H is a measurable function on X, it follows that E_{X_{n}} is a random variable on (Ω, F, P) for any initial distribution. With this notation the equation

E_{μ}(θ^{n}H|F_{n}^{X}) = E_{X_{n}}H, a.s. P_{μ}

valid for any bounded measurable h and fixed n ∈ ℤ_{+}, describes the the time homogeneous Markov property in a succinct way. It is not always the case that F_{n}^{X} is complete (contains every set of P_{μ}-measure zero). For any initial measure μ we say that an event A occurs P_{μ}-a.s. to indicate that A^{c} is a set contained in an element of F_{n}^{X} which is of P_{μ}-measure zero. If A occurs P_{x}-a.s. for all x ∈ X then we write that A occurs P_{∗}-a.s.

Definition 6 For any set A ∈ B(X) the occupation time η_{A} is the number of visits by X to A after times zero and is given by

η_{A} := ∑_{n=1}^{∞} 1_{{X_{n}∈A}}.

For any set A ∈ B(X), the variables

τ_{A} := min{n ⩾ 1 : X_{n} ∈ A},
σ_{A} := min{n ⩾ 0 : X_{n} ∈ A}

are called first return and first hitting times on A respectively.

We also refer to the kernel U defined as

U(x, A) := ∑_{n=1}^{∞} P^{n}(x, A) = E_{x}η_{A},

which maps X × B(X) to ℝ ∪ {∞}, and the return time probabilities

L(x, A) := P_{x}(τ_{A} < ∞) = P_{x}(X ever enters A).

A function ζ : Ω ∈ ℤ_{+} ∪ {∞} is a stopping time for X if for any initial distribution μ the event {ζ = n} ∈ F_{n}^{X} for all n ∈ ℤ_{+}.

Proposition 2 For any A ∈ B(X), the variables τ_{A} and σ_{A} are stopping times for X.

Proposition 3 For all x ∈ A, A ∈ B(X)

P_{x}(τ_{A} = 1) = P (x, A),

and inductively for n > 1

P_{x}(τ_{A} = n) = ∫_{A^{c}} P (x, dy)P_{y}(τ_{A} = n−1) = ∫_{A^{c}} P (x, dy_{1}) ∫_{A^{c}} P (y_{1}, dy_{2})... ∫_{A^{c}} P (y_{n−2}, dy_{n−1})P (y_{n−1}, A).

For all x ∈ X, a ∈ B(X)

P_{x}(σ_{A} = 0) = 1_{A}(x)

and for n ⩾ 1, x ∈ A^{c}

P_{x}(σ_{A} = n) = P_{x}(τ_{A} = n).

The simple Markov property (1.5) holds for any bounded measurable h and fixed n ∈ ℤ_{+}. We now extend (1.5) to stopping times. If ζ is an arbitrary stopping time, then the fact that our time-set is ℤ_{+} enables us to define the random variable X_{ζ} = X_{n} on the event {ζ = n}. For a stopping time ζ the property which tells us that the future evolution of X after the stopping time depends only on the value X_{ζ}, rather then on any other past values, is called the Strong Markov Property. To describe this formally, we need to define the σ-field

F_{ζ}^{X} := {A ∈ F : {ζ = n} ∩ A ∈ F_{n}^{X}, n ∈ ℤ_{+}},

which describes events which happen up to time ζ. For a stopping time ζ and a random variable H = h(X_{0}, X_{1}, ...) the shift θ^{ζ} is defined as

θ^{ζ} = h(X_{ζ}, X_{ζ+1}, ...),

on the set {ζ < ∞}. The required extension of (1.5) is then

Definition 7 We say that X has the Strong Markov Property if for any initial distribution μ, any real-valued bounded measurable function h on Ω, and any stopping time ζ,

E_{μ}(θ^{ζ}H|F_{ζ}^{X}) = E_{X_{ζ}}H a.s. P_{μ}

on the set {ζ < ∞}.

Proposition 4 For a Markov chain X with discrete time parameter, the Strong Markov Property always holds.

Irreducibility

2.1 Communicating classes and irreducibility

The idea of a Markov chain X reaching sets or points is much simplified when X is countable and the behavior of the chain is governed by a transition probability matrix P = P (x, y), x, y ∈ X. There are then number of essential equivalent ways of defining the operation of communication between states. The simplest is to say that state x leads to state y which we write as x → y, if L(x, y) > 0, and that two distinct states x and y in X when L(x, y) > 0 and L(y, x) > 0. By convention we also define x → x. The relation x ↔ y is often defined equivalently by requiring that there exists n(x, y) ⩾ 0 and m(y, x) ⩾ 0 such that P^{n}(x, y) > 0, and P^{m}(y, x) > 0 i.e. ∑_{n=0}^{∞} P^{n}(x, y) > 0 and ∑_{n=0}^{∞} P^{n}(y, x) > 0.

Proposition 5 The relation ↔ is an equivalence relation, and so the equivalence classes C(x) = {y : x ↔ y} cover X, with x ∈ C(x).

Definition 8 If C(x) = X for some x, then we say that X is irreducible. We say C(x) is absorbing if P (y, C(x)) = 1 for all y ∈ C(x).

When states do not all communicate, then although each state in C(x) communicates with every other state in C(x), it is possible that there are states y ∈ C(x)^{c} such that x → y. This happens if and only if C(x) is not absorbing. Suppose that X is not irreducible for X. If we reorder that states according to the equivalence classes defined by the communication operation, an if we further order the classes with absorbing classes coming first, then we have a decomposition of P such as

X = (∑_{x∈I} C(x)) ∪ D,

where I is the set of indicators of each different absorbing class.

Proposition 6 Suppose that C := C(x) is an absorbing communicating class for some x ∈ X. Let P_{C} denote the matrix P restricted to the states in C. Then there exists an irreducible Markov chain X_{C} whose state space is restricted to C and whose transition matrix is given by P_{C}.

2.2 ψ-Irreducibility

Definition 9 We call X φ-irreducible if there exists a measure φ on B(X) such that, whenever φ(A) > 0, we have L(x, A) > 0 for all x ∈ X. Proposition 7 The following are equivalent formulation of φ-irreducibility

1. for all x ∈ X, whenever φ(A) > 0, U(x, A) > 0;

2. for all x ∈ X, whenever φ(A) > 0, there exists some n > 0, possibly depending on both A and x such that P^{n}(x, A) > 0;

3. for all x ∈ X, whenever φ(A) > 0 then K_{1/2}(x, A) > 0. Proposition 8 If X is φ-irreducible for some measure φ, then there exists a probability measure ψ on B(X) such that

1. X is ψ-irreducible

2. for any other measure ψ′, the chain X is φ′-irreducible if and only if ψ ≻ φ′;

3. if ψ(A) = 0, then ψ({y : L(y, A) > 0}) = 0;

4. the probability measure ψ is equivalent to

ψ′(A) := ∫_{X} φ′(dy)K_{1/2}(y, A),

for any finite irreducible measure φ′. Definition 10 1. The Markov chain is called ψ-irreducible if it is φ-irreducible for some φ and the

measure ψ is a maximal irreducibility measure satisfying conditions of Proposition 8.

2. We write

B_{+}(X) := {A ∈ B(X) : ψ(A) > 0}

for the sets of positive ψ-measure; the equivalence of maximal irreducibility measures means that B_{+} is uniquely defined.

3. We call a set A ∈ B(X), full if ψ(A^{c}) = 0.

4. We call a set A ∈ B(X) absorbing if P (x, A) = 1, for x ∈ A. Proposition 9 Suppose that X is ψ=irreducible. Then

1. every absorbing set is full,

2. every full contains a non-empty, absorbing set. If a set C is absorbing and with there is a measure ψ for which

ψ(B) > 0 ⇒ L(x, B) > 0, x ∈ C

then we will call C an absorbing ψ-irreducible set. Proposition 10 Suppose that A is an absorbing set. Let P_{A} denote the kernel P restricted to the states in A. Then there exists a Markov chain X_{A} whose state space is A and whose transition matrix is given by P_{A}. Moreover, if X is ψ-irreducible then X_{A} is ψ-irreducible.

2.3 Accessible Sets

Definition 11 We say that a set B ∈ B(X) is accessible from another set A ∈ B(X) if L(x, B) > 0 for every x ∈ A; We say that a set B ∈ B(X) is uniformly accessible from another set A ∈ B(X) if there exists a δ > 0 such that

inf_{x∈A} L(x, B) ⩾ δ;  (2.1)

and when (2.1) holds we write A ↦ B

Let us define taboo probabilities

P_{A}^{n}(x, B) = P_{x}(X_{n} ∈ B, τ_{A} ⩾ n)

and

U_{A}(x, B) = ∑_{n=1}^{∞} P^{n}(x, B).

Lemma 1 If A ↦ B and B ↦ C then A ↦ C.

Definition 12 The set Ā := {x ∈ X : L(x, A) > 0} is the set of points from which A is accessible. The set Ā := {x ∈ X : ∑_{n=1}^{m} P^{n}(x, A) ⩾ m^{−1}}. The set A^{0} := {x ∈ X : L(x, A) = 0} = Ā^{c} is the set of points from which A is not accessible.

Lemma 2 The set Ā = ⋃_{m} Ā(m), and for each m we have Ā(m) ↦ A.

Pseudo Atoms

3.1 Minorization Condition

Definition 13 A set α ∈ B(X) is called an atom for X if there exists measure ν on B(X) such that

P (x, A) = ν(A), x ∈ α.

If X is ψ-irreducible and ψ(α) > 0 then α is called an accessible atom.

Proposition 11 Suppose there is an atom α in X such that ∑_{n} P^{n}(x, α) > 0 for all x ∈ X. Then α is an accessible atom and X is ν-irreducible with ν = P (α, ·).

Proposition 12 If L(x, A) > 0 for some state x ∈ α, where α is an atom, then α ↦ A.

Definition 14 (Minorization Condition) For some δ > 0, some C ∈ B(X) and some probability measure ν with ν(C^{c}) = 0 and ν(C) = 1

P(x, A) ⩾ δ1_{C}(x)ν(A), A ∈ B(X), x ∈ X .  (3.1)

The concept of splitting can be described as follows. Instead of X we write X̄ = X × {0, 1}, where X_{0} = X × {0} and X_{1} = X × {1} are copies of X equipped with copies B(X_{0}), B(X_{1}) of B(X) We will write x_{i}, i = 0, 1 for elements of X̄, with x_{0} denoting members of the upper level X_{0} and x_{1} denoting members of the lower level X_{1}. In order to describe more easily the calculation associated with moving between the original an the split chain, we will also sometimes call X_{0} the copy of X and will say that A ∈ B(X) is a copy of the corresponding set A_{0} ⊂ X_{0}. If λ is any measure on B(X), then the next step in the construction is to split the measure λ^{∗} on B(X) trough

λ^{∗}(A_{0}) = (1 − δ)λ(A ∩ C) + λ(A ∩ C^{c}),  (3.2)
λ^{∗}(A_{1}) = δλ(A ∩ C),

where δ and C are the constant and the set in (3.1). Note that in this sense the splitting is dependent on the choice of the set C, and although in general the set chosen is not relevant, we will on occasion need to make explicit the set in (3.1) when we use the split chain.

Note that λ is the marginal measure induced by λ^{∗}, in the sense that for any A ∈ B(X) we have

λ^{∗}(A_{0} ∪ A_{1}) = λ(A).

In the case when A ⊂ C^{c}, we have λ^{∗}(A_{0}) = λ(A); only subsets of C are really effectively split by this construction. Now the third, and the most subtle step in the construction is to split the chain X to form a chain X̄ which lives on (X̄, B(X̄)). Define the split kernel P̄(x_{i}, A) for x_{i} ∈ X̄ and A ∈ B(X̄) by

P̄(x_{0}, ·) = P (x, ·)^{∗}, x_{0} ∈ X_{0}\C_{0};  (3.3)
P̄(x_{0}, ·) = (1 − δ)^{−1}(P (x, ·)^{∗} − δν^{∗}(·)), x_{0} ∈ C_{0}  (3.4)
P̄(x_{1}, ·) = ν^{∗}(·), x_{1} ∈ X_{1}.  (3.5)

where C, δ and ν are the set, the constant and the measure in the Minorization Condition. Outside C the chain {X̄_{n}} behaves just like {X_{n}}, moving on the top half X_{0} of the split chain space. Each time it arrives in C, it is split: with probability 1 − δ it remains in C_{0}, with probability δ it drops to C_{1}. We can think of this splitting of the chain as tossing a δ-weighted coin to decide which level to choose on each arrival in the set C where the split takes place. When the chain remains on the top level its next step has the modified law (3.4). That (3.4) is always nonnegative follows from (3.1). This is sole use of the Minorization Condition, although without it the chain cannot be defined. Note here the whole point of the construction the bottom level of X_{1} is an atom, with φ^{∗}(X_{1}) = δφ(C) > 0 whenever the chain X is φ-irreducible. By (3.2) we have P̄^{n}(x_{1}, X_{1}\X_{1}) = 0 for all n ⩾ 1 and all x_{1} ∈ X̄, so that the atom C_{1} ⊂ X_{1} is the only part of the bottom level which is reached with positive probability. We will use the notation ᾱ := C_{1} when we wish to emphasize the fact that all transition out of C_{1} are identical, so that C_{1} is an atom in X̄.

3.2 Connecting the Split and Original Chains

Theorem 4 The chain X is the marginal chain of {X̄_{n}}: that is for any initial distribution λ on B(X) and any A ∈ B(X),

∫_{X} P^{k}(x, A)λ(dx) = ∫X̄ P̄^{k}(y_{i}, A_{0} ∪ A_{1})λ^{∗}(dy_{i}).  (3.6)

The chain X is φ-irreducible if X̄ is φ^{∗}-irreducible and if X is φ-irreducible with φ(C) > 0 then X̄ is ν^{∗}-irreducible, and ᾱ is an accessible atom for the split chain.

Note that for any measure μ on B(X) we have μ^{∗}P̄ = (μP)^{∗} that is

∫X̄ μ(dx_{i})P (x_{i}, ·) = (∫_{X} μ(dx)P (x_{i}, ·))^{∗}.

Since it is only the marginal chain X which is really of interest, we will usually consider only sets of the form Ā = A_{0} ∪ A_{1}, where A ∈ B(X), and we will largely restrict ourselves to functions on X̄ of the form f̄(x_{i}) = f(x_{i}), where f is some function on X; that is f̄ is identical on the two copies of X. By (3.6) we have for any k, any initial distribution λ and any function f̄ identical on X_{0} and X_{1}

E_{λ}f(X_{k}) = Ēf̄(X̄_{k}).

To emphasize the identity we will henceforth denote f̄ by f and Ā by A in these special instances. The context should make clear whether A is a subset of X or X̄ and whether the domain of f is X or X̄.

3.3 Small Sets

Definition 15 A set C ∈ B(X) is called a small set if there exists an m > 0, and a non trivial measure ν_{m} on B(X), such that for all x ∈ C, B ∈ B(X),

P^{m}(x, B) ⩾ ν_{m}(B).  (3.7)

When (3.7) holds we say that C is ν_{m}-small.

Theorem 5 Suppose φ is a σ-finite measure on (X , B(X)). Suppose A is any set in B(X) with φ(A) > 0 such that

φ(B) > 0, B ⊂ A ⇒ ∑_{k=1}^{∞} P^{k}(x, B) > 0, x ∈ A.

Then for every n the function p^{n} defined in the decomposition

P^{n}(x)(x, B) = ∫_{B} p^{n}(x, y)φ(dy) + P_{⊥}(x, B),

can be chosen to be a measurable function on X × X, and there exists C ⊂ A, m > 1, and δ > 0 such that φ(C) > 0 and

p^{m}(x, y) > δ, x, y ∈ C.

Theorem 6 If X is ψ-irreducible, then for every A ∈ B^{+}(X), there exists m ⩾ 1 and a ν_{m}-small set C ⊂ A such that C ∈ B_{+}(X) and ν_{m}(C) > 0.

Theorem 7 If X is ψ-irreducible, then the Minorization Condition holds for some m-skeleton, and for every K_{ε}-chain, 0 < ε < 1.

Proposition 13 1. If C ∈ B(X) is ν_{m}-small, and for any x ∈ D we have P^{m}(x, C) ⩾ δ, then D is ν_{n+m}-small, where ν_{n+m} is a multiple of ν_{n}.

2. Suppose X is ψ-irreducible. Then there exists a countable collection of sets C_{i} of small sets in B(X) such that

X = ⋃_{i=0}^{∞} C_{i}

3. Suppose X is ψ-irreducible. If C ∈ B^{+}(X) is ν_{n}-small, then we may find M ∈ ℤ_{+} and a measure ν_{M} such that C is ν_{M}-small, and ν_{M}(C) > 0.

Cyclic Behavior

4.1 Cycles for a Countable Space Chain

We first discuss the question for a countable space X. Let α be a specific state in X, and write

d(α) = G.C.D{n ⩾ 1 : P^{n}(α, α) > 0}.

We call d(α) the period of α. We recall that C(α) = {y : α ↔ α}.

Proposition 14 Suppose α has period d(α): then for any y ∈ C(α), d(α) = d(y).

Proposition 15 Let X be an irreducible Markov chain on a countable space, and let d denote the common period of the states in X. Then there exists disjoint sets D_{1}, D_{2}, ..., D_{d} ⊂ X such that

X = ⋃_{i=1}^{d} D_{k},

and

P (x, D_{k+1}) = 1, x ∈ D_{k}, k = 0, ..., d − 1 ( mod d)

Definition 16 An irreducible chain on a countable space X is called

1. aperiodic, if d(x) = 1, x ∈ X;

2. strongly aperiodic, if P (x, x), for some x ∈ X.

Proposition 16 Suppose X is an irreducible chain on a countable space X, with period d and cyclic classes {D_{1}, ..., D_{d}}. Then for the Markov chain X_{d} = {X_{d}, X_{2d}, ...} with transition matrix P^{d}, each D_{i} is an irreducible absorbing set of aperiodic states.

4.2 Cycles for a General Space Chain

The existence of small sets enables us to show that, even on a general space, we still have a finite periodic breakup into cyclic sets for ψ-irreducible chains. Suppose that C is any ν_{M}-small set, and assume that ν_{M}(C) > 0, as we may without loss of generality by Proposition 13. To simplify the notation we will suppress the subscript on ν. Hence we have P^{M}(x, ·) > ν(·), x ∈ C, and ν(C) > 0, so that, when the chain starts in C, there is a positive probability that the chain will return to C at time M. Let

E_{C} = {n ⩾ 1 : the set C is ν_{n}-small, with ν_{n} = δ_{n}ν for somedelta_{n} > 0.}

Notice that for B ⊂ C, n, m ∈ E_{C} implies

P^{n+m}(x, B) ⩾ ∫_{C} P^{m}(x, dy)P^{n}(y, B) ⩾ [δ_{m}δ_{n}ν(C)]ν(B), x ∈ C,

so that E_{C} is closed under addition. Thus there is a natural period for the set C, given by the greatest common divisor of E_{C}.

Lemma 3 The set C is ν_{nd}-small for large enough n.

Theorem 8 Suppose X is a ψ-irreducible chain on X. Let C ∈ B^{+}(X) be a ν_{M}-small set and let d be the greatest common divisor of the set E_{C}. Then there exists disjoint sets D_{1}, ..., D_{d} ∈ B(X) (a d-cycle) such that

1. for x ∈ D_{i}, P (x, D_{i+1}) = 1, i = 0, ..., d − 1, ( mod d);

2. the set N = (⋃_{i=1}^{d} D_{i})^{c} is ψ-null.

The d-cycle {D_{i}} is maximal in the sense that for any other collection {d′, D′_{k}, k = 1, ..., d′} satisfying (8), (1), we have d′ dividing d; whilst if d = d′, then by reordering the indices if necessary D′_{i} = D_{i} ψ-a.s.

Definition 17 Suppose that X is an φ-irreducible Markov chain.

1. The largest d for which a d-cycle occurs for X is called the period of X.

2. When d = 1, the chain X is called aperiodic.

3. When there exists a ν_{1}-small set A, with ν_{1}(A) > 0, then the chain is called strongly aperiodic.

Proposition 17 1. If X is strongly aperiodic, then the Minorization Condition holds.

2. The resolvent K_{ε} chain is strongly aperiodic for all 0 < ε < 1.

3. If X is aperiodic then every skeleton is ψ-irreducible and aperiodic, and some m-skeleton is strongly aperiodic.

Proposition 18 Suppose X is a ψ-irreducible chain with period d and d-cycle {D_{i}, i = 1, ..., d}. Then each of the sets D_{i} is absorbing ψ-irreducible set for the chain X_{d} corresponding to the transition probability kernel P^{d}, and X_{d} on each D_{i} is aperiodic.

4.3 Petite sets

Let a = {a(n)} be a distribution on ℤ_{+}, and consider the Markov chain

K_{a}(x, A) := ∑_{n=0}^{∞} P^{n}(x, A)a(n), x ∈ X , A ∈ B(X).

It is obvious that K_{a} is a transition kernel, so that X_{a} is a well-defined by Theorem 2. We will call X_{a} the K_{a}-chain, with sampling distribution a. Probabistically, X_{a} has the interpretation of being the chain X sampled at times-points drawn successively according to the distribution a, or more accurately, at time-points of an independent renewal process with increment distribution a. There are two specific sampled chains which we have already invoked, and which will be used frequently in the sequel. If a = δ_{m} then the K_{δ_{m}}-chain is the m-skeleton with transition kernel P^{m}. If a_{ε}(n) = (1−ε)ε^{n}, n = 1, 2, ... then the kernel K_{a_{ε}} is the resolvent K_{ε}. The concept of sampled chains immediately enables to develop conditions under which one set is uniformly accessible form another. We say that a set B ∈ B(X) is uniformly accessible using a from another set A ∈ B(X) if there exists δ > 0 such that

inf_{x∈A} K_{a}(x, B) > δ  (4.1)

and when (4.1) holds we write A ↦^{a} B.

Lemma 4 If A ↦^{a} B for some distribution a then A ↦ B.

Lemma 5 1. If a and b are distributions on ℤ_{+} then the sampled chains with transitions laws K_{a} and K_{b} satisfy the generalized Chapman-Kolmogorov equations

K_{a∗b}(x, A) = ∫ K_{a}(x, dy)K_{b}(y, A).

2. If A ↦^{a} B and B ↦^{b} C, then A ↦^{a∗b} C.

3. If a is a distribution on ℤ_{+} then the sampled chain with transition law K_{a} satisfies the relation

U(x, A) ⩾ ∫ U(x, dy)K_{a}(y, A).

Definition 18 We will call a set C ∈ B(X) ε_{a}-petite if the sampled chain satisfies the bound

K_{a}(x, B) ⩾ ν_{a}(B),

for all x ∈ C, B ∈ B(X), where ν_{a} is a non trivial measure on B(X).

Proposition 19 If C ∈ B(X) is ν_{m}-small then C is ν_{δ_{m}}-petite.

Proposition 20 1. If A ∈ B(X) is ν_{a}-petite, and D ↦^{b} A then D is ν_{b∗a}-petite, where ν_{b∗a} can be chosen as a multiple of ν_{a}.

2. If X is ψ-irreducible and if A ∈ B^{+}(X) is ν_{a}-petite, then ν_{a} is an irreducibility measure for X.

Proposition 21 Suppose X is ψ-irreducible.

1. If A is ν_{a}-petite, then there exists a sampling measure b such that A is also ψ_{b}-petite where ψ_{b} is a maximal irreducibility measure.

2. The union of two petite sets is petite.

3. There exists a sampling measure c, an everywhere positive, measurable function s : X → ℝ, and a maximal irreducibility measure ψ_{c} such that

K_{c}(x, B) ⩾ s(x)ψ_{c}(B), x ∈ X , B ∈ B(X).

Thus there is an increasing sequence {C_{i}} of ψ_{c}-petite sets, all with the same sampling distribution c and minorizing measure equivalent to ψ, with ⋃ C_{i} = X.

Proposition 22 Suppose that X is ψ-irreducible and C is ν_{a}-petite.

1. Without loss of generality we can take a to be either a uniform sampling distribution a_{m}(i) = 1/m, 1 ⩽ i ⩽ m, or a to be the geometric sampling distribution a_{ε}. In either case, there is a finite mean sampling time

m_{a} = ∑_{i} ia(i).

2. If X is strongly aperiodic then the set C_{0} ∪ C_{1} ⊂ X̄ corresponding to C is ν_{a}^{∗}-petite for the split chain X̄.

Theorem 9 If X is irreducible and aperiodic then every petite set is small.

Topology

5.1 Weak Feller Chains

Here we assume that X is equipped with a locally compact, separable, metrizable topology with B(X) as the Borel σ-field. Recall that a function h from X to ℝ is lower semicontinuous if

lim inf_{y→x} h(y) ⩾ h(x), x ∈ X ,

a typical, and frequently used, lower semicontinuous function is the indicator function 1_{G}(x) of an open set G ∈ B(X).

Definition 19 1. If P (·, G) is a lower semicontinuous function for any open set G ∈ B(X), then P is called a weak Feller chain.

2. If a is a sampling distribution and there exists a substochastic transition kernel T satisfying

K_{a}(x, A) ⩾ T (x, A), x ∈ X , A ∈ B(X),

where T (·, A) is a lower semicontinuous function for any A ∈ B(X), then T is called a continuous component of K_{a}.

3. If X is a Markov chain for which there exists a sampling measure a such that K_{a} possesses a continuous component T with T (x, X) > 0 for all x, then X is called T -chain.

Recall that the transition probability kernel P acts on bounded functions through the mapping

P h(x) = ∫ P (d, dy)h(y), , x ∈ X .

Suppose that X is a topological space and let us denote the class of bounded continuous function form X to ℝ by C(X).

Definition 20 The weak Feller property is frequently defined by requiring that the transition probability kernel P maps C(X) to C(X). If the transition probability kernel P maps all bounded measurable functions to C(X) then P (and also X) is called strong Feller.

Proposition 23 1. The transition kernel P 1_{G} is lower semicontinuous for every open set G ∈ B(X) if and only if P maps C(X) to C(X) and P maps all bounded measurable functions to C(X) if and only if the function P 1_{A} is lower semicontinuous for every set A ∈ B(X).

2. If the chain weak Feller then for any closed set C ⊂ X and any non-decreasing function m : ℤ_{+} → ℤ_{+} the function E_{x}(m(τ_{C})) is lower semicontinuous in x. Hence for any closed set C ⊂ X, r > 1 and n ∈ ℤ_{+} the functions

P_{x}(τ_{C} ⩾ n), E_{x}(τ_{C}), and E_{x}r^{τ_{C}}

are lower semicontinuous.

3. If the chain is weak Feller then for any open set G ⊂ X, the function P_{x}(τ_{G} ⩽ n) and hence also the functions K_{a}(x, G) and L(x, G) are lower semicontinuous.

5.2 Strong Feller Chains

Definition 21 1. A point x ∈ X is called reachable if for every open set G ∈ B(X) containing x

∑_{n} P^{n}(y, G) > 0, y ∈ X .

2. The chain X is called open set irreducible if every point is reachable.

Lemma 6 If X is ψ-irreducible then x^{∗} is reachable if and only if x^{∗} ∈ supp(ψ).

Proposition 24 If X is a strong Feller chain, and X contains one reachable point x^{∗}, then X is ψ=irreducible, with ψ(·) = P (x^{∗}, ·).

Proposition 25 If X is an open set irreducible strong Feller chain, then X is a ψ-irreducible chain.

5.3 T -chains

Proposition 26 If X is a T -chain, and X contains one reachable point x^{∗}, then X is ψ-irreducible, with ψ = T (x^{∗}, ·).

Proposition 27 If X is an open set irreducible T -chain, then X is a ψ-irreducible T -chain.

Proposition 28 If an open ν_{a}-petite set A exists, then K_{a} possesses a continuous component non trivial on all A.

Proposition 29 Suppose that for each x ∈ X there exists a probability distribution a_{x} on ℤ_{+} such that K_{a_{x}} possesses a continuous component T_{x} which is non trivial at x. Then X is a T -chain.

Theorem 10 If every compact set is petite, then X is T -chain. Conversely, if X is a ψ-irreducible T -chain then every compact set is petite, and consequently if X is an open set irreducible T -chain then every compact set is petite.

Proposition 30 If X is a ψ-irreducible T -chain, then there is a sampling distribution b, an everywhere strictly positive, continuous function s′ : X → ℝ, and a maximal irreducibility measure ψ_{b} such that

K_{b}(x, a) ⩾ s′(x)ψ_{b}(B), x ∈ X , B ∈ B(X).

Lemma 7 If X is a ψ-irreducible Feller chain, then the closure of every petite set is petite.

Proposition 31 Suppose that X is ψ-irreducible. Then all compact subsets of X are petite if either:

1. X has the Feller property and open ψ-positive petite set exists; or

2. X has the Feller property and supp(ψ) has non-empty interior.

Theorem 11 If a ψ-irreducible chain X is weak Feller and if supp(ψ) has nonempty interior then X is a T -chain.

5.4 e-Chains

One possible way to think of Markov chain is that the transition function P gives rise to a deterministic map from M the space of probability measures on B(X), to itself, and we can construct on this basis a dynamical system (P, M, d), provided we specify a metric d, and hence also topology on M We recall that a sequence of probability measures {μ_{k} : k ∈ ℤ_{+}} ⊂ M converges weakly to μ_{∞} ∈ M (denoted μ_{k} →^{w} μ_{∞}) if

lim_{k→∞} ∫ fdμ_{k} = ∫ fdμ_{∞}

for every f ∈ C(X). Due to our restrictions on the state space X, the topology of weak convergence is induced by a number of metrics on M. One such metric may be expressed

d_{m}(μ, ν) = ∑_{k=0}^{∞} | ∫ f_{k}dμ − ∫ f_{k}dν|2^{−k}, μ, ν ∈ M

where {f_{k}} is an appropriate set of functions in C_{c}(X), the set of continuous functions on X with compact support. For (P, M, d_{m}) to be a dynamical system we require that P be a continuous map on M. If P is continuous, then we must have in particular that if a sequence of point masses {δ_{x_{k}} : k ∈ ℤ_{+}} ⊂ M converge to some point mass δ_{x_{∞}} ∈ M, then

δ_{x_{k}}P →^{w} δ_{x_{∞}}P as k → ∞

or equivalently lim_{k→∞} P f(x_{k}) = P f(x_{∞}) for all f ∈ C(X). That is, if the Markov transition function induces a continuous map on M then P f must be continuous of any bounded continuous function f. Conversely it is clear that for any weak feller Markov transition function P, the associated operator P on M is continuous.

Proposition 32 The triple (P, M, d_{m}) is a dynamical system if and only if the Markov transition function P has the weak Feller property.

Definition 22 We say that X is an e-chain if for any f ∈ C_{c}(X) the sequence of functions {P^{k}f : k ∈ ℤ_{+}} is equicontinuous on compact sets.

Proposition 33 Suppose that the Markov chain X has the Feller property, and that there exists a unique probability measure π such that for every x

P^{n}(x, ·) →^{w} π.

Then X is an e-chain.

We say that the dynamical system (P, M, d_{m}) is called stable in the sense of Lyapunov if for each measure μ ∈ M,

lim_{ν→μ} sup_{k⩾0} d_{m}(νP^{k}, μP^{k}) = 0.

Proposition 34 The Markov is an e-chain if and only if the dynamical system (P, M, d_{m}) is stable in the sense of Lyapunov.

Stability in the sense of Lyapunov is a useful concept when a stationary point for the dynamical system exists. If x^{∗} is stationary point and the dynamical systems is stable in the sense of Lyapunov, the trajectories which start near x^{∗} will stay near x^{∗}, and this turns out to be a useful notion of stability. For the dynamical system (P, M, d_{m}), a stationary point is an invariant probability: that is, a probability satisfying

π(A) = ∫ π(dx)P (x, A), A ∈ B(X).

We say that (P, M, d_{m}) is Lagrange stable if, for every μ ∈ M, the orbit of measures μP^{k} is a precompact subset of M.

Definition 23 The Markov chain X is called bounded in probability if for each initial condition x ∈ X and each ε > 0, there exists a compact subset C ⊂ X such that

lim inf_{k→∞} P_{x}(X_{k} ∈ C) ⩾ 1 − ε.

Equivalently the family of measures {P (x, ·) : k ⩾ 1} is tight.

Proposition 35 The chain X is bounded in probability if and only if the dynamical system (P, M, d_{m}) is Lagrange stable.

Note that the space C(X) can be viewed as a normed linear space, where we take the norm | · |_{c} to be defined for f ∈ C(X) as

|f|_{c} := ∑_{k=0}^{∞} ∑_{k=0}^{∞} 2^{−k}( sup_{x∈C_{k}} |f(x)|)

where {C_{k}} is a sequence of open precompact sets whose union is equal to X. The associated metric d_{c} generates the topology of uniform convergence on compact subsets of X. If P is a weak Feller kernel, then the mapping P on C(X) is continuous with respect to this norm and in this case the triple (P, C(X), d_{c}) is a dynamical system.

Proposition 36 Suppose that X is bounded in probability. Then X is an e-chain if and only if the dynamical system (P, C(X), d_{c}) is Lagrange stable.

Transience and Recurrence

The idea is that for irreducible chains two sorts of behavior are expected: either samples eventually leave any bounded set with probability one or they will return infinitely many times to sets of positive measure.

Definition 24 1. We say that a set A is uniformly transient if for there exists M < ∞ such that E_{x}(η_{A}) ⩽ M for all x ∈ A.

2. The set A is called recurrent if E_{x}(η_{A}) = ∞ for all x ∈ A.

We say that X is recurrent if every set in B_{+}(X) is recurrent. If there is a countable covering of X with uniformly transient sets then we say that X is transient.

6.1 Transience and recurrence on countable state space

Definition 25 The state α is called transient if E_{α}(η_{α}) < ∞, and recurrent if E_{α}(η_{α}) = ∞.

Proposition 37 When X is countable and X is irreducible, either U(x, y) = ∞ for all x, y ∈ X or U(x, y) < ∞ for all x, y ∈ X.

Definition 26 1. If every state is transient the chain is called transient.

2. If every state is recurrent the chain is called recurrent.

Proposition 38 For any x ∈ X, U(x, x) = ∞, if and only if L(x, x) = 1.

Proposition 39 When X is irreducible, either L(x, y) = 1 for all x, y ∈ X or L(x, x) < 1 for all x ∈ X.

6.2 Transience and recurrence for individual sets

We recall that for general A, B ∈ B(X) the taboo probabilities are of the form

P_{A}^{n}(x, B) = P_{x}(X_{n} ∈ B, τ_{A} ⩾ n),

and by convention P_{A}^{0}(x, A) = 0.

Remark 1 There are two basic decompositions of P^{n}(x, ·) over the first return to A ∈ B(X): 1. first entrance decomposition

P^{n}(x, B) = P_{A}^{n}(x, B) + ∑_{j=1}^{n−1} ∫_{A} P_{A}^{j}(x, dw)P^{n−j}(w, B).

2. last exit decomposition

P^{n}(x, B) = P_{A}^{n}(x, B) + ∑_{j=1}^{n−1} ∫_{A} P^{j}(x, dw)P_{A}^{n−j}(w, B),

To analyze the transience and recurrence behavior we need

U^{(z)}(x, B) := ∑_{n=1}^{∞} P^{n}(x, B)z^{n}, |z| < 1;

U_{A}^{(z)}(x, B) := ∑_{n=1}^{∞} P_{A}^{n}(x, B)z^{n}, |z| < 1.

Th kernel U has the property

U(x, A) = ∑_{n=1}^{∞} P^{n}(x, A) = lim_{z→1} U^{(z)}(x, A)

and as in the countable case, for any x ∈ X, A ∈ B(X)

E_{x}(η_{A}) = U(x, A).

The return probabilities L(x, A) = P_{x}(τ_{A} < ∞) satisfy

L(x, A) = ∑_{n=1}^{∞} P_{A}^{n}(x, A) − lim_{z→1} U_{A}^{(z)}(x, A).

Exploiting the convolution forms in first entrance last exit decompositions we obtain U^{(z)}(x, B) = U_{A}^{(z)}(x, B) + ∫_{A} U_{A}^{(z)}(x, dw)U^{(z)}(w, B),

U^{(z)}(x, B) = U_{A}^{(z)}(x, B) + ∫_{A} U^{(z)}(x, dw)U_{A}^{(z)}(w, B).

6.3 The recurrence and transience for chains with an atom

Theorem 12 Suppose that X is ψ-irreducible and admits an atom α α ∈ B_{+}(X). Then 1. if α is recurrent then every set in B_{+}(X) is recurrent.

2. if α is transient, then there is a countable covering of X by uniformly transient sets. Definition 27 If A ∈ B(X) can be covered with a countable number of uniformly transient sets, then we call A transient.

6.4 The general recurrence/transience dichotomy

Definition 28 1. The chain X is called recurrent if it is ψ-irreducible and U(x, A) = ∞ for every

A ∈ B_{+}(X).

2. The chain X is called transient if it is ψ-irreducible and X is transient. Proposition 40 Suppose that X is ψ-irreducible and strongly aperiodic.Then either both X, X̄ are recurrent, or both X and X̄ are transient. Lemma 8 For any 0 < ε < 1 the following identity holds:

∑_{n=1}^{∞} K_{ε}^{n} = \frac{1 − ε}{ε} ∑_{n=0}^{∞} P^{n}.

Theorem 13 If X is ψ-irreducible, then X is either recurrent or transient. Theorem 14 Suppose that X is ψ-irreducible and aperiodic.

1. The chain X is transient if and only if one and then very m-skeleton is transient.

2. The chain X is recurrent if and only if one and there very m-skeleton is recurrent.

6.5 Transience and recurrence

Proposition 41 Suppose that X is a Markov chain (not necessarily irreducible)

1. If any set A ∈ B(X) is uniformly transient with U(x, A) ⩽ M for x ∈ A, then U(x, A) ⩽ 1 + M for every x ∈ X.

2. If any set A ∈ B(X) satisfies L(x, A) = 1 for all x ∈ A, then A is recurrent. If X is ψ irreducible, then A ∈ B^{+}(X) and we have U(x, A) ≡ ∞ for x ∈ X.

3. If any set A ∈ B(X) satisfies L(x, A) ⩽ ε < 1, x ∈ A, then we have U(x, A) ⩽ 1/(1−ε) for x ∈ X, so that in particular A is uniformly transient.

4. Let τ_{A}(k) denote the k-th return time to A, and suppose that for some m

P_{x}(τ_{A}(m) < ∞) ⩽ ε < 1, x ∈ A;

then U(x, A) ⩽ 1 + m/(1 − ε) for very x ∈ X. Proposition 42 If A is uniformly transient and B ↦^{a} A for some a, then B is uniformly transient. Hence if A is uniformly transient, there is a countable covering of Ā by uniformly transient sets. Proposition 43 Suppose D^{c} is absorbing and L(x, D^{c}) > 0 for all x ∈ D. Then D is transient.

6.6 Transient sets

We recall that Theorem 15 If X is ψ-irreducible, then X is either recurrent or transient. Theorem 16 If X is ψ-irreducible and transient then every petite set is uniformly transient. Theorem 17 Suppose that X is ψ-irreducible. Then

1. X is recurrent if there exists some petite set C ∈ B(X) such that L(x, C) = 1, for all x ∈ C.

2. X is transient if and only if there exist two sets D, C ∈ B_{+}(X) with L(x, C) < 1 for all x ∈ D. Proposition 44 If X is ψ-irreducible then every ψ-null set is transient. Proposition 45 Suppose that X is a ψ-irreducible Markov chain on (X , B(X). Then there exists sets D_{1}, ..., D_{d} ∈ B(X) such that

1. for x ∈ D_{i}, P (x, D_{i}) = 1, i = 0, ..., d − 1 ( mod d)

2. the set N = (⋃_{i=1}^{d} D_{i})^{c} is ψ-null and transient.