# Week 6 - lecture 2

## TOP TOPIC

Date: 01/09/22

6.6. The Transportation metric
6.7. Path Coupling
6.8. The Ising model

## Homework

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

## Reference

[1] Glasner, Shmuel.
Almost periodic sets and measures on the torus.
Israel J. Math. 32 (1979), no. 2-3, 161–-172.

[2] Berend, Daniel and Peres, Yuval.
Asymptotically dense dilations of sets on the circle.
J. London Math. Soc. (2) 47 (1993), no. 1, 1–-17.

[3] N. Alon and Y. Peres, "Uniform dilations'', Geometric and Functional Analysis, vol. 2, No. 1 (1992), 1–28.

[4] Nair, R. and Velani, S. L.
Glasner sets and polynomials in primes.
Proc. Amer. Math. Soc. 126 (1998), no. 10, 2835–-2840.