Advancing in the presence of a demon

Mathematica Slovaca

Guy Louchard¹  Helmut Prodinger¹ 

关键词: Gumbel distribution;    approximate counting;    demon;    trie;    search cost;    moment;   

DOI  :  10.2478/s12175-008-0072-5

学科分类：数学（综合）

来源: Slovenska Akademia Vied * Matematicky Ustav / Slovak Academy of Sciences, Mathematical Institute

【 摘 要 】

We study a parameter that contains approximate counting, i.e., the level reached after n random increments, driven by geometric probabilities, and insertion costs for tries as special cases. We are able to compute all moments of this parameter in a semi-automatic fashion. This is another showcase of the machinery developed in an earlier paper of these authors. Roughly speaking, it works when the underlying distributions are distributed according to the Gumbel distribution, or something similar.

【 授权许可】

Unknown