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:

    “The years seemed to stretch before her like the land: spring, summer, autumn, winter, spring; always the same patient fields, the patient little trees, the patient lives; always the same yearning; the same pulling at the chain—until the instinct to live had torn itself and bled and weakened for the last time, until the chain secured a dead woman, who might cautiously be released.”
    —Willa Cather (1873–1947)

    “They can rule the world while they can persuade us
    our pain belongs in some order.
    Is death by famine worse than death by suicide,
    than a life of famine and suicide ... ?”
    —Adrienne Rich (b. 1929)