Entropy
Entropy quantifies the average number of bits (uncertainty) required to convey the information in a random variable. For a discrete random variable , its entropy is defined as
where is a concave function, serving as a quantifier of the uncertainty associated with observing each .
Intuition
Given , we can quickly see that . This implies that the larger the probability of some is, the smaller the uncertainty associated with it. The addition of the base 2 logarithm to the function captures the exact amount of bits of information yielded by the value . While any base could be used, base 2 is preferred due to the binary nature of modern computers.
Now, take and find for all values. multiplied by the probability of each of those values occurring. You get entropy.
Properties
(Concavity)
(Joint Entropy) .
(Cond. Entropy) H(X \mid Y) = \mathbb{E}\left[ \dfrac{1}{p_{X \mid Y}(X \mid Y)} \right] = \large\sum_\limits{x}p_{X}(x)H(Y \mid X=x).
(Chain Rule) .
By definition, we know that . As such,
H(X, Y) &= -\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x,y)\log_2p(x,y) \\ &= -\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x,y)\log_2p(x)p(y \mid x) \\ &= -\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x, y)(\log_2p(x) +\log_2p(y \mid x)) \\ &= -\sum_{x \in \mathcal{X}}p(x)\log_2p(x)-\sum_{x \in \mathcal{X}}\sum_{y \in \mathcal{Y}}p(x)p(y \mid x)\log_2p(y \mid x) \\ &= H(X) + H(Y \mid X), \end{align*}$$ where marginal probability dictates that $-\sum\limits_{x \in \mathcal{X}}\sum\limits_{y \in \mathcal{Y}}p(x, y) = -\sum\limits_{x \in \mathcal{X}}p(x)$. Essentially, the chain rule states that the joint entropy of $X,Y$ is equivalent to the information that $X$ provides on its own, as well as the extra information provided by $Y$ given $X$. #### (*Independence*) If $X, Y$ are independent, $H(X, Y) = H(X) + H(Y)$, and $H(X \mid Y) = H(X)$. #### (Entropy Bounds) $H(X \mid Y) \leq H(X)$ and $H(X,Y) \leq H(X) + X(Y)$. #### (*Uniform Dist.*) $H(X) \leq \log_{2}|\mathcal{X}|$. where $H(X)=\log_{2}|\mathcal{X}|$ if $X \sim U(a,b)$. # Examples >[!example] Text Compression > >Suppose you want to transmit a message with the letters Y and N, where Y appears 95% of the time. With naive encoding, each symbol takes 1 bit on average. However, entropy tells us that the theoretical limit for compression is >$$H(X) = 0.95 \log_{2}\frac{1}{0.95} + 0.05 \log_{2}\frac{1}{0.05} \approx 0.286 \text{ bits per symbol.}$$ >[!example] Compression of a Markov Chain > >Consider an irreducible Markov chain $(X_{n})_{n \in \mathbb{N}}$ as shown below: >```tikz >\usepackage{tikz} >\usetikzlibrary{automata, positioning} > >\begin{document} > >\begin{tikzpicture}[->, semithick, node distance=3cm] > \tikzstyle{every state}=[thick, minimum size=35pt] > > \node[state] (A) {0}; > \node[state] (B) [right of=A] {1}; > > % Loops > \path (A) edge [loop left] node {\(1 - p\)} (A); > \path (B) edge [loop right] node {\(1 - p\)} (B); > > % Arrows between states > \path (A) edge [bend left] node[above] {\(p\)} (B); > \path (B) edge [bend left] node[below] {\(p\)} (A); >\end{tikzpicture} > >\end{document} >``` >Suppose $X_{0} \sim \operatorname{Ber}(1/2)$ and $p \neq 1/2$. Propose a scheme to represent $(X_0,\ldots,X_{n})$ in at most $n$ bits in expectation as $n \to \infty$, and state how many bits that would take. > >**SOLUTION:** >We quickly find that the stationary distribution is $\pi^*=\begin{bmatrix}1/2 & 1/2\end{bmatrix}$, given the transition matrix $P$. We also find that $H(X_{0})=1$ as $X_{0} \sim \operatorname{Ber}(1/2)$. Assuming that the chain has ran for a long time given the stationary distribution above, we find that >$$\begin{align} H(X_{n+1} \mid X_{n})&=\sum_{x_{n} \in \mathcal{X}}p_{X_{n}}(x_{n})\sum_{x_{n+1} \in \mathcal{X}}p_{X_{n+1} \mid X_{n}}(x_{n+1} \mid x_{n})\log_{2}\left( \frac{1}{p_{X_{n+1} \mid X_{n}}(x_{n+1} \mid x_{n})} \right) \\ &= \frac{1}{2}\left[(1-p)\log_{2}\frac{1}{1-p}+p\log_{2}\frac{1}{p}\right] + \frac{1}{2}\left[(1-p)\log_{2}\frac{1}{1-p}+p\log_{2}\frac{1}{p}\right] \\ &= (1-p)\log_{2}\frac{1}{1-p}+p\log_{2}\frac{1}{p}.\end{align}$$ > >This is a crucial result. Since $H(X_{n+1} \mid X_{n}) \leq 1$ (where the result equals $1$ if $p=1/2$), this means that if we know $X_{0}$, we will need $nH(X_{n+1} \mid X_{n})$ bits of information to determine the rest of the sequence. Recall that $H(X_{0})=1$. Putting this together, we find that we can recover, on average, the Markov Chain with $H(X_{1}, \ldots, X_{n})=nH(X_{n+1} \mid X_{n})+1 < n+1$ bits of information (strict inequality since $p \neq 1/2$.