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