The entropy \(H(x)\) of a random variable \(X\) is defined as

\[ \begin{aligned} \color{blue}{H(X) = - \sum_x p(x) \log{p(x)}} \end{aligned} \]

which measures the uncertainty of \(X\). Note \(H(X)\) depends only on the distribution of \(X\) but not on the actual values taken by \(X\). For example, here is a cute binary entropy function for \(X \thicksim \{\gamma, 1-\gamma\}\):

\[ \begin{aligned} h_b(\gamma) = - \gamma \log{\gamma} - (1-\gamma) \log{(1-\gamma}) \\ \end{aligned} \]

Via the use of expectation:

\[ \begin{aligned} E g(X) = \sum_x p(x) g(x) \\ \end{aligned} \]

Entropy can also be expressed compactly in terms of expectation:

\[ \begin{aligned} \color{blue}{H(X) = - E \log{p(X)}} = - \sum_x p(x) \log{p(x)} \end{aligned} \]

Interestingly, the joint entropy:

\[ \begin{aligned} H(X,Y) = - E \log{p(X,Y)} = - \sum_{x,y} p(x,y) \log{p(x,y)} \\ \end{aligned} \]

But the conditional entropy of \(Y\) given \(X\):

\[ \begin{aligned} \color{blue}{H(Y\,|\,X) = - E \log{p(Y\,|\,X)}} &= - \sum_{x,y} p(x,y) \log{p(y\,|\,x)} \\ &= - \sum_x \sum_y p(x) p(y\,|\,x) \log{p(y\,|\,x)} \\ &= \sum_x p(x) \left[-\sum_y p(y\,|\,x) \log{p(y\,|\,x)}\right] \\ &= \color{blue}{\sum_x p(x)\, H(Y\,|\,X=x)} \\ \end{aligned} \]

Similarly,

\[ \begin{aligned} H(Y\,|\,X,Z) = \sum_z p(z)\, H(Y\,|\,X,Z=z) \\ \end{aligned} \]

where

\[ \begin{aligned} H(Y\,|\,X,Z=z) = -\sum_{x,y} p(x,y\,|\,z) \log{p(y\,|\,x,z)} \\ \end{aligned} \]

Now it's not hard to show that

\[ \begin{aligned} \color{blue}{H(X,Y) = H(X) + H(Y\,|\,X)} \\ \end{aligned} \]

for

\[ \begin{aligned} H(X,Y) &= -E \log{p(X,Y)} = -E \log{\left[p(X) \, p(Y\,|\,X)\right]} \\ &= -E \log{p(X)} - E \log{p(Y\,|\,X)} \\ &= H(X) + H(Y|X) \\ \end{aligned} \]

In general, there is the Chain rule for Entropy:

\[ \begin{aligned} \color{blue}{H(X_1,X_2, \cdots, X_n)} &\color{blue}{= \sum_{i=1}^n H(X_i|X_1, \cdots , X_{i-1})} \\ \end{aligned} \]

which can be easily verified via induction. The base case is known to be true above. Suppose it is true for \(n\), then

\[ \begin{aligned} H(X_1,X_2, \cdots, X_n, X_{n+1}) &= H(X_{n+1}| X_1, \cdots , X_n) + H(X_1, \cdots , X_n) \\ &= H(X_{n+1}| X_1, \cdots , X_n) + \sum_{i=1}^{n} H(X_i|X_1, \cdots , X_{i-1}) & \text{induction hypothesis} \\ &= \sum_{i=1}^{n+1} H(X_i|X_1, \cdots , X_{i-1}) \\ \end{aligned} \]

\(\Box\)

Source: Information Theory.

# posted by rot13(Unafba Pune) @ 3:37 PM