0
$\begingroup$

While studying the chain rule for information entropy, I got confused as to its meaning. The rule states:

H(X, Y|Z) = H(X|Z) + H(Y|X, Z)

What then is the difference between $H(X, Y|Z)$ and $H(Y|Z, X)$?

I am wondering whether in $H(X, Y|Z)$ the pipe (|) has precedence so that entropy of the tuple $(X, Y)$ is considered when $Z$ is known or the comma (,) has precedence so that the entropy of the tuple (X, Y) happens which is $Y$ only depends when $Z$ is known?

What about $H(X, Y|Z, Q|K)$? Is there is any rule to understand this notation?

I'm very confused because $H(X, Y|Z)$ and $H(Y|Z, X)$ are not the same even though $H(X, Y) = H(Y, X)$ is valid.

$\endgroup$
0
$\begingroup$

In topics linked to probability and statistics, the pipe symbol | usually means "given": it denotes data known beforehand. For instance, taking two events $A$ and $B$ from a universe $\Omega$, the expression $P(A|B)$ denotes the probability of event $A$ happening, knowing that event $B$ has happened.

For probabilities, this notation denotes conditional probability. In information theory, when talking about Shannon entropy, it denotes conditional entropy (which is computed using conditional probability).

To further elaborate, let us take two random variables $X$ and $Y$ respectively taking values in sets $A$ and $B$. The Shannon entropy of $X$ is then (by convention, for values of $x$ where $P_X(x) = 0$, the term in the sum is considered to be $0$):

$H(X) = -\sum_{x \in A}P_X(x) \log{[P_X(x)]}$

The conditional entropy of $X$ given $Y = y$ is:

$H(X|Y=y) = -\sum_{x \in A}P_{X|Y}(x|y) \log{[P_{X|Y}(x|y)]}$

The conditional entropy of $X$ given $Y$ is then the weighted average of the previously defined entropy over all values of $Y$:

$H(X|Y) = -\sum_{x \in A, y \in B}P_Y(y)P_{X|Y}(x|y) \log{[P_{X|Y}(x|y)]} = -\sum_{x \in A, y \in B}P_{X,Y}(x,y) \log{[P_{X|Y}(x|y)]}$

Moving on to the comma notation, it denotes joint probability and thus joint entropy. In other words, $P_{X,Y}(x,y)$ can also be written as $P(X = x, Y = y)$.

Combining these two concepts, $P_{X,Y|Z}(x,y|z)$ denotes the probability of $(X,Y)$ taking the value $(x, y)$, knowing $Z$. The conditional entropy $H(X,Y|Z)$ makes use of this probability:

$H(X,Y|Z=z) = -\sum_{(x,y) \in A \times B}P_{X,Y|Z}(x,y|z) \log{P_{X,Y|Z}(x,y|z)}$

$H(X,Y|Z) = -\sum_{(x,y,z) \in A \times B \times C}P_{X,Y,Z}(x,y,z) \log{P_{X,Y|Z}(x,y|z)}$

Now that we have the basics down, we can move on to your questions.

First of all, $H(X,Y|Z)$ is the entropy of $X$ and $Y$ together (taking the value $(x,y)$) when the value of $Z$ is given, while $H(Z|X,Y)$ is the entropy of $Z$ when the values of $X$ and $Y$ are given.

There is no real rule to understand $H(X,Y|Z,Q|K)$ and I strongly doubt you will ever see this notation in any reputable textbook.

Finally, $H(X,Y|Z)$ and $H(Z|X,Y)$ cannot be equivalent, as you need to know the value of $Z$ for the first one and the value of $X$ and $Y$ for the second one.

As a rule of thumb, uppercase letters denote random variables, whereas lowercase letters denote actual numbers.

As an addendum, I would like to explain the chain rule (in its reduced format as you mention it in your questions). Seeing as entropy is a measure of uncertainty, we can say that the formula $H(X,Y|Z) = H(X|Z) + H(Y|X,Z)$ means: the uncertainty of $X$ and $Y$ knowing $Z$ is the uncertainty of $X$ knowing $Z$ plus the uncertainty of $Y$ knowing $X$ and $Z$ (since after the first term you've found out the actual value of $X$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.