Counting Complicated Combinatorial Sets using Markov Chain Monte-Carlo Algorithms

Trung Ngo

Can you imagine a set that is finite but impossible to practically count even with a supercomputer? One way to build such a set is to define it as a subset all permutations of the integers 1 through N. The hard-to-count set may not be particularly large, but the parent set (which has N! elements) may well be too large for an exhaustive check-and-count approach. Monte-Carlo Markov chain methods introduce randomness to estimate the sizes and other features of such complicated combinatorial sets. Trung Ngo applied four algorithms to one such counting problem. The algorithms were implemented in Python and tested and analyzed for performance, convergence, and accuracy.