2.1 Entropy

Entropy is a measure of the uncertainty of a random variable. Let \(X\) be a discrete random variable with alphabet \(\mathcal{X}\) and probability mass function \(p(x) = \Pr\{X = x\}\), \(x \in \mathcal{X}\).

Definition. The entropy \(H(X)\) of a discrete random variable \(X\) is defined by

\[H(X) = - \sum_{x \in \mathcal{X}} p(x) \log p(x)\]

The log is to the base \(2\) and entropy is expressed in bits.

We denote the expectation by \(E\). The expected value of the random variable \(g(X)\) is written

\[E_pg(X) = \sum_{x \in \mathcal{X}} g(x)p(x)\]

We shall take a peculiear interest in the eerily self-referential expectation of \(g(X)\) when \(g(X) = \log \frac{1}{p(X)}\).

Remark. The entropy of \(X\) can also be interpreted as the expected value of the random variable \(\log \frac{1}{p(X)}\). Thus,

\[H(X) = E_p \log \frac{1}{p(X)}\]

Lemma 2.1.1. \(H(X) \geq 0\).

Lemma 2.1.2. \(H_b(X) = (\log_b a)H_a(X)\).