Fall 2021 Seminar

This is the homepage for the UC Berkeley Student Probability Seminar, a venue for graduate students in the departments of mathematics, statistics, and others to study aspects of modern probability theory. We meet on Wednesdays in Evans Hall 939 from 2:00 PM - 3:00 PM.

Organizers: Ella Hiesmayr, Adam Quinn Jaffe, and Mehdi Ouaki.

This semester we are studying Markov chain mixing times, and we will primarily be following this text by Levin, Peres, and Wilmer .

• 25 August, Initial Meeting.
• A casual first meeting to get to know each other and decide on a topic for the semester.
• 1 September, Adam Quinn Jaffe, Introductory Talk.
• We introduce the basic convergence theorem for Markov chains, which states that an irreducible aperiodic Markov chain on a finite state space has a unique stationary distribution to which it converges from any initial distribution. Then, we heuristically describe the goal of the semester, which is to understand the speed of this convergence, typically in terms of asymptotics as the size of the chain increases. We also give various examples that we will later revisit throughout the semester.
• 8 September, Mehdi Ouaki, Total Variation Distance, Convergence and Coupling, Chapters 4 and 5.
• We introduce the definition of the total variation distance between two probability measures and its various formulations. In particular, we put a particular emphasis on its link with the notion of coupling and show it can be used to derive upper bounds on mixing times. We will also briefly go over the long run convergence of the MC marginals to its stationary distribution in the TV sense and show that the speed of convergence is exponential.
• 15 September, Daniel Raban, Stopping Times and Strong Stationary Times, Chapter 6.
• We introduce the notion of stopping times and, in particular, strong stationary times for Markov chains. We prove a general technique for proving upper bounds on mixing times using strong stationary times and apply the technique to compute upper bounds for examples, including a card-shuffling chain.
• 22 September, Mriganka Basu Roy Chowdhury, Lower Bounds for Mixing Times, Chapter 7.3.
• After discussing methods for upper bounding mixing times in the past few weeks, we now look at a few techniques that enable us to prove lower bounds. We also discuss the random walk on a hypercube for which we already proved an O(n log n) upper bound on its mixing time, and now prove a corresponding O(n log n) lower bound (but with different hidden constants).
• 29 September, Yang Chu, More Lower Bounds for Mixing Times, Chapter 7.1, 7.2.
• This week we will continue on lower bounds of mixing times. We will introduce basic methods like counting bounds and diameter bounds, as well as the bottleneck ratio which is a geometric feature of Markov chains, that will come up again when we discuss spectral methods. We will work on examples like top-to-random shuffle which has lower bound O(n log n), and riffle shuffle which has lower bound O(log n).
• 6 October, Zack Stier, Time-Reversal and Reversibility, Chapter 1.6, A.3.
• We will discuss time-reversal of Markov chains, and see the wide range of effects it can have on mixing times. We will also begin to discuss the condition of reversibility, which appears in many natural chains, and begin to explore spectral properties of reversible Markov chains.
• 13 October, Zack Stier, Spectral Theory of Reversible Markov Chains, Chapter 12.1, 12.2.
• We will leverage the useful notion of Markov chain reversibility to prove an analogue to the spectral theorem for symmetric matrices, then leverage this in turn to achieve upper and lower bounds for the mixing time.
• 20 October, Zachary McNulty, Applications of Spectral Bounds to Projected and Product Chains, Chapter 12.3.
• Today we will discuss a few applications of the spectral bounds on mixing times discussed in the previous lecture. In particular, we will discuss two techniques for building new chains from existing ones, quotients and products, and how this spectral analysis passes naturally through these operations.
• 27 October, Karissa Huang, Glauber Dynamics and Product Chains, Chapter 3.3, 12.4.
• In this talk we will introduce Glauber dynamics, provide a few examples, and bound the spectral gap for Glauber dynamics. Finally, we will return to the example of the lazy random walk on the hypercube, show a bound for its spectral gap using Glauber dynamics, and compare it to the bound obtained using the coupling method.
• 3 November, Ella Hiesmayr, Bounds on the Spectral Gap, Chapter 13.1.
• In this talk we will first prove a bound on the absolute spectral gap using contractions by couplings. We will then apply this bound to the Glauber dynamics on the hardcore model that was introduced last week. In a second part, we will introduce an upper and lower bound on the spectral gap in terms of the bottleneck ratio and prove parts of that theorem.
• 10 November, Nicholas Liskij, Path Couplings, Chapter 14.2.
• In this talk, we introduce the transportation metric and the notion of a path coupling. We then prove that a good path coupling gives an upper bound on the mixing time using the transportation metric. By applying this theorem, we get bounds for the exclusion process on the complete graph and for Glauber dynamics with q-colorings.
• 17 November, Zach Stier, Cutoff in Families of Markov Chains, Chapter 18.
• In this talk, we will define the notion of cutoff for a family of Markov chains, discuss some (non)examples, and consider the necessary condition of pre-cutoff.
• 1 December, Yang Chu, Random Walks on Groups.
• Today we focus on random walks on groups which were introduced at the beginning of this semester. In particular we will introduce tools from representation theory, i.e. Fourier analysis on groups, which play an important role in analyzing such Markov chains. We will see it's essential to study the characters of irreducible representations of the group.
• 8 December, Adam Quinn Jaffe, Phase Transition for the Mixing Time of Glauber Dynamics for the Ising Model, Chapter 15.2.
• The Glauber dynamics for the Ising model on a general graph is believed to be fast-mixing at high temperatures and slow-mixing at low temperatures. In this talk we prove a rigorous version of this statement for the complete graph. That is, we identify a critical temperature above which the mixing time is at most N log N and below which the mixing time is at least exponential in N.

Thanks for the great semester, everyone!