Information Bottleneck on General Alphabets
Georg Pichler, Günther Koliander

arXiv:1801.01050v1 [] 3 Jan 2018

Abstract—We prove rigorously a source coding theorem
that can probably be considered folklore, a generalization
to arbitrary alphabets of a problem motivated by the Information Bottleneck method. For general random variables
(Y, X), we show essentially that for some n ∈ N, a function f
with rate limit log|f | ≤ nR and I(Yn ; f (Xn )) ≥ nS exists if and
only if there is a discrete random variable U such that the
Markov chain Y −◦− X −◦− U holds, I(U; X) ≤ R and I(U; Y) ≤ S.

II. Main Result
Let Y and X be random variables with arbitrary alphabets
SY and SX , respectively. The bold-faced random vectors Y and
X are n i.i.d. copies of Y and X, respectively. We then have the
following definitions.
Definition 1. A pair (S, R) ∈ R2 is achievable if for some
n ∈ N there exists a measurable function f : SXn → M for some
finite set M with bounded cardinality n1 log|M| ≤ R and

I. Introduction
Since its inception [1], the Information Bottleneck (IB)

1
method became a widely applied tool, especially in the context
I Y; f (X) ≥ S.
(2)
n
of machine learning problems. It has been successfully applied
to various problems in machine learning [2], computer vision The set of all achievable pairs is denoted R ⊆ R2 .
[3], biomedical signal processing [4], and communications [5],
2
[6], [7]. Furthermore, it is a valuable tool for channel output Definition 2. A pair (S, R) ∈ R is IB-achievable if there
exists an additional random variable U with arbitrary alphabet
compression in a communication system [8], [9].
In the underlying information-theoretic problem, we define a SU , satisfying Y −◦− X −◦− U and
pair (S, R) ∈ R2 to be achievable for the two arbitrary random
R ≥ I(X; U),
(3)
sources (Y, X), if there exists a function f with rate limited
S
≤
I(Y;
U).
(4)
range n1 log|f | ≤ R and I(Y; f (X)) ≥ nS, where (Y, X) are n
independent and identically distributed (i.i.d.) copies of (Y, X). The set of all IB-achievable pairs is denoted RIB ⊆ R2 .
While this Shannon-theoretic problem and variants thereof
In what follows, we will prove the following theorem.
were also considered (e. g., [10], [11]), a large part of the
literature is aimed at studying the IB function
Theorem 3. The equality RIB = R holds.
SIB (R) =

sup

I(U; Y)

(1)

U : I(U;X)≤R
Y−
◦−X−◦−U

in different contexts. In particular, several works (e. g., [1], [2],
[12], [13], [14]) intend to compute a probability distribution
that achieves the supremum in (1). The resulting distribution
is then used as a building block in numerical algorithms, e. g.,
for document clustering [2] or dimensionality reduction [12].
In the discrete case, SIB (R) is equal to the maximum of all
S such that (S, R) is in the achievable region (closure of the
set of all achievable pairs). This statement has been re-proven
many times in different contexts [15], [11], [16], [17]. In this
note, we prove a theorem, which can probably be considered
folklore, extending this result from discrete to arbitrary random
variables. Formally speaking, using the definitions in [18], we
prove that a pair (S, R) is in the achievable region of an
arbitrary source (Y, X) if and only if, for every ε > 0, there
exists a random variable U with Y −◦− X −◦− U, I(X; U) ≤ R + ε,
and I(Y; U) ≥ S − ε. This provides a single-letter solution to
the information-theoretic problem behind the information bottleneck method for arbitrary random sources and in particular
it shows, that the information bottleneck for Gaussian random
variables [12] is indeed the solution to a Shannon-theoretic
problem.
In the proof, both the inner bound and the converse are
inferred from the discrete case. The techniques employed could
therefore be useful for lifting other discrete coding theorems to
the case of arbitrary alphabets.
G. Pichler is with the Institute of Telecommunications, Technische Universität Wien, Vienna, Austria
G. Koliander is with the Acoustics Research Institute, Austrian
Academy of Sciences, Vienna, Austria
Funding by WWTF Grants MA16-053, ICT15-119, and NXT17-013.

III. Preliminaries
When introducing a function, we implicitly assume it to be
measurable w.r.t. the appropriate σ-algebras. The σ-algebra
associated with a finite set is its power set and the σ-algebra
associated with R is the Borel σ-algebra. The symbol ∅ is used
for the empty set and for a constant random variable. When
there is no possibility for confusion, we will not distinguish
between a single-element set and its element, e. g., we write x
instead of {x} and 1x for the indicator function of {x}. We use
A △ B := A \ B ∪ B \ A to denote the symmetric set difference.
Let (Ω, Σ, µ) be a probability space. A random variable
X : Ω → SX takes values in the measurable space (SX , AX ). The
push-forward probability
measure µX : AX → [0, 1] is defined by

