Given 8 characters A–H with probabilities P(A)=1/2, P(B)=1/8, P(C)–P(H)=1/16 each, calculate the entropy and redundancy.

$H(X) = 2.375$ bits, with $H_0 = 3$ bits, giving a redundancy of $R = 0.625$ bits (relative redundancy $r = 5/24 \approx 20.8\%$).

* A non-uniform source has entropy below the 3-bit maximum, leaving 0.625 bit of redundancy. *

Calculation:

$$H_0(X) = \log_2(8) = 3 \text{ bits}$$

$$H(X) = -\left[\frac{1}{2} \cdot (-1) + \frac{1}{8} \cdot (-3) + 6 \cdot \frac{1}{16} \cdot (-4)\right] = \frac{1}{2} + \frac{3}{8} + \frac{6}{4} = 2.375 \text{ bits}$$

Redundancy:

$$R(X) = H_0(X) - H(X) = 3 - 2.375 = 0.625 \text{ bits}$$

$$r(X) = \frac{0.625}{3} = \frac{5}{24} \approx 20.8\%$$

Validity check: $0 \leq H(X) \leq \log_2(n) = H_0(X)$ is satisfied since $2.375 \leq 3$.

This shows that a non-uniform distribution has less entropy than the maximum — the dominant character A (50% probability) makes the source more predictable, increasing redundancy.

Go deeper:

• Entropy (information theory) — the entropy and redundancy formulas used here.