Modern Theory of Markov Chains

Tuesday 13:15-15:00 BBL071

Textbook

D.A. Levin, Y. Peres, E.L. Wilmer: Markov chains and mixing times, AMS 2008

Evaluation

(i) Written homework assignments contribute up to 50% to the final grade

(ii) Final written exam 50%

  • 08.02 Material covered: the top-to-random shuffle (section 6.1), pp. 3-6.

  • 15.02 Material covered: transient states, periodicity, p 8, section 1.4. subsections 1.5.1, 1.5.2 and 1.5.4

    Homework (to be returned 1.03): problems 1.1, 1.2, 1.3, 1.4, 1.5, 1.6 on page 18

  • 22.02 Material covered: pp. 12-17, sections 2.1, 2.2,2.4

  • 01.03 Material covered: pp. 47-54

    Homework (to be returned 15.03): problems 3.2 (read section 3.3), 4.4.

  • 8.03 Material covered: sections 4.4 and 4.5; pp. 63-65, MC as iterated function (section 1.2); the use of the functional representation to construct couplings, including ``grand coupling'' defined on p. 70

  • 15.03 Material covered: sections 5.3.1; 5.3.3; (part of 5.3.4); 6.2.1; 6.1; 6.2.2

    Homework (to be returned 29.03):

    1. Show that the construction on bottom p. 69 is a coupling

    2. Exercise 6.2

    3. (double points problem) You shuffle a binary string starting from 1111110000000000 (n ones, m zeroes) by first choosing (uniformly) at random two positions, then transposing the letters in these positions. For example if the choice is positions 3 and 7 then the transposition transforms the above initial string into 1101111000000000. Describe the stationary distribution, construct a coupling and use it to obtain estimates of the mixing time. Explore different regimes for m and n as m+n goes to infinity (e.g. m fixed, n foes to infinity; or m=n etc).

  • 22.03 Material covered: sections 6.4, 6.5 (except 6.5.1), section 2.6 (up to 2.6.2).

  • 29.03 Material covered: sections 7.1, 7.2 (up to p. 90), section 7.3 (up to 7.3.1). Homework: The Platonic solids problem.
  • 05.04 Material covered: `dealing' uniform permutations; Sections 8.1, 8.2 to 8.2.3

  • 12.04 Material covered: Section 8.3, Eulerian numbers, cutoff phenomenon.

    Homework: work out details of Exercise 8.11 and the details concerning the statement ``it follows from Exercise 8.11...'' on page 111.

  • 19.04 No lecture.
  • 03.05 Material covered: pp 119-121;

    Homework: problems 9.2, 9.3, 9.4

  • Final test 24.05 at 13:00--16:00 in BBL065
  • 10.05 Material covered: pp 121-124;

    Homework task: check constant 2 in the upper bound part of Proposition 9.16.