Question

A source of information randomly generates symbols from a four letter alphabet {w, x, y, z }. The probability of each symbol is as follows: P(w) = 1 2 ; P(x) = 1 4 ; P(y) = 1 8 ; and P(z) = 1 8 . These symbols are now encoded into binary codes using the scheme shown below. Let the random variable L denote the length of the binary code and pL(l) denote the PMF of L.symbol codew 0x 10y 110z 111Find the expectation and variance of L.

Answer 1

The expected length of code for one encoded symbol is

$\displaystyle\sum_{\alpha\in\{w,x,y,z\}}p_\alpha\ell_\alpha$

where $p_\alpha$ is the probability of picking the letter $\alpha$, and $\ell_\alpha$ is the length of code needed to encode $\alpha$. $p_\alpha$ is given to us, and we have

$\begin{cases}\ell_w=1\\\ell_x=2\\\ell_y=\ell_z=3\end{cases}$

so that we expect a contribution of

$\dfrac12+\dfrac24+\dfrac{2\cdot3}8=\dfrac{11}8=1.375$

bits to the code per encoded letter. For a string of length $n$, we would then expect $E[L]=1.375n$.

By definition of variance, we have

$\mathrm{Var}[L]=E\left[(L-E[L])^2\right]=E[L^2]-E[L]^2$

For a string consisting of one letter, we have

$\displaystyle\sum_{\alpha\in\{w,x,y,z\}}p_\alpha{\ell_\alpha}^2=\dfrac12+\dfrac{2^2}4+\dfrac{2\cdot3^2}8=\dfrac{15}4$

so that the variance for the length such a string is

$\dfrac{15}4-\left(\dfrac{11}8\right)^2=\dfrac{119}{64}\approx1.859$

"squared" bits per encoded letter. For a string of length $n$, we would get $\mathrm{Var}[L]=1.859n$.