Identifying Markov chains with a given invariant measure

by

Phil Pollett

Department of Mathematics The University of Queensland

PRELIMINARIES

State-space: S = {0, 1, … } Transition functions: A set of real-valued functions P (·) = (p_{ij}(·), i, j ∈ S) defined on (0, ∞) is called a process (or transition function) if

• p_{ij}(t) ≥ 0,

• ∑_{j} p_{ij}(t) ≤ 1, and

• p_{ij}(s + t) = ∑_{k} p_{ik}(s)p_{kj}(t). It is called standard

• lim_{t↓0} p_{ij}(t) = δ_{ij} and honest if

• ∑_{j} p_{ij}(t) = 1, for some (and then for all) t > 0.

THE Q-MATRIX

For a standard process P the right-hand derivative p′_{ij}(0+) = q_{ij} exists and defines a q-matrix Q = (q_{ij}, i, j ∈ S) whose entries satisfy

• 0 ≤ q_{ij} < ∞, j ≠ i, and

• ∑_{j≠i} q_{ij} ≤ −q_{ii} ≤ ∞.

We set q_{i} = −q_{ii}, i ∈ S.

Suppose that Q is given. Assume that Q is stable, that is q_{i} < ∞ for all i in S. A standard process P will then be called a Q-process if its q-matrix is Q.

THE KOLMOGOROV

DIFFERENTIAL EQUATIONS

For simplicity, we shall assume that Q is conservative, that is

_{j≠i}^{∑} q_{ij} = q_{i}

for all i ∈ S. Under this condition, every Qprocess P satisfies the backward equations,

BE_{ij} p_{ij}′(t) = _{k}^{∑} q_{ik}p_{kj}(t), t > 0,

but might not satisfy the forward equations,

FE_{ij} p_{ij}′(t) = _{k}^{∑} p_{ik}(t)q_{kj}, t > 0.

STATIONARY DISTRIBUTIONS

A collection of positive numbers π = (π_{j}, j ∈ S) is a stationary distribution if ∑_{j} π_{j} = 1 and

_{i}^{∑} π_{i}p_{ij}(t) = π_{j}.  (2)

Recipe: Find a collection of strictly positive numbers m = (m_{j}, j ∈ S) such that

_{i}^{∑} m_{i}q_{ij} = 0.

Such an m is called an invariant measure for Q. If ∑_{i} m_{i} < ∞, then we set

π_{j} = m_{j}/ _{i}^{∑} m_{i}

and hope that π satisfies (2).

BIRTH-DEATH PROCESSES

Transition rates: q_{i,i+1} = λ_{i} (↑ - birth rates) q_{i,i−1} = μ_{i} (↓ - death rates) (μ_{0} = 0) Solve: ∑_{i≥0} m_{i}q_{ij} = 0, j ≥ 0, that is,

−m_{0}λ_{0} + m_{1}μ_{1} = 0,

and, for j ≥ 1,

m_{j−1}λ_{j−1} − m_{j}(λ_{j} + μ_{j}) + m_{j+1} μ_{j+1} = 0. Solution: m_{0} = 1 and

m_{j} = j ; ∏ ; i=1 \frac{λ_{i−1}}{μ_{i}} , j ≥ 1.

MILLER’S EXAMPLE

Rates: fix r > 0 and set λ_{i} = r^{2i}, i ≥ 0, μ_{i} = r^{2i−1} , i ≥ 1.

Solution: m_{0} = 1 and

m_{j} = j ; ∏ ; i=1 \frac{λ_{i−1}}{μ_{i}} , j ≥ 1.

So,

m_{j} = ρ^{j}, where ρ = 1/r,

and hence if r > 1, π_{j} = (1 − ρ)ρ^{j}, j ≥ 0.

WHAT IS GOING WRONG?

Rates:

λ_{j} = r^{2j}, j ≥ 0,
μ_{j} = r^{2j−1} , j ≥ 1.

The relative proportion of births to deaths is r and so, if r > 1, the “process” is clearly transient.

In fact, the “process” is explosive: Q is not regular. R.G. Miller^{∗} showed that Q needs to be regular for the recipe to work.

∗Miller, R.G. Jr. (1963) Stationary equations in continuous time Markov chains. Trans. Amer. Math. Soc. 109, 35–44.

THE MOTIVATING QUESTION

If Q is regular, then there exists uniquely a Q-process, namely the minimal process: the minimal solution F (·) = (f_{ij}(·), i, j ∈ S) to BE_{ij}.

If Q is not regular there are infinitely many Qprocesses, infinitely many of which are honest.

