Renewal theory in the analysis of tries and strings

Asmussen, 1987 Athreya, 1978, Limit theorems for semi-Markov processes and renewal theory for Markov chains, Ann. Probab., 6, 788, 10.1214/aop/1176995429 Billingsley, 1968 N. Broutin, C. Holmgren, The total path length of split trees. Ann. Appl. Probab. (in press). arXiv:1102.2541. Bourdon, 2001, Size and path length of Patricia tries: dynamical sources context, Rand. Struct. Algorithms, 19, 289, 10.1002/rsa.10015 Christophi, 2008, On climbing tries, Probab. Engrg. Inform. Sci., 22, 133, 10.1017/S0269964808000089 Clément, 2001, Dynamical sources in information theory: a general analysis of trie structures, Algorithmica, 29, 307, 10.1007/BF02679623 Dennert, 2007, Renewals for exponentially increasing lifetimes, with an application to digital search trees, Ann. Appl. Probab., 17, 676, 10.1214/105051606000000862 Devroye, 2011, Long and short paths in uniform random recursive dags, Ark. Mat., 49, 61, 10.1007/s11512-009-0118-0 M. Drmota, Y. Reznik, S. Savari, W. Szpankowski, Precise asymptotic analysis of the Tunstall code, in: Proc. 2006 International Symposium on Information Theory, Seattle, 2006, pp. 2334–2337. Drmota, 2010, Tunstall code, Khodak variations, and random walks, IEEE Trans. Inform. Theory, 56, 2928, 10.1109/TIT.2010.2046248 M. Drmota, W. Szpankowski, On the exit time of a random walk with positive drift, in: Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07, Juan-les-Pins, 2007, Discrete Math. Theor. Comput. Sci. Proc. AH, 2007, pp. 291–302. Fayolle, 1985, Analysis of a stack algorithm for random multiple-access communication, IEEE Trans. Inform. Theory, 31, 244, 10.1109/TIT.1985.1057014 Feller, 1971 Gut, 2005 Gut, 2009 C. Holmgren, Novel characteristics of split trees by use of renewal theory. Preprint, 2010. arXiv:1005.4594. Jacquet, 1986, Trie partitioning process: limiting distributions, vol. 214, 196 Jacquet, 1988, Normal limiting distribution of the size of tries, 209 Jacquet, 1989, New results on the size of tries, IEEE Trans. Inform. Theory, 35, 203, 10.1109/18.42197 Jacquet, 1991, Analysis of digital tries with Markovian dependency, IEEE Trans. Inform. Theory, 37, 1470, 10.1109/18.133271 Janson, 2004, One-sided interval trees, J. Iranian Statistical Society, 3, 149 Janson, 2006, Rounding of continuous random variables and oscillatory asymptotics, Ann. Probab., 34, 1807, 10.1214/009117906000000232 Janson, 2000 Kesten, 1974, Renewal theory for functionals of a Markov chain with general state space, Ann. Probab., 2, 355, 10.1214/aop/1176996654 Knuth, 1998 Kontoyiannis, 1997, Second-order noiseless source coding theorems, IEEE Trans. Inform. Theory, 43, 1339, 10.1109/18.605604 Leadbetter, 1983 Louchard, 2006, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 431, 10.1007/s00453-006-0106-8 Mahmoud, 1992 Mahmoud, 2009, Imbalance in random digital trees, Methodol. Comput. Appl. Probab., 11, 231, 10.1007/s11009-008-9087-1 Mohamed, 2005, A probabilistic analysis of some tree algorithms, Ann. Appl. Probab., 15, 2445, 10.1214/105051605000000494 Mohamed, 2010, Dynamic tree algorithms, Ann. Appl. Probab., 20, 26, 10.1214/09-AAP617 Pittel, 1985, Asymptotical growth of a class of random trees, Ann. Probab., 13, 414, 10.1214/aop/1176993000 Pittel, 1986, Paths in a random digital tree: limiting distributions, Adv. Appl. Probab., 18, 139, 10.2307/1427240 Rais, 1993, Limiting distribution for the depth in PATRICIA tries, SIAM J. Discrete Math., 6, 197, 10.1137/0406016 Régnier, 1988, Trie hashing analysis, 377 Savari, 2000, Renewal theory and source coding, Proc. IEEE, 88, 1692, 10.1109/5.892705 Savari, 1997, Generalized Tunstall codes for sources with memory, IEEE Trans. Inform. Theory, 43, 658, 10.1109/18.556121 Szpankowski, 1990, Patricia tries again revisited, J. Assoc. Comput. Mach., 37, 691, 10.1145/96559.214080 Szpankowski, 2001 W. Szpankowski, Average redundancy for known sources: ubiquitous trees in source coding, in: Proceedings, Fifth Colloquium on Mathematics and Computer Science, Blaubeuren, 2008, Discrete Math. Theor. Comput. Sci. Proc. AI, 2008, pp. 19–58.