Name
Abstract | ||
|---|---|---|
Asymptotics of the variances of many cost measures in random digital search trees are often notoriously messy and involved to obtain. A new approach is proposed to facilitate such an analysis for several shape parameters on random symmetric digital search trees. Our approach starts from a more careful normalization at the level of Poisson generating functions, which then provides an asymptotically equivalent approximation to the variance in question. Several new ingredients are also introduced such as a combined use of the Laplace and Mellin transforms and a simple, mechanical technique for justifying the analytic de-Poissonization procedures involved. The methodology we develop can be easily adapted to many other problems with an underlying binomial distribution. In particular, the less expected and somewhat surprising n (logn)(2)-variance for certain notions of total path-length is also clarified. |
Year | Venue | Keywords |
|---|---|---|
2010 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | Digital search trees,Poisson generating functions,Poissonization,Laplace transform,Mellin transform,saddle-point method,Colless index,weighted path-length |
Field | DocType | Volume |
Mellin transform,Generating function,Discrete mathematics,Binomial distribution,Combinatorics,Normalization (statistics),Laplace transform,Algorithm,Poisson distribution,Delta method,Asymptotic analysis,Mathematics | Journal | 12.0 |
Issue | ISSN | Citations |
2.0 | 1462-7264 | 12 |
PageRank | References | Authors |
0.71 | 40 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsien-Kuei Hwang | 1 | 365 | 38.02 |
| Michael Fuchs | 2 | 52 | 8.98 |
| Vytas Zacharovas | 3 | 21 | 2.42 |