Learn / Library / Probability

Bits saved on a log

ProbabilityMedium

A logger stores the state of the spread, which has $6$ values with probabilities $\frac{1}{2}$ , $\frac{1}{8}$ , $\frac{1}{8}$ , $\frac{1}{8}$ , $\frac{1}{16}$ and $\frac{1}{16}$ . A fixed-length binary code uses the fewest whole bits that give every value its own word. How many bits in total does an optimal prefix code save over that fixed-length code on $8000$ states, in expectation? Give a whole number.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Find the entropy, since a code can reach it when probabilities are powers of $\frac{1}{2}$ .

Solution

All probabilities are powers of $\frac{1}{2}$ , so an optimal prefix code has word lengths $1$ , $3$ , $3$ , $3$ , $4$ , $4$ and averages the entropy: $\frac{1}{2} \times 1 + \frac{3}{8} \times 3 + \frac{1}{8} \times 4 = \frac{17}{8}$ bits.
Telling $6$ values apart takes $3$ bits, because $2^{2} = 4$ is too few and $2^{3} = 8$ is enough.
The saving per state is $3 - \frac{17}{8} = \frac{7}{8}$ , so the total is $8000 \times \frac{7}{8} = 7000$ .

Answer: $7000$

Next question Back to the library