Week 6 - lecture 2

TOP TOPIC

Date: 01/09/22

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

LECTURE presentation

1
2
3
4
Previous
Next
Download Presentation

Video lecture

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 X_1, \ldots, X_d be independent random variables taking values in a finite set S, and let \pi_i be the probability distribution of X_i.
Consider the chain on S^d which, at each move, picks a coordinate i at random, and updates the value at i with an element of S chosen according to \pi_i.
Show that for this chain, the spectral gap is \gamma = 1/n.  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  P for which all eigenvalues are non-negative.
Hint:  Show that \langle Pf,f \rangle \ge 0 for all functions f on the state space.

4.* Assume the G=(V,E) is a graph, \rho is the graph distance on V, and P is an irreducible transition matrix on V.  Let D_G be the diameter of V with respect to this metric, and suppose that \rho_K(\mu P, \nu P) \leq e^{-\alpha} \rho_K(\mu, \nu)

for all choices of probability measures \mu,\nu on V.
Show that  D_G \leq \frac{2}{1-e^{-\alpha}} \,.

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.

Contact Me