Next: Recursive Construction of the Up: Reversibility; Estimates for the Previous: Reversibility; Estimates for the   Contents

### Definition and Examples

• A stationary Markov chain and its corresponding pair consisting of the transition matrix and the stationary initial distribution is called reversible if its finite-dimensional distributions do not depend on the orientation of the time axis, i.e., if

 (84)

for arbitrary and .
• The reversibility of Markov chains is a particularly useful property for the construction of dynamic simulation algorithms, see Sections 3.3-3.5.

First of all we will derive a simple characterization for the reversibility of stationary (but not necessarily ergodic) Markov chains.

Theorem 2.13
• Let be a Markov chain with state space , transition matrix and stationary initial distribution .
• The Markov chain is reversible if and only if

 (85)

Proof

• By definition (84) the condition (85) is clearly necessary as (84) implies in particular

• Therefore

• Conversely, if (85) holds then the definition (3) of Markov chains yields

• i.e., (84) holds.

Remarks

• The proof of Theorem 2.13 does not require the stationary Markov chain to be ergodic.
• In other words
• If the transition matrix is not irreducible or not aperiodic and hence the limit distribution does not exist or is not uniquely determined, respectively,
• then Theorem 2.13 still holds if is an arbitrary stationary initial distribution.
• As is a stochastic matrix, (85) implies for arbitrary

• In other words: Every initial distribution satisfying the so-called detailed balance condition (85) is necessarily a stationary initial distribution, i.e. it satisfies the global balance condition .

Examples

1. Diffusion Model
• We return to the diffusion model already discussed in Section 2.2.3 with the finite state space , the irreducible (but aperiodic) transition matrix where

 (86)

and the (according to Theorem 2.10 uniquely determined but not ergodic) stationary initial distribution

 (87)

• One can easily see that

for arbitrary , i.e., the pair given by (86) and (87) is reversible.

2. Birth and Death Processes
• For the birth and death processes with two reflecting barriers considered in Section 2.2.3 let the transition matrix be of such a form that the equation has a uniquely determined probability solution .

• For this situation one can show that

3. Random Walks on Graphs
• We consider a connected graph
• with the set of vertices and the set of edges, each of them connecting two vertices
• such that for every pair of vertices there is a path of edges in connecting and .

 [width=9cm,angle=1800]graph1.eps

• We say that two vertices and are neighbors if there is an edge connecting them, i.e., an edge having both of them as endpoints, where denotes the number of neighbors of .
• A random walk on the graph is a Markov chain with state space and transition matrix , where

 (88)

• Figure 1 shows such a graph where the set contains vertices and the set consists of edges. More precisely

• One can show that
• the transition matrix given by (88) is irreducible,
• the (according to Theorem 2.10 uniquely determined) stationary initial distribution is given by

 (89)

• the pair given by (88)-(89) is reversible as for arbitrary

• The transition matrix given by (88) for the numerical example defined in Figure 1 is not only irreducible but also aperiodic and the stationary initial distribution is given by

4. Cyclic Random Walks
• The following example of a cyclic random walk is not reversible.
• Let and

 (90)

• i.e., the transition graph is given by Figure 2.

 [width=7cm, angle=1800]graph2.eps

• The transition matrix (90) is obviously irreducible, but not aperiodic, and the initial distribution (which is uniquely determined by Theorem 2.10) is given by .
• However,

• It is intuitively plausible that this cyclic random work is not reversible as clockwise steps are much more likely than counterclockwise movements.

5. Doubly-Stochastic Transition Matrix
• Finally we consider the following example of a transition matrix and a stationary initial distribution which are not reversible: For such that and let

 (91)

• This transition matrix is doubly-stochastic, i.e., the transposed matrix is also a stochastic matrix and is obviously quasi-positive.
• The (uniquely determined) stationary initial distribution is given by

• As the transition matrix in (91) is not symmetric the pair is not reversible.

Next: Recursive Construction of the Up: Reversibility; Estimates for the Previous: Reversibility; Estimates for the   Contents
Ursa Pantle 2006-07-20