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

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.

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

**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.

- By definition (84) the condition
(85) is clearly necessary as (84)
implies in particular
**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**-
*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

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

- One can easily see that

- 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
*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

- 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
.
*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 .

- 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

- 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) for the
numerical example defined in Figure 1 is not only
irreducible but also aperiodic and the stationary initial
distribution
is given by

- We consider a connected graph
*Cyclic Random Walks*- The following example of a cyclic random walk is
*not*reversible.- Let
and

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

- Let
and
- 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.

- The following example of a cyclic random walk is
*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

- 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.

- Finally we consider the following example of a transition matrix
and a stationary initial distribution
which are