gen-define-data-compression-limits-and-give-one-short-worked-exa-e843

Define data compression limits and give one short worked example.

# Data Compression Limits **Data compression limits** define the theoretical minimum size to which data can be compressed without losing information (lossless compression). ## Key Concepts: 1. **Shannon's Source Coding Theorem**: Data cannot be compressed below its **entropy** without losing information - Entropy H(X) = theoretical lower bound on average bits per symbol 2. **Kolmogorov Complexity**: The shortest program that can generate the data - Truly random data is incompressible - Pigeonhole Principle: Not all files can be compressed ## Worked Example: **Compress a biased coin flip sequence:** Given: 1000 flips where P(Heads) = 0.8, P(Tails) = 0.2 **Entropy calculation:** ``` H = -Σ P(x) log₂ P(x) H = -[0.8 × log₂(0.8) + 0.2 × log₂(0.2)] H = -[0.8 × (-0.322) + 0.2 × (-2.322)] H = -[-0.258 + -0.464] H = 0.722 bits per flip ``` **Compression limit:** - Naive storage: 1000 flips × 1 bit = **1000 bits** - Theoretical minimum: 1000 flips × 0.722 = **722 bits** This means optimal compression can reduce storage by ~28%, but no lossless algorithm can compress below 722 bits on average for this source.