James Allen Fill (Jim Fill)
	Professor of Applied Mathematics and Statistics
	Professor of Computer Science
	Department of Applied Mathematics and Statistics
	(formerly Department of Mathematical Sciences)
	The Johns Hopkins University
	Baltimore, MD 21218-2682
	Office:   Whitehead Hall 306-F
	Phone:   (410) 516-7219
	FAX:   (410) 516-7459
	E-mail:   jimfill@jhu.edu
	FULL DISCLOSURE: The photo isn't very recent!
	My CV, last updated November 13, 2012.

Research Interests

Probability, stochastic processes (esp. Markov chains), random structures and algorithms

Education

• Ph.D. Statistics, University of Chicago, 1980

• M.S. Statistics, University of Chicago, 1979

• B.S. Mathematics and Statistics, University of Illinois, 1976

Selected Technical Reports Available [in Portable Document Format (pdf)]

• Partitions with Distinct Multiplicities of Parts: On an ``Unsolved Problem'' Posed by Herbert Wilf. Coauthors: Svante Janson and Mark Daniel Ward. (Last revised March, 2012.) Electronic Journal of Combinatorics 19, Paper P18 (electronic) (2012).

• Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort. Extended abstract (last revised May, 2010): Refereed article, pages 221-234 in Proceedings of the 21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (eds.: M. Drmota and B. Gittenberger), 2010. Full paper (last revised March, 2012): Annals of Applied Probability 23:1129-1147 (2013).

• Distributional Convergence for the Number of Symbol Comparisons Used by QuickSelect. Coauthor: Takehiko Nakama. (Last revised September, 2012.) Advances in Applied Probability, to appear.

• The Number of Bit Comparisons Used by Quicksort: An Average-case Analysis. Coauthor: Svante Janson. Extended abstract (last revised October, 2003): Refereed article, pages 293-300 in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA04), 2004. Full paper (last revised May, 2012): Electronic Journal of Probability 17, Article 43, 1-22 (electronic) (2012).

• The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract). Coauthor: Patrick Bindjeme. Available in a shorter version [refereed article, pages 349-360 in 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'12), eds.: Nicolas Broutin and Luc Devroye, DMTCS Proceedings, 2012; last revised March, 2012] and a longer version (last revised January, 2012).

• Exact $L^2$-distance from the Limit for QuickSort Key Comparisons (Extended Abstract). Coauthor: Patrick Bindjeme. (Last revised March, 2012.) Refereed article, pages 339-348 in 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'12), eds.: Nicolas Broutin and Luc Devroye, DMTCS Proceedings, 2012.

• Hitting Times and Interlacing Eigenvalues: A Stochastic Approach Using Intertwinings. Coauthor: Vince Lyzinski. (Last revised August, 2012.) Journal of Theoretical Probability, to appear.

• Comparison Inequalities and Fastest-mixing Markov Chains. Coauthor: Jonas Kahn. (Last revised March, 2012.) Annals of Applied Probability, to appear. Here's a lecture based on this paper.

• On Vertex, Edge, and Vertex-edge Random Graphs. Coauthors: Elizabeth Beer, Svante Janson, and Edward R. Scheinerman. Extended abstract (last revised December, 2010): Refereed article, pages 16-22 in Joint Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) and the Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (2011). Full paper (last revised April, 2011): Electronic Journal of Combinatorics 18, Paper P110 (electronic) (2011).

• Perfect Simulation of Vervaat Perpetuities. Coauthor: Mark Huber. (Last revised January, 2010.) Electronic Journal of Probability 15, Paper No. 4, 96-109 (electronic) (2010).

• The Number of Symbol Comparisons in Quicksort and Quickselect. Coauthors: Brigitte Vallée, Julien Clément, and Philippe Flajolet. (Last revised April, 2009.) Refereed article, pages 750-763 in 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I, LNCS 5555 (eds.: S. Albers et al.), Springer-Verlag, 2009. Correction: The min/max constants in Figure 1 should be twice as large as stated.

• Analysis of the Expected Number of Bit Comparisons Required by Quickselect. Coauthor: Takehiko Nakama. Extended abstract (last revised January, 2008): Joint Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) and the Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (2008), 249-256. Full paper (last revised February, 2009): Algorithmica 58:730-769 (2010).

• On Hitting Times and Fastest Strong Stationary Times for Skip-free and More General Chains. (Last revised May, 2009.) Journal of Theoretical Probability 22:587-600 (2009). Here's a lecture based on this paper and the next listed.

• The Passage Time Distribution for a Birth-and-death Chain: Strong Stationary Duality Gives a First Stochastic Proof.. (Last revised May, 2009.) Journal of Theoretical Probability 22:543-557 (2009).

• Precise Logarithmic Asymptotics for the Right Tails of Some Limit Random Variables for Random Trees. Coauthor: Svante Janson. (Last revised September, 2007.) Special issue on Analysis of Algorithms, Annals of Combinatorics 12:399-412 (2008).

• Two-player Knock 'em Down. Coauthor: David B. Wilson. (Last revised January, 2008.) Electronic Journal of Probability 13, Paper No. 9, 198-212 (electronic) (2008).

• A Repertoire for Additive Functionals of Uniformly Distributed m-ary Search Trees. Coauthor: Nevin Kapur. Refereed extended abstract (last revised April, 2005): pages 105-114 in 2005 International Conference on the Analysis of Algorithms (ed.: Conrado Martinez), Discrete Mathematics and Theoretical Computer Science Proceedings, AD, 2005. Full paper (last revised February, 2008): unpublished.

