\magnification=1200
\baselineskip=20pt
\nopagenumbers
\font\big=cmr12 scaled \magstep2

\centerline{\bf STANFORD UNIVERSITY}
\centerline{\bf DEPARTMENT OF STATISTICS}
\centerline{\big DEPARTMENTAL SEMINAR}
\bigskip

\baselineskip=12pt
\centerline{4:15 p.m., Tuesday, February 6, 2001}
\centerline{Sequoia Hall Rm. 200}
\centerline{(Cookies at 3:45 in 1st Floor Lounge)}

\bigskip
\baselineskip=15pt
\centerline{\sl Mark L. Huber}
\centerline{\sl Cornell University}
\bigskip
\centerline{\bf The Randomness Recycler:}
\centerline{\bf A New Technique for Generating Perfect Samples
from High Dimensional Distributions}
\bigskip

For many probability distributions of interest, it is quite difficult to
obtain samples efficiently.  Often, Markov chains are employed to 
obtain approximately random samples from these distributions.  The 
primary drawback to traditional Markov chain methods is that the 
mixing time of the chain is usually unknown, making it impossible to 
determine how close the samples are to the target distribution.  Here 
we present a new protocol, the randomness recycler (RR), that 
overcomes this difficulty.  Unlike classical Markov chain approaches, 
an RR-based algorithm creates samples drawn exactly from the 
desired distribution.  Other perfect sampling methods such as coupling
from the past use existing Markov chains, but RR does away with the
traditional Markov chain in favor of a dual chain with absorbing states 
that are reached with probability equal to the desired distribution.  While 
by no means universally useful, RR does apply to a wide variety of 
problems.  In restricted instances of certain problems, it gives the first 
expected linear time algorithms for generating samples.  RR applies to 
such diverse problems as self-organizing lists, two sided interval 
permutations, random independent sets, random colorings, and the 
random cluster model.

\bye