Limit Laws for Random Recursive Structures and Algorithms.
Dissertation, Universität Freiburg i. Br., iv, 96 p. (1999).
[PS] [PDF]
On the internal path length of d-dimensional quad trees.
Random Structures and Algorithms 15 (1999), no. 1, 25-41.
[ARTICLE]
Perfect simulation from the quicksort limit distribution.
Electronic Communications in Probability 5 (2000), 95-99 (electronic).
[ARTICLE] [PDF]
Asymptotic distributions for partial match queries in K-d trees.
Random Structures and Algorithms 17 (2000), no. 3-4, 403-427.
[ARTICLE]
Limit laws for partial match queries in quadtrees.
The Annals of Applied Probability 11 (2001), no. 2, 452-469.
[ARTICLE] [PDF] ©
Rates of convergence for products of random stochastic 2x2 matrices.
Journal of Applied Probability 38 (2001), no. 3, 799-806.
[ARTICLE] [PS] [PDF]
On a multivariate contraction method for random recursive structures with applications to quicksort.
Random Structures and Algorithms 19 (2001), no. 3-4, 498-524.
[ARTICLE] [PS] [PDF]
On binary search tree recursions with monomials as toll functions.
Journal of Computational and Applied Mathematics 142 (2002), no. 1, 185-196.
[ARTICLE] [PS] [PDF]
Density approximation and exact simulation of random variables that are solutions of fixed-point equations.
Advances in Applied Probability 34 (2002), no. 2, 441-468.
[ARTICLE] [PS] [PDF]
Phase change of limit laws in the quicksort recurrence under varying toll functions.
SIAM Journal on Computing 31 (2002), no. 6, 1687-1722.
[ARTICLE] [PS] [PDF]
Rates of convergence for quicksort.
Journal of Algorithms 44 (2002), no. 1, 52-62.
[ARTICLE] [PS] [PDF]
A note on random suffix search trees.
Mathematics and Computer Science II (Versailles 2002), 267-278,
Trends in Mathematics, Birkhäuser, Basel, 2002.
[ARTICLE] [PS] [PDF]
The Wiener index of random trees.
Combinatorics, Probability & Computing 11 (2002), no. 6, 587-597.
[ARTICLE] [PS] [PDF]
Distribution of distances in random binary search trees.
The Annals of Applied Probability 13 (2003), no. 1, 253 -276.
[ARTICLE] [PDF] ©
Random suffix search trees.
Random Structures and Algorithms, 23 (2003), no. 4, 357-396.
[ARTICLE] [PS] [PDF]
A general limit theorem for recursive algorithms and combinatorial structures.
The Annals of Applied Probability 14 (2004), no. 1, 378-418.
[ARTICLE] [PDF] ©
Distances and finger search in random binary search trees.
SIAM Journal on Computing 33 (2004), no. 3, 647-658.
[ARTICLE] [PS] [PDF]
On the contraction method with degenerate limit equation.
The Annals of Probability 32 (2004), no. 3B, 2838-2856.
[ARTICLE] [PDF] ©
Probabilistic analysis for randomized game tree evaluation.
Mathematics and Computer Science III (Vienna 2004), 163-174,
Trends in Mathematics, Birkhäuser, Basel, 2004.
[ARTICLE] [PS] [PDF]
Stochastische Analyse von Algorithmen, Fixpunktgleichungen und ideale Metriken.
Habilitation (kumulativ), Universität Frankfurt a. M., 45 p. (2004).
[PDF]
Analysis of algorithms by the contraction method: additive and max-recursive sequences.
Interacting Stochastic Systems, 435-450, Springer, 2005.
[ARTICLE] [PS] [PDF]
Recursive random variables with subgaussian distributions.
Statistics & Decisions, 23 (2005), no. 2, 131-146.
[ARTICLE] [PDF] ©
A limit law for the root value of minimax trees.
Electronic Communications in Probability 10 (2005), 273-281.
[ARTICLE] [PDF]
A survey of multivariate aspects of the contraction method.
Discrete Mathematics & Theoretical Computer Science 8 (2006), 31-56.
[ARTICLE] [PS] [PDF]
Profiles of random trees: Limit theorems for random recursive trees and binary search trees.
Algorithmica 46 (2006), 367-407.
[ARTICLE] [PDF]
On the Length Distribution of External Branches in Coalescence Trees: Genetic Diversity within Species.
Theoretical Population Biology, 72 (2007), 245-252.
[ARTICLE] [PDF]
A note on the approximation of perpetuities.
DMTCS Proceedings (2007 Conference on Analysis of Algorithms), (2007), 115-126.
[ARTICLE] [PS] [PDF]
Tail bounds for the Wiener index of random trees.
DMTCS Proceedings (2007 Conference on Analysis of Algorithms), (2007), 279-290.
[ARTICLE] [PS] [PDF]
A functional limit theorem for the profile of search trees.
The Annals of Applied Probability 18 (2008), 288-333.
[ARTICLE] [PDF]
The size of random fragmentation trees.
Probability Theory and Related Fields, 142 (2008), 399-442.
[ARTICLE] [PS] [PDF]
Approximating perpetuities.
Methodology and Computing in Applied Probability, 10 (2008), 507-529.
[ARTICLE] [PDF]
Partial match queries in random quadtrees.
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2012), 1056-1065,
[ARTICLE] [PDF]
Asymptotic analysis of Hoppe trees.
Journal of Applied Probability, 50 (2013), 228-238.
[ARTICLE] [PDF]
Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model.
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) (2013), 877-886.
[ARTICLE] [PDF]
Appendix to "Approximating perpetuities".
Methodology and Computing in Applied Probability, 15 (2013), 707-712.
[ARTICLE] [PDF]
A limit process for partial match queries in random quad trees and 2-d trees.
The Annals of Applied Probability, 23 (2013), 2560-2603.
[ARTICLE] [PDF]
A statistical view on exchanges in Quickselect.
Analytic Algorithmics and Combinatorics (ANALCO) (2014), 40-51.
![[ARTICLE]](art.gif)
[PDF]
A Gaussian limit process for optimal FIND algorithms.
Electronic Journal of Probability, 19 (2014), no. 3, 1-28.
[ARTICLE] [PDF]
Pólya Urns Via the Contraction Method.
Combinatorics, Probability & Computing, 23 (2014), 1148-1186.
[ARTICLE] [PDF] © Cambridge University Press
Analysis of radix selection on Markov sources.
Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms.
(Eds. M. Bousquet-Mélou, M. Soria). DMTCS-HAL Proceedings series (2014), 253-264.
[PDF]
A multiple filter test for the detection of rate changes in renewal processes with varying variance.
The Annals of Applied Statistics, 8 (2014), 2027-2067.
[PDF]
Refined Quicksort asymptotics.
Random Structures and Algorithms, 46 (2015), 346-361.
[PDF]
Average Case and Distributional Analysis of Dual Pivot Quicksort.
ACM Transactions on Algorithms, 11 (2015), Article No. 22.
[PDF]
On a functional contraction method.
The Annals of Probability, 43 (2015), 1777-1822.
[PDF]
The CLT Analogue for Cyclic Urns.
Analytic Algorithmics and Combinatorics (ANALCO) (2016), 121-127.
[PDF]
A Limit Theorem for Radix Sort and Tries with Markovian Input.
Submitted for publication.
[PDF]
Dependence and phase changes in random m-ary search trees.
Random Structures and Algorithms, 50 (2017), no. 3, 353–379.
[PDF]
Rates of convergence for balanced irreducible two-color Pólya urns.
Analytic Algorithmics and Combinatorics (ANALCO) (2017), 94-99.
[PDF]
External Profile of Symmetric Digital Search Trees (Extended Abstract).
Analytic Algorithmics and Combinatorics (ANALCO) (2017), 124-130.
[PDF]
Probabilistic Analysis of the Dual-Pivot Quicksort "Count".
Analytic Algorithmics and Combinatorics (ANALCO) (2018), 1-7.
[PDF]
Refined Asymptotics for the Composition of Cyclic Urns.
Electronic Journal of Probability, 23 (2018), no. 117, 1-20.
[PDF]
Process convergence for the complexity of Radix Selection on Markov sources.
Stochastic Processes and their Applications, 129 (2019), 507-538.
[ARTICLE] [PDF]
Convergence Rates in the Probabilistic Analysis of Algorithms.
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), (2020), 22:1-22:13.
[ARTICLE] [PDF]
Node profiles of symmetric digital search trees: Concentration properties
Random Structures and Algorithms, 58 (2021), no. 3, 430-467.
[ARTICLE] [PDF]
A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees.
Discrete Applied Mathematics, 292 (2021), 64-71.
[ARTICLE] [PDF]
On the contraction method with reduced independence assumptions.
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA22), (2022), 14:1-14:13.
[ARTICLE] [PDF]
On solutions of the distributional Bellman equation.
Electron. Res. Arch., 31 (2023), 4459-4483. Special Issue: Mathematics of Machine Learning and Related Topics.
[ARTICLE] [PDF]
On fluctuations of complexity measures for the FIND algorithm.
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA24), Art. No. 9, 15 pp, Leibniz Int. Proc. Inform., 302, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.
[ARTICLE] [PDF]
Patricia's Bad Distributions.
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA24), Art. No. 25, 8 pp, Leibniz Int. Proc. Inform., 302, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2024.
[ARTICLE] [PDF]
Bivariate change point detection in movement direction and speed.
Electronic Journal of Statistics, accepted for publication (2025)
[PDF]
Analysis of Multidimensional Search Trees for Point Data: A Selected Review.
Submitted for publication (2024)
On Policy Evaluation Algorithms in Distributional Reinforcement Learning.
Submitted for publication (2024)
[PDF]
Random 2-SAT: The set of atoms of the limiting empirical marginal distribution.
Submitted for publication (2024)
[PDF]
On fine fluctuations of the complexity of the QuickSelect algorithm.
Submitted for publication (2024)
[PDF]
Probabilistic analysis of otimal multi-pivot Quicksort.
Submitted for publication (2025)
[PDF]