I'm looking for two intuitive examples of random variables X, Y and Z. One where
$ I(X;Y|Z) > I(X;Y) $
and another set of X,Y and Z where
$ I(X;Y|Z) < I(X;Y)$
According to wikipedia conditioning can both reduce and increase mutual information, but I haven't found any simple, clear and intuitive examples of this yet.
On
When searching on another closely related subject, I found this wikipedia article which gave the following two great examples:
Increases by conditioning
$I(X;Y|Z) > I(X;Y)$ when X and Y both are causes of some common effect Z. This means, that if you know that Z has happened, suddenly X and Y are more dependent than they were before.
For example, if a car's engine fails to start(event Z) it may be because of either blocked fuel pump(X) or that the battery is dead(Y). Normally X and Y are independent($I(X;Y) = 0$), since the fuel pump and battery work independently.
But if the engine doesn't start, they suddenly become very dependent. If the fuel pump works, it implies that the battery is dead and if the battery works, it implies that the fuel pump is blocked, giving $I(X;Y|Z) > 0 = I(X;Y)$
Decreases by conditioning
$I(X;Y|Z) < I(X;Y)$ when Z is the cause of both X and Y. For example if clouds always cause rain and blocks the sun $I(rainy,dark|cloudy) = 0$, since we already know everything about $rainy$ and $dark$ if we know that their common cause $cloudy$ is true. But if we don't know the root cause, the event $rainy$ could influence the event $dark$, giving $I(rainy;dark) > 0$. So $I(rainy;dark|cloudy) < I(rainy;dark)$
$I(X;Y|Z)$ is interpreted as `` the reduction in uncertainty of $X$ due to the knowledge of $Y$ when $Z$ is given''.
The Data Processing inequality tells you if $X \to Y \to Z$ (that is, $X,Y,Z$ form a Markov Chain), then $I(X;Y) \geq I(X;Z)$. Taking $Z=g(Y)$, you get $I(X;Y) \geq I(X;g(Y))$ - that is, functions of $Y$ cannot increase mutual information. Another corollary is, $I(X;Y|Z) \leq I(X;Y)$ where $X \to Y \to Z$.
In the case where $X,Y,Z$ do not follow a Markov chain, you can have $I(X;Y|Z) > I(X;Y)$. Easy example is $X,Y$ are independent Bernoulli(1/2) random variables and $Z=X+Y$. $I(X;Y) = 0$, but $I(X;Y|Z) = 1/2$.
(This is taken from Cover & Thomas, Elements of Information Theory 2e, Chapter 2. There is a nice problem in Chapter 2 on what goes wrong with extending mutual information to multiple variables, but it isn't the same idea.)