Estimation of search tree size and approximate counting: A likelihood approach
Florian Dennert, Rudolf Grübel · Statistics & Risk Modeling · 2009
Abstract We consider the problem of estimating the size of a random digital search tree on the basis of the maximal node depth observed along a specific path. We show that the maximum likelihood estimator exists and we investigate its properties. A similar problem arises in the context of approximate counting. In both cases a simple pure birth process plays a central role. We also construct confidence bounds.