Information Bottlenecks in Markov Chains

Sources:

1. Thomas M. Cover & Joy A. Thomas. (2006). Chapter 8. Differential Entropy. Elements of Information Theory (2nd ed., pp. 243-255). Wiley-Interscience.
2. Fady Alajaji & Po-Ning Chen. (2018). Chapter 5. Differential Entropy and Gaussian Channels. An Introduction to Single-User Information Theory (1st ed., pp. 165-218). Springer.

For discrete states

Suppose a (non-stationary) Markov chain starts in one of $n$ states, necks down to $k<n$ states, and then back to $m>k$ states. Thus $X_1\to X_2\to X_3$, i.e., $p(x_1,x_2,x_3)=$ $p\left(x_1\right)p(x_2\mid x_1)p(x_3\mid x_2)$, for all $x_1\in \{1,2,\dots ,n\},x_2\in \{1,2,\dots ,k\},x_3\in \{1,2,\dots ,m\}$.

Questions:

1. Show that the dependence of $X_1$ and $X_3$ is limited by the bottleneck by proving that $I(X_1;X_3)\le$ $\log k$.

2. Evaluate $I(X_1;X_3)$ for $k=1$, and conclude that no dependence can survive such a bottleneck.

Solution:

Since $X_1\to X_2\to X_3$, from the data processing inequality we have: $$I(X_1;X_3)\le I(X_1;X_2).$$

By the definition of muual information, we know $$I(X_1;X_2)=H\left(X_2\right)-H(X_2\mid X_1).$$ Since entropy is non-negative, we ontain: $$I(X_1;X_2)=H\left(X_2\right)-H(X_2\mid X_1)\le H(X_2).$$ Meanwhile, let ${\mathcal{X}}_2$ denote the number of elements in the range of $X_2$, due to theorem $H(X)\le \log |\mathcal{X}|$, we have $$H(X_2)\le {\mathcal{X}}_2$$ Finally, $$I(X_1;X_3)\le I(X_1;X_2)=H\left(X_2\right)-H(X_2\mid X_1)\le H\left(X_2\right)\le \log k.$$

2. For $k=1,I(X_1;X_3)\le \log 1=0$. Hence $I(X_1;X_3)=0$. Hence, for $k=1,X_1$ and $X_3$ are

For continual states