Studies in Perfect Simulation and Combinatorial Probability

Johns Hopkins University, Baltimore MD

Investigators

Abstract

One focus of the research is perfect simulation. Markov chain Monte Carlo (MCMC) approximate sampling methods have become extremely popular for Bayesian inference problems and for problems in other areas, such as spatial statistics, statistical physics, and computer science as a way of sampling approximately from a complicated probability distribution. For some problems, it is now possible to use more sophisticated MCMC techniques to sample perfectly (that is, without error) from the distribution of interest. The investigator and his colleagues work on creating, improving, analyzing, and applying efficient perfect simulation algorithms; these algorithms include the Fill-Machida-Murdoch-Rosenthal algorithm and the new Randomness Recycler technique pioneered by the investigator and his colleague Mark Huber. The second focus concerns probability and combinatorial structures, especially trees. The investigator and his colleagues study such problems as characterizing the "shape" of random multiway search trees (via fundamental research in the area of analytic combinatorics known as singularity analysis); generalizing the analyses of the height of a random incomplete digital search tree, of the move-to-front rule for self- organizing lists, and of recursive trees; and extending the so-called generalized smoothing transformation to distributions on the entire real line. One focus of the investigator's research is perfect simulation from probability distributions. Standard "Markov chain Monte Carlo" (MCMC) methods for approximate simulation from complicated probability distributions have proved extremely useful for problems in statistics (including image analysis), physics (including models for magnetism and for phase changes), and computer science as a way of sampling approximately from a complicated probability distribution. But there are problems with the MCMC approach -- most notably that for many problems it is unknown for how long the simulations must be run in order to come close to the distribution of interest. For some problems, it is now possible to use more sophisticated MCMC techniques to sample perfectly (that is, without error) from the distribution of interest. The investigator and his colleagues work on creating, improving, analyzing, and applying efficient perfect simulation algorithms, including two different algorithms pioneered by the investigator. The second focus concerns interplays between probability and combinatorial structures, especially trees, which are fundamental structures for the storage of computer data. This second focus of research has applications to the modeling of epidemics, family trees of ancient manuscripts, and pyramid schemes and to the election of multiple leaders in a multiprocessor computer network.