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:

    “You know, he wanted to shoot the Royal Family, abolish marriage, and put everybody who’d been to public school in a chain gang. Yeah, he was a idealist, your dad was.”
    —David Mercer, British screenwriter, and Karel Reisz. Mrs. Dell (Irene Handl)

    “In Russia, whatever be the appearance of things, violence and arbitrary rule is at the bottom of them all. Tyranny rendered calm by the influence of terror is the only kind of happiness which this government is able to afford its people.”
    —Marquis De Custine (1790–1857)