Week 2 - lecture 2

TOP TOPIC

Date: 01/09/22

2.6. Mixing via coupling
2.7. The cycle and the Hypercube
2.8. Stationary Times
2.9. Strong Stationary Times and separation distance 

LECTURE presentation

1
2
3
4
5
6
7
8
9
10
Previous
Next
Download Presentation

Video lecture

Homework

1.*  Let \{X_t\} be simple random walk on the hypercube \{0,1\}^n, and let Y_t denote the Hamming weight (i.e., the number of ones) of X_t.  Then \{Y_t\} is also a Markov chain, with transition probabilities   P(0,1)=P(n,n-1)=1 and P(k,k-1)=\frac{k}{n}, \; \, P(k,k+1)=\frac{n-k}{n} for 0<k<n. Read about projected (or lumped) chains on pages 23-25 of the textbook, and calculate  E_k(\tau_0) for 0<k \le n. Hint: it suffices to calculate  E_k(\tau_{k-1}).

2.  Show that the mixing time of lazy simple random walk on the discrete torus {\mathbb Z}_n^d (see section 5.3.3 and Theorem 5.6 of the book) is O(d \log d \cdot n^2).

3*.   Consider the following Markov chain on the integers:  Fix q \in (0,1). Let    P(n,n-1)=q=1-P(n,n+2) for all integers n. Let X_0=1. For which q is the hitting time \tau_0 finite almost surely, and what is its expectation E_1(\tau_0)?

A key issue is determining when the expectation is finite.  It is OK to use the strong law of large numbers.

4. Given an irreducible aperiodic transition matrix P, show that for any two states x,y, there is a coupling of the chains X_t, Y_t  started from x,y respectively, such that the expected coalescence time of these chains is at most 2t_{\rm mix}(P).

5. Solve exercises 4.3 and 4.4 in the book, which can be found at https://www.yuval-peres-books.com/markov-chains-and-mixing-times/

 

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