µX (A) = µ X−1 (A) for all A ∈ AX . We will state most results
in terms of push-forward measures and usually ignore the
background probability space. When multiple random variables
are defined, we implicitly assume the push-forward measures to
be consistent in the sense that, e. g., µX (A) = µXY (A × SY ) for
all A ∈ AX .
For n ∈ N let Ωn denote the n-fold Cartesian product
of (Ω, Σ, µ). A bold-faced random vector, e. g., X, defined on
Ωn , is an n-fold copy of X, i. e., X = Xn . Accordingly, the
corresponding push-forward measure, e. g., µX is the n-fold
product measure.
For a random variable X let aX , bX , and cX denote arbitrary
functions on SX , each with finite range. We will use the symbol
MX to denote the range of aX , i. e., aX : SX → MX .
Definition 4 ([19, Definition 8.11]). The conditional expectation of a random variable X with SX = R, given a random
variable Y, is a random variable E[X|Y] such that
1) E[X|Y] is σ(Y)-measurable, and





2) for all A ∈ σ(Y), we have E 1A E[X|Y] = E[1A X] .
The conditional probability of an event B ∈ Σ given Y is defined
as P{B|Y} := E[1B |Y].
The conditional expectation and therefore also the conditional
probability exists and is unique up to equality almost surely
by [19, Theorem 8.12]. Furthermore, if (SX , AX ) is a standard
space [18, Section 1.5], there even exists a regular conditional
distribution of X given Y [19, Theorem 8.37].
Definition 5. For two random variables X and Y a regular
conditional distribution of X given Y is a function κX|Y : Ω ×
AX → [0, 1] such that
1) for every ω ∈ Ω, the set function κX|Y (ω) := κX|Y (ω, · ) is
a probability measure on (SX , AX ).
2) for every set A ∈ AX , the function κX|Y ( · ; A) is σ(Y)measurable.
3) for
 µ-a. e. ω ∈ Ω and all A ∈ AX , we have κX|Y (ω; A) =
P X−1 (A) Y (ω) (cf. Def. 4).
Note, in particular, that finite spaces are standard spaces.

Remark 1. If the random variable Y is discrete, then κX|Y
reduces to conditioning given events Y = y for y ∈ SY , i. e.,
κX|Y (ω; A) = µXYµY(A×Y(ω))
(cf. [19, Lemma 8.10]).
(Y(ω))
We use the following definitions and results from [18], [19].
Definition 6. For random variables X and Y with |SX | < ∞
the conditional entropy is defined as [18, Section 5.5]
H(X|Y) :=

Z



(5)

H κX|Y dµ,

I(X; Y|Z) := sup



aX aY



D κaX (X),aY (Y)|Z κaX (X)|Z × κaY (Y)|Z dµ
(6)



= sup H(aX (X)|Z) + H(aY (Y)|Z) − H(aX (X)aY (Y)|Z) , (7)
aX ,aY

κaX (X)aY (Y)|Z ( · ; A × B)




−1
= P X−1 (a−1
(a−1
X (A)) ∩ Y
Y (B)) Z

=P X

−1

(a−1
X (A))



Z P Y

−1

(a−1
Y (B))

(10)
Z

= κaX (X)|Z ( · ; A)κaY (Y)|Z ( · ; B),

(11)
(12)

where (10) and (12) follow from part 3 of Def. 5. This proves
that µ-a. e. the equality of measures κaX (X)aY (Y)|Z = κaX (X)|Z ×
κaY (Y)|Z holds. By the properties of Kullback-Leibler divergence
[18, Theorem 2.3.1] we have I(X; Y|Z) = 0 due to (6).
On the other hand, assume I(X; Y|Z) = 0 and choose arbitrary sets A ∈ AX and B ∈ AY . We define aX := 1A ,
aY := 1B , X̂ := aX (X), and Ŷ := aY (Y). By (6) we have
D κX̂Ŷ|Z (ω) κX̂|Z (ω) × κŶ|Z (ω) = 0 for µ-a. e. ω ∈ Ω, which
is equivalent to the equality µ-a. e. of the measures κX̂Ŷ|Z =
κX̂|Z × κŶ|Z . We obtain µ-a. e.,



P X−1 (A) ∩ Y−1 (B) Z = κX̂Ŷ|Z ( · ; 1 × 1)
= κX̂|Z ( · , 1)κŶ|Z ( · , 1)



=P X

−1



(A) Z P Y

−1

(13)
(14)

(B) Z .

(15)

