Entropy - Information Theory

Setting

For a discrete r.v. $X\sim P$ where $P_X(x):=\mathrm{Pr}(X)\leftrightarrow p(x)$ is the PMF, we define the entropy of $X$ as

$$H(X):=-\sum _{x\in \mathcal{X}}p(x)\log p(x)$$

Intuition Behind Entropy

Imagine you are predicting the outcome of an event, such as flipping a coin. If the coin is fair, the result (heads or tails) is maximally uncertain, and observing the outcome provides a "surprising" or informative answer. Conversely, if the coin is heavily biased (e.g., 99% chance of heads), the outcome is predictable, so learning the result yields little new information. Entropy formalizes this intuition:

• High entropy: Outcomes are uncertain or diverse (e.g., fair coin).
• Low entropy: Outcomes are predictable or concentrated (e.g., biased coin).

Entropy as Expected "Surprise"

Each outcome $x$ of $X$ carries a self-information (or "surprise") defined as $-\log p(x)$. Rare events (small $p(x)$) yield large self-information, as they are more surprising. Entropy $H(X)$ is the average self-information over all outcomes:

$$H(X)=\mathbb{E}[-\log p(X)]=-\sum _{x\in \mathcal{X}}p(x)\log p(x).$$

This means entropy measures the expected unpredictability of $X$.

Binary Entropy

For a binary variable $X$ (e.g., coin flip) with $p(0)=q$ and $p(1)=1-q$:

$$H(X)=-q\log q-(1-q)\log (1-q).$$

This function peaks at $q=0.5$ (fair coin, $H(X)=1$ bit) and drops to $0$ for $q=0$ or $q=1$ (no uncertainty).

Joint Entropy and Conditional Entropy

Joint Entropy

The joint entropy $H(X,Y)$ of a pair of discrete random variables $(X,Y)$ with a joint distribution $p(x,y)$ is defined as

$$H(X,Y):=-\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log p(x,y)$$

which can also be expressed as the expectation form

$$H(X,Y):=-\mathbb{E}\left[\log p(X,Y)\right]$$

Bijection and Joint Entropy

If there exists a bijection between $(X,Y)$ and $(U,V)$, then the joint entropies are equal: $H(X,Y)=H(U,V)$. A bijection implies a one-to-one and onto mapping, meaning each outcome in $(X,Y)$ corresponds uniquely to an outcome in $(U,V)$, and vice versa. Therefore, the uncertainty (and thus information entropy) is the same for both.

Conditional Entropy

$$\begin{array}{rl}H(Y|X)& =\sum _{x\in \mathcal{X}}p(x)H(Y\mid X=x)\\ & =-\sum _{x\in \mathcal{X}}p(x)\sum _{y\in \mathcal{Y}}p(y|x)\log p(y|x)\\ & =-\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log p(y|x)\\ & =-\mathbb{E}\left[\log P(Y|X)\right]\end{array}$$

Chain Rule

$$H(X,Y)=H(X)+H(Y|X)$$

Equivalently,

$$\log p(X,Y)=\log p(X)+\log p(Y|X)$$

Corollary

$$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$

Proof

$$\begin{array}{rl}H(X,Y)& =H(X)+H(Y|X)\\ ⟹H(X,Y|Z)& =H(X|Z)+H(Y|X,Z)\end{array}$$

Asymmetry

$H(X|Y)\ne H(Y|X)$

Relative Entropy and Mutual Information

K-L Divergence (Relative Entropy)

see also Kullback–Leibler Divergence

$${\mathbb{D}}_{\mathrm{KL}}(p\Vert q):=\sum _{x\in \mathcal{X}}p(x)\log \frac{p(x)}{q(x)}={\mathbb{E}}_p\log \frac{p(X)}{q(X)}$$

Note

In this definition, we use the covention that $0\log \frac{0}{0}=0$, $0\log \frac{0}{p}=0$, and $p\log \frac{p}{0}=\infty$. Thus, if there is any symbol $x\in \mathcal{X}$ such that $p(x)>0$ and $q(x)=0$, then ${\mathbb{D}}_{\mathrm{KL}}(p\Vert q)=\infty$.

Asymmetry

${\mathbb{D}}_{\mathrm{KL}}(p\Vert q)\ne {\mathbb{D}}_{\mathrm{KL}}(q\Vert p)$

Mutual Information

Consider two random variables $X$ and $Y$ with a joint distribution $p(x,y)$ and marginal probability mass function $p(x)$ and $p(y)$. The mutual information $I(X;Y)$ is the relative entropy between $p(x,y)$ and $p(x)p(y)$.

$$I(X;Y):={\mathbb{D}}_{\mathrm{KL}}[p(x,y)\Vert p(x)p(y)]=\sum _{x\in \mathcal{X}}\sum _{y\in \mathcal{Y}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}$$

