Entropy, Mutual Information, and the Information Bottleneck

Let $X$ and $Y$ be finite discrete random variables with joint distribution

$$p(x,y)=\Pr(X=x,Y=y).$$

The marginals are

$$p(x)=\sum_y p(x,y), \qquad p(y)=\sum_x p(x,y).$$

Using base-2 logarithms, entropy is measured in bits:

$$H(X)=-\sum_x p(x)\log_2 p(x).$$

The convention is that terms with $p(x)=0$ contribute $0$, because $\lim_{p\to 0^+}p\log p=0$.

Conditional entropy measures the uncertainty left in $Y$ after observing $X$:

$$H(Y\mid X)=-\sum_{x,y}p(x,y)\log_2 p(y\mid x).$$

Mutual information is the uncertainty reduction:

$$I(X;Y)=H(Y)-H(Y\mid X).$$

Equivalently, it is the KL divergence between the true joint table and the independent table formed from the marginals:

$$I(X;Y)=\sum_{x,y}p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)} =\mathrm{KL}(p(x,y)\|p(x)p(y)).$$

That identity is the operational test for dependence. If $p(x,y)=p(x)p(y)$ everywhere, the log ratio is $0$ and $I(X;Y)=0$. If the joint table differs from independence, mutual information is positive.

Now introduce a representation $T$ produced from $X$. In the most general discrete form, an encoder $p(t\mid x)$ defines

$$p(t,y)=\sum_x p(t\mid x)p(x,y).$$

The bottleneck objective can be written as a tradeoff:

$$\max_{p(t\mid x)} I(T;Y)-\lambda I(X;T),$$

where $\lambda\ge 0$ controls how much we punish complexity. The relevance term $I(T;Y)$ says how much the representation keeps about the target. The complexity term $I(X;T)$ says how much detail about the original input survived.

In the deterministic merge used in the demo, $T=g(X)$, so $H(T\mid X)=0$ and

$$I(X;T)=H(T)-H(T\mid X)=H(T).$$

That makes the tradeoff visible without estimators. A merge can reduce $I(X;T)$, but because $T$ is computed from $X$, it cannot create new information about $Y$:

$$I(T;Y)\le I(X;Y).$$

The best bottleneck is therefore not always the representation with maximum relevance and not always the smallest representation. It depends on the penalty and on which distinctions in $X$ matter for $Y$.