Seminar

Random sampling is ubiquitous throughout mathematics, computing and the sciences as a means of studying very large sets. In this talk we will discuss simple, classical Markov chains for efficiently sampling paths and permutations. We will look at various natural generalizations with some surprising results. First, we show how to extend these Markov chain algorithms to sample biased paths, with applications to tile-based self-assembly, asymmetric exclusion processes, self-organized lists, and biased card shuffling. Next, we show how generating random configurations with mutliple paths allows us to sample planar tilings and colorings. Using insights from statistical physics, however, we will see why these methods break down and may be inefficient in models with non-uniform bias, in higher dimensions, or in weighted models with sufficiently high fugacity.