= Prefix code for a rare geometric success
{title2=$\mathbb E L=n+\bigl(1-(1-2^{-n})^{2^n}\bigr)^{-1}$}
For a success index $J$ with <geometric distribution> of parameter $q=2^{-n}$, write $J-1=2^nQ+R$, $0\leq R<2^n$. Encode $Q$ by $Q$ ones followed by zero, then encode $R$ in exactly $n$ <bits>. This <prefix code> has length $n+Q+1$. Since $\mathbb P(Q\geq k)=(1-q)^{k2^n}$, its expected length is the displayed expression, at most $n+e/(e-1)$. Thus a very rare success can be communicated in approximately the logarithm of its inverse <probability>, rather than one <bit> per trial.
// Target: quantum-theory.bigb
Back to article page
