Dr. Stephen DeSalvo (UCLA)

Title: Probabilistic Divide-and-Conquer - a new method for exact simulation

Abstract: We describe a general method for the generation of a random sample from a se<t of objects under a given distribution, typically of the combinatorial type. For example, the uniform distribution over the set of all integer partitions. The general setup is roughly as follows. Suppose the random objects $S$ can be described as $S = (A,B)$, where $A\in \mathcal{A}$ and $B\in \mathcal{B}$ can be simulated separately. Suppose there is a matching function $h: \mathcal{A} \times \mathcal{B} \to \{0,1\}$ that determines which As and Bs can be paired together to form a matching pair in $S$, so that the desired distribution on the set of objects $S$ is equal in distribution to $( (A,B) | h(A,B) = 1)$. We will focus in this talk on the application to the random generation of integer partitions to demonstrate how one would carry out this technique. Our main result says that our algorithm is O( \sqrt{n} ), which is also the lower entropy limit of a random ensemble. Only basic probability will be assumed.

This is joint work with Richard Arratia.