Asymptotic Analysis of Run-Length Encoding

Gallager and Van Voorhis have found optimal prefix-free codes $\kappa (K)$ for a random variable $K$ that is geometrically distributed: $\mathrm{Pr}[K=k]=p(1-p{)}^k$ for $k\ge 0$. We determine the asymptotic behavior of the expected length ${\rm Ex}[{#\kappa(K)}]$ofthesecodesas$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$isthefractionalpartof$z$\mathrm{.}Thefunction$f(z)$isaperiodicfunction(withperiod$1$) that exhibits small oscillations (with magnitude less than $0.005$) about an even smaller average value (less than $0.0005$).