|
Problemy Peredachi Informatsii, 1998, Volume 34, Issue 2, Pages 56–61
(Mi ppi403)
|
|
|
|
This article is cited in 27 scientific papers (total in 27 papers)
Information Theory and Coding Theory
On Asymptotics of Certain Recurrences Arising in Universal Coding
W. Szpankowski
Abstract:
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.
Received: 18.02.1997 Revised: 07.10.1997
Citation:
W. Szpankowski, “On Asymptotics of Certain Recurrences Arising in Universal Coding”, Probl. Peredachi Inf., 34:2 (1998), 56–61; Problems Inform. Transmission, 34:2 (1998), 142–146
Linking options:
https://www.mathnet.ru/eng/ppi403 https://www.mathnet.ru/eng/ppi/v34/i2/p56
|
Statistics & downloads: |
Abstract page: | 387 | Full-text PDF : | 135 | References: | 37 |
|