Relationship with independence: $I(X;Y)=0⟺X,Y\text{ are independent}$.

Relationship between Mutual Information and Entropy

$$I(X;Y)=H(X)+H(Y)-H(X,Y)$$

In particular

$$I(X;X)=H(X)+H(X)-H(X,X)=H(X)-H(X|X)=H(X)$$

By this relationship we also have $I(X;Y)=I(Y;X)$

More Chain Rules

Chain rule of entropy

$$H(X_1,X_2,\dots ,X_n)=\sum _{i=1}^{n}H(X_i\mid X_{i-1},\dots ,X_1)$$

Conditional mutual information

$$I(X;Y|Z)=H(X|Z)-H(X|Y,Z)$$

For

$$\begin{array}{rl}I(X;Y|Z)& =H(X|Z)+H(Y|Z)-H(X,Y|Z)\\ & =H(X|Z)-H(X|Y,Z)\end{array}$$

Chain rule for information

$$I(X_1,X_2,\dots ,X_n;Y)=\sum _{i=1}^{n}I(X_i;Y|X_{i-1},X_{i-2},\dots ,X_1)$$

Conditional relative entropy

$$\begin{array}{rl}{\mathbb{D}}_{\mathrm{KL}}(p(y|x)\Vert q(y|x))& =\sum _{x}p(x)\sum _{y}p(y|x)\log \frac{p(y|x)}{q(y|x)}\\ & ={\mathbb{E}}_{p(x,y)}\log \frac{p(Y|X)}{q(Y|X)}\end{array}$$

Chain rule for relative entropy

$${\mathbb{D}}_{\mathrm{KL}}(p(x,y)\Vert q(x,y))={\mathbb{D}}_{\mathrm{KL}}(p(x)\Vert q(x))+{\mathbb{D}}_{\mathrm{KL}}(p(y|x)\Vert q(y|x))$$

Jenson's Inequality

See also Jensen's Inequality

Definition

If $f$ is a convex function and $X$ is a random variable

$$\mathbb{E}\left[f(X)\right]\ge f(\mathbb{E}\left[X\right])$$

Moreover, if $f$ is strictly convex, the equality implies that $X=\mathbb{E}[X]$ with probability $1$ (i.e., $X$ is a constant)

Information inequality

$${\mathbb{D}}_{\mathrm{KL}}(p\Vert q)\ge 0$$

with equality if and only if $p(x)=q(x)$ for all $x$.

Non-negativity of mutual information

$$I(X;Y)\ge 0$$

with equality if and only if $X$ and $Y$ are independent.

Upper bound of $H(X)$

$H(X)\le \log \left|\mathcal{X}\right|$, where $\left|\mathcal{X}\right|$ denotes the number of elements in the range of $X$, with equality if and only if $X$ has a uniform distribution over $\mathcal{X}$.

we can prove this by calculating the KL divergence between any PMF $p$, and the uniform PMF $u\equiv \frac{1}{\left|\mathcal{X}\right|}$:

$${\mathbb{D}}_{\mathrm{KL}}\left(p\Vert u\right)=\sum p(x)\log \frac{p(x)}{u(x)}=\log \left|\mathcal{X}\right|-H(X)\ge 0$$

