James Allen Fill

Two-player Knock 'em Down (2008)

Multiway trees of maximum and minimum probability under the

Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu, Wilson, David B; Microsoft; Dbwilson@microsoft.com

We analyze the two-player game of Knock 'em Down, asymptotically as the number of tokens to be knocked down becomes large. Optimal play requires mixed strategies with deviations of order √n...

and (2008)

COMMUNICATIONS in PROBABILITY A CHARACTERIZATION OF THE SET OF FIXED POINTS OF THE QUICKSORT TRANSFORMATION (2008)

This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

Quicksort, fixed point, characteristic function, smoothing transformation, domain of attraction, coupling, integral equation. The limiting distribution µ of the normalized number of key comparisons...

(EXT. ABS.) (2008)

perfect rejection sampling algorithm to general chains

and (2008)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...

(EXT. ABS.) (2008)

perfect rejection sampling algorithm to general chains

and (2008)

James Allen Fill, David B. Wilson

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...

Abstract (2008)

E l e c t r o n

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...

Abstract (2007)

The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the...

Keith Crank, James Allen Fill

We establish, for various scenarios, whether or not interruptible exact stationary sampling is possible when a finite-state Markov chain can only be viewed passively. In particular, we prove that...

Short title: Moore--Penrose Generalized Inverse for Sums (2007)

James Allen Fill, Donniell E. Fishkind

In this paper we exhibit, under suitable conditions, a neat relationship between the Moore--Penrose generalized inverse of a sum of two matrices and the Moore--Penrose generalized inverses of the...

Chapter 9 A Second Look at General Markov Chains (2007)

Theorem A.1. Let L 0 (2007)

In the spirit of Chapter 2, this is an unsystematic treatment of scattered topics which are related to topics discussed for reversible chains, but where reversibility plays no essential role. Section...

This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.

The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...

G(n, m, p) and G(n, p) models (2007)

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique xed point with zero mean of a certain distributional...

James Allen Fill, Edward R. Scheinerman

of the

Theorem A.1. Let L 0 (2007)

Fakultat fur Mathematik (2007)

This appendix to [2] contains a proof of the improved estimates in Remark 7.3 of that paper for the moment generating function of the (normalized) number of comparisons in Quicksort.

Holger Dette, Jim Pitman, James Allen Fill, William J. Studden

For a birth and death chain on the nonnegative integers with birth and death probabilities p i and q i j 1 \Gamma p i and reflecting barrier at 0, it is shown that the right tails of the probability...

[short title: Random multiway trees] (2007)

Multiway trees of maximum and minimum probability under the

On the Markov (2007)

Truman State University and (2007)

chain for the move-to-root rule for binary search trees [short title: Move-to-root rule for binary search trees]

Singularity Analysis, Hadamard Products, and Tree Recurrences (2007)

Total path length for random recursive trees

James Allen Fill, Philippe Flajolet, James Allen, Nevin Kapur

We present a toolbox for extracting asymptotic information on the coefficients of combinatorial generating functions. This toolbox notably includes a treatment of the effect of Hadamard products on...

On hitting times and fastest strong stationary times for skip-free chains (2007)

Fill, James Allen

An (upward) skip-free Markov chain with the set of nonnegative integers as state space is a chain for which upward jumps may be only of unit size; there is no restriction on downward jumps. In a 1987...

The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof (2007)

Fill, James Allen

A well-known theorem usually attributed to Keilson states that, for an irreducible continuous-time birth-and-death chain on the nonnegative integers and any d, the passage time from state 0 to state...

Analysis of the expected number of bit comparisons required by Quickselect (2007)

Fill, James Allen, Nakama, Take

When algorithms for sorting and searching are applied to keys that are represented as bit strings, we can quantify the performance of the algorithms not only in terms of the number of key comparisons...

Precise logarithmic asymptotics for the right tails of some limit random variables for random trees (2007)

Two-player Knock 'em Down (2006)

For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i)...

Fill, James Allen, Wilson, David B.

We analyze the two-player game of Knock 'em Down, asymptotically as the number of tokens to be knocked down becomes large. Optimal play requires mixed strategies with deviations of order sqrt(n) from...

A repertoire for additive functionals of uniformly distributed m-ary search trees (2005)

Destruction of very simple trees (2004)

Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on $m$-ary search trees on $n$ keys with toll...

