Spring 2016

Sampling Elements with Fixed Rank in Graded Posets

Monday, Jun. 5, 2017 3:30 pm4:00 pm

Add to Calendar

We show that for certain classes of posets, biased Markov chains that walk along edges of their Hasse diagrams can be used to approximately generate samples with any fixed rank in expected polynomial time. A noteworthy application of our method is sampling restricted classes of integer partitions of n. We give the first provably efficient Markov chain algorithm to uniformly sample integer partitions of n from various natural restricted classes. Related applications include sampling permutations with a fixed number of inversions and lozenge tilings on the triangular lattice with a fixed average height.