On Asymptotics of Certain Recurrences Arising in Universal Coding

Ramanujan's $Q$-function, the Lambert $W$-function, and the so-called “tree function” $T(z)$ defined implicitly by the equation $T(z)=ze^{T(z)}$ have found applications in hashing, the birthday paradox problem, random mappings, caching, memory conflicts, and so forth. Recently, several novel applications of these functions to information theory problems such as linear coding and universal portfolios were brought to light. In this paper, we study them in the context of another information theory problem, namely, universal coding which was recently investigated by [Yu. M. Shtarkov et al.,Probl. Inf. Trans., 31, No. 2, 114–127 (1995)]. We provide asymptotic expansions of certain recurrences studied there which describe the optimal redundancy of universal codes. Our methodology falls under the so-called analytical information theory, which was recently applied to a variety of problems of information theory.