Entropy is the basic numerical invariant of a discrete distribution. It measures the logarithmic effective size of the support, with probabilities counted according to their mass rather than only by their cardinality.
Entropy
Definition. For a finite random variable \(X\sim P\) on alphabet \(\mathcal X\), the entropy is \[ H(X)=H(P)=-\sum_{x\in\mathcal X}P(x)\log P(x), \] with the convention \(0\log0=0\). For a pair \((X,Y)\), define \(H(X,Y)\) from its joint law, and define conditional entropy by \(H(X\mid Y)=H(X,Y)-H(Y)\).
Chain rule and conditioning
Proposition. For finite random variables, \[ H(X_1,\ldots,X_n)=\sum_{i=1}^n H(X_i\mid X_1,\ldots,X_{i-1}). \] Moreover \(0\le H(X\mid Y)\le H(X)\), and equality on the right holds exactly when \(X\) and \(Y\) are independent.
Proof by factorization
Proof. The joint mass factors as \(p(x_1,\ldots,x_n)=\prod_i p(x_i\mid x_1, \ldots,x_{i-1})\). Taking \(-\log\), integrating with respect to the joint law, and using linearity gives the chain rule. Nonnegativity follows because each conditional entropy is an average of ordinary entropies. The inequality \(H(X\mid Y)\le H(X)\) is equivalent to nonnegativity of mutual information, proved from the log-sum inequality on the next page.
Interpretation as exponential volume
Remark. Entropy should be read as an asymptotic volume exponent: for independent samples from \(P\), most probability lies on about \(\exp(nH(P))\) typical strings. That operational interpretation is made precise by the asymptotic equipartition property.
Entropy as expected self-information
Definition. The self-information of an event with probability \(p>0\) is \[ \imath(p)=-\log p. \] Thus \(H(X)=\mathbb E\,\imath\{p_X(X)\}\). Changing the logarithm base rescales every information quantity; base \(2\) gives bits and base \(e\) gives nats.
Proposition. If \(X\) takes at most \(m\) values, then \[ 0\le H(X)\le\log m. \] The lower equality holds exactly when \(X\) is constant, and the upper equality holds exactly when \(X\) is uniform on its support.
Proof. Every term \(-p\log p\) is nonnegative. For the upper bound, let \(U\) be uniform: \[ D(P_X\|U)=\sum_xp(x)\log\{p(x)m\} =\log m-H(X)\ge0. \] Equality in KL occurs exactly at \(P_X=U\). Entropy zero forces every positive-mass term to have \(-\log p=0\), hence one atom has mass one.
Concavity and mixing
Theorem. Entropy is concave on the probability simplex: \[ H\{\lambda P+(1-\lambda)Q\} \ge\lambda H(P)+(1-\lambda)H(Q), \qquad0\le\lambda\le1. \]
Proof. The scalar function \(\varphi(t)=-t\log t\) has \(\varphi''(t)=-1/t<0\) on \((0,\infty)\). Apply scalar concavity coordinatewise and sum. Strict concavity gives equality, for \(0<\lambda<1\), exactly when \(P=Q\) on the common alphabet.
Mixing distributions increases uncertainty because forgetting the mixture label cannot reveal more than retaining it. If \(J\) is the label and \(X\mid J=j\sim P_j\), then \[ \sum_j\pi_jH(P_j)=H(X\mid J)\le H(X)\le H(J)+H(X\mid J). \]
Conditional entropy as an average
Proposition. \[ H(X\mid Y)=\sum_yp_Y(y)H(P_{X\mid Y=y}) =-\sum_{x,y}p(x,y)\log p(x\mid y). \]
Proof. Use \(p(x,y)=p(y)p(x\mid y)\): \[ H(X,Y)= -\sum_{x,y}p(x,y)\log p(y) -\sum_{x,y}p(x,y)\log p(x\mid y) =H(Y)+\text{second term}. \]
Deterministic maps and entropy
Proposition. If \(Y=f(X)\), then \[ H(Y)\le H(X), \] with equality exactly when \(X\) is almost surely a function of \(Y\), equivalently when \(f\) is injective on the support of \(X\).
Proof. Since \(H(Y\mid X)=0\), \[ H(X)=H(X,Y)=H(Y)+H(X\mid Y)\ge H(Y). \] Equality holds exactly when \(H(X\mid Y)=0\), which means each positive-probability fiber of \(f\) contains one possible \(X\)-value.
Subadditivity and independence
Corollary. \[ H(X_1,\ldots,X_n)\le\sum_{i=1}^nH(X_i), \] with equality exactly when the variables are mutually independent.
Proof. Apply the chain rule and \(H(X_i\mid X_1,\ldots,X_{i-1})\le H(X_i)\). Equality at every step means \(X_i\) is independent of its predecessors, which is equivalent to joint factorization.
Entropy of a Bernoulli variable
Example. If \(X\sim\operatorname{Bernoulli}(p)\), \[ h_2(p)=-p\log p-(1-p)\log(1-p). \] Its derivative is \(\log\{(1-p)/p\}\), and \(h_2''(p)=-1/[p(1-p)]<0\). Hence entropy is symmetric about \(1/2\), maximal at \(p=1/2\), and locally \[ h_2(1/2+u)=\log2-2u^2+O(u^4) \] in nats.
Shearer's inequality
Theorem. Let \(X=(X_1,\ldots,X_n)\), and let \(\mathcal S\) be a multiset of coordinate subsets such that each coordinate occurs in at least \(k\) members. Then \[ H(X)\le\frac1k\sum_{S\in\mathcal S}H(X_S). \]
Proof. Order coordinates. For each \(S\), \[ H(X_S)=\sum_{i\in S} H(X_i\mid X_{S\cap\{1,\ldots,i-1\}}) \ge\sum_{i\in S}H(X_i\mid X_1,\ldots,X_{i-1}), \] because conditioning reduces entropy. Summing over \(S\), each chain-rule term appears at least \(k\) times. Divide by \(k\).
Shearer's inequality is a reusable bridge from local projections to global combinatorial volume. It underlies Loomis-Whitney-type bounds, counting arguments, and entropy proofs in combinatorics.