4Time reversal
IB Markov Chains
4 Time reversal
Physicists have a hard time dealing with time reversal. They cannot find a
decent explanation for why we can move in all directions in space, but can only
move forward in time. Some physicists mumble something about entropy and
pretend they understand the problem of time reversal, but they don’t. However,
in the world of Markov chain, time reversal is something we understand well.
Suppose we have a Markov chain
X
= (
X
0
, ··· , X
N
). We define a new
Markov chain by
Y
k
=
X
N−k
. Then
Y
= (
X
N
, X
N−1
, ··· , X
0
). When is this a
Markov chain? It turns out this is the case if
X
0
has the invariant distribution.
Theorem. Let X be positive recurrent, irreducible with invariant distribution
π. Suppose that X
0
has distribution π. Then Y defined by
Y
k
= X
N−k
is a Markov chain with transition matrix
ˆ
P = (ˆp
i,j
: i, j ∈ S), where
ˆp
i,j
=
π
j
π
i
p
j,i
.
Also π is invariant for
ˆ
P .
Most of the results here should not be surprising, apart from the fact that
Y is Markov. Since Y is just X reversed, the transition matrix of Y is just the
transpose of the transition matrix of
X
, with some factors to get the normalization
right. Also, it is not surprising that
π
is invariant for
ˆ
P
, since each
X
i
, and
hence Y
i
has distribution π by assumption.
Proof.
First we show that
ˆp
is a stochastic matrix. We clearly have
ˆp
i,j
≥
0. We
also have that for each i, we have
X
j
ˆp
i,j
=
1
π
i
X
j
π
j
p
j,i
=
1
π
i
π
i
= 1,
using the fact that π = πP .
We now show π is invariant for
ˆ
P : We have
X
i
π
i
ˆp
i,j
=
X
i
π
j
p
j,i
= π
j
since P is a stochastic matrix and
P
i
p
ji
= 1.
Note that our formula for ˆp
i,j
gives
π
i
ˆp
i,j
= p
j,i
π
j
.
Now we have to show that Y is a Markov chain. We have
P(Y
0
= i
0
, ··· , Y
k
= i
k
) = P(X
N−k
= i
k
, X
N−k+1
= i
k−1
, ··· , X
N
= i
0
)
= π
i
k
p
i
k
,i
k−1
p
i
k−1
,p
k−2
···p
i
1
,i
0
= (π
i
k
p
i
k
,i
k−1
)p
i
k−1
,p
k−2
···p
i
1
,i
0
= ˆp
i
k−1
i
k
(π
i
k−1
p
i
k−1
,p
k−2
) ···p
i
1
,i
0
= ···
= π
i
0
ˆp
i
0
,i
ˆp
i
1
,i
2
··· ˆp
i
k−1
,i
k
.
So Y is a Markov chain.
Just because the reverse of a chain is a Markov chain does not mean it is
“reversible”. In physics, we say a process is reversible only if the dynamics of
moving forwards in time is the same as the dynamics of moving backwards in
time. Hence we have the following definition.
Definition (Reversible chain). An irreducible Markov chain
X
= (
X
0
, ··· , X
N
)
in its invariant distribution
π
is reversible if its reversal has the same transition
probabilities as does X, ie
π
i
p
i,j
= π
j
p
j,i
for all i, j ∈ S.
This equation is known as the detailed balance equation. In general, if
λ
is a
distribution that satisfies
λ
i
p
i,j
= λ
j
p
j,i
,
we say (P, λ) is in detailed balance.
Note that most chains are not reversible, just like most functions are not
continuous. However, if we know reversibility, then we have one powerful piece
of information. The nice thing about this is that it is very easy to check if the
above holds — we just have to compute π, and check the equation directly.
In fact, there is an even easier check. We don’t have to start by finding
π
,
but just some λ that is in detailed balance.
Proposition. Let
P
be the transition matrix of an irreducible Markov chain
X
.
Suppose (
P, λ
) is in detailed balance. Then
λ
is the unique invariant distribution
and the chain is reversible (when X
0
has distribution λ).
This is a much better criterion. To find π, we need to solve
π
i
=
X
j
π
j
p
j,i
,
and this has a big scary sum on the right. However, to find the
λ
, we just need
to solve
λ
i
p
i,j
= λ
j
p
j,i
,
and there is no sum involved. So this is indeed a helpful result.
Proof.
It suffices to show that
λ
is invariant. Then it is automatically unique
and the chain is by definition reversible. This is easy to check. We have
X
j
λ
j
p
j,i
=
X
j
λ
i
p
i,j
= λ
i
X
j
p
i,j
= λ
i
.
So λ is invariant.
This gives a really quick route to computing invariant distributions.
Example (Birth-death chain with immigration). Recall our birth-death chain,
where at each state
i >
0, we move to
i
+ 1 with probability
p
i
and to
i −
1 with
probability q
i
= 1 − p
i
. When we are at 0, we are dead and no longer change.
We wouldn’t be able to apply our previous result to this scenario, since 0
is an absorbing equation, and this chain is obviously not irreducible, let alone
positive recurrent. Hence we make a slight modification to our scenario — if
we have population 0, we allow ourselves to have a probability
p
0
of having an
immigrant and get to 1, or probability q
0
= 1 − p
0
that we stay at 0.
This is sort of a “physical” process, so it would not be surprising if this is
reversible. So we can try to find a solution to the detailed balance equation. If
it works, we would have solved it quickly. If not, we have just wasted a minute
or two. We need to solve
λ
i
p
i,j
= λ
j
p
j,i
.
Note that this is automatically satisfied if
j
and
i
differ by at least 2, since both
sides are zero. So we only look at the case where
j
=
i
+ 1 (the case
j
=
i −
1 is
the same thing with the slides flipped). So the only equation we have to satisfy
is
λ
i
p
i
= λ
i+1
q
i+1
for all i. This is just a recursive formula for λ
i
, and we can solve to get
λ
i
=
p
i−1
q
i
λ
i−1
= ··· =
p
i−1
q
i
p
i−2
q
i−1
···
p
0
q
1
λ
0
.
We can call the term in the brackets
ρ
i
=
p
i−1
q
i
p
i−2
q
i−1
···
p
0
q
1
.
For λ
i
to be a distribution, we need
1 =
X
i
λ
i
= λ
0
X
i
ρ
i
.
Thus if
X
ρ
i
< ∞,
then we can pick
λ
0
=
1
P
ρ
i
and λ is a distribution. Hence this is the unique invariant distribution.
If it diverges, the method fails, and we need to use our more traditional
methods to check recurrence and transience.
Example (Random walk on a finite graph). A graph is a collection of points
with edges between them. For example, the following is a graph:
More precisely, a graph is a pair
G
= (
V, E
), where
E
contains distinct unordered
pairs of distinct vertices (u, v), drawn as edges from u to v.
Note that the restriction of distinct pairs and distinct vertices are there to
prevent loops and parallel edges, and the fact that the pairs are unordered means
our edges don’t have orientations.
A graph
G
is connected if for all
u, v ∈ V
, there exists a path along the edges
from u to v.
Let
G
= (
V, E
) be a connected graph with
|V | ≤ ∞
. Let
X
= (
X
n
) be a
random walk on G. Here we live on the vertices, and on each step, we move to
one an adjacent vertex. More precisely, if
X
n
=
x
, then
X
n+1
is chosen uniformly
at random from the set of neighbours of
x
, i.e. the set
{y ∈ V
: (
x, y
)
∈ E}
,
independently of the past. This is a Markov chain.
For example, our previous simple symmetric random walks on
Z
or
Z
d
are
random walks on graphs (despite the graphs not being finite). Our transition
probabilities are
p
i,j
=
(
0 j is not a neighbour of i
1
d
i
j is a neighbour of i
,
where d
i
is the number of neighbours of i, commonly known as the degree of i.
By connectivity, the Markov chain is irreducible. Since it is finite, it is
recurrent, and in fact positive recurrent.
This process is a rather “physical” process, and again we would expect it to
be reversible. So let’s try to solve the detailed balance equation
λ
i
p
i,j
= λ
j
p
j,i
.
If
j
is not a neighbour of
i
, then both sides are zero, and it is trivially balanced.
Otherwise, the equation becomes
λ
i
1
d
i
= λ
j
1
d
j
.
The solution is obvious. Take
λ
i
=
d
i
. In fact we can multiply by any constant
c, and λ
i
= cd
i
for any c. So we pick our c such that this is a distribution, i.e.
1 =
X
i
λ
i
= c
X
i
d
i
.
We now note that since each edge adds 1 to the degrees of each vertex on the
two ends,
P
d
i
is just twice the number of edges. So the equation gives
1 = 2c|E|.
Hence we get
c =
1
2|E|
.
Hence, our invariant distribution is
λ
i
=
d
i
2|E|
.
Let’s look at a specific scenario.
Suppose we have a knight on the chessboard. In each step, the allowed moves
are:
– Move two steps horizontally, then one step vertically;
– Move two steps vertically, then one step horizontally.
For example, if the knight is in the center of the board (red dot), then the
possible moves are indicated with blue crosses:
×
×
×
×
×
×
×
×
At each epoch of time, our erratic knight follows a legal move chosen uniformly
from the set of possible moves. Hence we have a Markov chain derived from the
chessboard. What is his invariant distribution? We can compute the number of
possible moves from each position:
2
3
3
4
4
4
44
6
6
6 6
8
8
8
8
The sum of degrees is
X
i
d
i
= 336.
So the invariant distribution at, say, the corner is
π
corner
=
2
336
.