Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Generalized hit-and-run is a framework for describing and analyzing a wide class of Markov chain Monte Carlo methods. This talk focuses on an instance of generalized hit-and-run for sampling permutations from a class of models called first order distributions. These first order distributions are a broad class that includes Mallows models with Lp distances. The new hit-and-run sampler extends existing work that was specific to Mallows L1 and L2 models. A novel algorithm for sampling permutations with one-sided restrictions dramatically reduces the per-step complexity of the hit-and-run sampler. The talk also presents both upper and lower bounds on the mixing time of the hit-and-run sampler in different parameter regimes. Finally, we will discuss how understanding examples of generalized hit-and-run can contribute towards a general theory of these Markov chain Monte Carlo methods.