Faculty

James A. Fill

Professor & Associate Director of Undergraduate Studies

Research Interests

  • Probability
  • Stochastic Processes
  • Random Structures and Algorithms

James Allen Fill, a professor of applied mathematics and statistics, focuses on probability and stochastic processes, with work lying at the interface with theoretical computer science. He has a secondary appointment in the Department of Computer Science.

Fill’s research on Markov chains has focused on rates of convergence to stationarity, hitting times, and perfect simulation. He coauthored work introducing and developing strong stationary duality (SSD), a powerful technique for bounding mixing times for Markov chains, and he has written several papers applying SSD and other techniques to probabilistic analysis of self-organizing data structures for dynamic file maintenance. In addition, he created two general algorithms, “Fill’s algorithm” and “Randomness Recycler,” that modify existing Markov chain Monte Carlo algorithms to produce samples perfectly from a desired (stationary) distribution.

Fill is a leader in the analysis of algorithms (AofA) community. He is known for a series of papers with Svante Janson of Uppsala University giving an in-depth analysis of the QuickSort sorting algorithm, the AofA revolution he has led by providing more realistic analyses of key-comparison algorithms such as QuickSort and QuickSelect in terms of symbol-comparison counts, and his fundamental work with the late Philippe Flajolet and Nevin Kapur on the singularity analysis of Hadamard products of generating functions. All told, he has written more than 25 AofA-related papers.

Fill has made research contributions on a variety of additional topics, including large deviation probabilities, small deviations, percolation and first-passage percolation, random graphs, minimal spanning trees, Radon transforms, projection pursuit, matrix analysis, partially ordered sets, applied game theory, partitions, and mathematical problems in music.

Current interests include the geometry and simulation of multivariate (Pareto) records.

Fill is a Fellow of the American Mathematical Society and of the Institute of Mathematical Statistics, and a member of the American Statistical Association, the Association for Computing Machinery, and the Mathematical Association of America. He also is the long-standing editor-in-chief of the Journal of Theoretical Probability and has been an associate editor for the Annals of Applied Probability, the Electronic Journal of Probability, and Electronic Communications in Probability. A guest editor and referee for numerous other publications, Fill is a two-time recipient of the Professor Joel Dean Award for Excellence in Teaching for the Department of Applied Mathematics and Statistics at Johns Hopkins.

Fill received his bachelor’s degree with a double major in mathematics and statistics from the University of Illinois in 1976. He then earned a master’s degree and PhD in statistics from the University of Chicago in 1979 and 1980, respectively. Fill worked as an assistant professor of statistics at Stanford University before joining the Whiting School of Engineering faculty in 1988, and has held visiting positions at the University of Chicago, MIT, and Microsoft Research.

Education
  • Ph.D. 1980, UNIV CHICAGO
Experience
  • 2016 - Present:  JOINT/SECONDARY APPOINTMENT CS, WSE Computer Science
  • 2012 - 2016:  JOINT/SECONDARY APPOINTMENT CS, WSE Computer Science
  • 2001 - 2001:  Visiting Researcher, Microsoft Research, Theory Group (Redmond, Washington)
  • 2001 - Present:  Professor of Computer Science, Computer Science
  • 1995 - Present:  Professor of Applied Mathematics and Statistics, Department of Applied Mathematics and Statistics, The Johns Hopkins University
  • 1991 - 1995:  Associate Professor of Mathematical Sciences, Mathematical Sciences
  • 1991 - 1991:  Visiting Associate Professor of Mathematics, Massachusetts Institute of Technology
  • 1988 - 1991:  Assistant Professor of Mathematical Sciences, Mathematical Sciences
  • 1986 - 1987:  Visiting Assistant Professor of Statistics, University Of Chicago
  • 1980 - 1988:  Assistant Professor of Statistics, Stanford University
  • 1974 - 1974:  Data Analyst, Division of Research and Statistics, American Hospital Association
Research Areas
  • Analysis of algorithms and data structures
  • Monte Carlo simulation
  • Probability
  • Random data structures
  • Stochastic processes (especially Markov chains)