Question: Suppose that there exists a collection of strictly positive numbers π = (π_{j}, j ∈ S) such that

_{i}^{∑} π_{i} = 1 and _{i}^{∑} π_{i}q_{ij} = 0.

Does π admit an interpretation as a stationary distribution for any of these processes?

AN INVARIANCE RESULT

Let m = (m_{i}, i ∈ S) be a collection of strictly positive numbers. We call m a subinvariant measure for Q if

_{i}^{∑} m_{i}q_{ij} ≤ 0,

and an invariant measure for Q if

_{i}^{∑} m_{i}q_{ij} = 0.

It is called an invariant measure for P if

_{i}^{∑} m_{i}p_{ij}(t) = m_{j}.

Theorem: Let P be an arbitrary Q-process. If m is invariant for P, then m is subinvariant for Q, and invariant for Q if and only if P satisfies the forward equations FE_{ij} over S.

Corollary: If m is invariant for the minimal process F, then m is invariant for Q.

A CONSTRUCTION PROBLEM

Suppose that Q is a stable and conservative q-matrix, and that m is subinvariant for Q.

Problem 1: Does there exist a Q-process for which m is invariant?

Problem 2: Does there exist an honest Qprocess for which m is invariant?

Problem 3: When such a Q-process exists, is it unique?

Problem 4: In the case of non-uniqueness, can one identify all Q-processes (or perhaps all honest Q-processes) for which m is invariant?

THE RESOLVENT

Let P be a transition function. If we write

ψ_{ij}(λ) = ∫_{0}^{∞} e^{−λt}p_{ij}(t)dt, λ > 0,

for the Laplace transform of p_{ij}(·), then Ψ(·) = (ψ_{ij}(·), i, j ∈ S) enjoys the following (analogous) properties:

• ψ_{ij}(λ) ≥ 0,

• ∑_{j} λψ_{ij}(λ) ≤ 1, and

• ψ_{ij}(λ)−ψ_{ij}(μ)+(λ−μ) ∑_{k} ψ_{ik}(λ)ψ_{kj}(μ) = 0.

Ψ is called the resolvent of P. Indeed, if Ψ is a given resolvent, in that it satisfies these properties, then there exists a standard (!) process P with Ψ as its resolvent^{∗}.

∗Reuter, G.E.H. (1967) Note on resolvents of denumerable submarkovian processes. Z. Wahrscheinlichkeitstheorie 9, 16–19.

IDENTIFYING Q-PROCESSES

USING RESOLVENTS

Now, if one is given a stable and conservative q-matrix Q, together with a resolvent Ψ which satisfies the backward equations,

λψ_{ij}(λ) = δ_{ij} + _{k}^{∑} q_{ik}ψ_{kj}(λ), λ > 0,

then Ψ determines a standard Q-process. In particular, as λ → ∞,

• λψ_{ij}(λ) → δ_{ij}, and

• λ(λψ_{ij}(λ) − δ_{ij}) → q_{ij}.

One can also use the resolvent to determine whether or not the Q-process is honest, for this happens when and only when

_{j}^{∑} λψ_{ij}(λ) = 1, i ∈ S, λ > 0.

IDENTIFYING INVARIANT MEASURES USING RESOLVENTS

Theorem: Let P be an arbitrary process and let Ψ be its resolvent. Then, m is invariant for P if and only if it is invariant for Ψ, that is,

_{i}^{∑} m_{i}p_{ij}(t) = m_{j}

if and only if

_{i}^{∑} m_{i}λψ_{ij}(λ) = m_{j}.

THE EXISTENCE OF A

Q-PROCESS WITH A GIVEN

INVARIANT MEASURE

Theorem: Let Q be a stable and conservative q-matrix, and suppose that m is a subinvariant measure for Q. Let Φ(·) = (ϕ_{ij}(·), i, j ∈ S) be the resolvent of the minimal Q-process and define z(·) = (z_{i}(·), i ∈ S) and d(·) = (d_{i}(·), i ∈ S) by

z_{i}(λ) = 1 − ∑_{j} λϕ_{ij}(λ),

and

d_{i}(λ) = m_{i} − ∑_{j} m_{j}λϕ_{ji}(λ).

Then, if d = 0, m is invariant for the minimal Q-process. Otherwise, if

∑_{i} d_{i}(λ) ≤ ∑_{i} m_{i}z_{i}(λ) < ∞,

for all λ > 0, there exists a Q-process P for which m is invariant.

Theorem continued: The resolvent of one such process is given by

ψ_{ij}(λ) = ϕ_{ij}(λ) + \frac{z_{i}(λ)d_{j}(λ)}{λ ∑_{k} m_{k}z_{k}(λ)} ,  (4)

