Law

Entropy: the floor for any code

The minimum size for a column of N values is N × H bits.

H = - i \sum p_{i} lo g_{2} p_{i} bits per value

How it behaves

One input on the horizontal axis, the others held fixed.

Data table

Entropy of a two-valued column, by how often the commoner value occurs
Frequency of the commoner value p	Entropy H (bits per value)
0.5	1
0.506	1
0.512	1
0.519	0.999
0.525	0.998
0.531	0.997
0.537	0.996
0.544	0.994
0.55	0.993
0.556	0.991
0.562	0.989
0.569	0.986
0.575	0.984
0.581	0.981
0.587	0.978
0.594	0.974
0.6	0.971
0.606	0.967
0.612	0.963
0.619	0.959
0.625	0.954
0.631	0.95
0.637	0.945
0.644	0.94
0.65	0.934
0.656	0.928
0.662	0.922
0.669	0.916
0.675	0.91
0.681	0.903
0.687	0.896
0.694	0.889
0.7	0.881
0.706	0.874
0.712	0.866
0.719	0.857
0.725	0.849
0.731	0.84
0.737	0.831
0.744	0.821
0.75	0.811
0.756	0.801
0.762	0.791
0.769	0.78
0.775	0.769
0.781	0.758
0.787	0.746
0.794	0.734
0.8	0.722
0.806	0.709
0.812	0.696
0.819	0.683
0.825	0.669
0.831	0.655
0.837	0.64
0.844	0.625
0.85	0.61
0.856	0.594
0.862	0.578
0.869	0.561
0.875	0.544
0.881	0.526
0.887	0.508
0.894	0.489
0.9	0.469
0.906	0.449
0.912	0.428
0.919	0.407
0.925	0.385
0.931	0.362
0.937	0.338
0.944	0.313
0.95	0.287
0.956	0.26
0.962	0.231
0.969	0.201
0.975	0.169
0.981	0.135
0.987	0.098
0.994	0.056
1	0.001

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Encoding, Serialization & Compression
What do we turn our values into when we turn them into bytes, and what does that choice cost?
$H = - \sum p \cdot lo g_{2} p$
Read it in place →