Fill, James Allen, Kapur, Nevin, Panholzer, Alois

We consider the total cost of cutting down a random rooted tree chosen from a family of so-called very simple trees (which include ordered trees, $d$-ary trees, and Cayley trees); these form a...

The space requirement of m-ary search trees: distributional asymptotics for m >= 27 (2004)

Percolation, first-passage percolation, and covering times for Richardson's model on the n-cube (2004)

We study the space requirement of $m$-ary search trees under the random permutation model when $m \geq 27$ is fixed. Chauvin and Pouyanne have shown recently that $X_n$, the space requirement of an...

Fill, James Allen, Pemantle, Robin

Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube B_n ={0,1}^n with nearest neighbor edges. For oriented and unoriented percolation, p=e/n and p=1/n...

Limiting Distributions For Additive Functionals On Catalan Trees (2004)

James Allen, James Allen Fill, Nevin Kapur

Additive tree functionals represent the cost of many divide-andconquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the form (a) n when #...

[short title: Total path length] (2004)

Transfer Theorems and Asymptotic Distributional Results m-ary Search Trees (2004)

recursive trees

James Allen Fill, Nevin Kapur

We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of a simple additive...

[short title: Number of m-ary search trees] (2004)

James Allen Fill, Robert P. Dobrow

The number of m-ary search trees on n keys

Asymptotic analysis via Mellin transforms for small deviations in $L^2$-norm of integrated Brownian sheets (2003)

Fill, James Allen, Torcaso, Fred

We use Mellin transforms to compute a full asymptotic expansion for the tail of the Laplace transform of the squared $L^2$-norm of any multiply-integrated Brownian sheet. Through reversion we obtain...

Singularity analysis, Hadamard products, and tree recurrences (2003)

Fill, James Allen, Flajolet, Philippe, Kapur, Nevin

We present a toolbox for extracting asymptotic information on the coefficients of combinatorial generating functions. This toolbox notably includes a treatment of the effect of Hadamard products on...

Limiting distributions for additive functionals on Catalan trees (2003)

Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees (2003)

Additive tree functionals represent the cost of many divide-and-conquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the form (a) n^\alpha...

Singularity Analysis, Hadamard Products, and Tree Recurrences (2003)

We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m-ary search trees, for functionals that satisfy recurrence relations of a simple additive...

James Allen Fill, Philippe Flajolet, Nevin Kapur

We present a toolbox for extracting asymptotic information on the coecients of combinatorial generating functions. This toolbox notably includes a treatment of the eect of Hadamard products on...

and (2003)

James Allen Fill, Fred Torcaso

We use Mellin transforms to compute a full asymptotic expansion for the tail of the Laplace transform of the squared L 2-norm of any multiply-integrated Brownian sheet. Through reversion we obtain...

Speeding up the FMMR perfect sampling algorithm: A case study revisited (2003)

Speeding up the FMMR perfect sampling algorithm: A case study revisited (2002)

In a previous paper by the second author, two Markov chain Monte Carlo perfect sampling algorithms -- one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling -- are...

Dobrow, Robert P., Fill, James Allen

In a previous paper by the second author,two Markov chain Monte Carlo perfect sampling algorithms -- one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling -- are...

Interruptible exact sampling in the passive case (2002)

Crank, Keith, Fill, James Allen

We establish, for various scenarios, whether or not interruptible exact stationary sampling is possible when a finite-state Markov chain can only be viewed passively. In particular, we prove that...

and (2002)

The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...

and (2002)

On Compositions of Random Functions on a Finite Set (2002)

The number of comparisons Xn used by Quicksort to sort an array of n distinct numbers has mean µn of order n log n and standard deviation of order n. Using different methods, Régnier and Rösler...

Extension of Fill's perfect rejection sampling algorithm to general chains (Extended abstract) (2001)

We establish the limiting distribution of the number T n of random functions on a set of size n which must be composed before a constant function results. In more detail, let f 1 , f 2 , . . . be...

Fill, James Allen, Machida, Motoya, Murdoch, Duncan J., Rosenthal, Jeffrey S.

We provide an extension of the perfect sampling algorithm of Fill (1998) to general chains, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a...

Extension of Fill's perfect rejection sampling algorithm to general chains (2001)

Fill, James Allen, Machida, Motoya, Murdoch, Duncan J., Rosenthal, Jeffrey S.

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

Approximating the limiting Quicksort distribution (2001)

