{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:00Z","timestamp":1753893780018,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to $b$ items (the so called $b$-tries). We assume that such a tree is built from $n$ random strings (items) generated by an unbiased memoryless source. In this paper, we discuss the case when $b$ and $n$ are both large. We shall identify five regions of the height distribution that should be compared to three regions obtained for fixed $b$. We prove that for most $n$, the limiting distribution is concentrated at the single point $k_1=\\lfloor \\log_2 (n\/b)\\rfloor +1$ as $n,b\\to \\infty$. We observe that this is quite different than the height distribution for fixed $b$, in which case the limiting distribution is of an extreme value type concentrated around $(1+1\/b)\\log_2 n$. We derive our results by analytic methods, namely generating functions and the saddle point method. We also present some numerical verification of our results.<\/jats:p>","DOI":"10.37236\/1517","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T02:03:13Z","timestamp":1578708193000},"source":"Crossref","is-referenced-by-count":8,"title":["A Note on the Asymptotic Behavior of the Heights in $b$-Tries for $b$ Large"],"prefix":"10.37236","volume":"7","author":[{"given":"Charles","family":"Knessl","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2000,8,1]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v7i1r39\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v7i1r39\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,18]],"date-time":"2020-01-18T05:22:34Z","timestamp":1579324954000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v7i1r39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8,1]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2000,1,1]]}},"URL":"https:\/\/doi.org\/10.37236\/1517","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2000,8,1]]},"article-number":"R39"}}