(ii): see [18, Lemma 5.5.6].
(iii): see [18, Lemma 5.5.7].
(iv): Using Prop. (i) we have I(X; Z|Y) = 0 and by Prop. (iii)
it follows that
I(X; Z) ≤ I(X; YZ)

(16)

= I(X; Y) + I(X; Z|Y) = I(X; Y).

where H( · ) denotes discrete entropy on SX . For arbitrary random variables X, Y, and Z the conditional mutual information
is defined as [18, Lemma 5.5.7]

Z

denote arbitrary functions and pick two arbitrary sets A ⊆ MX ,
B ⊆ MY (cf. Section III) and we obtain µ-a. e.

where D( · k · ) denotes Kullback-Leibler divergence [18, Section 2.3]. The mutual information is given by [18, Lemma 5.5.1]

Occasionally we will interpret a probability measure on a
finite space M as a vector in [0, 1]M , equipped with the Borel
σ-algebra. We will use the L∞ -distance on this space.
Definition 9. For two probability measures µ and ν on a finite
space M, their distance is defined as the L∞ -distance d(µ, ν) :=
maxm∈M |µ(m)−ν(m)|. The diameter of A ⊆ [0, 1]M is defined
as diam(A) = supa,b∈A d(a, b).

(8)

Lemma 10 ([20, Lemma 2.7]). For two probability measures µ
and ν on a finite space M with d(µ, ν) ≤ ε ≤ 21 the inequality
|H(µ) − H(ν)| ≤ −ε|M| log ε holds.

Definition 7 ([19, Definition 12.20]). For arbitrary random
variables X, Y, and Z, the Markov chain X −◦− Y −◦− Z holds if,
for any A ∈ AX , B ∈ AZ , the following holds µ-a. e.:

For finite spaces SY , SX , and SU , the statement RIB ⊆ R is
well known, cf., [10, Section IV], [11, Section III.F]. We restate
it in the form of the following lemma.

I(X; Y) := I(X; Y|∅) = sup I(aX (X); aY (Y)).
aX ,aY





IV. Inner Bound



P X−1 (A) ∩ Z−1 (B) Y = P X−1 (A) Y P Z−1 (B) Y . (9)
In the following, we collect some properties of these definitions.
Lemma 8. For random variables X, Y, and Z the following
properties hold:
(i) I(X; Y|Z) ≥ 0 with equality if and only if X −◦− Z −◦− Y.
(ii) For discrete X, i. e., |SX | < ∞, we have I(X; Y) = H(X) −
H(X|Y).
(iii) I(X; YZ) = I(X; Z) + I(X; Y|Z).
(iv) If X −◦− Y −◦− Z, then I(X; Y) ≥ I(X; Z).
Proof. (i): The claim I(X; Y|Z) ≥ 0 follows directly from (6)
and the non-negativity of divergence.
that 
X −◦− Y −◦− Z, i. e., P X−1 (A) ∩ Y−1 (B) Z =
Assume
−1
P X (A) Z P Y−1 (B) Z almost everywhere. Let aX and aY

Lemma 11. For random variables Y, X, and U with finite SY ,
SX , and SU , assume that Y −◦− X −◦− U holds. Then, for any
ε > 0, there exists n ∈ N and a function f : SXn → M with
1
log|M| ≤ I(X; U) + ε such that n1 I Y; f (X) ≥ I(Y; U) − ε.
n
In a first step, we will utilize Lem. 11 to show RIB ⊆ R for
an arbitrary alphabet SX , i. e., we wish to prove the following
Proposition 12, lifting the restriction |SX | < ∞.
Proposition 12. For random variables Y, X, and U with finite
SY and SU , assume that Y −◦− X −◦− U holds. Then, for any
ε > 0, there exists n ∈ N and a function f : SXn → M with
1
log|M| ≤ I(X; U) + ε such that
n


1
I Y; f (X) ≥ I(Y; U) − ε.
n

(17)


