What are redundancy $R(X)$ and relative redundancy $r(X)$?

Redundancy $R(X) = H_0(X) - H(X)$ measures "wasted" bits; relative redundancy $r(X) = \frac{R(X)}{H_0(X)}$ expresses this as a fraction of the maximum.

Absolute redundancy:

$$R(X) = H_0(X) - H(X)$$

This tells you how many bits per character are "wasted" due to non-uniform character distribution.

Relative redundancy:

$$r(X) = \frac{R(X)}{H_0(X)} = 1 - \frac{H(X)}{H_0(X)}$$

• $r(X) = 0$: No redundancy, maximum entropy (uniform distribution)
• $r(X) = 1$: Maximum redundancy, zero entropy (only one character ever appears)

Example — English text:

• Alphabet: 26 letters → $H_0 = \log_2(26) \approx 4.7$ bits/character
• Actual entropy: $H \approx 1.0 - 1.5$ bits/character (due to letter frequencies, digrams, etc.)
• Relative redundancy: $r \approx 68 - 79\%$

This high redundancy is what makes cryptanalysis of simple ciphers possible — and why compression before encryption is a good idea.

Go deeper:

• Redundancy (information theory) — the formal definition of redundancy.
• Frequency analysis — how language redundancy breaks classical ciphers.