Shannon entropy, named after Claude Shannon, is a fundamental concept in information theory that quantifies the average amount of information produced by a stochastic source of data. It measures the uncertainty or unpredictability associated with a random variable, typically expressed in bits. Higher entropy indicates greater unpredictability, while lower entropy implies more structured or redundant information. Shannon entropy serves as the foundation for data compression, communication theory, and many other fields.
1 Definition and Intuition
1.1 Formal Definition for Discrete Random Variables
For a discrete random variable \(X\) with probability mass function \(p(x)\), the Shannon entropy \(H(X)\) is defined as
\[ H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_2 p(x), \]
where \(\mathcal{X}\) is the set of possible outcomes. The logarithm base 2 expresses entropy in bits. If \(p(x) = 0\), the term \(0 \log_2 0\) is taken to be zero, consistent with the limit.
1.2 Extension to Continuous Variables (Differential Entropy)
For a continuous random variable with probability density function \(f(x)\), the differential entropy \(h(X)\) is defined analogously:
\[ h(X) = -\int_{\mathcal{X}} f(x) \log_2 f(x) \, dx. \]
Unlike discrete entropy, differential entropy can be negative, lacks invariance under coordinate transformations, and is not a direct measure of absolute information content. It is useful in contexts such as signal processing and Gaussian channel analysis.
1.3 Intuitive Interpretation: Surprise and Information Content
Entropy quantifies the average "surprise" or uncertainty of outcomes. An event with low probability carries more surprise (information) than a highly probable event. Entropy is the expected value of surprise over all outcomes.
1.3.1 Relationship to Self-Information
The self-information of an outcome \(x\) is \(I(x) = -\log_2 p(x)\) bits. It measures the information gained when that outcome occurs. Shannon entropy is simply the expectation of self-information: \(H(X) = \mathbb{E}[I(X)]\).
1.4 Examples
1.4.1 Fair Coin vs. Biased Coin
A fair coin (\(p = 0.5\)) has entropy \(H = -0.5 \log_2 0.5 - 0.5 \log_2 0.5 = 1\) bit. A biased coin with \(p = 0.9\) for heads has entropy \(H = -0.9 \log_2 0.9 - 0.1 \log_2 0.1 \approx 0.469\) bits. The biased coin is more predictable, hence lower entropy.
1.4.2 Uniform Distribution
For a discrete uniform distribution over \(n\) outcomes, each with probability \(1/n\), entropy is \(H = \log_2 n\) bits. This is the maximum possible entropy for a given \(n\), reflecting maximal uncertainty.
2 Fundamental Properties
2.1 Non-Negativity
For any discrete random variable, \(H(X) \ge 0\), with equality if and only if one outcome has probability 1 (deterministic). This follows because each term \(-p \log p \ge 0\).
2.2 Maximum Entropy
For a given number of outcomes \(n\), entropy is maximized when the distribution is uniform. For continuous variables under constraints (e.g., fixed variance), the maximum-entropy distribution is often Gaussian.
2.3 Symmetry
Entropy is symmetric: \(H(X)\) depends only on the probability values, not on the labeling of outcomes. Permuting the outcomes does not change entropy.
2.4 Additivity and Subadditivity
For independent random variables \(X\) and \(Y\), entropy is additive: \(H(X,Y) = H(X) + H(Y)\). In general, joint entropy satisfies subadditivity: \(H(X,Y) \le H(X) + H(Y)\), with equality if and only if \(X\) and \(Y\) are independent.
2.5 Chain Rule and Conditional Entropy
2.5.1 Joint Entropy
The joint entropy of two discrete random variables \(X, Y\) with joint distribution \(p(x,y)\) is
\[ H(X,Y) = -\sum_{x,y} p(x,y) \log_2 p(x,y). \]
2.5.2 Conditional Entropy
| The conditional entropy \(H(Y | X)\) measures the remaining uncertainty of \(Y\) given knowledge of \(X\): |
|---|
\[
| H(Y | X) = \sum_{x} p(x) H(Y | X=x) = -\sum_{x,y} p(x,y) \log_2 p(y | x). |
|---|
\]
| The chain rule states \(H(X,Y) = H(X) + H(Y | X)\). |
|---|
2.5.3 Mutual Information
Mutual information \(I(X;Y)\) quantifies the amount of information shared between \(X\) and \(Y\):
\[
| I(X;Y) = H(X) - H(X | Y) = H(Y) - H(Y | X) = H(X) + H(Y) - H(X,Y). |
|---|
\]
It is symmetric, non-negative, and zero if and only if \(X\) and \(Y\) are independent.
2.6 Gibbs’ Inequality and Relative Entropy (Kullback–Leibler Divergence)
Gibbs’ inequality states that for two probability distributions \(p\) and \(q\) over the same alphabet, the Kullback–Leibler divergence (relative entropy)
\[ D_{\text{KL}}(p \parallel q) = \sum_{x} p(x) \log_2 \frac{p(x)}{q(x)} \]
is non-negative, and equals zero only if \(p = q\). It measures the inefficiency of using \(q\) to approximate \(p\).
2.6.1 Properties of Relative Entropy
- It is not a metric because it is asymmetric and does not satisfy the triangle inequality.
- It is convex in the pair \((p,q)\).
- It appears in many information-theoretic bounds, including the data processing inequality and the variational bound in Bayesian inference.
3 Applications
3.1 Data Compression and Source Coding
3.1.1 Shannon’s Source Coding Theorem
The theorem states that for a discrete memoryless source with entropy \(H\), the minimum average number of bits per symbol needed to represent the source without loss is arbitrarily close to \(H\) (but not less). Conversely, any code with average length less than \(H\) is impossible without loss.
3.1.2 Optimal Code Length
Huffman coding and arithmetic coding achieve average code lengths within one bit of the entropy. For fixed-length codes, entropy sets the limit on the compression rate.
3.2 Communication Channels
3.2.1 Channel Capacity
The capacity of a discrete memoryless channel is the maximum mutual information between input and output over all possible input distributions:
\[ C = \max_{p(x)} I(X;Y). \]
It represents the highest rate of reliable information transmission.
3.2.2 Noisy Channel Coding Theorem
Shannon’s second theorem states that if the transmission rate \(R\) is less than channel capacity \(C\), there exist error-correcting codes that achieve arbitrarily low error probability. If \(R > C\), reliable communication is impossible.
3.3 Cryptography and Randomness
Entropy measures the unpredictability of a secret key or plaintext. High entropy is necessary for strong cryptographic security. Random number generators are evaluated by their entropy output. In cryptanalysis, entropy reduction indicates leakage of information.
3.4 Machine Learning and Decision Trees
3.4.1 Information Gain
| In decision tree learning, information gain is the reduction in entropy after splitting a dataset on an attribute. It is defined as \(\text{Gain}(S, A) = H(S) - H(S | A)\). Attributes with higher information gain are preferred for splits. |
|---|
3.4.2 Entropy in Neural Networks
Entropy-based loss functions (e.g., cross-entropy loss) are commonly used in classification tasks. Cross-entropy measures the difference between true and predicted distributions and is equivalent to the negative log-likelihood. Entropy regularization encourages output distributions with higher entropy to improve generalization.
3.5 Statistical Physics and Thermodynamic Entropy
3.5.1 Boltzmann Entropy vs. Shannon Entropy
Boltzmann entropy \(S = k \ln \Omega\) (where \(\Omega\) is the number of microstates) is structurally identical to Shannon entropy with a constant multiplicative factor. Shannon entropy generalizes Boltzmann’s concept to any probability distribution, linking information theory to statistical mechanics. This connection underlies modern fields such as maximum entropy methods and nonequilibrium thermodynamics.
4 Generalizations and Extensions
4.1 Rényi Entropy
The Rényi entropy of order \(\alpha\) (\(\alpha \ge 0, \alpha \neq 1\)) is
\[ H_\alpha(X) = \frac{1}{1-\alpha} \log_2 \sum_{x} p(x)^\alpha. \]
It reduces to Shannon entropy as \(\alpha \to 1\). Rényi entropy is used in quantum information, ecology, and fractal dimension estimation.
4.2 Tsallis Entropy
Tsallis entropy is a nonextensive generalization:
\[ S_q = \frac{1}{q-1} \left(1 - \sum_x p(x)^q\right), \]
with \(q\) as the entropic index. It recovers Shannon entropy in the limit \(q \to 1\) and is used in nonextensive statistical mechanics.
4.3 Differential Entropy and Limitations
Differential entropy for continuous variables lacks invariance under change of variables and can be negative. It does not represent an absolute measure of information; instead, comparisons of relative information (e.g., mutual information) are more meaningful.
4.4 Entropy Rate for Stochastic Processes
For a stochastic process (e.g., a Markov chain), the entropy rate is the limiting average entropy per symbol:
\[ \lim_{n\to\infty} \frac{1}{n} H(X_1, X_2, \dots, X_n). \]
It quantifies the irreducible complexity of the process and is fundamental in source coding, language modeling, and time series analysis.
5 Historical Context
5.1 Claude Shannon and “A Mathematical Theory of Communication”
Claude Shannon published the seminal paper “A Mathematical Theory of Communication” in 1948, introducing entropy as the central measure of information. He built on earlier work by Nyquist and Hartley, providing a unified mathematical framework for communication systems.
5.2 Relationship to Hartley’s Information Measure
In 1928, Ralph Hartley proposed a logarithmic measure of information based on the number of possible sequences, \(H = \log n\), without considering probabilities. Shannon generalized this to probabilistic sources, giving birth to modern information theory.
5.3 Subsequent Development and Influence
Shannon’s work rapidly influenced coding theory (Hamming codes, Lempel–Ziv compression), cryptography (unconditional security, entropy arguments), and later areas such as artificial intelligence, neurobiology, and quantum information. The concept of entropy remains a core tool across science and engineering.
6 See Also
- Mutual information
- Entropy (information theory)
- Data compression
- Channel capacity
- Kullback–Leibler divergence
- Maximum entropy principle
- Algorithmic information theory (Kolmogorov complexity)
7 References
- Shannon, C. E. (1948). “A Mathematical Theory of Communication”. *Bell System Technical Journal*.
- Cover, T. M., & Thomas, J. A. (2006). *Elements of Information Theory* (2nd ed.). Wiley.
- MacKay, D. J. C. (2003). *Information Theory, Inference, and Learning Algorithms*. Cambridge University Press.