3Long-run behaviour
IB Markov Chains
3.2 Convergence to equilibrium
So far, we have discussed that if a chain converged, then it must converge to an
invariant distribution. We then proved that the chain has a (unique) invariant
distribution if and only if it is positive recurrent.
Now, we want to understand when convergence actually occurs.
Theorem. Consider a Markov chain that is irreducible, positive recurrent and
aperiodic. Then
p
i,k
(n) → π
k
as n → ∞, where π is the unique invariant distribution.
We will prove this by “coupling”. The idea of coupling is that here we have
two sets of probabilities, and we want to prove some relations between them. The
first step is to move our attention to random variables, by considering random
variables that give rise to these probability distribution. In other words, we look
at the Markov chains themselves instead of the probabilities. In general, random
variables are nicer to work with, since they are functions, not discrete, unrelated
numbers.
However, we have a problem since we get two random variables, but they are
completely unrelated. This is bad. So we will need to do some “coupling” to
correlate the two random variables together.
Proof.
(non-examinable) The idea of the proof is to show that for any
i, j, k ∈ S
,
we have
p
i,k
(
n
)
→ p
j,k
(
n
) as
n → ∞
. Then we can argue that no matter where
we start, we will tend to the same distribution, and hence any distribution tends
to the same distribution as π, since π doesn’t change.
As mentioned, instead of working with probability distributions, we will work
with the chains themselves. In particular, we have two Markov chains, and we
imagine one starts at
i
and the other starts at
j
. To do so, we define the pair
Z
= (
X, Y
) of two independent chains, with
X
= (
X
n
) and
Y
= (
Y
n
) each
having the state space S and transition matrix P .
We can let
Z
= (
Z
n
), where
Z
n
= (
X
n
, Y
n
) is a Markov chain on state space
S
2
. This has transition probabilities
p
ij,kℓ
= p
i,k
p
j,ℓ
by independence of the chains. We would like to apply theorems to
Z
, so we
need to make sure it has nice properties. First, we want to check that
Z
is
irreducible. We have
p
ij,kℓ
(n) = p
i,k
(n)p
j,ℓ
(n).
We want this to be strictly positive for some
n
. We know that there is
m
such
that
p
i,k
(
m
)
>
0, and some
r
such that
p
j,ℓ
(
r
)
>
0. However, what we need is
an
n
that makes them simultaneously positive. We can indeed find such an
n
,
based on the assumption that we have aperiodic chains and waffling something
about number theory.
Now we want to show positive recurrence. We know that
X
, and hence
Y
is positive recurrent. By our previous theorem, there is a unique invariant
distribution π for P . It is then easy to check that Z has invariant distribution
ν = (ν
ij
: ij ∈ S
2
)
given by
ν
i,j
= π
i
π
j
.
This works because X and Y are independent. So Z is also positive recurrent.
So Z is nice.
The next step is to couple the two chains together. The idea is to fix some
state
s ∈ S
, and let
T
be the earliest time at which
X
n
=
Y
n
=
s
. Because of
recurrence, we can always find such at
T
. After this time
T
,
X
and
Y
behave
under the exact same distribution.
We define
T = inf{n : Z
n
= (X
n
, Y
n
) = (s, s)}.
We have
p
i,k
(n) = P
i
(X
n
= k)
= P
ij
(X
n
= k)
= P
ij
(X
n
= k, T ≤ n) + P
ij
(X
n
= k, T > n)
Note that if
T ≤ n
, then at time
T
,
X
T
=
Y
T
. Thus the evolution of
X
and
Y
after time T is equal. So this is equal to
= P
ij
(Y
n
= k, T ≤ n) + P
ij
(X
n
= k, T > n)
≤ P
ij
(Y
n
= k) + P
ij
(T > n)
= p
j,k
(n) + P
ij
(T > n).
Hence we know that
|p
i,k
(n) − p
j,k
(n)| ≤ P
ij
(T > n).
As n → ∞, we know that P
ij
(T > n) → 0 since Z is recurrent. So
|p
i,k
(n) − p
j,k
(n)| → 0
With this result, we can prove what we want. First, by the invariance of
π
, we
have
π = πP
n
for all n. So we can write
π
k
=
X
j
π
j
p
j,k
(n).
Hence we have
|π
k
− p
i,k
(n)| =
X
j
π
j
(p
j,k
(n) − p
i,k
(n))
≤
X
j
π
j
|p
j,k
(n) − p
i,k
|.
We know that each individual
|p
j,k
(
n
)
− p
i,k
(
n
)
|
tends to zero. So by bounded
convergence, we know
π
k
− p
i,k
(n) → 0.
So done.
What happens when we have a null recurrent case? We would still be able to
prove the result about
p
i,k
(
n
)
→ p
j,k
(
n
), since
T
is finite by recurrence. However,
we do not have a π to make the last step.
Recall that we motivated our definition of
π
i
as the proportion of time we
spend in state i. Can we prove that this is indeed the case?
More concretely, we let
V
i
(n) = |{m ≤ n : X
m
= i}|.
We thus want to know what happens to
V
i
(
n
)
/n
as
n → ∞
. We think this
should tend to π
i
.
Note that technically, this is not a well-formed question, since we don’t exactly
know how convergence of random variables should be defined. Nevertheless, we
can give an informal proof of this result.
The idea is to look at the average time between successive visits. We assume
X
0
=
i
. We let
T
m
be the time of
m
th return to
i
. In particular,
T
0
= 0. We
define
U
m
=
T
m
− T
m−1
. All of these are iid by the strong Markov property,
and has mean µ
i
by definition of µ
i
.
Hence, by the law of large numbers,
1
m
T
m
=
1
m
m
X
r=1
U
r
∼ E[U
1
] = µ
i
. (∗)
We now want to look at
V
i
. If we stare at them hard enough, we see that
V
i
(
n
)
≤ k
if and only if
T
k
≤ n
. We can write an equivalent statement by letting
k
be a real number. We denote
⌈x⌉
as the least integer greater than
x
. Then we
have
V
i
(n) ≤ x ⇔ T
⌈x⌉
≤ n.
Putting a funny value of x in, we get
V
i
(n)
n
≤
A
µ
i
⇔
1
n
T
⌈An/µ
i
⌉
≤ 1.
However, using (∗), we know that
T
An/µ
i
An/µ
i
→ µ
i
.
Multiply both sides by A/µ
i
to get
A
µ
i
T
An/µ
i
An/µ
i
=
T
An/µ
i
n
→
Aµ
i
µ
i
= A.
So if
A <
1, the event
1
n
T
An/µ
i
≤
1 occurs with almost probability 1. Otherwise,
it happens with probability 0. So in some sense,
V
i
(n)
n
→
1
µ
i
= π
i
.