Logo

Mathematical Sciences Research Institute

Home » Sampling Paths, Permutations and Lattice Structures

Seminar

Sampling Paths, Permutations and Lattice Structures April 02, 2012 (04:10 PM PDT - 05:00 PM PDT)
Location: UC Berkeley, 60 Evans Hall
Speaker(s) Dana Randall (Georgia Institute of Technology)
Description No Description

Video
No Video Uploaded
Abstract/Media

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.

No Notes/Supplements Uploaded No Video Files Uploaded