Shannon Entropy

Shannon entropy is the fundamental quantitative measure in information theory and computation and algorithms that characterizes the average uncertainty, surprise, or minimum expected number of binary symbols required to encode draws from a probability distribution. Introduced by American mathematician and electrical engineer Claude E. Shannon in his landmark 1948 Bell System Technical Journal monograph, A Mathematical Theory of Communication, Shannon entropy separates the statistical structure of a message source from its semantic meaning. By proving that the entropy H(X) of a discrete memoryless source defines the operational boundary for lossless compression—and that mutual information defines the error-free transmission capacity of a noisy communication channel—Shannon established the mathematical foundations of digital telecommunications, cryptography, statistical physics, and genomic sequence analysis.

Self-Information and Units of Information

Let X be a discrete random variable taking values in a finite alphabet χ = {x₁, x₂, ..., x_m} with probability mass function P(X = x_i) = p_i ≥ 0 satisfying ∑_i=1^m p_i = 1. The self-information (or surprisal) associated with observing a specific outcome x_i is defined as:

I(x_i) = −log_b p_i = log_b(1 / p_i)

An event that occurs with probability p_i = 1 carries zero surprise (I = 0), whereas a rare event (p_i ≪ 1) carries large positive self-information. Moreover, for two statistically independent events A and B with P(A, B) = P(A)P(B), the logarithmic definition ensures additivity: I(A, B) = I(A) + I(B). The choice of logarithm base b determines the measurement unit:

• Base b = 2 (Bits or Shannons, Sh): Measures information in binary yes/no decisions; observing one of two equally likely outcomes (p = 0.5) yields −log₂(0.5) = 1 bit.
• Base b = e (Nats): Uses the natural logarithm ln, standard in differential calculus, statistical mechanics, and maximum-likelihood inference (1 nat = log₂ e ≈ 1.4427 bits).
• Base b = 10 (Hartleys, Bans, or Dits): Measures information in decimal digits (1 hartley = log₂ 10 ≈ 3.3219 bits).

Definition and the Shannon–Khinchin Axioms

Shannon entropy H(X) is defined as the expected value of the self-information over the probability distribution P(X):

H(X) = E[I(X)] = −∑_i=1^m p_i log₂ p_i

with the continuity convention 0 log₂ 0 = lim_p→0⁺ p log₂ p = 0, so adding zero-probability outcomes does not alter the entropy. For a binary Bernoulli random variable with success probability p and failure probability 1 − p, the binary entropy function is H_b(p) = −p log₂ p − (1 − p) log₂(1 − p), which vanishes at p = 0 and p = 1 and achieves its global maximum of 1 bit at p = 0.5. More generally, across an alphabet of size m, Jensen's inequality implies 0 ≤ H(X) ≤ log₂ m, with equality on the upper bound if and only if X follows a uniform distribution (p_i = 1/m for all i, the Hartley entropy).

Shannon (1948) and Aleksandr Khinchin (1953) proved that H(p₁, ..., p_m) = −C ∑ p_i log p_i (for a positive scaling constant C > 0) is the unique functional satisfying four natural axioms:

1. Continuity: H is a continuous function of the probability vector (p₁, ..., p_m).
2. Maximality and Monotonicity for Uniform Distributions: For p_i = 1/m, the quantity H(1/m, ..., 1/m) is a monotonically increasing function of m.
3. Expansibility: Appending an impossible outcome (p_m+1 = 0) leaves H unchanged.
4. Strong Additivity (Grouping Recursive Property): If a choice is partitioned into sequential stages, the total entropy equals the weighted sum of the individual stage entropies: H(X, Y) = H(X) + H(Y | X).

Conditional Entropy, Mutual Information, and Kullback–Leibler Divergence

For a pair of discrete random variables (X, Y) with joint distribution p(x, y) and conditional distribution p(y | x) = p(x, y)/p(x), the joint entropy is H(X, Y) = −∑_x,y p(x, y) log₂ p(x, y), and the conditional entropy (equivocation) of Y given X is:

H(Y | X) = −∑_x,y p(x, y) log₂ p(y | x) = H(X, Y) − H(X)

Conditioning never increases average uncertainty: H(Y | X) ≤ H(Y). The reduction in the uncertainty of X obtained by observing Y defines the mutual information I(X; Y):

I(X; Y) = H(X) − H(X | Y) = H(Y) − H(Y | X) = H(X) + H(Y) − H(X, Y)

Equivalently, mutual information equals the Kullback–Leibler divergence D_KL(P(X, Y) ‖ P(X)P(Y)) between the joint distribution and the product of the marginal distributions, establishing I(X; Y) ≥ 0 with equality if and only if X and Y are statistically independent.

Relation to Boltzmann–Gibbs Thermodynamic Entropy

Shannon's formula bears a direct structural equivalence to the canonical Gibbs entropy of statistical mechanics, S = −k_B ∑_i p_i ln p_i, where k_B = 1.380649 × 10⁻²³ J·K⁻¹ is the Boltzmann constant and p_i is the probability of microstate i (reducing to Boltzmann's equation S = k_B ln Ω when all Ω accessible microstates are equiprobable, p_i = 1/Ω). Thus, 1 bit of Shannon entropy corresponds to a thermodynamic entropy increment of k_B ln 2 ≈ 9.57 × 10⁻²⁴ J·K⁻¹.