Quicksort asymptotics (2001)

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional...

Mixing Times for Markov Chains on Wreath Products and Related Homogeneous Spaces (2001)

The number of comparisons X_n used by Quicksort to sort an array of n distinct numbers has mean mu_n of order n log n and standard deviation of order n. Using different methods, Regnier and Roesler...

Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu

We develop a method for analyzing the mixing times for a quite general class of Markov chains on the complete monomial group G wr Sn and a quite general class of Markov chains on the homogeneous...

Stochastic Monotonicity and Realizable Monotonicity (2001)

Fill, James Allen, Machida, Motoya

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) $\mathcal{S}$ when the measures are...

The randomness recycler approach to perfect sampling (2001)

The randomness recycler approach to perfect sampling (2001)

At the heart of the Monte Carlo approach is the ability to sample from distributions that are in general very difficult to describe completely. For instance, the distribution might have an unknown...

Mixing times for Markov Chains on Wreath Products and Related Homogeneous Spaces (2001)

At the heart of the Monte Carlo approach is the ability to sample from distributions that are in general very di#cult to describe completely. For instance, the distribution might have an unknown...

James Allen Fill, Clyde H. Schoolfield Jr.

this paper have evolved. We develop a method, with broad applications, for bounding the rate of convergence to stationarity for a general class of random walks and Markov chains in terms of closely...

Approximating the Limiting Quicksort Distribution (2001)

The randomness recycler approach to perfect sampling (2001)

The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique xed point with zero mean of a certain distributional...

Realizable monotonicity and inverse probability transform (2000)

At the heart of the Monte Carlo approach is the ability to sample from distributions that are in general very difficult to describe completely. For instance, the distribution might have an unknown...

Fill, James Allen, Machida, Motoya

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 on some probability...

The Randomness Recycler: A new technique for perfect sampling (2000)

Fill, James Allen, Huber, Mark L.

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....

Mixing times for Markov chains on wreath products and related homogeneous spaces (2000)

Fill, James Allen, Schoolfield, Clyde H.

We develop a method for analyzing the mixing times for a quite general class of Markov chains on the complete monomial group G \wr S_n (the wreath product of a group G with the permutation group S_n)...

Perfect Simulation from the Quicksort Limit Distribution (2000)

Devroye, Luc; McGill University; Luc@cs.mcgill.ca, Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu, Neininger, Ralph; Universität Freiburg; Rn@stochastik.uni-freiburg.de

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 fixed-point...

Stochastic monotonicity and realizable monotonicity (2000)

Fill, James Allen, Machida, Motoya

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 measures are indexed by...

A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)

Fill, James Allen; The Johns Hopkins University; Jimfill@jhu.edu, Janson, Svante; Uppsala University; Svante.janson@math.uu.se

The limiting distribution m 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 transformation T...

Smoothness and decay properties of the limiting Quicksort density function (2000)

A characterization of the set of fixed points of the Quicksort transformation (2000)

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 positive and...

Perfect simulation from the Quicksort limit distribution (2000)

The limiting distribution \mu 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 transformation...

Devroye, Luc, Fill, James Allen, Neininger, Ralph

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 fixed-point...

Perfect simulation from the quicksort limit distribution (2000)

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 fixed-point...

The randomness recycler: a new technique for perfect sampling (2000)

Smoothness and Decay Properties of the Limiting Quicksort Density Function (2000)

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....

Approximations of the Limiting Quicksort Distribution (2000)

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 positive and...

James Allen Fill, Svante Janson, This Is, A Draft

THIS IS A DRAFT. Date. June 30, 2000. 1 Research supported by NSF grant DMS--9803780, and by the Acheson J. Duncan Fund for the Advancement of Research in Statistics. 1 1 Introduction and summary The...

A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)

Smoothness and Decay Properties of the Limiting Quicksort Density Function (2000)

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 transformation T...

A Characterization of the Set of Fixed Points of the Quicksort Transformation (2000)

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 positive and...

The Randomness Recycler: A New Technique for Perfect Sampling (2000)

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 transformation T...

Perfect Simulation from the Quicksort Limit Distribution (2000)

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....

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 fixed-point...

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 positive and...

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 transformation T...

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 transformation T...

The randomness recycler: a new technique for perfect sampling (2000)

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 positive and...

Extension of Fill's perfect rejection sampling algorithm to general chains (1999)

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....

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

