Advancing in the presence of a demon

Year, pages: 2008, 263 - 276

We study a parameter that contains \emph{approximate counting}, i.e., the level reached after $n$ random increments, driven by geometric probabilities, and \emph{insertion costs} for \emph{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 \emph{Gumbel} distribution, or something similar.

Louchard, G., Prodinger, H. 2008. Advancing in the presence of a demon. In Mathematica Slovaca, vol. 58, no.3, pp. 263-276. 0139-9918.

Louchard, G., Prodinger, H. (2008). Advancing in the presence of a demon. Mathematica Slovaca, 58(3), 263-276. 0139-9918.