+ 2δ|SU | log δ −
≥ H µe
U
e ) + 2δ|SU | log δ,
= I(X̂; U

an
X( · )

Y −◦− X

g( · )
X̂

(a) Inner bound.

f (X)

≈

U

ZY −◦− X

≈

(18)

g( · )

e
U

g(X̂)

X̂

(b) Outer bound.

Fig. 1: Illustrations.

Proof of Proposition 12. Let µYXU be a probability measure on
Ω := SY ×SX ×SU , such that Y −◦− X −◦− U holds. Fix 0 < δ ≤ 21
and find a finite, measurable partition (Pi )i∈I of the space of
probability measures on SU such that for every i ∈ I we have
diam(Pi ) ≤ δ and choose νi ∈ Pi arbitrarily for every i ∈ I.
Define the random variable X̂ : Ω → I as X̂ = i if κU|X ∈ Pi . The
random variable X̂ is σ(X)-measurable (see Appendix A). We
can therefore find a measurable function g such that X̂ = g(X)
by the factorization lemma [19, Corollary 1.97]. Define the new
probability space Ω × ×i∈I SU , equipped with the probability
:= µYXU × ×i∈I νi . Slightly abusing notation,
measure µYXUe
U
I

e i (for every i ∈ I)
we define the random variables Y, X, U, and U
as the according projections. We also use X̂ = g(X) and define
e=U
e X̂ . From this construction we have
the random variable U
µYXUe
-a.
e.
the
equality
of
measures κe
= κe
= νX̂ , as well
U
U|X̂
U|X
I

e and Y −◦− X −◦− U
e (see Appendix B). Therefore,
as Y −◦− X̂ −◦− U
we have µYXUe
-a. e.
U
I

d(κe
, κU|X ) ≤ δ, and
U|X̂

d(κe
, κU|X ) ≤ δ,
U|X

(18)

by κe
= κe
= νX̂ and κU|X , νX̂ ∈ PX̂ . Thus, for any u ∈ SU ,
U|X̂
U|X
µU (u) =
≤

Z

Z

κU|X ( · ; u) dµYXU

(19)

(κe
( · ; u) + δ) dµYXUe
= µe
(u) + δ
U|X
UI
U

(20)

Thus, we obtain

I(X; U) = H(µU ) − H(U|X)


+ δ|SU | log δ −
≥ H µe
U

(21)

Z

H κU|X dµYXU

dµYXUe
U

I

(24)
(25)

=

Z
Z

Z
(18)
≤

≤

Z

κYU|X ( · ; y × u) dµYXU

(26)

κY|X ( · ; y)κU|X ( · ; u) dµYXU

(27)

κY|X ( · ; y)(κe
( · ; u) + δ) dµYXUe
U|X
U

I

κYe
( · ; y × u) dµYXUe
+δ
U|X
U
I

= µYe
(y × u) + δ,
U

(28)
(29)
(30)

where (26) and (30) follow from the defining property of
conditional probability, part 2 of Def. 4. Equality in (29) follows
e and Def. 7. By the same argument, one can
from Y −◦− X −◦− U
show that µYU (y × u) ≥ µYe
(y × u) − δ. Therefore, in total,
U
d(µYU , µYe
)
≤
δ
and,
by
Lem.
10,
U

e )| ≤ −δ|SY ||SU | log δ.
|H(YU) − H(YU

(31)

Thus, the mutual information can be bounded by
I(Y; U) = H(Y) + H(U) − H(YU)

(32)

(21)

e − δ|SU | log δ − H(YU)
≤ H(Y) + H(U)

(33)

(31)

e ) − δ(|SY | + 1)|SU | log δ
≤ I(Y; U

e ) − 2δ|SY ||SU | log δ,
≤ I(Y; U

(34)
(35)

where we applied Lem. 10 in (33) and (34). We apply Lem. 11
e and obtain a function
to the three random variables Y, X̂, and U
e ) − δ and
fˆ: I n → M with n1 I Y; fˆ(X̂) ≥ I(Y; U

(25)
1
e + δ ≤ I(X; U) + δ − 2δ|SU | log δ.
log|M| ≤ I(X̂; U)
n
We have X̂ = g n ◦ X and defining f := fˆ ◦ g, we obtain
1
1
e) − δ
I(Y; f (X)) = I(Y; fˆ(X̂)) ≥ I(Y; U
n
n
(35)
≥ I(Y; U) + 2δ|SY ||SU | log δ − δ.

(36)

(37)
(38)

Choosing δ such that ε ≥ −2δ|SY ||SU | log δ + δ completes the
proof.
We can now complete the proof of the inner bound by
showing the following lemma.
Lemma 13. RIB ⊆ R.

(22)
(23)

0 = I(Y; U|X) = sup I(cY (Y); cU (U)|X) ≥ I(Ŷ; Û|X) ≥ 0 (39)

(21)





Proof. Assuming (S, R) ∈ RIB , choose µYXU according to Def. 2.
Clearly I(X; U) < ∞ to satisfy (3) and thus also I(Y; U) < ∞
by Prop. (ii) of Lem. 8 as Y −◦− X −◦− U holds.
 Pick ε > 0, select
functions aY , aX such that I aX (X); aU (U) ≥ I(X;
 U) − ε, and
select functions bY , bU such that I bY (Y); bU (U) ≥ I(Y; U) − ε
(cf. (8)). Using Û := aU (U), bU (U) as well as Ŷ := aY (Y), we
have

and, by the same argument, µU (u) ≥ µe
(u) − δ, i. e., in total,
U
d(µU , µe
) ≤ δ.
U



H κe
U|X̂

where (22) and (25) follow from Prop. (ii) of Lem. 8, and in
both (23) and (24) we used Lem. 10. From Y −◦− X −◦− U and
Def. 7, we know that µYXU -a. e., we have the equality of measures κYU|X = κY|X × κU|X . Using this equality in (27) we obtain
µYU (y × u) =

Remark 2. Considering that both definitions of achievability
(Defs. 1 and 2) only rely on the notion of mutual information,
it is natural to assume that Def. 6 can be used to directly infer
Proposition 12 from Lem. 11. However, this is not the case. For
an arbitrary discretization aX (X) of X, we do have I(aX (X); U) ≤
I(X; U). However, the Markov chain Y −◦− aX (X) −◦− U does
not hold in general. To circumvent this problem, we will use
a discrete random variable X̂ = g(X) with an appropriate
e , satisfying
quantizer g and construct a new random variable U
e such that I(Y; U
e ) is close
the Markov chain Y −◦− X̂ −◦− U
to I(Y; U). Figure 1a illustrates this strategy. We choose the
quantizer g based on the conditional probability distribution of
U given X, i. e., quantization based on κU|X using L∞ -distance
(cf. Def. 9). Subsequently, we will use that, by Lem. 10, a small
L∞ -distance guarantees a small gap in terms of information
measures.

Z

cY ,cU

as well as



I(X; U) = sup I cX (X); cU (U)
cX ,cU

(40)

≥ sup I(cX (X); Û) = I(X; Û)

(41)

cX

and



I(Y; U) − ε ≤ I bY (Y); bU (U) ≤ I(Ŷ; Û).

(42)

We apply Proposition 12, substituting Û → U and Ŷ → Y.
Proposition 12 guarantees the existence of a function f : SXn →
M with

1
n

(41)

(3)

log|M| ≤ I(X; Û) + ε ≤ I(X; U) + ε ≤ R + ε and

1
1
I(Y; f (X)) = sup I(cY ◦ Y; f (X))
n
n cY
1
1
≥ I(an
◦ Y; f (X)) = I(Ŷ; f (X))
n Y
n
(17)

(42)

(43)
(44)

(4)

≥ I(Ŷ; Û) − ε ≥ I(Y; U) − 2ε ≥ S − 2ε.

(45)

Thus, (S − 2ε, R − ε) ∈ R and therefore (S, R) ∈ R.
V. Outer Bound
We also start the proof of the outer bound with the wellknown result RIB ⊆ R for finite spaces SY , SX , and SU , cf., [10,
Section IV], [11, Section III.F]. The statement is rephrased in
the following lemma.
Lemma 14. Assume that the spaces SY and SX are both finite
and µYX is fixed. For some n ∈ N, let f : SXn → M be a function
with |M| < ∞. Then there exists a probability measure µYXU ,
extending µYX , such that SU is finite, Y −◦− X −◦− U, and
1
(46)
I(X; U) ≤ log|M|,
n
1
I(Y; U) ≥ I(Y; f (X)).
(47)
n
We can slightly strengthen Lem. 14.
Corollary 15. Assume that, in the setting of Lem. 14, we are
given µZYX on SZ ×SY ×SX , extending µYX , where SZ is arbitrary,
not necessarily finite. Then there exists a probability measure
µZYXU , extending µZYX , such that SU is finite and ZY −◦− X −◦− U,
(46), and (47) hold.
Proof. Apply Lem. 14 to obtain µYXU on SY ×SX ×SU satisfying
(46), (47), and Y −◦− X −◦− U. We define µZYXU by
µZYXU (A × y × x × u) =


1
I Y; f (X) − ε.
(50)
n
Remark 3. In the proof of Proposition 16, we face a similar
problem as in the inner bound, which was described in Rmk. 2.
For any “per-letter” quantization X̂ := an
X (X), in general f (X)
cannot be written as a function g(X̂) of the quantization X̂.
We will approach this problem, by choosing aX such that, for
m ∈ M, the pre-image f −1 (m), can be well approximated,
−1
in terms of low probability of error, by (an
(Am ) for some
X)
n
Am ⊆ MX . Choosing g such that, g(x̂) = m with high
probability, whenever x̂ ∈ Am , we obtain g(X̂), which is close to
f (X) in terms of distribution and thus the information measures
are also close by Lem. 10. Figure 1b provides a sketch of this
strategy.
I(Y; U) ≥

µZYX (A × y × x)
µYXU (y × x × u)
µYX (y × x)
(48)

for any (y, x, u) ∈ SY × SX × SU and A ∈ AZ . Pick arbitrary
A ∈ AZ , y ∈ SY , and u ∈ SU . The Markov chain ZY −◦− X −◦− U
now follows as the events Z−1 (A) ∩ Y−1 (y) and U−1 (u) are
independent given X−1 (x) for any x ∈ SX (cf. Rmk. 1).
Again, we proceed by extending Cor. 15, lifting the restriction that SX is finite and obtain the following proposition.
Proposition 16. Given a probability measure µZYX as in
Cor. 15, assume that |SY | < ∞. For some n ∈ N, let f : SXn → M
be a function with |M| < ∞. Then, for any ε > 0, there exists a
probability measure µZYXU , extending µZYX with ZY −◦− X −◦− U
and
1
I(X; U) ≤ log|M|
(49)
n

S

Qm
Proof of Proposition 16. We can partition SXn =
m∈M
into finitely many measurable, mutually disjoint sets Qm :=
f −1 (m), m ∈ M. We want to approximate the sets Qm by a finite union of rectangles in the semiring [19, Definition 1.9] Ξ :=

B : B = ×n
i=1 Bi with Bi ∈ AX . We choose δ > 0, which
will be specified S
later. According to [19, Theorem 1.65(ii)], we
K
(m)
(m)
obtain B(m) := k=1 Bk for each m ∈ M, where Bk ∈ Ξ
(m)
are mutually disjoint sets, satisfying µX (B
△ Qm ) ≤ δ. Since
(m)
(m)
(m)
(m)
Bk ∈ Ξ, we have Bk = ×n
B
for some Bk,i ∈ AX . We
i=1 k,i
can construct functions aX and g such that g ◦San
X (x) = m
′
whenever x ∈ B(m) and x 6∈ B(6m) with B(6m) := m′ 6=m B(m ) .
Indeed, we obtain aX by finding a measurable partition of SX
(m)
(m)
that is finer than (Bk,i , (Bk,i )c ) for all i, k, m. For fixed
m ∈ M, we have
Qm ⊆ Qm ∪ B(m) \ B(6m)
⊆ B

(m)

\B

(6m)





∪ Qm \ B



(m)



[

∪



[

Qm ∩ B

(52)

m′ 6=m



[

⊆ B(m) \ B(6m) ∪ Qm △ B(m) ∪
⊆ B(m) \ B(6m) ∪

(51)
(m′ )

′

B(m ) \ Qm′

(53)

m′ 6=m

′

B(m ) △ Qm′ ,

(54)

m′

where we used the fact that Qm ∩ Qm′ = ∅ for m 6= m′ in (53).
Using X̂ := aX (X), we obtain for any y ∈ SYn
µYf (X) (y × m) = µYX (y × Qm )
(54)

≤ µYX (y × B(m) \ B(6m) ) +

(55)

X

′

µX (B(m ) △ Qm′ )

(56)

m′

≤ µYg(X̂) (y × m) + |M|δ.
On the other hand, we have
µYf (X) (y × m) = µY (y) −

X

(57)

µYf (X) (y × m′ )

(58)



(59)

m′ 6=m

(57)

≥ µY (y) −

X

µYg(X̂) (y × m′ ) + |M|δ

m′ 6=m

≥ µYg(X̂) (y × m) − |M|2 δ.

(60)

We thus obtain d(µYf (X) , µYg(X̂) ) ≤ |M|2 δ. This also implies
d(µf (X) , µg(X̂) ) ≤ |SY |n |M|2 δ. Assume |SY |n |M|2 δ ≤ 12 and
apply Cor. 15 substituting X̂ → X, XZ → Z, and the function
g → f . This yields a random variable U with XZY −◦− X̂ −◦− U,
I(X̂; U) ≤

1
log|M|, and
n

I(Y; U) ≥


1
I Y; g(X̂) .
n

(61)

We also obtain ZY −◦− X −◦− U due to
0 = I(XZY; U|X̂)

(62)

= I(XZY; U) − I(U; X̂)

(63)

≥ I(XZY; U) − I(U; X)

(64)

= I(ZY; U|X)

(65)

≥ 0,

(66)

where (62) follows from XZY −◦− X̂ −◦− U using Prop. (i)
of Lem. 8, (63) and (65) follow from Prop. (iii) of Lem. 8, (64)
is a consequence of Def. 6, and we used Prop. (i) of Lem. 8 in
(66). This also immediately implies 0 = I(X; U|X̂) and hence
(61)
1
log|M| ≥ I(X̂; U) = I(X̂; U) + I(X; U|X̂)
n
= I(XX̂; U) = I(X; U),

(67)
(68)

every component is σ(X)-measurable. Thus, we have X̂−1 (i) =
h−1 (Pi ) ∈ σ(X).

e and Conditional Independence
B. Distribution of U
We will first show that µYXUe
-a. e.
U
I

κe
= κe
= νX̂ .
U|X̂
U|X

Clearly, νX̂ is a probability measure everywhere. Fixing u ∈ SU ,
we need that νX̂ (u) is σ(X̂)-measurable, which is shown by the
factorization lemma [19, Corollary 1.97], when writing νX̂ (u) =
ν(·) (u) ◦ X̂. Also, this proves σ(X)-measurability as X̂ is σ(X)measurable, i. e., σ(X̂) ⊆ σ(X). It remains to show the defining
property of conditional probability, part 2 of Def. 4. Choosing
B ∈ σ(X) and u ∈ SU , we need to show that

h

(61) 1

I Y; g(X̂)



n

1
H(Y) + H(g(X̂)) − H(Yg(X̂))
n
 1
1
≥ I Y; f (X) + |SY |n |M|3 δ log(|M|2 δ)
n
n
1
+ |SY |n |M|3 δ log(|SY |n |M|2 δ)
n
 2
1
≥ I Y; f (X) + |SY |n |M|3 δ log(|M|2 δ)
n
n
where we used Lem. 10 in (71). Select δ such that
− n2 |SY |n |M|3 δ log(|M|2 δ).
=

(69)
(70)

E[1B νX̂ (u)] =
=

(71)
=

(72)



ε ≥

=
=

(73)

1
I(X; U) ≤ log|M| ≤ R
n
I(Y; U) ≥ I(aY (Y); U)



Z

i

(81)
(82)
(83)
(84)

Z

e )1y (Y) dµ
1 B 1 u (U
.
YXUe
U
I

and by integrating, we indeed obtain

=

1B κY|X ( · ; y)νX̂ (u) dµYXU

(86)

XZ

(87)

1B 1i (X̂)κY|X ( · ; y)νi (u) dµYXU

i∈I

(76)
=

Hence, (S − 2ε, R) ∈ RIB and consequently (S, R) ∈ RIB .

X

νi (u)

i∈I

=

XZ
i∈I

=

XZ
i∈I

Appendix

For u ∈ SU consider the σ(X)-measurable function hu :=
κU|X ( · ; u) on [0, 1]. We obtain the vector valued function h :=
(hu )u∈SU on [0, 1]|SU | . This function h is σ(X)-measurable as

i

i



(85)

(75)

A. X̂ is σ(X)-measurable

e)
E 1i (X̂)1B 1u (U

1B κY|X ( · ; y)νX̂ (u) dµYXU =

(74)

Acknowledgment

(80)

where we used Fubini’s theorem [19, Theorem 14.16] in (82).
e |X) = 0, we need to show that for every y ∈
To prove I(Y; U
SY , u ∈ SU , and B ∈ σ(X), we have

Z

The authors would like to thank Michael Meidlinger for
providing inspiration for this work.



ei)
E 1i (X̂)1B 1u (U

X h
h

(79)

e) ,
= E 1 B 1 u (U

(73)

I an
Y (Y); f (X) − ε ≥ S − 2ε.

i 



e i ) E 1i (X̂)1B
E 1 u (U

X h
i∈I

(2)



νi (u)E 1i (X̂)1B

X h
i∈I

This is possible by applying [18, Lemma 5.2.2] with the algebra
that is generated by the rectangles (cf. the paragraph above [18,
Lemma 5.5.1]). We apply Proposition 16, substituting aY (Y) →
Y and Y → Z. For arbitrary ε > 0, Proposition 16 provides U
with YaY (Y) −◦− X −◦− U (i. e., Y −◦− X −◦− U) and

n

X

i∈I



≥

E 1i (X̂)1B νi (u)

i∈I

Lemma 17. R ⊆ RIB .

(50) 1

X 
i∈I

Proof. Assume (S, R) ∈ R and choose n ∈ N and f , satisfying
1
log|M| ≤ R and (2). Choose any ε > 0 and find aY such that
n

(78)

The statement for B ∈ σ(X̂) then follows by σ(X̂) ⊆ σ(X), i. e.,
the σ(X)-measurability of X̂. We prove (78) by

We can now finish the proof by showing the following lemma.

I an
Y (Y); f (X) ≥ I Y; f (X) − ε ≥ nS − ε.

i

e .
E[1B νX̂ (u)] = E 1B 1{u} (U)

where we used Prop. (iii) of Lem. 8 in (68). We also have
I(Y; U) ≥

(77)

=

XZ
i∈I

=

Z

Z

1B 1i (X̂)κY|X ( · ; y) dµYXU

e i ) dµ
1 u (U
eUI

Z

1B 1i (X̂)1y (Y) dµYXU

e i )1i (X̂)1y (Y) dµ
1 B 1 u (U
YXUe
U

I

e )1i (X̂)1y (Y) dµ
1 B 1 u (U
YXUe
U

I

e )1y (Y) dµ
,
1 B 1 u (U
YXUe
U
I

(88)
(89)
(90)
(91)
(92)

where we used part 2 of Def. 4 in (89) and Fubini’s theorem [19,
Theorem 14.16] in (90). By replacing κY|X with κY|X̂ and using
e |X̂) =
B ∈ σ(X̂), the same argument can be used to show I(Y; U
0.
References
[1] N. Tishby, F. C. Pereira, and W. Bialek, “The information
bottleneck method,” in Proc. 37th Annual Allerton Conference
on Communication, Control, and Computing, Monticello, IL,
Sep. 1999, pp. 368–377.
[2] N. Slonim and N. Tishby, “Document clustering using word
clusters via the information bottleneck method,” in Proceedings
of the 23rd Annual International ACM SIGIR Conference on
Research and Development in Information Retrieval, ser. SIGIR
’00, ACM. New York, NY, USA: ACM, 2000, pp. 208–215.
[3] S. Gordon, H. Greenspan, and J. Goldberger, “Applying the
information bottleneck principle to unsupervised clustering of
discrete and continuous image representations,” in Computer
Vision, 2003. Proceedings. Ninth IEEE International Conference
on, Oct 2003, pp. 370–377 vol.1.
[4] E. Schneidman, N. Slonim, N. Tishby, R. deRuyter van
Steveninck, and W. Bialek, “Analyzing neural codes using the
information bottleneck method,” Proc. of Advances in Neural
Information Processing System (NIPS-13), 2002.
[5] G. Zeitler, R. Kötter, G. Bauch, and J. Widmer, “On quantizer
design for soft values in the multiple-access relay channel,” in
Proc. IEEE ICC 2009, Jun. 2009.
[6] G. Zeitler, A. Singer, and G. Kramer, “Low-precision A/D
conversion for maximum information rate in channels with memory,” IEEE Trans. Communications, vol. 60, no. 9, pp. 2511–
2521, 9 2012.
[7] A. Winkelbauer and G. Matz, “Joint network-channel coding for
the asymmetric multiple-access relay channel,” in Proc. IEEE
ICC 2012, Jun. 2012, pp. 2485–2489.
[8] A. Winkelbauer, S. Farthofer, and G. Matz, “The rateinformation trade-off for Gaussian vector channels,” in IEEE
Int. Symp. Information Theory, Honolulu, HI, USA, 6 2014.
[9] A. Winkelbauer and G. Matz, “On quantization of log-likelihood
ratios for maximum mutual information,” in Proc. IEEE
SPAWC, 6 2015, pp. 316–320.
[10] G. Pichler, P. Piantanida, and G. Matz, “Distributed
information-theoretic biclustering of two memoryless sources,”
in Proc. 53rd Annual Allerton Conference on Communication,
Control, and Computing, Monticello, IL, Sep. 2015, pp. 426–433.
[11] T. A. Courtade and T. Weissman, “Multiterminal source coding
under logarithmic loss,” IEEE Trans. Inf. Theory, vol. 60, no. 1,
pp. 740–761, Jan. 2014.
[12] G. Chechik, A. Globerson, N. Tishby, and Y. Weiss, “Information bottleneck for gaussian variables,” Journal of Machine
Learning Research, vol. 6, pp. 165–188, Jan. 2005.
[13] N. Slonim and N. Tishby, “Agglomerative information
bottleneck,” in Advances in Neural Information Processing
Systems 12, S. Solla, T. Leen, and K. Müller, Eds. MIT Press,
2000, pp. 617–623.
[14] B. M. Kurkoski, “On the relationship between the kl means
algorithm and the information bottleneck method,” in Proc.
11th International ITG Conference on Systems, Communications and Coding (SCC), Hamburg, Germany, 2 2017, pp. 1–6.
[15] M. B. Westover and J. A. O’Sullivan, “Achievable rates for
pattern recognition,” IEEE Trans. Inf. Theory, vol. 54, no. 1,
pp. 299–320, Jan. 2008.
[16] R. Ahlswede and I. Csiszár, “Hypothesis testing with communication constraints,” IEEE Trans. Inf. Theory, vol. 32, no. 4, pp.
533–542, Jul. 1986.
[17] T. S. Han, “Hypothesis testing with multiterminal data compression,” IEEE Trans. Inf. Theory, vol. 33, no. 6, pp. 759–772,
Nov. 1987.
[18] R. M. Gray, Entropy and Information Theory, 1st ed. SpringerVerlag, 2013.
[19] A. Klenke, Probability Theory, ser. Universitext.
SpringerVerlag GmbH, 2013.

[20] I. Csiszár and J. Körner, Information Theory: Coding Theorems
for Discrete Memoryless Systems. Cambridge University Press,
Aug. 2011.

