\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, July 11, 2000}
\centerline{Sequoia Hall Rm. 200}
\centerline{(Cookies at 3:45 in 1st Floor Lounge)}

\bigskip
\baselineskip=15pt
\centerline{\sl Mark Huber}
\centerline{\sl Stanford University}
\bigskip
\centerline{\bf Acceptance/Rejection Sampling from Restricted Permutations}
\bigskip


In restricted permutations, each element $i$ may only be moved to a
restricted set of positions $S_i$.  The problem of sampling uniformly from
the set of restricted permutations turns out to be quite difficult.
Applications for such samples include 
estimating the permanent, generating random Latin rectangles, and finding
the level of nonparametric tests for correlation in doubly truncated data
sets.  We build two approaches for this problem based on
acceptance/rejection techniques.  One approach is the first to generate
exact samples in polynomial time in polynomial time over a nontrivial set
of restrictions. The second approach proves useful when dealing with
interval permutations, and we apply it to a problem of quasar luminosity
evolution studied by Efron and Petrosian.

\bye