41 citations · 98 across the 8 of their papers we have counts for
6 papers · 1 filter
Realizable monotonicity and inverse probability transform
James Allen Fill, Motoya Machida
A system (P_a: a in A) of probability measures on a common state space S indexed by another index set A can be ``realized'' by a system (X_a: a in A) of S-valued random variables o…
The Randomness Recycler: A new technique for perfect sampling
James Allen Fill, Mark L. Huber
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 t…
Stochastic monotonicity and realizable monotonicity
James Allen Fill, Motoya Machida
We explore and relate two notions of monotonicity, stochastic and realizable, for a system of probability measures on a common finite partially ordered set (poset) S when the measu…
Perfect simulation from the Quicksort limit distribution
Luc Devroye, James Allen Fill, Ralph Neininger
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional…
A characterization of the set of fixed points of the Quicksort transformation
James Allen Fill, Svante Janson
The limiting distribution μof the normalized number of key comparisons required by the Quicksort sorting algorithm is known to be the unique fixed point of a certain distributional…
Smoothness and decay properties of the limiting Quicksort density function
James Allen Fill, Svante Janson
Using Fourier analysis, we prove that the limiting distribution of the standardized random number of comparisons used by Quicksort to sort an array of n numbers has an everywhere p…