The DOI matches its Crossref record; 19 of the 21 references it cites were found in a registry or an index.
A diffusion limit for a class of randomly-growing binary trees
Open accessOverview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“so that the expected compression is asymptotically well-approximated by n/log2n”
From A statistical test suite for random and pseudorandom number generators for cryptographic applications (2000) · cites this paper as Aldous and Shields (1988)
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“which implies that a central Hmit theorem holds for the number of words in the Lempel-Ziv compression.”
From A statistical test suite for random and pseudorandom number generators for cryptographic applications (2000) · cites this paper as Aldous and Shields (1988)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,000
Doob, J. L., & Doob, J. L. (1953) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,053
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Ross, S. M. (1982) · Cited by 3,812
The Theory of Stochastic Processes
Cox, D. R., Miller, H. D., Weiss, G., & Shuler, K. (1966) · Physics Today · doi:10.1063/1.3047872 · Cited by 3,324
The Theory of Stochastic Processes III
Gihman, I. I., & Skorohod, A. V. (1979) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4615-8065-2 · Cited by 1,184
The Art of Computer Programming, Vol. 2
Knuth, D. E. (1981) · Medical Entomology and Zoology · Cited by 886
Oriented Percolation in Two Dimensions
Durrett, R. T. (1984) · The Annals of Probability · doi:10.1214/aop/1176993140 · Cited by 366
Stopping Times and Tightness. II
Aldous, D. (1989) · The Annals of Probability · doi:10.1214/aop/1176991417 · Cited by 343
Self-citationCoding theorems for individual sequences
Ziv, J. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055911 · Cited by 181
Research works printed but not linked: 2
- Elliott, R.: Stochastic calculus and its applications. New York: Springer 1982
- Wignarajah, G.: Complexity tests for statistical independence. M.S. thesis, University of Toledo, 1985
Cited by
Rukhin, A., Sota, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., et al. (2000) · doi:10.6028/nist.sp.800-22 · Cited by 1,867
Probability Distributions on Cladograms
Aldous, D. (1996) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4612-0719-1_1 · Cited by 216
Self-citationAsymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
Jacquet, P., & Szpankowski, W. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00298-w · Cited by 106
Average redundancy rate of the Lempel-Ziv code
Louchard, G., & Szpankowski, W. (1997) · IEEE Transactions on Information Theory · doi:10.1109/18.567640 · Cited by 92
On the entropy of DNA: algorithms and measurements based on memory and rapid convergence
Farach-Colton, M., Noordewier, M. O., Savari, S. A., Shepp, L. A., Wyner, A. J., & Ziv, J. (1995) · doi:10.5555/313651.313662 · Cited by 81
Asymptotic Recurrence and Waiting Times for Stationary Processes
Kontoyiannis, I. (1998) · Journal of Theoretical Probability · doi:10.1023/a:1022610816550 · Cited by 76
Asymptotic properties of data compression and suffix trees
Szpankowski, W. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.259648 · Cited by 75
Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees
Fuchs, M., Hwang, H., & Neininger, R. (2006) · Algorithmica · doi:10.1007/s00453-006-0109-5 · Cited by 65
Martingales and Profile of Binary Search Trees
Chauvin, B., Klein, T., Marckert, J., & Rouault, A. (2005) · Electronic Journal of Probability · doi:10.1214/ejp.v10-257 · Cited by 56
Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
Louchard, G., & Szpankowski, W. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.370149 · Cited by 55
Corrections of the NIST Statistical Test Suite for Randomness
Kim, S.-J., Umeno, K., & Hasegawa, A. (2004) · arXiv · doi:10.48550/arxiv.nlin/0401040 · Cited by 54
Generalized Digital Trees and Their Difference—Differential Equations
Flajolet, P., & Richmond, B. (1992) · Random Structures and Algorithms · doi:10.1002/rsa.3240030309 · Cited by 54
Park, G., Hwang, H., Nicodème, P., & Szpankowski, W. (2009) · SIAM Journal on Computing · doi:10.1137/070685531 · Cited by 49
Data compression and learning in time sequences analysis
Andrea Puglisi, B., Benedetto, D., Caglioti, E., Loreto, V., & Vulpiani, A. (2003) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(03)00047-2 · Cited by 45
Testing Randomness: A Suite of Statistical Procedures
Ruhkin, A. L. (2001) · Theory of Probability and Its Applications · doi:10.1137/s0040585x97978087 · Cited by 43
Digital Search Trees Again Revisited: The Internal Path Length Perspective
Kirschenhofer, P., Prodinger, H., & Szpankowski, W. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539790189368 · Cited by 43
Majumdar, S. N. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.68.026103 · Cited by 39
Analytic analysis of algorithms
Flajolet, P. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55719-9_74 · Cited by 36
Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source
Jacquet, P., Szpankowski, W., & Tang, J. (2001) · Algorithmica · doi:10.1007/s00453-001-0053-3 · Cited by 32
Analytic Pattern Matching: From DNA to Twitter
Jacquet, P., & Szpankowski, W. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9780511843204 · Cited by 31
Asymptotic variance of random symmetric digital search trees
Hwang, H., Fuchs, M., & Zacharovas, V. (2010) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.498 · Cited by 31
Laws of large numbers and tail inequalities for random tries and PATRICIA trees
Devroye, L. (2002) · Journal of Computational and Applied Mathematics · doi:10.1016/s0377-0427(01)00458-7 · Cited by 28
Diffusion-limited aggregation on a tree
Barlow, M. T., Pemantle, R., & Perkins, E. (1997) · Probability Theory and Related Fields · doi:10.1007/s004400050076 · Cited by 27
Pemantle, R. (1995) · Statistical Science · doi:10.1214/ss/1177010038 · Cited by 24
Universal Asymptotics for Random Tries and PATRICIA Trees
Devroye, L. (2005) · Algorithmica · doi:10.1007/s00453-004-1137-7 · Cited by 24
Knessl, C., & Szpankowski, W. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539799356812 · Cited by 23
Domination Between Trees and Application to an Explosion Problem
Pemantle, R., & Peres, Y. (1994) · The Annals of Probability · doi:10.1214/aop/1176988855 · Cited by 21
A note on the probabilistic analysis of patricia trees
Devroye, L. (1992) · Random Structures and Algorithms · doi:10.1002/rsa.3240030209 · Cited by 21
Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
Drmota, M., & Hwang, H. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480104440134 · Cited by 21
Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm
Louchard, G., Szpankowski, W., & Tang, J. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796301811 · Cited by 21
How many random questions are necessary to identify n distinct objects?
Pittel, B. G., & Rubin, H. (1990) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(90)90072-5 · Cited by 17
Testing randomness: a suite of statistical procedures
Rukhin, A. L., & Rukhin, A. L. (2000) · Теория вероятностей и ее применения · doi:10.4213/tvp328 · Cited by 15
Devroye, L. (2001) · Random Structures and Algorithms · doi:10.1002/rsa.10006 · Cited by 13
Stochastic explosion and non-uniqueness for α-Riccati equation
Dascaliuc, R., Thomann, E., & Waymire, E. C. (2018) · Journal of Mathematical Analysis and Applications · doi:10.1016/j.jmaa.2018.11.064 · Cited by 12
Park, G., Hwang, H., Nicodème, P., & Szpankowski, W. (2008) · Springer eBooks · doi:10.1007/978-3-540-78773-0_1 · Cited by 11
Connecting Yule Process, Bisection and Binary Search Tree via MartingalesPreprint
Chauvin, B., & Rouault, A. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0410318 · Cited by 11
Generalized Lempel-Ziv parsing scheme and its preliminary analysis of the average profile
Louchard, G., & Szpankowski, W. (2002) · DCC · doi:10.1109/dcc.1995.515516 · Cited by 9
Phase Transition in a Generalized Eden Growth Model on a Tree
Dean, D. S., & Majumdar, S. N. (2006) · Journal of Statistical Physics · doi:10.1007/s10955-006-9193-9 · Cited by 8
Almost sure asymptotics for the random binary search tree
Roberts, M. I. (2010) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.2775 · Cited by 8
A functional limit theorem for the profile of b-ary trees
Schopp, E.-M. (2010) · The Annals of Applied Probability · doi:10.1214/09-aap640 · Cited by 7
Dascaliuc, R., Michalowski, N., Thomann, E., & Waymire, E. C. (2017) · Proceedings of the American Mathematical Society · doi:10.1090/proc/13905 · Cited by 7
The variance of the height of digital search trees
Drmota, M. (2002) · Acta Informatica · doi:10.1007/s236-002-8034-5 · Cited by 6
Limiting distribution of Lempel Ziv'78 redundancy
Jacquet, P., & Szpankowski, W. (2011) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2011.6033794 · Cited by 6
Doubly stochastic Yule cascades (Part I): The explosion problem in the time-reversible case
Dascaliuc, R., Pham, T. N., Thomann, E., & Waymire, E. C. (2022) · Journal of Functional Analysis · doi:10.1016/j.jfa.2022.109722 · Cited by 6
Node profiles of symmetric digital search trees: Concentration properties
Drmota, M., Fuchs, M., Hwang, H., & Neininger, R. (2020) · Random Structures and Algorithms · doi:10.1002/rsa.20979 · Cited by 5
Scaling limits of external multi-particle DLA on the plane and the supercooled Stefan problem
Nadtochiy, S., Shkolnikov, M., & Zhang, X. (2024) · Annales de l Institut Henri Poincaré Probabilités et Statistiques · doi:10.1214/22-aihp1330 · Cited by 5
A Central Limit Theorem for Non-Overlapping Return Times
Johnson, O. (2006) · Journal of Applied Probability · doi:10.1017/s0021900200001340 · Cited by 5
Behavior near the extinction time in self-similar fragmentations II: Finite dislocation measures
Goldschmidt, C., & Haas, B. (2016) · The Annals of Probability · doi:10.1214/14-aop988 · Cited by 5
Doubly stochastic Yule cascades (part II): The explosion problem in the non-reversible case
Dascaliuc, R., Pham, T. N., Thomann, E., & Waymire, E. C. (2023) · Annales de l Institut Henri Poincaré Probabilités et Statistiques · doi:10.1214/22-aihp1316 · Cited by 4
On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources
Jacquet, P., & Szpankowski, W. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2358679 · Cited by 4
Selection of a Metric for the Nearest Neighbor Entropy Estimators
Тимофеев, Е. А. (2014) · Journal of Mathematical Sciences · doi:10.1007/s10958-014-2181-8 · Cited by 3
Nearest-neighbor entropy estimators with weak metrics
Тимофеев, Е. А., & Kaltchenko, A. (2014) · Advances in Mathematics of Communications · doi:10.3934/amc.2014.8.119 · Cited by 3
A hooray for Poisson approximation
Grübel, R. (2005) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3357 · Cited by 3
Compression based homogeneity testing
Malyutov, M. B. (2012) · Doklady Mathematics · doi:10.1134/s1064562412020251 · Cited by 3
The Aldous-Shields model revisited with application to cellular ageing
Best, K., & Pfaffelhuber, P. (2010) · Electronic Communications in Probability · doi:10.1214/ecp.v15-1581 · Cited by 3
Continuous-time digital search tree and a border aggregation model
Janson, S., & Thacker, D. (2022) · Bernoulli · doi:10.3150/21-bej1429 · Cited by 2
Digital search trees and chaos game representation
Cénac, P., Chauvin, B., Ginouillac, S., & Pouyanne, N. (2008) · ESAIM Probability and Statistics · doi:10.1051/ps:2007043 · Cited by 2
A Markovian Growth Dynamics on Rooted Binary Trees Evolving According to the Gompertz Curve
Landim, C., Portugal, R. D., & Svaiter, B. F. (2012) · Journal of Statistical Physics · doi:10.1007/s10955-012-0549-z · Cited by 2
A functional equation often arising in the analysis of algorithms (extended abstract)
Jacquet, P., & Szpankowski, W. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195456 · Cited by 2
Growing binary trees in a random environment
Kessler, I., & Sidi, M. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.179356 · Cited by 2
Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme
Knessl, C., & Szpankowski, W. (2000) · Symposium on Discrete Algorithms · doi:10.5555/338219.338251 · Cited by 2
Analysis of Lempel-Ziv'78 for Markov Sources
Jacquet, P., & Szpankowski, W. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.aofa.2020.15 · Cited by 1
Concentration Properties of Extremal Parameters in Random Discrete Structures
Drmota, M. (2006) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3517 · Cited by 1
Flajolet, P. (2001) · Random Structures and Algorithms · doi:10.1002/rsa.10022 · Cited by 1
Growing binary trees in a random environment
Kessler, I., & Sidi, M. (1991) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.1991.147565 · Cited by 1
Discs and other related data structures
Luccio, F., Régnier, M., & Schott, R. (1989) · Lecture notes in computer science · doi:10.1007/3-540-51542-9_17 · Cited by 1
The height of symmetric digital search trees: two-point concentration and the law of the heightPreprint
Na, S. (2026) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.23132297 · Cited by 1
An integer-visiting process with real multipliers: coverage and ratesPreprint
Na, S. (2026) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.23138274 · Cited by 1
Asymptotic behavior of the Lempel-Ziv parsing scheme and digital trees
Jacquet, P., & Szpankowski, W. (2002) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.1995.531116
Discovery of patterns in LZ-78 text discrimination
Malyutov, M. B., & Cunningham, G. (2010) · IEEE Region International Conference on Computational Technologies in Electrical and Electronics Engineering · doi:10.1109/sibircon.2010.5555303
GROWING BINARY TREES IN A RANDOM
Kesslert, I., & Sidi, M. (1991)
SCOT-Modeling and Nonparametric Testing of Stationary Strings
Ryabko, B. Y., Astola, J. T., & Malyutov, M. B. (2016) · Springer eBooks · doi:10.1007/978-3-319-32253-7_3
Szpankowski, W. (2001) · Wiley eBooks · doi:10.1002/9781118032770.biblio
Continuous Parameter Jump Markov Processes
Bhattacharya, R. N., & Waymire, E. C. (2023) · Graduate texts in mathematics · doi:10.1007/978-3-031-33296-8_4
Metadata
- Authors
- Aldous, D., & Shields, P.
- Affiliations
- University of California, Berkeley (US)
- University of Toledo (US)
- ORCID
- Aldous, David
- Venue
- Probability Theory and Related Fields
- Published
- 1988-11
- Volume
- 79
- Issue
- 4
- Pages
- 509-542
- ISSN
- 0178-8051 (ISSN-L)
- 1432-2064
- OpenAlex
- W2052638374
- Cited by
- 78
- References
- 21
- Citations by year
- 2026: 2 · 2024: 1 · 2023: 2 · 2022: 2 · 2020: 2 · 2018: 1 · 2017: 2 · 2016: 2 · 2015: 1 · 2014: 3 · 2012: 2
- FWCI
- 2.01
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.springer.com/tdm (tdm)
- www.springer.com/tdm (vor)
- Locations
- Probability Theory and Related Fields (publishedVersion)
- eScholarship (California Digital Library) (submittedVersion)
- Funders
- National Science Foundation
- Magyar Tudományos Akadémia
- Topics
- Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Mathematics › Mathematical Physics › Mathematical Dynamics and Fractals
- Keywords
- random binary trees, diffusion limit, strong law of large numbers, central limit theorem, tree height distribution, asymptotic normality, entropy estimation, maximum tree height
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