and this process is honest if and only if

_{i}^{∑} d_{i}(λ) = _{i}^{∑} m_{i}z_{i}(λ),

for all λ > 0. A sufficient condition for there to exist an honest Q-process for which m is invariant is that m satisfies

_{j}^{∑} m_{j}(1 − λϕ_{jj}(λ)) < ∞,

for all λ > 0.

Corollary: If m is a subinvariant probability distribution for Q, then there exists an honest Q-process with stationary distribution m. The resolvent of one such process is given by (4).

THE SINGLE-EXIT CASE

Suppose that Q is a single-exit q-matrix, that is, the space of bounded, non-negative vectors ξ = (ξ_{i}, i ∈ S) which satisfy

_{j}^{∑} q_{ij}ξ_{j} = αξ_{i}, α > 0,

has dimension 1. (The minimal process has only one available “escape route” to infinity). Then, the condition

∑_{i} d_{i}(λ) ≤ ∑_{i} m_{i}z_{i}(λ) < ∞

is necessary for the existence of a Q-process for which the specified measure is invariant; the Q-process is then determined uniquely by

ψ_{ij}(λ) = ϕ_{ij}(λ) + \frac{z_{i}(λ)d_{j}(λ)}{λ ∑_{k} m_{k}z_{k}(λ)} .

NON-UNIQUENESS

Consider a pure-birth process with strictly positive birth rates (q_{i}, i ≥ 0), but imagine that we have two distinct sets of birth rates, (q_{i}^{(0)} , i ≥ 0) and (q_{i}^{(1)} , i ≥ 0), which satisfy

∞ ; ∑ ; i=0 1/q_{i}^{(r)} < ∞, r = 0, 1.

Let S = {0, 1} × {0, 1, … } and define Q = (q_{xy}, x, y ∈ S) by

