The Moments of the Profile in Random Binary Digital Trees


Authors

Ramin Kazemi - Department of Statistics, Imam Khomeini International University, Qazvin, Iran. Saeid Delavar - Department of Statistics, Imam Khomeini International University, Qazvin, Iran.


Abstract

The purpose of this paper is to provide a precise analysis of the \(t\)-th moment of the profile in random binary digital trees. We assume that the \(n\) input strings are independent and follow a (binary) Bernoulli model. In tries, the main difference with the previous analysis is that we have to deal with an inhomogeneous part in the proper functional equation satisfied by the \(t\)-th moment and in digital search trees with an inhomogeneous part in a proper functional-differential equation. We show that \(t\)-th moment of the profile (\(t\geq 2\)) is asymptotically of the same order as the expected value (\(t=1\)). These results are derived by methods of analytic combinatorics.


Share and Cite

  • Share on Facebook
  • Share on Twitter
  • Share on LinkedIn
ISRP Style

Ramin Kazemi, Saeid Delavar, The Moments of the Profile in Random Binary Digital Trees, Journal of Mathematics and Computer Science, 6 (2013), no. 3, 176-190

AMA Style

Kazemi Ramin, Delavar Saeid, The Moments of the Profile in Random Binary Digital Trees. J Math Comput SCI-JM. (2013); 6(3):176-190

Chicago/Turabian Style

Kazemi, Ramin, Delavar, Saeid. "The Moments of the Profile in Random Binary Digital Trees." Journal of Mathematics and Computer Science, 6, no. 3 (2013): 176-190


Keywords


MSC


References