On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

The information bottleneck (IB) seeks a representation U of a source X that retains as much information as possible about a target Y, subject to a constraint on I(U;X). A classical argument shows that it suffices to consider representations with at most |X|+1 symbols, and this bound is known to be tight whenever |X| ≥ 3. We show that the binary case behaves differently: if X is binary and Y is finite, then for every joint distribution of (X,Y) and every rate constraint, the IB optimum is attained by a binary U. Hence the bound |U| ≤ |X|+1 sharpens to |U| ≤ |X| for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.