DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty One
TITLE: "Microsurveys in Discrete Probability"
EDITORS: David Aldous and James Propp.

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.

PREFACE


This book contains eleven articles surveying emerging topics in discrete probability. The papers are based on talks given by experts at the DIMACS "Microsurveys in Discrete Probability" workshop held at the Institute for Advanced Study, Princeton, NJ, in 1997. This compilation of current research in discrete probability provides a unique overview that is not available elsewhere in book or survey form.

Topics covered in the volume include: Markov chains (perfect sampling, coupling from the past, mixing times), random trees (spanning trees on infinite graphs, enumeration of trees and forests, tree-valued Markov chains), distributional estimates (method of bounded differences, Stein-Chen method for normal approximation), dynamical percolation, Poisson processes, and reconstructing random walk from scenery.

TABLE OF CONTENTS


Foreword						vii

Preface							 ix

Tree-valued Markov chains and Poisson-Galton-Watson 
  distributions
    David Aldous					  1

On the central role of scale invariant Poisson 
  processes on (0, infinity)
    Richard Arratia					 21


Beyond the method of bounded differences
    Anant P. Godbole and Pawel Hitczenko 		 43

Dynamical percolation: Early results and open problems
    Olle Häggström					 59

Distinguishing and reconstructing sceneries from 
  observations along random walk paths
    Harry Kesten					 75

Mixing times
    Laszlo Lovász and Peter Winkler			 85 

A bird's-eye view of uniform spanning trees and forests
    Russell Lyons					135

Enumerations of trees and forests related to branching 
  processes and random walks
    Jim Pitman						163

Coupling from the past: A user's guide
    James Propp and David Wilson			181

Couplings for normal approximations with Stein's 
  method
    Gesine Reinert					193

Annotated bibliography of perfectly random sampling 
  with Markov chains
    David B. Wilson 					209
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.