Asymptotic Analysis of Run-Length Encoding

Nabil Zaman, Nicholas Pippenger

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 t…