{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:21Z","timestamp":1759637601416},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,12,11]],"date-time":"2014-12-11T00:00:00Z","timestamp":1418256000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The depth of a trie has been deeply studied when the source which produces the words is a simple source (a memoryless source or a Markov chain). When a source is simple but not an unbiased memoryless source, the expectation and the variance are both of logarithmic order and their dominant terms involve characteristic objects of the source, for instance the entropy. Moreover, there is an asymptotic Gaussian law, even though the speed of convergence towards the Gaussian law has not yet been precisely estimated. The present paper describes a \u2018natural\u2019 class of general sources, which does not contain any simple source, where the depth of a random trie, built on a set of words independently drawn from the source, has the same type of probabilistic behaviour as for simple sources: the expectation and the variance are both of logarithmic order and there is an asymptotic Gaussian law. There are precise asymptotic expansions for the expectation and the variance, and the speed of convergence toward the Gaussian law is optimal. The paper first provides analytical conditions on the Dirichlet series of probabilities of a general source under which this Gaussian law can be derived: a pole-free region where the series is of polynomial growth. In a second step, the paper focuses on sources associated with dynamical systems, called dynamical sources, where the Dirichlet series of probabilities is expressed with the transfer operator of the dynamical system. Then, the paper extends results due to Dolgopyat, already generalized by Baladi and Vall\u00e9e, and shows that the previous analytical conditions are fulfilled for \u2018most\u2019 dynamical sources, provided that they \u2018strongly differ\u2019 from simple sources. Finally, the present paper describes a class of sources not containing any simple source, where the trie depth has the same type of probabilistic behaviour as for simple sources, even with more precise estimates.<\/jats:p>","DOI":"10.1017\/s0963548314000741","type":"journal-article","created":{"date-parts":[[2014,12,11]],"date-time":"2014-12-11T12:23:24Z","timestamp":1418300604000},"page":"54-103","source":"Crossref","is-referenced-by-count":5,"title":["Gaussian Distribution of Trie Depth for Strongly Tame Sources"],"prefix":"10.1017","volume":"24","author":[{"given":"EDA","family":"CESARATTO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BRIGITTE","family":"VALL\u00c9E","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,12,11]]},"reference":[{"key":"S0963548314000741_ref9","unstructured":"Cl\u00e9ment J. , Nguyen Thi T. H. and Vall\u00e9e B. Towards a realistic analysis of some popular sorting algorithms. Combin. Probab. Comput."},{"key":"S0963548314000741_ref34","first-page":"199","volume-title":"Proc. 8th International Conference: WORDS 2011","author":"Roux","year":"2011"},{"key":"S0963548314000741_ref37","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770"},{"key":"S0963548314000741_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10015"},{"key":"S0963548314000741_ref14","first-page":"231","volume-title":"Proc. AofA'10","author":"Flajolet","year":"2010"},{"key":"S0963548314000741_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385798117431"},{"key":"S0963548314000741_ref5","unstructured":"Cesaratto E. and Vall\u00e9e B. (2007) Distribution of the average external depth for tries in dynamical sources context. In Proc. Logic Computability and Randomness 2007, pp. 33\u201334."},{"key":"S0963548314000741_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<428::AID-RSA12>3.0.CO;2-6"},{"key":"S0963548314000741_ref7","unstructured":"Cl\u00e9ment J. , Fill J. A. , Nguyen Thi T. and Vall\u00e9e B. Towards a realistic analysis of the QuickSelect algorithm. In Theory of Computing Systems, special issue for STACS 2013, to appear."},{"key":"S0963548314000741_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800015846"},{"key":"S0963548314000741_ref35","volume-title":"Thermodynamic Formalism","author":"Ruelle","year":"1978"},{"key":"S0963548314000741_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0053-3"},{"key":"S0963548314000741_ref20","first-page":"1","volume-title":"Proc. ANALCO'14","author":"Hun","year":"2014"},{"key":"S0963548314000741_ref27","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S0963548314000741_ref21","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0179"},{"key":"S0963548314000741_ref13","first-page":"1","volume-title":"Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science: STACS 2006","author":"Flajolet","year":"2006"},{"key":"S0963548314000741_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnt.2004.08.008"},{"key":"S0963548314000741_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0215054"},{"key":"S0963548314000741_ref18","first-page":"627","article-title":"Sur un th\u00e9or\u00e8me spectral et son application aux noyaux lipchitziens","volume":"118","author":"Hennion","year":"1993","journal-title":"Proc. Amer. Math. Soc"},{"key":"S0963548314000741_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/18.133271"},{"key":"S0963548314000741_ref17","first-page":"55","volume-title":"Constructive, Experimental, and Nonlinear Analysis","author":"Flajolet","year":"2000"},{"key":"S0963548314000741_ref10","doi-asserted-by":"publisher","DOI":"10.2307\/121012"},{"key":"S0963548314000741_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00298-W"},{"key":"S0963548314000741_ref38","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4064\/aa-81-2-101-144","article-title":"Op\u00e9rateurs de Ruelle\u2013Mayer g\u00e9n\u00e9ralis\u00e9s et analyse en moyenne des algorithmes de Gauss et d'Euclide","volume":"81","author":"Vall\u00e9e","year":"1997","journal-title":"Acta Arith."},{"key":"S0963548314000741_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679623"},{"key":"S0963548314000741_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35208-4"},{"key":"S0963548314000741_ref31","volume-title":"Collection de Monographies sur la Th\u00e9orie des Fonctions","author":"N\u00f6rlund","year":"1929"},{"key":"S0963548314000741_ref19","unstructured":"Hun K. (2014) Analysis of depth of digital trees built on general sources. PhD thesis, University of Caen."},{"key":"S0963548314000741_ref26","volume-title":"Perturbation Theory for Linear Operators","author":"Kato","year":"1980"},{"key":"S0963548314000741_ref30","doi-asserted-by":"publisher","DOI":"10.1109\/18.567640"},{"key":"S0963548314000741_ref4","first-page":"5","article-title":"Transformations dilatantes de l'intervalle et th\u00e9or\u00e8mes limites","volume":"238","author":"Broise","year":"1996","journal-title":"Ast\u00e9risque"},{"key":"S0963548314000741_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/18.370149"},{"key":"S0963548314000741_ref33","unstructured":"Roux M. (2011) S\u00e9ries de Dirichlet, th\u00e9orie de l'information, et analyse d'algorithmes. PhD thesis, University of Caen."},{"key":"S0963548314000741_ref32","volume-title":"Vorlesungen \u00fcber Differenzenrechnung","author":"N\u00f6rlund","year":"1954"},{"key":"S0963548314000741_ref40","first-page":"750","volume-title":"Proc. ICALP 2009, part I","author":"Vall\u00e9e","year":"2009"},{"key":"S0963548314000741_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1057-y"},{"key":"S0963548314000741_ref1","doi-asserted-by":"publisher","DOI":"10.1142\/3657"},{"key":"S0963548314000741_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679622"},{"key":"S0963548314000741_ref22","first-page":"196","volume-title":"Proc. 11th Colloquium on Trees in Algebra and Programming: CAAP '86 (P. Franchi-Zannettacci","author":"Jacquet","year":"1986"},{"key":"S0963548314000741_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00281-M"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000741","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T20:53:42Z","timestamp":1555880022000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000741\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,11]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0963548314000741"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000741","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,11]]}}}