Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-17T22:43:15.385Z Has data issue: false hasContentIssue false

Limit distribution of distances in biased random tries

Published online by Cambridge University Press:  14 July 2016

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: rafikaguech@ipeit.rnu.tn
∗∗ Postal address: Département de Mathématiques, IPEIT, 2 rue Jawaher Lel Nehru 1008 Montfleury, Tunis, Tunisia. Email address: nabillasmar@yahoo.fr
∗∗∗ Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA. Email address: hosam@gwu.edu
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.

Information

Type
Research Papers
Copyright
© Applied Probability Trust 2006