Description
1. (20 points) (Random Walks on Graphs) Let G = (V, E) be a graph with a
vertex set V and a set of edges E ⊆ V × V. G = (V, E) is undirected if ∀v1, v2 ∈
V, ((v1, v2) ∈ E) ⇔ ((v2, v1) ∈ E). A random walk in a connected, undirected
graph G is defined as follows – assume you are currently at vertex v1 ∈ V, you
pick one its dv-many neighboring vertices (i.e. one-hop-adjacent vertices) with
probability 1
dv
, and proceed as often as necessary. Show that in steady-state you
will spend dv
2card(E) % of time in vertex v, where card(•) is the cardinality (i.e.
size) of the set-argument.
2. (80 points) (Random Knight’s Tour) In this problem we start the knight at one
of the four corner squares in an otherwise empty chessboard. The knight selects
one of the next positions at random independently of the past moves.
(a) (5 points) Interpret the Knight’s tour as a Markov Chain, where the discretestates represent the 64 squares of the chessboard. (PS: I am just looking for
an implicit definition of the 64 × 64 probability-matrix here; if you want,
give me a piece of pseudo-code that constructs the probability-matrix).
(b) (20 points) As a follow-on to problem 2a, is the Markov Chain irreducible?
Is it aperiodic?
(c) (50 points) Find the stationary distribution of this Markov Chain.
(d) (5 points) Where is the Knight most likely to be spotted in steady-state?
Where is the Knight least likely to be spotted in steady-state?
1
