Graduate-Faculty Seminar
Wednesday, November 1, 2023, 10:00am, Gross 330
Scott McIntyre
Efficiently Sampling Maximal Couplings of Markov Chains

Abstract:

For two Markov chains with the same transition function but different initial states, a maximal coupling of those chains introduces dependence between these chains that maximizes the probability of these two chains occupying the same state at every time. If the Markov chains can occupy more than two states, explicitly writing down a maximal coupling becomes tricky. After discussing this motivation in detail, I will present an algorithm for efficiently sampling paths from maximal couplings of finite-state, discrete-time Markov chains. This algorithm is inspired by James Pitman's construction of a maximal coupling, which will be modified with a time reversal procedure that allows for efficient sampling. We will also view some examples of maximal couplings of random walks that were sampled with this algorithm.

---

Generated at 7:54am Tuesday, June 9, 2026 by Mcal.   Top * Reload * Login