• Destruction of Very Simple Trees. Coauthors: Nevin Kapur and Alois Panholzer. (Last revised August, 2005.) Special issue on Analysis of Algorithms, Algorithmica 46:345-366 (2007).

• The Space Requirement of m-ary Search Trees: Distributional Asymptotics for m ≥ 27. Coauthor: Nevin Kapur. (Last revised May, 2004.) Invited paper appearing (page numbers unknown) in Proceedings of the 7th Iranian Statistical Conference, 2004.

• Exact Expectations of Minimal Spanning Trees for Graphs with Random Edge Weights. Coauthor: J. Michael Steele. (Last revised April, 2004.) Refereed article, pages 169-180 in Stein's Method and Applications (eds.: A. D. Barbour and Louis H. Y. Chen), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 5, World Scientific, 2005.

• Asymptotic Analysis via Mellin Transforms for Small Deviations in $L^2$-norm of Integrated Brownian Sheets. Coauthor: Fred Torcaso. (Last revised March, 2004.) Probability Theory and Related Fields 130:259-288 (2004).

• Limiting Distributions for Additive Functionals on Catalan Trees. Coauthor: Nevin Kapur. (Last revised April, 2004.) Theoretical Computer Science 326:69-102 (2004).

• Singularity Analysis, Hadamard Products, and Tree Recurrences. Coauthors: Philippe Flajolet and Nevin Kapur. (Last revised June, 2003.) Journal of Computational and Applied Mathematics 174/2:271-313 (2004).

• Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees. Coauthor: Nevin Kapur. (Last revised July, 2004.) Random Structures & Algorithms 26:359-391 (2005).

• Speeding Up the FMMR Perfect Sampling Algorithm: A Case Study Revisited. Coauthor: Robert P. Dobrow. (Last revised June, 2003.) Random Structures & Algorithms 23:434-452 (2003).

• Interruptible Exact Sampling in the Passive Case. Coauthor: Keith Crank. (Last revised October, 2002.) Special International Workshop on Applied Probability issue, Methodology and Computing in Applied Probability 4:359-376 (2002).

• Quicksort Asymptotics, with an unpublished Appendix. Coauthor: Svante Janson. (Last revised May, 2002.) Special issue on Analysis of Algorithms, Journal of Algorithms 44:4-28 (2002).

• Approximating the Limiting Quicksort Distribution. Coauthor: Svante Janson. (Last revised August, 2001.) Special issue on Analysis of Algorithms, Random Structures & Algorithms 19:376-406 (2001).

• Realizable Monotonicity and Inverse Probability Transform. Coauthor: Motoya Machida. (Last revised September, 2000.) Refereed article, pages 63-72 in Proceedings of Distributions with Given Marginals and Statistical Modelling (eds.: C. M. Cuadras, J. Fortiana, and J. Rodriguez-Lallena), Kluwer Academic Publishers, 2002.

• The Randomness Recycler: A New Technique for Perfect Sampling. Coauthor: Mark Huber. (Last revised August, 2000.) Refereed extended abstract, pages 503-511 in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000. The Randomness Recycler Approach to Perfect Sampling. Coauthor: Mark Huber. (Last revised April, 2001.) Short paper presented at the Invited Papers Meeting on Perfect Simulation, 53rd Session of the International Statistical Institute, Seoul, Korea, in August, 2001.

• Mixing Times for Markov Chains on Wreath Products and Related Homogeneous Spaces. Coauthor: Clyde H. Schoolfield, Jr. (Last revised June, 2000.) Electronic Journal of Probability 6, Paper No. 11, 1-22 (electronic) (2001).

• Perfect Simulation from the Quicksort Limit Distribution. Coauthors: Luc Devroye and Ralph Neininger. (Last revised June, 2000.) Electronic Communications in Probability 5:95-99 (electronic) (2000).

• A Characterization of the Set of Fixed Points of the Quicksort Transformation. Coauthor: Svante Janson. (Last revised June, 2000.) Electronic Communications in Probability 5:77-84 (electronic) (2000).

• Smoothness and Decay Properties of the Limiting Quicksort Density Function. Coauthor: Svante Janson. (Last revised June, 2000.) Refereed article, pages 53-64 in Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (eds.: D. Gardy and A. Mokkadem), a volume in the series Trends in Mathematics, Birkhäuser Verlag, 2000.

• Extension of Fill's Perfect Rejection Sampling Algorithm to General Chains. Coauthors: Motoya Machida, Duncan J. Murdoch, and Jeffrey S. Rosenthal. Refereed extended abstract (a user-friendly version; last revised September, 1999): pages 37-52 in Monte Carlo Methods (ed.: N. Madras), Fields Institute Communications 26, American Mathematical Society, 2000. Full paper (version including technical details; last revised July, 2000): Random Structures & Algorithms 17:290-316 (2000).

• Stochastic Monotonicity and Realizable Monotonicity. Coauthor: Motoya Machida. (Last revised November, 2000.) Annals of Probability 29:938-978 (2001).

• The Moore-Penrose Generalized Inverse for Sums of Matrices. Coauthor: Donniell E. Fishkind. (Last revised September, 1998.) SIAM Journal on Matrix Analysis and Applications 21:629-635 (1999).

• An Interruptible Algorithm for Perfect Sampling via Markov Chains. (Last revised February, 1998.) Annals of Applied Probability 8:131-162 (1998).

Monograph

• David J. Aldous and I are writing a book, Reversible Markov Chains and Random Walks on Graphs. Follow the title link for more information.

• Department Home page.

Last modified March 10, 2013 by Jim Fill