# Working Group: Markov Processes and Mixing

Spring 2023

## Logistical Information

Organizers Gautam Iyer All talks are Tuesdays 2:00PM in WEH 7218, unless otherwise noted. https://www.cmu.edu/math/news-events/cna_working_group_seminars.html Please email Gautam Iyer to be added to the list.

## Tentative schedule

Jan 24 Alan Frieze: Markov Chains for Counting, and Related Problems (Special time 2:30PM) Wesley Pegden: Markov Chains for Sampling vs Markov Chains for Outlier detection Wesley Pegden: Markov Chains for Sampling vs Markov Chains for Outlier detection (cont.) Alan Frieze: Markov Chains for Counting, and Related Problems (cont.) Martin Larsson TBA (Gautam? Prasad?) (No meeting, Spring Break) TBA (Gautam?) Mykhaylo Shkolnikov: Shuffling Cards and Stopping Times Mykhaylo Shkolnikov: Strong Stationary Times, and Intertwining

## Topics

Here are a few topics we are considering for the semester in no particular order. If you’d like to give a lecture or two on one of these topics, browse through the reference and send me an email. Talks are all informal so not knowing every last detail about the subject is OK 😄.

If you have other things you like to think about, let me know and I can add them to the list.

### Markov Chains for Counting (Alan)

• How do you count perfect matchings in bipartite graph? A Markov chain approach, Cheeger constants (conductance), and other fun things. Reference: Notes on counting and mixing

### Enhanced dissipation / Speeding up Random Walks by Mixing (Gautam)

• Fix $N$ and look at the random walk $X_{n+1} = f(X_n) + ε_{n+1} \pmod{N}$, where $ε_n$’s are i.i.d.\ uniformly distributed on $\{\pm 1, 0\}$, and $f$ is a bijection on $\{0, \dots, N-1\}$. For “almost every” $f$, the mixing time is $O(\log N)$. Reference: Chatterjee, Diaconis

• Look at $dX = u(X) \, dt + \sqrt{2\kappa} \, dW$ on the Torus, where the deterministic flow of $u$ is “sufficiently mixing”. Then the mixing time of $X$ is $O(\abs{\ln \kappa}^3)$. References: Feng, Iyer ‘19, Iyer, Zhou ‘22.

• Consider an overdamped Langevin system $dX_t = -\nabla U(X) \, dt + \sqrt{2\kappa} dW_t$ on the Torus. When the potential is non-convex, the mixing time is $O(e^{1/\kappa})$. You can add a mixing drift to this to make the mixing time polynomial in $1/\kappa$.

• Blow-up suppression in Nonlinear PDEs: If the mixing time of $dX = u(X) \, dt + \sqrt{\kappa} \, dW_t$ is small enough, then you can avoid “blow up” in certain nonlinear PDEs (like the Keller–Segel model for chemotaxis). Reference: Iyer, Xu, Zlatoš ‘19.

### Strong Stationary Times (Misha)

• How many times do you need to shuffle a deck of cards before it’s random? (And applications to random walks.) Reference: Aldous, Diaconis

• Intertwining for diffusions.

• The long-time asymptotics of certain nonlinear, nonlocal, diffusive equations with a gradient flow structure. Reference: Carrillo, McCann, Villani

### Cutoff Phenomenon

• In some Markov chains, the distance to equilibrium drops dramatically during a small window when mixing occurs. Techniques to prove this, examples and applications. Reference: Levin, Peres, Wilmer, Chapter 18

### Randomly Switched Systems

• A randomly switched system is one where you take finitely many vector fields $u_1, \dots u_N$, run the flow of one of them for a random (exponentially distributed time), and then switch to a different one and repeat. Under certain “user friendly” conditions these have a unique invariant measure and mix exponentially. Reference: Benaïm, Hurth, Strickler.