Awards
  • 2018:  Master Mentor program, invited member of inaugural Homewood Campus cohort
  • 2014:  Elected Fellow, American Mathematical Society
  • 2013:  Professor Joel Dean Award for Excellence in Teaching
  • 1999:  Elected Fellow, Institute of Mathematical Statistics
  • 1978:  Member, Sigma Xi
  • 1976:  B.S. degree awareded Summa Cum Laude, with Highest Distinction in Mathematics and Highest Distinction in Statistics
  • 1976:  McCormick Foundation Fellow at University of Chicago (through 1980)
  • 1976:  Member, Phi Beta Kappa
  • 1976:  Member, Phi Kappa Phi
  • 1976:  NSF Graduate Fellow at University of Chicago (through 1979)
  • 1973:  Member, Phi Eta Sigma
Journal Articles
  • Fill JA, Ward MD (2018).  Preface.  Leibniz International Proceedings in Informatics, LIPIcs.  110.
  • Fill JA, Hung WC (2018).  On the tails of the limiting QuickSort density.  Leibniz International Proceedings in Informatics, LIPIcs.  110.
  • Fill JA, Hung, Wei-Chun (2018).  On the tails of the limiting QuickSort density.  Electronic Communications in Probability.  submitted in February, 2018.  16 pages.
  • Fill JA (2017).  A local limit theorem for Quicksort key comparisons via multi-round smoothing.  Journal of Discrete Algorithms.  submitted in January, 2017.  29 pages..
  • Fill JA, Lyzinski V (2016).  Strong Stationary Duality for Diffusion Processes.  Journal of Theoretical Probability.  29(4).
  • Clément J, Fill JA, Nguyen Thi TH, Vallée B (2016).  Towards a Realistic Analysis of the QuickSelect Algorithm.  Theory of Computing Systems.  58(4).
  • Fill JA, Clément J, Nguyen Thi T, Vallée B (2015).  Towards a realistic analysis of the QuickSelect algorithm.  Theory of Computing Systems.  51.
  • Fill JA, Lyzinski V (2015).  Strong stationary duality for diffusion processes.  Journal of Theoretical Probability.  41.
  • Fill JA, Matterer J (2014).  Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find.  Combinatorics Probability and Computing.  23(5).
  • Fill JA, Lyzinski V (2014).  Hitting Times and Interlacing Eigenvalues: A Stochastic Approach Using Intertwinings.  Journal of Theoretical Probability.  27(3).
  • Fill JA, Kahn J (2013).  Comparison inequalities and fastest-mixing Markov chains.  Annals of Applied Probability.  23(5).
  • Fill JA, Nakama T (2013).  Distributional convergence for the number of symbol comparisons used by QuickSelect.  Advances in Applied Probability.  45(2).
  • Fill JA (2013).  Distributional convergence for the number of symbol comparisons used by quicksort.  Annals of Applied Probability.  23(3).
  • Fill JA, Janson S (2012).  The number of bit comparisons used by Quicksort: An average-case analysis.  Electronic Journal of Probability.  17.
  • Fill JA, Janson S, Ward MD (2012).  Partitions with distinct multiplicities of parts: On an "unsolved problem" posed by Herbert Wilf.  Electronic Journal of Combinatorics.  19(2).
  • Beer E, Janson S, Fill JA, Scheinerman ER (2011).  On vertex, edge, and vertex-edge random graphs.  Electronic Journal of Combinatorics.  18(1).
  • Beer E, Fill JA, Janson S, Scheinerman ER (2011).  On vertex, edge, and vertex-edge random graphs.  8th Workshop on Analytic Algorithmics and Combinatorics 2011, ANALCO 2011.
  • Fill JA, Nakama T (2010).  Analysis of the expected number of bit comparisons required by quickselect.  Algorithmica (New York).  58(3).
  • Fill JA, Huber ML (2010).  Perfect simulation of vervaat perpetuities.  Electronic Journal of Probability.  15.
  • Vallée B, Clément J, Fill JA, Flajolet P (2009).  The number of symbol comparisons in quicksort and quickselect.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  5555 LNCS(PART 1).
  • Fill JA (2009).  On hitting times and fastest strong stationary times for skip-free and more general chains.  Journal of Theoretical Probability.  22(3).
  • Fill JA (2009).  The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof.  Journal of Theoretical Probability.  22(3).
  • Fill JA, Janson S (2009).  Precise logarithmic asymptotics for the right tails of some limit random variables for random trees.  Annals of Combinatorics.  12(4).
  • Fill JA, Nakama T (2008).  Analysis of the expected number of bit comparisons required by quickselect.  Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics.
  • Fill JA, Wilson DB (2008).  Two-player knock ’em down.  Electronic Journal of Probability.  13.
  • Panario D, Sedgewick B, Fill J, Frieze A, Hitczenko P, Hwang HK, Martinez C, Mitzenmacher M, Munro I, Neininger R, Schaeffer G, Sedgewick R, Flajolet P, Szpankowski W (2007).  Analco workshop preface.  Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics.
  • Fill JA, Kapur N, Panholzer A (2006).  Destruction of very simple trees.  Algorithmica (New York).  46(3-4).
  • Fill J, Golin M, Jacquet P, Kenyan C, McDiarmid C, Panario D, Sedgewick R, Viola A, Ward M, Flajolet P, Szpankowski W (2006).  Analco workshop preface.  Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics.  2006.
  • Fill JA, Kapur N (2005).  Transfer theorems and asymptotic distributional results for m-ary search trees.  Random Structures and Algorithms.  26(4).
  • Fill JA, Flajolet P, Kapur N (2005).  Singularity analysis, Hadamard products, and tree recurrences.  Journal of Computational and Applied Mathematics.  174(2).
  • Fill JA, Kapur N (2004).  Limiting distributions for additive functionals on Catalan trees.  Theoretical Computer Science.  326(1-3).
  • Fill JA, Torcaso F (2004).  Asymptotic analysis via Mellin transforms for small deviations in L 2-norm of integrated Brownian sheets.  Probability Theory and Related Fields.  130(2).
  • Fill JA, Janson S (2004).  The Number of Bit Comparisons Used by Quicksort: An Average-case Analysis.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.  15.
  • Torcaso F, Fill J (2004).  Asymptotic analysis via Mellin transforms for the L2 small ball of integrated Brownian sheet.  Probability Theory & Related Fields.  130(2).  pp. 259-288.
  • Dobrow RP, Fill JA (2003).  Speeding up the FMMR Perfect Sampling Algorithm: A Case Study Revisited.  Random Structures and Algorithms.  23(4).
  • Fill JA, Janson S (2002).  Quicksort asymptotics.  Journal of Algorithms.  44(1).
  • Fill JA, Janson S (2001).  Approximating the limiting quicksort distribution.  Random Structures and Algorithms.  19(3-4).
  • Fill JA, Machida M (2001).  Stochastic monotonicity and realizable monotonicity.  Annals of Probability.  29(2).
  • Fill JA, Janson S (2001).  Approximating the limiting quicksort distribution.  Random Structures and Algorithms.  19(3-4).
  • Fill JA, Schoolfield CH (2001).  Mixing times for markov chains on wreath products and related homogeneous spaces.  Electronic Journal of Probability.  6.
  • Fill JA, Huber M (2000).  Randomness recycler: A new technique for perfect sampling.  Annual Symposium on Foundations of Computer Science - Proceedings.
  • Fill JA, Scheinerman ER, Singer-Cohen KB (2000).  Random intersection graphs when m= ω(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models.  Random Structures and Algorithms.  16(2).
  • Fill JA, Machida M, Murdoch DJ, Rosenthal JS (2000).  Extension of fill's perfect rejection sampling algorithm to general chains.  Random Structures and Algorithms.  17(3-4).
  • Fill JA, Janson S (2000).  A characterization of the set of fixed points of the quicksort transformation.  Electronic Communications in Probability.  5.
  • Fill JA, Fishkind DE (1999).  The Moore-Penrose generalized inverse for sums of matrices.  SIAM Journal on Matrix Analysis and Applications.  21(2).
  • Dobrow RP, Fill JA (1999).  Total Path Length for Random Recursive Trees.  Combinatorics Probability and Computing.  8(4).
  • Fill JA (1998).  The move-to-front rule: A case study for two perfect sampling algorithms.  Probability in the Engineering and Informational Sciences.  12(3).
  • Fill JA, Fishkind DE, Scheinerman ER (1998).  Affine Isomorphism for Partially Ordered Sets.  Order.  15(2).
  • Fill JA (1998).  An interruptible algorithm for perfect sampling via Markov chains.  Annals of Applied Probability.  8(1).
  • Fill JA (1997).  Interruptible algorithm for perfect sampling via Markov chains.  Conference Proceedings of the Annual ACM Symposium on Theory of Computing.
  • Fill JA, Dobrow RP (1997).  The Number of m-ary Search Trees on n Keys.  Combinatorics Probability and Computing.  6(4).
  • Dette H, Fill JA, Pitman J, Studden WJ (1997).  Wall and Siegmund Duality Relations for Birth and Death Chains with Reflecting Barrier.  Journal of Theoretical Probability.  10(2).
  • Fill JA (1996).  Limits and rates of convergence for the distribution of search cost under the move-to-front rule.  Theoretical Computer Science.  164(1-2).
  • Fill JA (1996).  On the distribution of binary search trees under the random permutation model.  Random Structures and Algorithms.  8(1).
  • Dobrow RP, Fill JA (1996).  Multiway trees of maximum and minimum probability under the random permutation model.  Combinatorics Probability and Computing.  5(4).
  • Fill JA, Holst L (1996).  On the distribution of search cost for the move-to-front rule.  Random Structures and Algorithms.  8(3).
  • Fill JA, Mahmoud HM, Szpankowski W (1996).  On the distribution for the duration of a randomized leader election algorithm.  Annals of Applied Probability.  6(4).
  • Fill JA (1996).  An exact formula for the move-to-front rule for self-organizing lists.  Journal of Theoretical Probability.  9(1).
  • Fill JA (1992).  Strong stationary duality for continuous-time Markov chains. Part I: Theory.  Journal of Theoretical Probability.  5(1).
  • Diaconis P, Fill JA, Pitman J (1992).  Analysis of Top To Random Shuffles.  Combinatorics, Probability and Computing.  1(2).
  • Fill JA (1991).  Time to stationarity for a continuous-time markov chain.  Probability in the Engineering and Informational Sciences.  5(1).
  • Diaconis P, Fill JA (1990).  Examples for the theory of strong stationary duality with countable state spaces.  Probability in the Engineering and Informational Sciences.  4(2).
  • Fill JA (1989).  Asymptotic expansions for large deviation probabilities in the strong law of large numbers.  Probability Theory and Related Fields.  81(2).
  • Fill JA, Wichura MJ (1989).  The convergence rate for the strong law of large numbers: General lattice distributions.  Probability Theory and Related Fields.  81(2).
  • Fill J (1987).  The convergence rate for the strong law of large numbers: General lattice distributions.  Stochastic Processes and their Applications.  26(C).
  • Fill JA, Bollobás B, Riordan O (2017).  A local limit theorem for Quicksort key comparisons via multi-round smoothing.  Journal of Discrete Algorithms.  29.
  • Fill JA, Janson S  The sum of powers of subtree sizes for conditioned Galton-Watson trees.  Random Structures and Algorithms.
  • "A local limit theorem for QuickSort key comparisons via multi-round smoothing", AofA 2017: 28th Intl. Mtg. on Probab., Combin. & Asymptotic Methods for Analysis of Algorithms.  Princeton New Jersey, United States of America (the).  June 20, 2017
  • "A local limit theorem for QuickSort key comparisons via multi-round smoothing", Joint Applied Mathematics and Statistics Colloquium.  Baltimore Maryland, United States of America (the).  April 7, 2017
  • "A local limit theorem for QuickSort key comparisons via multi-round smoothing", Workshop in Analytic and Probabilistic Combinatorics.  Banff International Research Station for Mathematical Innovation and Discovery in Banff, Alberta, Canada.  October 25, 2016
  • "A local limit theorem for QuickSort key comparisons via multi-round smoothing", Stochastic Models V.  Mathematical Research and Conference Center in Bedlewo, Poland.  September 14, 2016
  • "A local limit theorem for QuickSort key comparisons via multi-round smoothing", Probabilistic and Extremal Combinatorics Downunder.  Monash University, Melbourne, Australia.  June 13, 2016
  • "Probabilistic Analysis of QuickSort: An Overview", Workshop on Algorithms and Applications (In Honor of Ed Reingold's Contributions on his 70th Birthday).  Illinois Institute of Technology.  October 12, 2015
  • "Probabilistic Analysis of QuickSort: An Overview", Conference in Honour of Svante Janson's 60th Birthday.  Uppsala, Sweden.  June 1, 2015
  • "Limiting Distributions for Residual Costs, for Key Comparisons, Symbol Comparisons, and Other Cost Functions: Scale Mixtures of Gaussian Laws", AofA 2015: The 26th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms.  Strobl (near Salzburg), Austria.  June 1, 2015
  • "Probabilistic Analysis of QuickSort: An Overview", Conference on Probability Theory and Combinatorial Optimization.  Duke University.  March 1, 2015
  • "Probabilistic Analysis of QuickSort: An Overview", George Mason University, Mathematical Sciences Colloquium.  George Mason University, Mathematical Sciences.  January 23, 2015
Back to top