1. You can modify any of the C++ code on Compass to solve these problems, if you want. It might help you with honing your programming skills. If these attempts (at using C++ code) is turning out to to be intense, you can use MATLAB just this once.
2. You will submit a PDF-version of your answers on Compass on-or-before mid- night of the due date.
Instructions
d
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 , and proceed as often as necessary. Show that in steady-state you
v
2card(E)
will spend dv % 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 discrete- states 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?
