1.* (Review problem). Suppose that we move a knight randomly on a standard chess board according to the following rules. Initially, the knight stands on one of the corners of the chess board. Then, at each step, the knight chooses one of the possible moves at random with equal probabilities, independently of what happened before. Compute the expected number of steps for the knight to return to its starting point. Hint: The answer is in the interval [160,170].

2.* Let be independent random variables taking values in a finite set , and let be the probability distribution of .

Consider the chain on which, at each move, picks a coordinate at random, and updates the value at with an element of chosen according to .

Show that for this chain, the spectral gap is . Deduce the Efron-Stein inequality for these variables, see wikipedia or Exercise 13.12 in the textbook for the statement.

3.* Show that Glauber dynamics for the Ising model has a transition matrix for which all eigenvalues are non-negative.

Hint: Show that for all functions on the state space.

4.* Assume the is a graph, is the graph distance on , and is an irreducible transition matrix on . Let be the diameter of with respect to this metric, and suppose that

for all choices of probability measures on .

Show that