Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-15T13:23:20.339Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit distribution of distances in biased random tries

Part of: Combinatorial probability Theory of data Graph theory Limit theorems

Published online by Cambridge University Press:  14 July 2016

Rafik Aguech ,
Nabil Lasmar  and
Hosam Mahmoud
Rafik Aguech*
Affiliation:
Faculté des Sciences de Monastir, Tunisia
Nabil Lasmar*
Affiliation:
IPEIT, Tunisia
Hosam Mahmoud*
Affiliation:
The George Washington University
*
∗Postal address: Département de Mathématiques, Faculté des Sciences de Monastir, 5019 Monastir, Tunisia. Email address: [email protected]
∗∗Postal address: Département de Mathématiques, IPEIT, 2 rue Jawaher Lel Nehru 1008 Montfleury, Tunis, Tunisia. Email address: [email protected]
∗∗∗Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The trie is a sort of digital tree. Ideally, to achieve balance, the trie should grow from an unbiased source generating keys of bits with equal likelihoods. In practice, the lack of bias is not always guaranteed. We investigate the distance between randomly selected pairs of nodes among the keys in a biased trie. This research complements that of Christophi and Mahmoud (2005); however, the results and some of the methodology are strikingly different. Analytical techniques are still useful for moments calculation. Both mean and variance are of polynomial order. It is demonstrated that the standardized distance approaches a normal limiting random variable. This is proved by the contraction method, whereby the limit distribution is shown to approach the fixed-point solution of a distributional equation in the Wasserstein metric space.

Keywords

Random treerecurrenceMellin transformpoissonizationfixed pointcontraction method

MSC classification

Primary: 05C05: Trees 60C05: Combinatorial probability
Secondary: 60F05: Central limit and other weak theorems 68P05: Data structures 68P10: Searching and sorting 68P20: Information storage and retrieval
Type
Research Papers
Information
Journal of Applied Probability , Volume 43 , Issue 2 , June 2006 , pp. 377 - 390
Copyright
© Applied Probability Trust 2006 

References

Chern, H. H., Hwang, H. K. and Tsai, T. H. (2002). An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms. J. Algorithms 44, 177–225.CrossRefGoogle Scholar
Christophi, C. and Mahmoud, H. (2005). The oscillatory distribution of distances in random tries. Ann. Appl. Prob. 15, 1536–1564.CrossRefGoogle Scholar
De La Briandais, R. (1959). File searching using variable length keys. In Proc. Western Joint Computer Conference, AFIPS, San Francisco, CA, pp. 295–298.Google Scholar
Flajolet, P. and Sedgewick, R. (1995). Mellin transforms and asymptotics: finite differences and Rice's integrals. Theoret. Comput. Sci. 144, 101–124.CrossRefGoogle Scholar
Flajolet, P., Gourdon, X. and Dumas, P. (1995). Mellin transforms and asymptotics: harmonic sums. Theoret. Comput. Sci. 144, 3–58.CrossRefGoogle Scholar
Fredkin, E. (1960). Trie memory. Commun. ACM 3, 490–499.CrossRefGoogle Scholar
Jacquet, P. and Régnier, M. (1987). Normal limiting distribution of the size of tries. In Performance '87, North-Holland, Amsterdam, pp. 209–223.Google Scholar
Jacquet, P. and Szpankowski, W. (1991). Analysis of digital tries with Markovian dependency. IEEE Trans. Inf. Theory 37, 1470–1475.CrossRefGoogle Scholar
Jacquet, P. and Szpankowski, W. (1998). Analytical depoissonization and its applications. Theoret. Comput. Sci 201, 1–62.CrossRefGoogle Scholar
Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to quicksort. Random Structures Algorithms 19, 498–524.CrossRefGoogle Scholar
Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Prob. 14, 378–418.CrossRefGoogle Scholar
Pittel, B. (1986). Paths in a random digital tree: limiting distributions. Adv. Appl. Prob. 18, 139–155.CrossRefGoogle Scholar
Rachev, S. T. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Adv. Appl. Prob. 27, 770–799.CrossRefGoogle Scholar
Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Informatique Théoret. Appl. 25, 85–100.CrossRefGoogle Scholar
Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29, 238–261.CrossRefGoogle Scholar
Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29, 3–33.CrossRefGoogle Scholar
Szpankowski, W. (2001). Average Case Analysis of Algorithms on Sequences. Wiley-Interscience, New York.CrossRefGoogle Scholar