Philippe Flajolet: Random Sampling from Boltzmann Principles

This is a joint work with Philippe Duchon, Guy Louchard, and Gilles Schaeffer.

This note proposes a new framework for random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by placing an appropriate measure spread over the whole of a combinatorial class. The resulting algorithms often operate in linear time. They can be implemented easily within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.

Back to the Index


Please send comments and corrections to Thomas Klausner.