Conditional Entropy - Chain Rule

Chain Rule

Assume that the combined system determined by two random variables X and Y has entropy, that is, we need bits of information to describe its exact state. Now if we first learn the value of, we have gained bits of information. Once is known, we only need bits to describe the state of the whole system. This quantity is exactly, which gives the chain rule of conditional probability:

Formally, the chain rule indeed follows from the above definition of conditional probability:

\begin{align} H(Y|X)=&\sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log \frac {p(x)} {p(x,y)}\\ =&-\sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x,y) + \sum_{x\in\mathcal X, y\in\mathcal Y}p(x,y)\log\,p(x) \\ =& H(X,Y) + \sum_{x \in \mathcal X} p(x)\log\,p(x) \\ =& H(X,Y) - H(X). \end{align}

Read more about this topic:  Conditional Entropy

Famous quotes containing the words chain and/or rule:

    “Oft, in the stilly night, Ere Slumber’s chain has bound me, Fond Memory brings the light Of other days around me.”
    —Thomas Moore (1779–1852)

    “The earliest instinct of the child, and the ripest experience of age, unite in affirming simplicity to be the truest and profoundest part for man. Likewise this simplicity is so universal and all-containing as a rule for human life, that the subtlest bad man, and the purest good man, as well as the profoundest wise man, do all alike present it on that side which they socially turn to the inquisitive and unscrupulous world.”
    —Herman Melville (1819–1891)