LIPIcs.AofA.2020.4.pdf
- Filesize: 0.56 MB
- 19 pages
Document
Two Arithmetical Sources and Their Associated Tries
Authors
-
Part of:
Volume:
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-10
Cite As Get BibTex
Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.AofA.2020.4
Abstract
This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.
Subject Classification
ACM Subject Classification
- Theory of computation → Pattern matching
- Theory of computation → Randomness, geometry and discrete structures
Keywords
- Combinatorics of words
- Information Theory
- Probabilistic analysis
- Analytic combinatorics
- Dirichlet generating functions
- Sources
- Partitions
- Trie structure
- Continued fraction expansion
- Farey map
- Sturm words
- Transfer operator
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- V. Baladi and B. Vallée. Euclidean algorithms are Gaussian. J. Number Theory, 110(2):331-386, 2005. URL: https://doi.org/10.1016/j.jnt.2004.08.008.
- V. Berthé. Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci., 165(2):295-309, 1996. URL: https://doi.org/10.1016/0304-3975(95)00224-3.
- P. Cénac, B. Chauvin, F. Paccaut, and N. Pouyanne. Uncommon suffix tries. Random Structures Algorithms, 46(1):117-141, 2015. URL: https://doi.org/10.1002/rsa.20500.
- E. Cesaratto and B. Vallée. Gaussian distribution of trie depth for strongly tame sources. Combin. Probab. Comput., 24(1):54-103, 2015. URL: https://doi.org/10.1017/S0963548314000741.
- J. Clément, P. Flajolet, and B. Vallée. Dynamical sources in information theory: a general analysis of trie structures. Algorithmica, 29(1-2):307-369, 2001. URL: https://doi.org/10.1007/BF02679623.
- D. Dolgopyat. On decay of correlations in Anosov flows. Ann. of Math. (2), 147(2):357-390, 1998. URL: https://doi.org/10.2307/121012.
- P. Flajolet. Singularity analysis and asymptotics of Bernoulli sums. Theoret. Comput. Sci., 215(1-2):371-381, 1999. URL: https://doi.org/10.1016/S0304-3975(98)00220-5.
- P. Flajolet and R. Sedgewick. Digital search trees revisited. SIAM J. Comput., 15(3):748-767, 1986. URL: https://doi.org/10.1137/0215054.
- P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: finite differences and Rice’s integrals. Theoret. Comput. Sci., 144(1-2):101-124, 1995. URL: https://doi.org/10.1016/0304-3975(94)00281-M.
- P. Flajolet and R. Sedgewick. Analytic combinatorics. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511801655.
-
P. Flajolet and B. Vallée. Continued fractions, comparison algorithms, and fine structure constants. In Constructive, experimental, and nonlinear analysis (Limoges, 1999), volume 27 of CRC Math. Model. Ser., pages 53-82. CRC, Boca Raton, FL, 2000.
-
G. H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures: in Pascal and C. Addison-Wesley, Reading, MA, second edition, 1991.
- R. R. Hall. A note on Farey series. J. London Math. Soc. (2), 2:139-148, 1970. URL: https://doi.org/10.1112/jlms/s2-2.1.139.
- S. Kanemitsu, R. Sitaramachandra Rao, and A. Siva Rama Sarma. Some sums involving Farey fractions. I. J. Math. Soc. Japan, 34(1):125-142, 1982. URL: https://doi.org/10.2969/jmsj/03410125.
-
A. Ya. Khinchin. Continued fractions. The University of Chicago Press, Chicago, Ill.-London, 1964.
- N. Moshchevitin and A. Zhigljavsky. Entropies of the partitions of the unit interval generated by the Farey tree. Acta Arith., 115(1):47-58, 2004. URL: https://doi.org/10.4064/aa115-1-4.
-
N. E. Nörlund. Lecons sur les équations linéaires aux différences finies. Collection de monographies sur la théorie des fonctions. Gauthier-Villars, Paris, 1929.
-
N. E. Nörlund. Vorlesungen über Differenzenrechnung. Chelsea Publishing Company, New York, 1954.
- T. Prellberg and J. Slawny. Maps of intervals with indifferent fixed points: thermodynamic formalism and phase transitions. J. Statist. Phys., 66(1-2):503-514, 1992. URL: https://doi.org/10.1007/BF01060077.
- W. Szpankowski. Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2001. URL: https://doi.org/10.1002/9781118032770.
-
G. Tenenbaum. Introduction à la théorie analytique et probabiliste des nombres, volume 1 of Cours Spécialisés [Specialized Courses]. Société Mathématique de France, Paris, second edition, 1995.
- B. Vallée. Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss. Acta Arith., 81(2):101-144, 1997. URL: https://doi.org/10.4064/aa-81-2-101-144.
- B. Vallée. Dynamical sources in information theory: fundamental intervals and word prefixes. Algorithmica, 29(1-2):262-306, 2001. URL: https://doi.org/10.1007/BF02679622.
- B. Vallée. The depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume 110 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 35, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Long version http://arxiv.org/pdf/1802.04988. URL: https://doi.org/10.4230/LIPIcs.AofA.2018.35.