Gallager and Van Voorhis have found optimal prefix-free codes $\kappa(K)$ for a random variable $K$ that is geometrically distributed: $\Pr[K=k] = p(1-p)^k$ for $k\ge 0$. We determine the asymptotic behavior of the expected length ${ \rm Ex}[{ \#\kappa(K)}]$ of these codes as $p\to 0$: $${ \rm Ex}[{ \#\kappa(K)}] = \log_2 { 1\over p} + \log_2 \log 2 + 2 + f\left(\log_2 { 1\over p} + \log_2 \log 2\right) + O(p),$$ where $$f(z) = 4\cdot 2^{ -2^{ 1-\{ z\}}} - \{ z\} - 1,$$ and $\{ z\} = z - \lfloor z\rfloor$ is the fractional part of $z$. The function $f(z)$ is a periodic function (with period $1$) that exhibits small oscillations (with magnitude less than $0.005$) about an even smaller average value (less than $0.0005$).
Categories: cs.IT math.IT