Advanced L² Techniques for Bounding Mixing Times (1999)

Extension of Fill's perfect rejection sampling algorithm to general chains (Extended Abstract) (1999)

Chapter 2 section yyy:6.2, and Chapter 3 yyy:(55) and the spectral representation give useful reexpressions: kP i (X t 2 \Delta) \Gamma (\Delta)k 2 2 = X j j / p ij (t) j \Gamma 1 ! 2 = p ii (2t) i...

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal, Je#rey S. Rosenthal

. We provide an extension of the perfect sampling algorithm of Fill (1998) to general chains, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a...

Extension of Fill's perfect rejection sampling algorithm to general chains (1999)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal, Je#rey S. Rosenthal

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

Extension of Fill's perfect rejection sampling algorithm to general chains (1999)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

Extension of Fill's perfect rejection sampling algorithm to general chains (Extended Abstract) (1999)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

. We provide an extension of the perfect sampling algorithm of Fill (1998) to general chains, and describe how use of bounding processes can ease computational burden. Along the way, we unearth a...

Extension of Fill's perfect rejection sampling algorithm to general chains (1999)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

Extension of Fill's perfect rejection sampling algorithm to general chains (1999)

James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal

By developing and applying a broad framework for rejection sampling using auxiliary randomness, we provide an extension of the perfect sampling algorithm of Fill (1998) to general chains on quite...

An interruptible algorithm for perfect sampling via Markov chains (1998)

Fill, James Allen

For a large class of examples arising in statistical physics known as attractive spin systems (e.g., the Ising model), one seeks to sample from a probability distribution $\pi$ on an enormously large...

An Interruptible Algorithm for Perfect Sampling via Markov Chains (1998)

An interruptible algorithm for perfect sampling via Markov chains (1998)

For a large class of examples arising in statistical physics known as attractive spin systems (e.g., the Ising model), one seeks to sample from a probability distribution # on an enormously large...

On the distribution for the duration of a randomized leader election algorithm (1996)

For a large class of examples arising in statistical physics known as attractive spin systems (e.g., the Ising model), one seeks to sample from a probability distribution π on an enormously large...

Fill, James Allen, Mahmoud, Hosam M., Szpankowski, Wojciech

We investigate the duration of an elimination process for identifying a winner by coin tossing or, equivalently, the height of a random incomplete trie. Applications of the process include the...

Infinite Graphs (1996)

Examples: Special Graphs and Trees (1996)

Introduction There is a huge research literature concerning random walks on infinite discrete groups, and more generally on infinite graphs. Woess [22] provides an invaluable recent survey, quoting...

On the Distribution for the Duration of a Randomized Leader Election Algorithm (1996)

8.928> x + E x T v = w w vx ; where w = X i X j w ij : (2) Specializing to the unweighted case, E v T x = 2jE(v; x)j + 1 (3) E v T x +E x T v = 2jEj: (4) 1 Proof. It is enough to prove (1), since...

James Allen Fill, Hosam M. Mahmoud, Wojciech Szpankowski

We investigate the duration of an elimination process for identifying a winner by coin tossing, or, equivalently, the height of a random incomplete trie. Applications of the process include the...

A Second Look at General Markov Chains (1995)

Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (1994)

s for reversible chains. Here we discuss underlying "exact" results. Fix an initial distribution . Then 1 associated with each notion of mixing, there is a corresponding construction of a...

Interacting Particles on Finite Graphs (1994)

) The relaxation time 2 , i.e. the time constant in the asymptotic rate of convergence to the stationary distribution. (v) A "flow" parameter c = sup A (A)(A c ) P i2A P j2A c i p ij = sup...

Reversible Markov Chains (1994)

intuitively obvious that P (X x) P (Y x) for all x: (1) 1 One could verify this from the exact formulas, but there is a more elegant non-computational proof. For 1 i n define events (A i ; B i ; C i...

ly, call f : [0; 1) ! [0; 1) completely monotone (CM) if there is a non-negative measure on [0; 1) such that f(t) = Z 1 0 e \Gamma`t (d`); 0 t ! 1: (41) Our applications will use only the special...

Cover Times (1994)

Symmetric Graphs and Chains (1994)

subset at the time when the graph is almost covered is believed to be "fractal" (see the Notes on Chapter 7). 1 We are ultimately interested in random walks on unweighted graphs, but some...