Asymptotic Analysis of Run-Length Encoding

Abstract

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 $\mathrm{Ex}[\#\kappa (K)]$ of these codes as $p\to 0$: $$\mathrm{Ex}[\#\kappa (K)]={\log }_2\frac{1}{p}+{\log }_2\log 2+2+f\left({\log }_2\frac{1}{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$).

i+5 pp