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

`\frac12+\frac24+\frac{2\cdot3}8=\frac{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=\frac12+\frac{2^2}4+\frac{2\cdot3^2}8=\frac{15}4`

so that the variance for the length such a string is

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

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