Is a binary representation always sufficient for the binary-source information bottleneck?

The cardinality bound asks how many symbols U needs

The information bottleneck looks for a representation U of a source X that keeps as much information as possible about a target Y while holding I(U;X) below a rate constraint R. Formally, for R ≥ 0 the optimal tradeoff is the IB function F(R) = max { I(U;Y) : U↔X↔Y, I(U;X) ≤ R }. The question this paper answers is not how to compute F(R), but how large the alphabet of U must be for that maximum to be attained.

A classical argument, due to Witsenhausen and Wyner and also following from the support lemma, shows that |U| ≤ |X|+1 symbols always suffice. That bound was later shown to be tight whenever |X| ≥ 3: for Hamming channels with uniform input, |X|+1 symbols are necessary for all rates in some interval (0, R_c). The binary case |X| = 2 was left uncovered by those results, and this paper closes that gap.

Binary sources need only two symbols, not three

Theorem 2.1 states that if X = {0,1} and Y is finite, then for any R ≥ 0 the maximum in the IB function is attained by some U with |U| ≤ 2. The result holds for every joint distribution P_XY and every rate constraint, not just for symmetric channels. Consequently the general bound |U| ≤ |X|+1 is never tight for binary sources, and the condition |X| ≥ 3 in the earlier tightness result cannot be dropped.

This is a statement about the IB function F itself, not only about the IB Lagrangian. Earlier work had pointed out that a claim of |U| ≤ |X| conflates the Lagrangian, for which |X| symbols do suffice, with F, whose graph may contain linear segments. The binary theorem is therefore stronger than a Lagrangian cardinality claim: it covers the function's optimum at every rate.

Why the extra symbol was thought necessary

The |X|+1 bound is not an artifact of loose analysis. For Hamming channels with uniform input and |X| ≥ 3, every optimal U needs |X|+1 symbols at small rates, so the bound is achieved. The reason the binary case escapes this is structural: the proof technique that yields the sharper bound relies on the source posterior being a scalar, which fails once the probability simplex on X has dimension |X|−1 ≥ 2.

For a doubly symmetric binary source, Mrs. Gerber's Lemma already showed that a binary U is optimal, but that argument uses the symmetry of the channel. The contribution here is to remove the symmetry assumption and establish the binary optimum for arbitrary joint distributions with a binary X.

The proof turns IB into a convex hull problem

The argument reduces the IB problem to minimizing H(Y|U) over the convex hull K of a curve. Each symbol u of a candidate U corresponds to a point q_u = P(X=1|U=u) in [0,1], and the achievable pairs (H(X|U), H(Y|U)) are exactly the points (s,t) with (p,s,t) ∈ K, where p = P(X=1). Because I(U;X) = h(p) − H(X|U) and I(U;Y) = H(Y) − H(Y|U), maximizing I(U;Y) under I(U;X) ≤ R is equivalent to minimizing t over K subject to s ≥ h(p) − R.

Applying the separating hyperplane theorem to K and the region { s ≥ h(p) − R, t < t* } produces a nonzero vector (c0, c1, c2) with c2 ≥ 0 and a function ψ(q) = c0 q + c1 h(q) + c2 g(q), where h is the binary entropy of q and g(q) = H(f(q)) with f(q) = (1−q)w0 + q w1. Every atom q*_u of an optimal U is then a minimizer of ψ on [0,1] with the same minimum value α.

Concavity of a derivative ratio limits the minimizers

The key step is a curvature computation specific to binary sources. Writing ψ''(q) = h''(q)(c1 + c2 r(q)) with r(q) = g''(q)/h''(q), the paper shows that r(q) = 1 − Σ_y w0(y)w1(y)/f_y(q), and since each 1/f_y(q) is convex in q and w0(y)w1(y) ≥ 0, r is concave on (0,1). Because h''(q) < 0, the set where ψ''(q) < 0 is the superlevel set { q : c1 + c2 r(q) > 0 } of a concave function, hence an interval.

That interval property is what bounds the number of minimizers. Lemma 4.1 shows that if ψ(q) = α at more than two points in [0,1], then ψ is identically α on [0,1]. The proof uses the fact that the set where ψ'' < 0 cannot meet both intervals between three ordered minimizers q1 < q2 < q3, since that would force ψ''(q2) < 0 at an interior minimizer, contradicting ψ''(q2) ≥ 0. The remaining case reduces to a polynomial identity argument.

Two cases both yield a binary optimum

Given that every q*_u minimizes ψ, Lemma 4.1 leaves two possibilities. In the first case the q*_u take at most two distinct values, and merging the symbols of U* that share the same q*_u produces a new representation Û = σ(U*) with |Û| ≤ 2. The merged representation preserves the point z* = (p, H(X|U*), H(Y|U*)), so it is optimal.

In the second case ψ ≡ α, which forces c1 + c2 r(q) ≡ 0 and hence c2 > 0. Then H(Y|U) is determined by H(X|U) through H(Y|U) = (α − c0 p − c1 H(X|U))/c2, so any U with H(X|U) = s* is optimal. A binary such U is constructed by time-sharing: with T ~ Bern(θ) and X' ~ P_X independent of (X,Y), set U_θ = X when T = 1 and U_θ = X' when T = 0. Since H(X|U_θ) is continuous in θ and runs from 0 at θ = 1 to h(p) at θ = 0, the intermediate value theorem gives a θ* with H(X|U_θ*) = s*. In both cases the maximum is attained by some U with |U| ≤ 2.

The tight bound splits at three source symbols

Combining Theorem 2.1 with the earlier Hamming-channel result gives the tight cardinality bound M, the smallest M such that |U| ≤ M suffices for every P_XY: M = 2 when |X| = 2, and M = |X|+1 when |X| ≥ 3. The binary case is therefore not a small instance of the general bound but a genuinely different regime.

The paper also explains why the proof does not extend to |X| ≥ 3. Steps 1 and 2 still go through, but Steps 3 and 4 rely on q being a scalar. For |X| ≥ 3 the second derivative becomes a Hessian c1 ∇²_q H(q) + c2 ∇²_q H(qW), and the set where it fails to be positive semidefinite is determined by a generalized eigenvalue problem rather than by the sign of a single concave function. Ordering also breaks down: a simplex of dimension at least two has no natural middle point among three minimizers, and the target would be at most |X| minimizers rather than two. These obstructions are not merely technical, since for the Hamming channels the corresponding ψ has at least |X|+1 distinct minimizers. Characterizing which sources with |X| ≥ 3 admit |X| symbols remains open.

Sources used in this answer