DailyDDoSe: Conditional entropy -

Friday, February 11, 2011

Conditional entropy -

Conditional entropy

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Individual (H(X),H(Y)), joint (H(X,Y)), and conditional entropies for a pair of correlated subsystems X,Y with mutual information I(X; Y).

In information theory, the conditional entropy (or equivocation) quantifies the remaining entropy (i.e. uncertainty) of a random variable $Y$ given that the value of another random variable $X$ is known. It is referred to as the entropy of $Y$ conditional on $X$ , and is written $H (Y | X)$ . Like other entropies, the conditional entropy is measured in bits, nats, or bans.

Contents
[hide]

1 Definition

2 Chain rule

3 Intuition

4 Generalization to quantum theory

5 Other properties

6 References

7 See also

[edit] Definition

More precisely, if $H (Y | X = x)$ is the entropy of the variable $Y$ conditional on the variable $X$ taking a certain value $x$ , then $H (Y | X)$ is the result of averaging $H (Y | X = x)$ over all possible values $x$ that $X$ may take.

Given discrete random variable $X$ with support $\mathcal X$ and $Y$ with support $\mathcal Y$ , the conditional entropy of $Y$ given $X$ is defined as:

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

[edit] Chain rule

From this definition and the definition of conditional probability, the chain rule for conditional entropy is

$H(Y|X)\,=\,H(Y,X)-H(X) \, .$

This is true because

$\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}$

[edit] Intuition

Intuitively, the combined system contains $H (X, Y)$ bits of information: we need $H (X, Y)$ bits of information to reconstruct its exact state. If we learn the value of $X$ , we have gained $H (X)$ bits of information, and the system has $H (Y | X)$ bits of uncertainty remaining.

$H (Y | X) = 0$ if and only if the value of $Y$ is completely determined by the value of $X$ . Conversely, $H (Y | X) = H (Y)$ if and only if $Y$ and $X$ are independent random variables.

[edit] Generalization to quantum theory

In quantum information theory, the conditional entropy is generalized to the conditional quantum entropy.

[edit] Other properties

For any $X$ and $Y$ :

$H(X|Y) \le H(X)$

$H (X, Y) = H (X | Y) + H (Y | X) + I (X; Y)$ , where $I (X; Y)$ is the mutual information between $X$ and $Y$ .

$I(X;Y) \le H(X)$ , where $I (X; Y)$ is the mutual information between $X$ and $Y$ .

For independent $X$ and $Y$ :

$H (Y | X) = H (Y)$ and $H (X | Y) = H (X)$

[edit] References

Theresa M. Korn; Korn, Granino Arthur. Mathematical Handbook for Scientists and Engineers: Definitions, Theorems, and Formulas for Reference and Review. New York: Dover Publications. pp. 613–614. ISBN 0-486-41147-8.

C. Arndt (2001). Information Measures: Information and its description in Science and Engineering). Berlin: Springer. pp. 370–373. ISBN 3-540-41633-1.

[edit] See also

Entropy (information theory)

Mutual information

Conditional quantum entropy

Variation of information

Likelihood function