q_{(r,i)(s,j)} = \{ \begin{matrix}q_{i}^{(r)} , & ifj = i + 1 and s = r, \\ −q_{i}^{(r)} , & ifj = i and s = r, \\ 0, & otherwise, \end{matrix}

for r = 0, 1 and i ≥ 0. The measure m = (m_{x}, x ∈ S), given by

m_{(r,i)} = 1/q_{i}^{(r)} , r = 0, 1, i ≥ 0,

is subinvariant for Q.

NON-UNIQUENESS

The resolvents of two distinct Q-processes for which m is invariant are given by

ψ_{(r,i)(s,j)} (λ) = δ_{rs}ϕ_{ij}^{(r)} (λ) + \frac{z_{i}^{(r)} (λ)ϕ_{0j}^{(s)}(λ)}{2 − \{z_{0}^{(0)} (λ) + z_{0}^{(1)} (λ)\}}

and

ψ_{(r,i)(s,j)} (λ) = \{ \begin{matrix}ϕ_{ij}^{(r)} (λ) + \frac{z_{i}^{(r)} (λ)z_{0}^{(1−r)} (λ)ϕ_{0j}^{(r)}(λ)}{1−z_{0}^{(0)} (λ)z_{0}^{(1)} (λ)} , & s = r \\ \frac{z_{i}^{(r)} (λ)ϕ_{0j}^{(1−r)} (λ)}{1−z_{0}^{(0)} (λ)z_{0}^{(1)} (λ)} , & s ≠ r. \end{matrix}

Interpretation: The first process chooses between (0, 0) and (1, 0) with equal probability as the starting point following an explosion, no matter which was the most recently traversed path, and the second process traverses alternate paths following successive explosions.

THE REVERSIBLE CASE

Suppose that Q is symmetrically reversible with respect to m, that is, m_{i}q_{ij} = m_{j}q_{ji}, i, j ∈ S. Then, d_{i}(λ) = m_{i}z_{i}(λ), and so we arrive at the following corollary due to Hou and Chen^{∗}.

Corollary: If Q is reversible with respect to m, then there exists uniquely a Q-function P for which m is invariant if and only if ∑_{j} m_{j}z_{j}(λ) < ∞, for all λ > 0. It is honest and its resolvent is given by

ψ_{ij}(λ) = ϕ_{ij}(λ) + \frac{z_{i}(λ)m_{j}z_{j}(λ)}{λ ∑_{k∈S} m_{k}z_{k}(λ)} .

Moreover, P is reversible with respect to m in that m_{i}p_{ij}(t) = m_{j}p_{ji}(t) (or, equivalently, m_{i}ψ_{ij}(λ) = m_{j}ψ_{ji}(λ)).

∗Hou Chen-Ting and Chen Mufa (1980) Markov processes and field theory. Kexue Tongbao 25, 807–811.

BIRTH-DEATH PROCESSES

Suppose that the birth rates (λ_{i}, i ≥ 0) and death rates (μ_{i}, i ≥ 1) are strictly positive. The q-matrix Q is then regular if and only if

∞ ; ∑ ; i=0 \frac{1}{λ_{i}m_{i}} i ; ∑ ; j=0 m_{j} = ∞.  (6)

Proposition: Let m = (m_{i}, i ∈ S) be the essentially unique invariant measure for Q.

(i) m is invariant for the minimal Q-process if and only if (6) holds.

(ii) When (6) fails, there exists uniquely a Qprocess P for which m is invariant if and only if m is finite, in which case P is the unique, honest Q-process which satisfies FE_{ij}; P is positive recurrent and its stationary distribution is obtained by normalizing m.

μ-INVARIANCE

Suppose that S = {0}∪C, where 0 is an absorbing state and C is irreducible (for F). Let μ ≥ 0. A collection m = (m_{i}, i ∈ C) of strictly positive numbers is called a μ-subinvariant measure for Q if

∑_{i∈C} m_{i}q_{ij} ≤ −μm_{j}, j ∈ C,

and a μ-invariant measure for Q if

∑_{i∈C} m_{i}q_{ij} = −μm_{j}, j ∈ C.

It is called a μ-invariant measure for P, where P is any transition function, if

∑_{i∈C} m_{i}p_{ij}(t) = e^{−μt}m_{j}, j ∈ C.

Proposition: A probability distribution π = (π_{i}, i ∈ C) is a μ-invariant measure for some μ > 0 if and only if it is a quasistationary distribution: for j ∈ C,

p_{j}(t) = _{i∈C}^{∑} m_{i}p_{ij}(t) ⇒ p_{j}(t)/ _{k∈C}^{∑} p_{k}(t) = m_{j}.

μ-INVARIANCE FOR F

Theorem: If m is μ-invariant for P, then m is μ-subinvariant for Q, and μ-invariant for Q if and only if P satisfies the forward equations over C. For example, if m is μ-invariant for the minimal process, then it is μ-invariant for Q.

Theorem: If m is μ-invariant for Q, then it is μ-invariant for F if and only if the equations

_{i∈C}^{∑} y_{i}q_{ij} = −νy_{j}, 0 ≤ y_{i} ≤ m_{i}, i ∈ C,

have no non-trivial solution for some (and then all) ν < μ.

Theorem: If m is a finite μ-invariant measure for Q, then

μ _{i∈C}^{∑} m_{i}a_{i}^{F} ≤ _{i∈C}^{∑} m_{i}q_{i0},  (8)

where a_{i}^{F} = lim_{t→∞} f_{i0}(t), and m is μ-invariant for F if and only if equality holds in (8).

Q-PROCESSES WITH A GIVEN

μ-INVARIANT MEASURE

Theorem: Suppose that Q is single-exit and that m is a finite μ-subinvariant measure for Q. Then, there exists a Q-process for which m is μ-invariant if and only if

_{i∈C}^{∑} m_{i}q_{i0} ≤ μ _{i∈C}^{∑} m_{i}.

The resolvent Ψ of any Q-process for which m is μ-invariant must be of the form

ψ_{ij}(λ) = ϕ_{ij}(λ)+\frac{z_{i}(λ)d_{j}(λ)}{(λ + μ) ∑_{k∈C} m_{k}z_{k}(λ)} , i, j ∈ S,

where

d_{j}(λ) = m_{j} − _{i∈C}^{∑} m_{i}(λ + μ)ϕ_{ij}(λ), j ∈ C,

d_{0}(λ) = e/λ − _{i∈C}^{∑} m_{i}(λ + μ)ϕ_{i0}(λ),

and e satisfies ∑_{i∈C} m_{i}q_{i0} ≤ e ≤ μ ∑_{i∈C} m_{i}.

Q-PROCESSES WITH A GIVEN

μ-INVARIANT MEASURE

Theorem continued: Conversely, if

_{i∈C}^{∑} m_{i}q_{i0} ≤ μ _{i∈C}^{∑} m_{i},

then all Q-processes for which m is μ-invariant can be constructed in this way by varying e in the range

_{i∈C}^{∑} m_{i}q_{i0} ≤ e ≤ μ _{i∈C}^{∑} m_{i}.

Exactly one of these is honest; this is obtained by setting e = μ ∑_{i∈C} m_{i}. And, exactly one satisfies the forward equations FE_{i0} over i ∈ C; this is obtained by setting e = ∑_{i∈C} m_{i}q_{i0}.