Conditioning reduces entropy (Information can't hurt)

$$H(X|Y)\le H(X)$$

since

$$0\le I(X;Y)=H(X)+H(Y)-H(X,Y)=H(X)-H(X|Y)$$

Independence bound on entropy

Let $X_1,X_2,\dots ,X_n$ be drawn according to $p(x_1,x_2,\dots ,x_n)$. Then

$$H(X_1,X_2,\dots ,X_n)\le \sum _{i=1}^{n}H(X_i)$$

with equality if and only if the $X_i$ are independent.

Proof By the chain rule for entropies,

$$\begin{array}{rl}H(X_1,X_2,\dots ,X_n)& =\sum _{i=1}^{n}H(X_i\mid X_1,\dots ,X_{i-1})\\ & \le \sum _{i=1}^{n}H(X_i)(\text{Information can’t hurt})\end{array}$$

Log Sum Inequality

Definition

For non-negative numbers, $a_1,a_2,\dots ,a_n$ and $b_1,b_2,\dots ,b_n$,

$$\sum _{i=1}^n{a}_i\log \frac{a_i}{b_i}\ge \left(\sum _{i=1}^n{a}_i\right)\log \frac{{\sum }_{i=1}^n{a}_i}{{\sum }_{i=1}^n{b}_i}$$

with equality if and only if $\frac{a_i}{b_i}=\text{const}$.

Proof Setting $f(x)=x\log x$, by Jenson's inequality

$$\begin{array}{rl}\sum _{i=1}^n\log \frac{a_i}{b_i}=\sum _{i=1}^n{b}_{i}f\left(\frac{a_i}{b_i}\right)& =\left(\sum _{i=1}^n{b}_i\right)\sum _{i=1}^n\frac{b_i}{{\sum }_{i=1}^n{b}_i}f\left(\frac{a_i}{b_i}\right)\\ & \ge \left(\sum _{i=1}^n{b}_i\right)f\left(\sum _{i=1}^n\frac{b_i}{{\sum }_{i=1}^n{b}_i}\frac{a_i}{b_i}\right)=\left(\sum _{i=1}^n{b}_i\right)f\left(\frac{{\sum }_{i=1}^n{a}_i}{{\sum }_{i=1}^n{b}_i}\right)\\ & =\left(\sum _{i=1}^n{a}_i\right)\log \frac{{\sum }_{i=1}^n{a}_i}{{\sum }_{i=1}^n{b}_i}\end{array}$$

Convexity of KL divergence

${\mathbb{D}}_{\mathrm{KL}}(p\Vert q)$ is convex in the pair $(p,q)$: that is, if $(p_1,q_1)$ and $(p_2,q_2)$ are two pairs of probability mass functions, then

$${\mathbb{D}}_{\mathrm{KL}}\left[\lambda p_1+(1-\lambda )p_2\Vert \lambda q_1+(1-\lambda )q_2\right]\le \lambda {\mathbb{D}}_{\mathrm{KL}}(p_1\Vert q_1)+(1-\lambda ){\mathbb{D}}_{\mathrm{KL}}(p_2\Vert q_2)$$

Concavity of entropy

$H(p)$ is a concave function $p$, since $H(p)\equiv \log \left|\mathcal{X}\right|-{\mathbb{D}}_{\mathrm{KL}}(p\Vert u)$.

Data-Processing Inequality (DPI)

Markov chain

Random variables $X,Y,Z$ are said to form a Markov chain in that order (denoted by $X\to Y\to Z$) if

$$p(x,y,z)=p(x)p(y|x)p(z|y)$$

Data-processing inequality

If $X\to Y\to Z$, then $I(X;Y)\ge I(X;Z)$.

Idea

This means that processing $Y$ to produce $Z$ cannot increase the amount of information $Z$ contains about $X$. At best, $Z$ retains the same amount of information as $Y$, but typically, some information is lost.

The data-processing inequality captures the idea that processing data cannot increase the amount of information it contains about the original source. It formalizes the intuition that each step of processing (e.g., encoding, transmitting, decoding) can only preserve or reduce information, never create new information about the original data.

Proof: By the chain rule, we can expand mutual information in two different ways:

$$\begin{array}{rl}I(X;Y,Z)& =I(X;Z)+I(X;Y|Z)\\ & =I(X;Y)+I(X;Z|Y)\end{array}$$

Since $X$ and $Z$ are conditionally independent give $Y$, we have $I(X;Z|Y)=0$, since $I(X;Y|Z)\ge 0$, we have $I(X;Y)\ge I(X;Z)$.

Similarly, one can prove that $I(Y;Z)\ge I(X;Z)$.

Corollary If $X\to Y\to Z$, then $I(X;Y|Z)\le I(X;Y)$

Why $I(X;Y|Z)\le I(X;Y)$

• When $Z$ is known, some of the information $Y$ contains about $X$ might already be "explained" by $Z$. This reduces the additional information $Y$ can provide about $X$ beyond what $Z$ already tells us.
• In other words, $Z$ acts as a "summary" or "partial explanation" of $Y$, so knowing $Z$ reduces the uncertainty about $X$ that $Y$ can resolve.

Sufficient Statistics

Reference: Sufficient Statistic

Suppose that we have a family of probability mass functions $\left\{f_{\theta }(x)\right\}$ indexed by $\theta$, and let $X$ be a sample from a distribution in this family. Let $T(X)$ be any statistic (i.e. function of the sample) like the sample man or sample variance. Then $\theta \to X\to T(X)$, and by the data-processing inequality, we have

$$I(\theta ;T(X))\le I(\theta ;X)$$

for any distribution on $\theta$. However, if equality holds, no information is lost.

A function $T(X)$ is said to be a sufficient statistic relative to the family $\left\{f_{\theta }(x)\right\}$ if $X$ is independent of $\theta$ given $T(X)$ for any distribution on $\theta$. (i.e., $\theta \to T(X)\to X$ forms a Markov chain).

This is the same as the condition (since we have both $\theta \to T(X)\to X$ and $\theta \to X\to T(X)$)

$$I(\theta ;X)=I(\theta ;T(X))$$

A statistic $T(X)$ is a minimal sufficient statistic relative to $\left\{f_{\theta }(x)\right\}$ if it is a function of every other sufficient statistic $U$. Interpreting this in terms of the data-processing inequality, this implies that

$$\theta \to T(X)\to U(X)\to X$$

Hence, a minimal sufficient statistic maximally compresses the information about $\theta$ in the sample. Other sufficient statistics may contain additional irrelevant information. For example, for a normal distribution with mean $\theta$, the pair of functions giving the mean of all odd samples and the mean of all even samples is a sufficient statistic, but not a minimal sufficient statistic (i.e. just one function giving the mean of all samples).

Fano's Inequality

Suppose that we know a random variable $Y$ and we wish to guess the value of a correlated random variable $X$. Fano's inequality relates the probability of error in guessing the random variable $X$ to its conditional entropy $H(X|Y)$.

Fano's Inequality. For any estimator $\hat{X}$ such that $X\to Y\to \hat{X}$, with an error probability $P_e=P(X\ne \hat{X})$, we have

$$H(P_e)+P_e\log \left|\mathcal{X}\right|\ge H(X|\hat{X})\ge H(X|Y)$$

The core idea here is that

1. the uncertainty about $X$ given our estimate $\hat{X}$ ($H(X|\hat{X})$) must be at least as large as the uncertainty about $X$ given the original variable $Y$ ($H(X|Y)$). This makes intuitive sense because $\hat{X}$ is derived from $Y$, so it can't contain more information about $X$ than $Y$ itself does.
2. The term $H(P_e)+P_e\log |\mathcal{X}|$ is an upper bound on $H(X|\hat{X})$. Here, $H(P_e)$ is the entropy of the error event (i.e., the entropy of a binary random variable that is $1$ with probability $P_e$ and $0$ with probability $1-P_e$). The term $P_e\log |\mathcal{X}|$ accounts for the worst-case scenario: when an error occurs, we have no information about $X$, so we might have to choose from all possible values in the alphabet $\mathcal{X}$, resulting in an uncertainty of at most $\log |\mathcal{X}|$

Note that $H(P_e)\le -\frac{1}{2}{\log }_2\frac{1}{2}-\frac{1}{2}{\log }_2\frac{1}{2}=1$, This inequality can be weakened to

$$1+P_e\log \left|\mathcal{X}\right|\ge H(X|Y)$$

or

$$P_e\ge \frac{H(X|Y)-1}{\log \left|\mathcal{X}\right|}$$

Proof. The first inequality can be proven by expanding $H(E,X\mid \hat{X})$ in two ways

$$\begin{array}{rl}H(E,X\mid \hat{X})& =\underset{\le H(E)=H(P_e)}{\underbrace{H(E\mid \hat{X})}}+\underset{P_e\log |\mathcal{X}|}{\underbrace{H(X\mid E,\hat{X})}}\\ & =H(X\mid \hat{X})+\underset{=0}{\underbrace{H(E\mid X,\hat{X})}}\end{array}$$

Where for the $H(X\mid E,\hat{X})$ term we used

$$\begin{array}{rl}H(X\mid E,\hat{X})& =P(E=0)H(X\mid \hat{X},E=0)+P(E=1)H(X\mid \hat{X},E=1)\\ & \le (1-P_e)0+P_e\log \left|\mathcal{X}\right|\end{array}$$

Corollary. For any two random variables $X$ and $Y$, let $p=P(X\ne Y)$. We have

$$H(p)+p\log \left|\mathcal{X}\right|\ge H(X|Y)$$

Corollary. Let $P_e=P(X\ne \hat{X})$, and let $\hat{X}:\mathcal{Y}\to \mathcal{X}$; then

$$H(P_e)+P_e\log (\left|\mathcal{X}\right|-1)\ge H(X|Y)$$

The proof of the theorem goes through without change with the original proof, except that

$$\begin{array}{rl}H(X\mid E,\hat{X})& =P(E=0)H(X\mid \hat{X},E=0)+P(E=1)H(X\mid \hat{X},E=1)\\ & \le (1-P_e)0+P_e\log \left(\left|\mathcal{X}\right|-1\right)\end{array}$$

since given $E=1$, the range of possible $X$ outcomes is $\left|\mathcal{X}\right|-1$.

Lemma. If $X$ and $X^{\prime }$ are i.i.d. with entropy $H(X)$,

$$P(X=X^{\prime })\ge 2^{-H(X)}$$

with equality if and only if $X$ has a uniform distribution. Proof of Lemma. Suppose that $X\sim p(x)$. By Jensen's inequality, we have

$$2^{\mathbb{E}[\log p(X)]}\le \mathbb{E}\left[2^{\log p(X)}\right]$$

which implies that

$$2^{-H(X)}=2^{\sum p(x){\log }_{2}p(x)}\le \sum p(x)2^{{\log }_{2}p(x)}=\sum p^2(x)=P(X=X^{\prime })$$