In 1957, Edwin T. Jaynes formalized this bridge through the ** Principle of Maximum Entropy: statistical mechanics can be derived as a form of statistical inference in which the canonical Boltzmann distribution is the unique probability assignment that maximizes Shannon entropy H(p) subject to known macroscopic expectation constraints (such as mean internal energy ⟨E⟩). In 1961, Rolf Landauer established Landauer's principle**, demonstrating that irreversibly erasing 1 bit of information in a physical memory register at temperature T dissipates at least k_BT ln 2 of heat into the surrounding environment (≈ 2.85 × 10⁻²¹ J at 298 K).

Lossless Compression: Huffman, Arithmetic, and Lempel–Ziv Coding

Shannon's Source Coding Theorem (Noiseless Coding Theorem) proves that for N independent and identically distributed draws from a random variable X, no uniquely decodable prefix-free binary code can achieve an expected codeword length L strictly less than H(X) bits per symbol, whereas optimal codes exist satisfying H(X) ≤ L < H(X) + 1/N.

• Huffman Coding (1952): Constructs an optimal symbol-by-symbol prefix tree assigning short integer-length binary strings to high-probability symbols and longer strings to rare symbols, achieving H(X) ≤ L < H(X) + 1.
• Arithmetic and Asymmetric Numeral Systems (ANS) Coding: Encodes an entire message sequence into a single fractional interval within [0, 1), bypassing the integer-bit-per-symbol penalty to approach the Shannon limit H(X) within fractions of a bit.
• Universal Dictionary Compression: When the source probability distribution P(X) is unknown a priori and exhibits stationary ergodic correlations, dictionary algorithms based on Lempel–Ziv complexity (LZ77, LZ78) parse recurring substrings so that the asymptotic compression ratio converges to the true entropy rate h = lim_n→∞ H(X₁, ..., X_n)/n.

Sequence Logos and Motif Information Content in Genomics

In molecular biology and bioinformatics, Thomas D. Schneider and R. Michael Stephens (1990) applied Shannon entropy to quantify evolutionary conservation across multiple sequence alignments via sequence logos. At alignment column l, the observed site entropy across an alphabet of size A (A = 4 nucleotides for DNA/RNA; A = 20 amino acids for proteins) is:

H(l) = −∑_b∈A f(b, l) log₂ f(b, l)

where f(b, l) is the relative frequency of residue b at position l. Assuming a uniform background composition of maximum entropy H_max = log₂ A (2 bits for DNA/RNA; log₂ 20 ≈ 4.322 bits for proteins), the positional information content R_seq(l) (corrected by small-sample approximation e(n)) is:

R_seq(l) = log₂ A − (H(l) + e(n)) (in bits)

An invariant DNA site where a single nucleotide occurs with frequency 1.0 has H(l) = 0 and R_seq(l) = 2.0 bits, whereas an unconstrained site where A, C, G, and T each occur at 25% has H(l) = 2.0 bits and R_seq(l) = 0 bits. Summing R_seq(l) across all columns of a transcription-factor binding site or splice junction quantifies the total sequence specificity (in bits) required for a regulatory protein to locate its target genomic motif amidst billions of background base pairs.

Can Shannon entropy be negative?

For a discrete probability distribution, Shannon entropy H(X) = −∑ p_i log₂ p_i is always non-negative (H(X) ≥ 0) because 0 ≤ p_i ≤ 1 implies −log₂ p_i ≥ 0. However, the continuous analogue—differential entropy h(X) = −∫ f(x) log₂ f(x) dx for a probability density f(x)—can be negative whenever f(x) > 1 on a narrow support (for instance, Uniform(0, 1/4) has differential entropy −2 bits), and is not invariant under coordinate scaling.

How does Shannon entropy differ from Kolmogorov complexity?

Shannon entropy is a property of a probability distribution (a random source ensemble), measuring the average code length across messages drawn from that source. Kolmogorov complexity K(s) is defined for an individual finite string s as the length of the shortest program on a universal Turing machine that outputs s; its expectation over a computable distribution P matches H(P) up to an additive constant.

Why does a uniform random sequence have the highest entropy but carry no structure?

In Shannon's theory, entropy measures unpredictability at the source rather than structural organization. Independent fair coin tosses cannot be compressed below 1 bit per toss because every outcome is maximally surprising. Structural regularity amidst noise is quantified instead by mutual information I(X; Y) between past and future subsequences.

1. Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
2. Jaynes, E. T. (1957). Information theory and statistical mechanics. Physical Review, 106(4), 620–630. https://doi.org/10.1103/PhysRev.106.620
3. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098–1101. https://doi.org/10.1109/JRPROC.1952.273898
4. Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3), 183–191. https://doi.org/10.1147/rd.53.0183
5. Schneider, T. D., & Stephens, R. M. (1990). Sequence logos: A new way to display consensus sequences. Nucleic Acids Research, 18(20), 6097–6100. https://doi.org/10.1093/nar/18.20.6097