Page 187 - Applied Probability

9. Descent Graph Methods
172
Conversely, if an irreducible Markov chain satisfies Kolmogorov’s crite-
rion, then the chain is reversible. This fact can be demonstrated by explic-
itly constructing the equilibrium distribution and showing that it satisfies
detailed balance. The idea behind the construction is to choose some arbi-
trary reference state i and to pretend that π i is given. If j is another state,
let i → i 1 → ··· → i m → j be any path leading from i to j. Then the
formula
p
p ii 1 i 1 i 2 ··· p i m j
π j = π i (9.4)
p
p ji m i m i m−1 ··· p i 1 i
defines π j . A straightforward application of Kolmogorov’s criterion (9.3)
shows that the definition (9.4) does not depend on the particular path
chosen from i to j. To validate detailed balance, suppose that k is adjacent
to j. Then i → i 1 → ··· → i m → j → k furnishes a path from i to k
through j. It follows from (9.4) that π k = π j p jk /p kj , which is obviously
equivalent to detailed balance. In general, the value of π i is not known
beforehand. Setting π i = 1 produces the equilibrium distribution up to a
normalizing constant.
Example 9.2.1 Two Different Markov Chains on a DNA Strand
As explained in Appendix A, a DNA strand is constructed from the four
bases A (adenine), G (guanine), C (cytosine), and T (thymine). The strand
has a directionality so that we can imagine starting at its 5 end and walking

toward its 3 end. As one proceeds along the strand, the bases encountered
are not independent. To a first approximation [37], the successive bases
conform to a Markov chain with transition matrix
A C G T
 
A .32 .18 .23 .27
C  .37 .23 .05 .35 
P =   .
G  .30 .21 .25 .24 
T .23 .19 .25 .33

It is easy to check that the equilibrium distribution of this aperiodic chain
is π =(.30,.20,.20,.30).
Bishop et al. [2] use the above chain to construct a more complicated
Markov chain capturing the random distances between restriction sites.
Restriction enzymes recognize certain specific sequences of bases along
a DNA strand and cut the DNA at these restriction sites. For instance, the
enzyme AluI recognizes the sequence AGCT. To investigate the random
distance between restriction sites for AluI, it is helpful to construct a chain
with states A, C, G, T, AG, AGC, and AGCT. The first four states are
interpreted as in the chain above. AG is the state where the current DNA
base is G and the previous base is A. Here part of the desired restriction
site pattern has been achieved. The state AGC is even further along on