Exercise Solutions

CS8803 MCMC
Fall 2014
Exercise Solutions
Instructor: Dana Randall
Student: Prateek Bhakta, TA
These exercises use the convention that vectors are row vectors, and multiplication is usually on
the right, unless specified otherwise.
1. Prove the statement in the middle of page 654:
⌧"  ⌧1/4 log2 "
1
Solution: Let P be the transtion matrix of the Markov chain, and let d(t) = maxx kP t (x, ·)
⇡ktv be the maximum distance to ⇡ of the distribution x after t steps of the Markov chain.
Lemma 1.1: For all s, t 2 N, d(s + t)  2d(s)d(t).
Proof: Let x be some initial distribution. After P s steps, the
Assuming that d is non-decreasing (Homework 1), we then use this lemma to show the
stronger fact that ⌧"  ⌧1/4 blog2 " 1 c.
d(⌧1/4 · blog2 "
1
c)  (2d(⌧1/4 ))blog2 "
1c
/2  (1/2)blog2 "
1c
/2  "
Thus d(⌧1/4 · blog2 " 1 c) steps are sufficient to ensure that the total variation distance is
< ", and it is therefore an upper bound of ⌧" .
2. Show that if M is stochastic, then its eigenvalues obey | |  1. Hint: for a vector v, let kvkmax
denote maxi |vi |, and show that kM vkmax  kvkmax .
Solution: Recall that the eigenvalues of M are well defined whether we consider left- or
right- eigenvectors. Though we usually multiply stochastic matrices on the right, for this
problem we will consider multiplication on the left.
As in the hint, let kvkmax = maxi |vi |. For all v, we have
X
X
X
kM vk = max|
Mi,j vj |  max|
Mi,j kvkmax | = kvkmax |
Mi,j | = kvkmax
i
j
i
j
j
For any eigenvalue,left-eigenvector pair , v, kM vkmax = k vkmax = | |kvkmax .
kM vkmax  kvkmax for all v, it follows that any eigenvalue of M must have | |  1.
As
3. Let M be a real, symmetric matrix. Show that its eigenvalues are real, and that if u and v are
eigenvectors with di↵erent eigenvalues, then u and v are orthogonal. Hint: consider the inner
product uT M v.
Solution: Say u, v are eigenvectors for di↵erent eigenvalues, u , v . Then uT M v = uT v v,
T
and also uT M v = uT u v. Thus ( u
v )u v = 0. Since by assumption u 6= v , we must
have uT v = 0, or u and v are orthogonal.
CS8803 MCMC
Fall 2014
Exercise Solutions
Instructor: Dana Randall
Student: Prateek Bhakta, TA
To show that the eigenvalues are real, Let , v be an eigenvalue, eigenvector pair. Then
¯ v . Thus ¯ , v¯ is also an eigenvector, eigenvalue
M v = v, thus M¯v = ¯v, or M v¯ = lambda¯
¯
T
¯
pair. As before, we have that (
)v v = 0. As v 6= 0, we know that v¯v = hv, vi > 0, thus
= ¯ . Thus is real.
4. Let M be a stochastic matrix, which may or may not be symmetric, with a unique eigenvector
v0 = Peq of eigenvalue 1. Let 1 = (1, 1, 1, 1, · · · , 1). Show that all of M’s eigenvectors vk . other
than v0 obey 1 · vk = 0; in other words, their total probability
is zero. Then show that any
P
probability distribution can be written in the form Peq + k6=0 ak vk .
Solution: Let v be an eigenvector corresponding to 6= 1. Then we have that vM 1T =
v1T . But since M is stochastic, all its row sums are 1, and M 1T = 1T . Therefore
vM 1T = v1T , and (1
)v1T = 0. Thus if 6= 1, we must have that v1T = 1 · v = 0.
The next part of the exercise seems to assume either that M is fully diagonalizable or that
we allow vk to be pseudo-eigenvectors. With thisP
assumption, any probability distribution P
(and in fact any vector), can beP
written as P = k ak vk . As P is a probabilityPdistribution,
we must have that 1 = P 1T = k ak vk 1T = a0 Peq 1T = a0 . Thus P = Peq + k>0 ak vk as
desired.
5. Suppose M obeys detailed balance, but that some if its eigenvalues may be negative. Consider a
“lazy” version of M , which takes a step according to M with probability 1/2, and stays put with
probability 1/2. Show that the transition matrix of this Markov chain is Mlazy = (1 + M)/2,
that its equilibrium distribution is the same as M , and that its eigenvalues lazy = (1 + )/2
are non-negative.
Solution: As stated above, for all pairs of states a 6= b, Plazy (a, b) = PM (a, b)/2, and for
all states a, Plazy (a, a) = 12 (1 + PM (a, a)). Thus we have shown that Mlazy = (1 + M)/2
entry by entry.
If Peq M = Peq , then Peq Mlazy = Pe q(1 + M)/2 = 12 Peq + 12 Peq M = 12 Peq + 12 Peq = Peq .
If , v is an eigenvalue,eigenvector pair of Mlazy , then as M = 2Mlazy 1, it follows that
vM = v(2Mlazy 1) = 2 v v = (2
1)v, thus 2
1, v is an eigenvalue,eigenvector pair
of M . As every By a previous exercise, it follows that 2
1
1, or
0.
6. Consider a random walk on an undirected graph G. At each step, we move from the current
vertex x to a uniformly random neighbor y, so that M (x ! y) = 1/deg(x) if x and y are
neighbors, and 0 otherwise.
Show that this walk is ergodic if G is connected and non-bipartite. Show that if it is connected
but bipartite, it has a unique eigenvector with eigenvalue 1. Then show that the “lazy” walk
defined in Exercise 12.12, where we stay at a vertex with probability 1/2 and move to a random
neighbor with probability 1/2, is ergodic if G is connected.
Finally, show that the equilibrium probability of each vertex is proportional to its degree, so
that Peq (x) = deg(x)/2m, where m is the number of edges.
Page 2
CS8803 MCMC
Fall 2014
Exercise Solutions
Instructor: Dana Randall
Student: Prateek Bhakta, TA
Solution: If G is connected, then between any two vertices x, y, there is some path
x = v0 , v1 , . . . vl = y, where each (vi , vi+1 ) 2 E. Starting at x, we could move to y with a
sequence of moves following this path. Thus the Markov chain is irreducible.
If G isn’t bipartite, then there must be some odd cycle (v1 , . . . v2l+1 ) in G. Starting at v1 ,
we could arrive at v1 after 2l + 1 steps by following steps in the cycle. We can also arrive at
v1 after two steps following the path v1 , v2 , v1 . As gcd(2, 2l + 1) = 1, it follows that this
Markoc chain is aperiodic as well, and therefore ergodic.
If the MC is lazy, then beginning at v1 , we can arrive at v1 after one step (by staying in
place), or after two steps, (by moving and returning). As gcd(1, 2) = 1, the Markov Chain
is aperiodic, and therefore ergodic.
Finally, to show that Peq (x) = deg(x)/2m, we show that detailed balance holds with this
distribution, therefore it must be the stationary distribution. To show this, let x, y be
neighbors. Then P (x, y) = 1/deg(x), and P (y, x) = 1/deg(y). Thus Peq (x)P (x, y) =
1/2m = Peq (y)P (y, x) for all x,y.
Page 3

Download Report