×

On the Horton-Strahler number for random tries. (English) Zbl 0867.68087

Summary: We consider random tries constructed from i.i.d. sequences of independent Bernoulli \((p)\) random variables, \(0<p<1\). We study the Horton-Strahler number \(H_n\), and show that \[ \frac{H_n}{\log n}\to \frac{1}{\log \frac{1}{\min(p,1-p)}} \] in probability as \(n\to\infty\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1 A. V. AHO. , J. E. HOPCROFT and J. D. ULLMAN, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983. Zbl0487.68005 MR666695 · Zbl 0487.68005
[2] 2 D. ARQUÈS, N. JANEY and X. G. VIENNOTModélisation de la croissance et de la forme de structures arborescentes par matrice d’évolution. In Actes de MICAD’91, Paris, 1991, pp. 321-336.
[3] 3. L. DEVROYE, A note ontheprobabilistic analysis of Patricia trees, Random Structures and Algorithms, 1992, 3, pp. 203-214 Zbl0768.05083 MR1151362 · Zbl 0768.05083 · doi:10.1002/rsa.3240030209
[4] 4. L. DEVROYE and P. KRUSZEWSKI, A note on the Horton-Strahler number for random trees, Information Processing Letters, 1994, 52, pp. 155-159. Zbl0809.05031 MR1302588 · Zbl 0809.05031 · doi:10.1016/0020-0190(94)00135-9
[5] 5. A. P. ERSHOV, On programming of arithmetic operations, Communications of the ACM, 1958, 1, pp. 3-6. Zbl0086.33203 · Zbl 0086.33203 · doi:10.1145/368892.368907
[6] 6. R. FAGIN, J. NIEVERGELT, N. PIPPENGER and H. R. STRONG, Extendible hashing - a fast access method for dynamic files, ACM Transactions on Database Systems, 1979, 4, pp. 315-344.
[7] 7. P. FLAJOLET, J. C. RAOULT and J. VUILLEMIN, The number of registers required for evaluating arithmetic expressions, Theoretical Computer Science, 1979, 9, pp. 99-125. Zbl0407.68057 MR535127 · Zbl 0407.68057 · doi:10.1016/0304-3975(79)90009-4
[8] 8. J. FRANÇON, Sur le nombre de registres nécessaires à l’évaluation d’une expression arithmétique, RAIRO Theoretical Informatics, 1984, 18, pp. 355-364. Zbl0547.68041 MR775838 · Zbl 0547.68041
[9] 9. E. H. FREDKIN, Trie memory, Communications of the ACM, 1960, 3, pp. 490-500.
[10] 10. W. HOEFFDING, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 1963, 58, pp. 13-30. Zbl0127.10602 MR144363 · Zbl 0127.10602 · doi:10.2307/2282952
[11] 11. R. E. HORTON, Erosional development of streams and their drainage basins; hydrophysical approach to quantitative morphology, Bulletin of the Geological Society of America, 1945, 56, pp. 275-370.
[12] 12. P. JACQUET and W. SZPANKOWSKI, Analysis of digital tries with Markovian dependency, IEEE Transactions on Information Theory, 1991, IT37, pp. 1470-1475.
[13] 13. R. KEMP, The average number of registers needed to evaluate a binary tree optimally, Acta Informatica, 1979, 11, pp. 363-372. Zbl0395.68059 MR533482 · Zbl 0395.68059 · doi:10.1007/BF00289094
[14] 14. D. E. KNUTH, The Art of Computer Programming. Sorting and Searching, volume 3, Addison-Wesley, Reading, MA, 1973. MR378456 · Zbl 0302.68010
[15] 15. P. KRUSZEWSKI, A probabilistic exploration of the Horton-Strahler number for random binary trees, Master’s thesis, School of Computer Science, McGill University, 1993.
[16] 16. P. A. LARSON, Dynamic hashing. BIT, 1978, 75, pp. 184-201. Zbl0377.68026 MR483823 · Zbl 0377.68026 · doi:10.1007/BF01931695
[17] 17. W. LITWIN, Trie hashing. In Proceedings of the ACM - SIGMOD Conf. MOD., Ann Arbor, Michigan, 1981.
[18] 18. A. MEIR and J. W. MOON, Stream lengths in random channel networks, Congressus Numerantium, 1980, 33, pp. 25-33. Zbl0496.94020 MR681917 · Zbl 0496.94020 · doi:10.1137/0601005
[19] 19. A. MEIR, J. W. MOON and J. R. POUNDER, On the order of random channel networks, SIAM Journal of Algebraic and Discrete Methods, 1980, 1, pp. 25-33. Zbl0496.94020 MR563011 · Zbl 0496.94020 · doi:10.1137/0601005
[20] 20. J. W. MOON, On Horton’s law for random channel networks, Annals of Discrete Mathematics, 1980, 8, pp. 117-121. Zbl0443.05035 MR597163 · Zbl 0443.05035
[21] 21. J. G. PENAUD, Matrice de ramification des arbres binaires, Discrete Applied Mathematics, 1991, 31, pp. 1-21. Zbl0732.05038 MR1097523 · Zbl 0732.05038 · doi:10.1016/0166-218X(91)90028-U
[22] 22. B. PITTEL, Asymptotic growth of a class of random trees, Annals of Probability, 1985, 18, pp. 414-427. Zbl0563.60010 MR781414 · Zbl 0563.60010 · doi:10.1214/aop/1176993000
[23] 23. H. PRODINGER, Solution of a problem of Yekutieli and Mandelbrot, Technical report, Technical University of Vienna, Austria, 1995.
[24] 24. A. N. STRAHLER, Hypsometric (area-altitude) analysis of erosional topology, Bulletin of the Geological Society of America, 1952, 63, pp. 1117-1142.
[25] 25. J. VANNIMENUS and X. G. VIENNOT, Combinatorial Tools for the Analysis of Ramified Patterns, Journal of Statistical Physics, 1989, 54, pp. 1529-1539. MR993071
[26] 26. M. VAUCHAUSSADE de CHAUMONT, Nombre de Strahler des arbres, langages algébriques et dénombrement des structures secondaires en biologie moléculaire, PhD thesis, Université de Bordeaux I, 1985.
[27] 27. M. VAUCHAUSSADE de CHAUMONT and X. G. VIENNOT, Enumeration of RNAs secondary structures by complexity, Mathematics in Medicine and Biology, Lecture Notes in Biomathematics, 1985, 57, pp. 360-365. Zbl0579.92012 · Zbl 0579.92012
[28] 28. X. G. VIENNOT, Trees everywhere. In A. Arnold ed., Proceedings of the 15th Colloquium on Trees in Algebra and Programming, Copenhagen, Denmark, May 15-18, 1990, Lecture Notes in Computer Science, Springer-Verlag, Berlin 1990, volume 431, pp. 18-41. Zbl0785.68092 MR1075020 · Zbl 0785.68092
[29] 29. X. G. VIENNOT, G. EYROLLES, N. JANEY and D. ARQUÈS, Combinatorial analysis of ramified pattems and computer imagery of trees. In Proceedings of SIGGRAPH’89, Computer Graphics, 1989, volume 23, pp. 31-40.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.