A new approach to mutual information
A NEW APPROACH TO MUTUAL INFORMATION
FUMIO HIAI 1 AND DÉNES PETZ 2
Abstract. A new expression as a certain asymptotic limit via “discrete micro-
states” of permutations is provided to the mutual information of both continuous
and discrete random variables.
Introduction
One of the important quantities in information theory is the mutual information of
two random variables X and Y which is expressed in terms of the Boltzmann-Gibbs
entropy H(·) as follows:
I(X ∧ Y ) = −H(X, Y ) +H(X) +H(Y )
when X, Y are continuous variables. For the expression of I(X∧Y ) of discrete variables
X, Y , the aboveH(·) is replaced by the Shannon entropy. A more practical and rigorous
definition via the relative entropy is
I(X ∧ Y ) := S(µ(X,Y ), µX ⊗ µY ),
where µ(X,Y ) denotes the joint distribution measure of (X, Y ) and µX⊗µY the product
of the respective distribution measures of X, Y .
The aim of this paper is to show that the mutual information I(X∧Y ) is gained as a
certain asymptotic limit of the volume of “discrete micro-states” consisting of permu-
tations approximating joint moments of (X, Y ) in some way. In Section 1, more gener-
ally we consider an n-tuple of real bounded random variables (X1, . . . , Xn). Denote by
∆(X1, . . . , Xn;N,m, δ) the set of (x1, . . . ,xn) of xi ∈ R
N whose joint moments (on the
uniform distributed N -point set) of order up tom approximate those of (X1, . . . , Xn) up
to an error δ. Furthermore, denote by ∆sym(X1, . . . , Xn;N,m, δ) the set of (σ1, . . . , σn)
of permutations σi ∈ SN such that (σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;N,m, δ) for
some x1, . . . ,xn ∈ R
≤ , where R
≤ is the R
N -vectors arranged in increasing order. Then,
the asymptotic volume
log γ⊗nSN
∆sym(X1, . . . , Xn;N,m, δ)
under the uniform probability measure γSN on SN is shown to converge as lim supN→∞
(also lim infN→∞) and then limm→∞,δց0 to
−H(X1, . . . , Xn) +
H(Xi)
1 Supported in part by Grant-in-Aid for Scientific Research (B)17340043.
2 Supported in part by the Hungarian Research Grant OTKA T068258.
AMS subject classification: Primary: 62B10, 94A17.
http://arxiv.org/abs/0704.0588v1
2 F. HIAI AND D. PETZ
as long as H(Xi) > −∞ for 1 ≤ i ≤ n. Thus, we obtain a kind of discretization of the
mutual information via symmetric group (or permutations).
The approach can be applied to an n-tuple of discrete random variables (X1, . . . , Xn)
as well. But the definition of the ∆sym-set of micro-states for discrete variables is
somewhat different from the continuous variable case mentioned above, and we discuss
the discrete variable case in Section 2 separately.
The idea comes from the paper [3]. Motivated by theory of mutual free information in
[6], a similar approach to Voiculescu’s free entropy is provided there. The free entropy
is the free probability counterpart of the Boltzmann-Gibbs entropy, and RN -vectors
and the symmetric group SN here are replaced by Hermitian N ×N matrices and the
unitary group U(N), respectively. In this way, the “discretization approach” here is in
some sense a classical analog of the “orbital approach” in [3].
1. The continuous case
For N ∈ N let RN≤ be the convex cone of the N -dimensional Euclidean space R
consisting of x = (x1, . . . , xN ) such that x1 ≤ x2 ≤ · · · ≤ xN . The space R
N is naturally
regarded as the real function algebra on the N -point set. Let SN be the symmetric
group of order N (i.e., the permutations on {1, 2, . . . , n}). Throughout this section let
(X1, . . . , Xn) be an n-tuple of real random variables on a probability space (Ω,P), and
assume that the Xi’s are bounded (i.e., Xi ∈ L
∞(Ω;P)). The Boltzmann-Gibbs entropy
of (X1, . . . , Xn) is defined to be
H(X1, . . . , Xn) := −
· · ·
p(x1, . . . , xn) log p(x1, . . . , xn) dx1 · · · dxn
if the joint density p(x1, . . . , xn) of (X1, . . . , Xn) exists; otherwise H(X1, . . . , Xn) =
−∞. Note that the above integral is well defined in [−∞,∞) since the density p is
compactly supported.
Definition 1.1. The mean value of x = (x1, . . . , xN) in R
N is given by
κN(x) :=
For each N,m ∈ N and δ > 0 we define ∆(X1, . . . , Xn;N,m, δ) to be the set of all
n-tuples (x1, . . . ,xn) of xi = (xi1, . . . , xiN ) ∈ R
N , 1 ≤ i ≤ n, such that
|κN(xi1 · · ·xik)− E(Xi1 · · ·Xik)| < δ
for all 1 ≤ i1, . . . , ik ≤ n with 1 ≤ k ≤ m, where xi1 · · ·xik means the pointwise
product, i.e.,
xi1 · · ·xik := (xi11 · · ·xik1, xi12 · · ·xik2, . . . , xi1N · · ·xikN ) ∈ R
and E(·) denotes the expectation on (Ω,P). For each R > 0, define ∆R(X1, . . . , Xn;
N,m, δ) to be the set of all (x1, . . . ,xn) ∈ ∆(X1, . . . , Xn;N,m, δ) such that xi ∈
[−R,R]N for all 1 ≤ i ≤ n.
Heuristically, ∆(X1, . . . , Xn;N,m, δ) is the set of “micro-states” consisting of n-
tuples of discrete random variables on the N -point set with the uniform probability
A NEW APPROACH TO MUTUAL INFORMATION 3
such that all joint moments of order up to m give the corresponding joint moments of
X1, . . . , Xn up to an error δ.
For x ∈ RN write ‖x‖p := (N
j=1 |xj |
p)1/p for 1 ≤ p < ∞ and ‖x‖∞ :=
max1≤j≤N |xj| while ‖X‖p denotes the L
p-norm of a real random variable X on (Ω,P).
The next lemma is seen from [4, 5.1.1] based on the Sanov large deviation theorem,
which says that the Boltzmann-Gibbs entropy is gained as an asymptotic limit of the
volume of the approximating micro-states.
Lemma 1.2. For every m ∈ N and δ > 0 and for any choice of R ≥ max1≤i≤n ‖Xi‖∞,
the limit
log λ⊗nN
∆R(X1, . . . , Xn;N,m, δ)
exists, where λN is the Lebesgue measure on R
N . Furthermore, one has
H(X1, . . . , Xn) = lim
m→∞,δց0
log λ⊗nN
∆R(X1, . . . , Xn;N,m, δ)
independently of the choice of R ≥ max1≤i≤n ‖Xi‖∞.
In the following let us introduce some kinds of mutual information in the discretiza-
tion approach using micro-states of permutations.
Definition 1.3. The action of SN on R
N is given by
σ(x) := (xσ−1(1), xσ−1(2), . . . , xσ−1(N))
for σ ∈ SN and x = (x1, . . . , xN) ∈ R
N . For each N,m ∈ N, δ > 0 and R > 0 we
denote by ∆sym,R(X1, . . . , Xn;N,m, δ) the set of all (σ1, . . . , σn) ∈ S
N such that
(σ1(x1), . . . , σn(xn)) ∈ ∆R(X1, . . . , Xn;N,m, δ)
for some (x1, . . . ,xn) ∈ (R
n. For each R > 0 define
Isym,R(X1, . . . , Xn) := − lim
m→∞,δց0
lim sup
log γ⊗nSN
∆sym,R(X1, . . . , Xn;N,m, δ)
where γSN is the uniform probability measure on SN . Define also Isym,R(X1, . . . , Xn)
by replacing lim sup by lim inf. Obviously,
0 ≤ Isym,R(X1, . . . , Xn) ≤ Isym,R(X1, . . . , Xn).
Moreover, ∆sym,∞(X1, . . . , Xn;N,m, δ) is defined by replacing ∆R(X1, . . . , Xn;N,m, δ)
in the above by ∆(X1, . . . , Xn;N,m, δ) without cut-off by the parameter R. Then
Isym,∞(X1, . . . , Xn) and Isym,∞(X1, . . . , Xn) are also defined as above.
Definition 1.4. For each 1 ≤ i ≤ n we choose and fix a sequence ξi = {ξi(N)} of
ξi(N) ∈ R
≤ , N ∈ N, such that κN (ξi(N)
k) → E(Xki ) as N → ∞ for all k ∈ N, i.e.,
ξi(N) → Xi in moments. For each N,m ∈ N and δ > 0 we define ∆sym(X1, . . . , Xn :
ξ1(N), . . . , ξn(N);N,m, δ) to be the set of all (σ1, . . . , σn) ∈ S
N such that
(σ1(ξ1(N)), . . . , σn(ξn(N))) ∈ ∆(X1, . . . , Xn;N,m, δ).
4 F. HIAI AND D. PETZ
Define
Isym(X1, . . . , Xn : ξ1, . . . , ξn)
:= − lim
m→∞,δց0
lim sup
log γ⊗nSN
∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ)
and Isym(X1, . . . , Xn : ξ1, . . . ξn) by replacing lim sup by lim inf.
The next proposition asserts that the quantities in Definitions 1.3 and 1.4 are all
equivalent.
Lemma 1.5. For any choice of R ≥ max1≤i≤n ‖Xi‖∞ and for any choices of approxi-
mating sequences ξ1, . . . , ξn one has
Isym,∞(X1, . . . , Xn) = Isym,R(X1, . . . , Xn) = Isym(X1, . . . , Xn : ξ1, . . . , ξn), (1.1)
Isym,∞(X1, . . . , Xn) = Isym,R(X1, . . . , Xn) = Isym(X1, . . . , Xn : ξ1, . . . , ξn). (1.2)
Proof. It is obvious that ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ) is included in
∆sym,∞(X1, . . . , Xn;N,m, δ) for any approximating sequences ξi. Moreover, for each
1 ≤ i ≤ n an approximating sequence ξi can be chosen so that ‖ξi(N)‖∞ ≤ ‖Xi‖∞
for all N ; then ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ) ⊂ ∆sym,R(X1, . . . , Xn;
N,m, δ) for any R ≥ R0 := max1≤i≤n ‖Xi‖∞. Hence it suffices to prove that for any
approximating sequences ξi and for every m ∈ N and δ > 0, there are an m
′ ∈ N, a
δ′ > 0 and an N0 ∈ N so that
∆sym,∞(X1, . . . , Xn;N,m
′, δ′) ⊂ ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ)
for all N ≥ N0. Choose a ρ ∈ (0, 1) with m(R0 + 1)
m−1ρ < δ/2. By [5, Lemma 4.3]
(also [4, 4.3.4]) there exist an m′ ∈ N with m′ ≥ 2m, a δ′ > 0 with δ′ ≤ min{1, δ/2}
and an N0 ∈ N such that for every 1 ≤ i ≤ n and every x ∈ R
≤ with N ≥ N0,
if |κN (x
k) − E(Xki )| < δ
′ for all 1 ≤ k ≤ m′, then ‖x − ξi(N)‖m < ρ. Suppose
N ≥ N0 and (σ1, . . . , σn) ∈ ∆sym,∞(X1, . . . , Xn;N,m
′, δ′); then (σ1(x1), . . . , σn(xn)) ∈
∆(X1, . . . , Xn;N,m
′, δ′) for some (x1, . . . ,xn) ∈ (R
n. Since |κN(x
i ) − E(X
i )| < δ
for all 1 ≤ k ≤ m′, we get ‖xi − ξi(N)‖m ≤ ρ and
‖xi‖m ≤ ‖xi‖2m = κN(x
< (E(X2mi ) + 1)
≤ (R2m0 + 1)
1/2m ≤ R0 + 1.
Therefore,
|κN(σi1(ξi1(N)) · · ·σik(ξik(N)))− E(Xi1 · · ·Xik)|
≤ |κN(σi1(ξi1(N)) · · ·σik(ξik(N)))− κN(σi1(xi1) · · ·σik(xik))|
+ |κN(σi1(xi1) · · ·σik(xik))− E(Xi1 · · ·Xik)|
≤ m(R0 + 1)
m−1ρ+ δ′ < δ
for all 1 ≤ i1, . . . , ik ≤ n with 1 ≤ k ≤ m. The above latter inequality follows from the
Hölder inequality. Hence (σ1, . . . , σn) ∈ ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ),
and the result follows. �
A NEW APPROACH TO MUTUAL INFORMATION 5
Consequently, we denote all the quantities in (1.1) by the same Isym(X1, . . . , Xn) and
those in (1.2) by Isym(X1, . . . , Xn). We call Isym(X1, . . . , Xn) and Isym(X1, . . . , Xn) the
mutual information and upper mutual information of (X1, . . . , Xn), respectively. The
terminology “mutual information” will be justified after the next theorem.
In the continuous variable case, our main result is the following exact relation of Isym
and Isym with the Boltzmann-Gibbs entropy H(·), which says that Isym(X1, . . . , Xn) is
formally the sum of the separate entropiesH(Xi)’s minus the compoundH(X1, . . . , Xn).
Thus, a naive meaning of Isym(X1, . . . , Xn) is the entropy (or information) overlapping
among the Xi’s.
Theorem 1.6.
H(X1, . . . , Xn) = −Isym(X1, . . . , Xn) +
H(Xi)
= −Isym(X1, . . . , Xn) +
H(Xi).
Proof. If the coordinates si of s ∈ R
N are all distinct, then s is uniquely written as
s = σ(x) with x ∈ RN≤ and σ ∈ SN . Note that the set of s ∈ R
N with si = sj for some
i 6= j is a closed subset of λN -measure zero. Under the correspondence
s ∈ RN ←→ (x, σ) ∈ RN≤ × SN , s = σ(x)
(well defined on a co-negligible subset of RN), the measure λN is transformed into the
product of λN |RN
and the counting measure on SN .
In the following proof we adopt, due to Lemma 1.5, the description of Isym and
Isym as Isym,R(X1, . . . , Xn) and Isym,R(X1, . . . , Xn) with R := max1≤i≤n ‖Xi‖∞. For
each N,m ∈ N and δ > 0, suppose (s1, . . . , sn) ∈ ∆R(X1, . . . , Xn;N,m, δ) and write
si = σi(xi) with xi ∈ R
≤ and σi ∈ SN . Then it is obvious that
(x1, . . . ,xn; σ1, . . . , σn)
∆R(Xi;N,m, δ) ∩ R
×∆sym,R(X1, . . . , Xn;N,m, δ).
By Lemma 1.2 and the fact stated at the beginning of the proof, we obtain
H(X1, . . . , Xn) ≤ lim
log λ⊗nN
∆R(X1, . . . , Xn;N,m, δ)
≤ lim inf
log λN
∆R(Xi;N,m, δ) ∩ R
+ log#∆sym,R(X1, . . . , Xn;N,m, δ)
= lim inf
log λN
∆R(Xi;N,m, δ)
− n logN !
6 F. HIAI AND D. PETZ
+ log#∆sym,R(X1, . . . , Xn;N,m, δ)
log λN
∆R(Xi;N,m, δ)
+ lim inf
log γ⊗nSN
∆sym,R(X1, . . . , Xn;N,m, δ)
This implies that
H(X1, . . . , Xn) ≤
H(Xi)− Isym(X1, . . . , Xn). (1.3)
Conversely, for each m ∈ N and δ > 0, by [5, Lemma 4.3] (also [4, 4.3.4]) there are
an m′ ∈ N with m′ ≥ m, a δ′ > 0 with δ′ ≤ δ/2 and an N0 ∈ N such that for every
N ∈ N and for every x,y ∈ RN≤ , if ‖x‖∞ ≤ R and |κN(x
k) − κN(y
k)| < 2δ′ for all
1 ≤ k ≤ m′, then ‖x− y‖1 < δ/2m(R + 1)
m−1. Suppose N ≥ N0 and
(x1, . . . ,xn; σ1, . . . , σn)
∆R(Xi;N,m
′, δ′) ∩ RN≤
×∆sym,R(X1, . . . , Xn;N,m
′, δ′)
so that (σ1(y1), . . . , σn(yn)) ∈ ∆R(X1, . . . , Xn;N,m
′, δ′) for some (y1, . . . ,yn) ∈ (R
Since
|κN(x
i )− κN(y
i )| ≤ |κN(x
i )− E(X
i )|+ |κN(y
i )− E(X
i )| < 2δ
for all 1 ≤ k ≤ m′, we get ‖xi − yi‖1 < δ/2m(R + 1)
m−1 for 1 ≤ i ≤ n. Therefore,
|κN (σi1(xi1) · · ·σik(xik))− E(Xi1 · · ·Xik)|
≤ |κN(σi1(xi1) · · ·σik(xik))− κN(σi1(yi1) · · ·σik(yik))|
+ |κN(σi1(yi1) · · ·σik(yik))− E(Xi1 · · ·Xik)|
≤ m(R + 1)m−1 max
1≤i≤n
‖xi − yi‖1 + δ
+ δ′ ≤ δ
for all 1 ≤ i1, . . . , ik ≤ n with 1 ≤ k ≤ m. This implies that (σ1(x1), . . . , σn(xn)) ∈
∆R(X1, . . . , Xn;N,m, δ). By Lemma 1.2 we obtain
H(Xi)− Isym(X1, . . . , Xn)
log λN
∆R(Xi;N,m
′, δ′)
+ lim sup
log γ⊗nSN
∆sym,R(X1, . . . , Xn;N,m
′, δ′)
= lim sup
log λN
∆R(Xi;N,m
′, δ′) ∩ RN≤
A NEW APPROACH TO MUTUAL INFORMATION 7
+ log#∆sym,R(X1, . . . , Xn;N,m
′, δ′)
≤ lim sup
log λ⊗nN
∆R(X1, . . . , Xn;N,m, δ)
This implies by Lemma 1.2 once again that
H(Xi)− Isym(X1, . . . , Xn) ≤ H(X1, . . . , Xn). (1.4)
The result follows from (1.3) and (1.4). �
Let µ(X1,...,Xn) be the joint distribution measure on R
n of (X1, . . . , Xn) while µXi is
that of Xi for 1 ≤ i ≤ n. Let S(µ(X1,...,Xn), µX1 ⊗· · ·⊗µXn) denote the relative entropy
(or the Kullback-Leibler divergence) of µ(X1,...,Xn) with respect to the product measure
µX1 ⊗ · · · ⊗ µXn , i.e.,
S(µ(X1,...,Xn), µX1 ⊗ · · · ⊗ µXn) :=
dµ(X1,...,Xn)
d(µX1 ⊗ · · · ⊗ µXn)
dµ(X1,...,Xn)
if µ(X1,...,Xn) is absolutely continuous with respect to µX1 ⊗ · · · ⊗ µXn ; otherwise
S(µ(X1,...,Xn), µX1 ⊗ · · · ⊗ µXn) := +∞. When H(Xi) > −∞ for all 1 ≤ i ≤ n,
one can easily verify that
S(µ(X1,...,Xn), µX1 ⊗ · · · ⊗ µXn) = −H(X1, . . . , Xn) +
H(Xi).
Thus, the above theorem yields the following:
Corollary 1.7. If H(Xi) > −∞ for all 1 ≤ i ≤ n, then
Isym(X1, . . . , Xn) = Isym(X1, . . . , Xn)
= S(µ(X1,...,Xn), µX1 ⊗ · · · ⊗ µXn).
Corollary 1.8. Under the same assumption as the above corollary, Isym(X1, . . . , Xn) =
0 if and only if X1, . . . , Xn are independent.
In particular, the originalmutual information I(X1∧X2) of two real random variables
X1, X2 is normally defined as
I(X1 ∧X2) := S(µ(X1,X2), µX1 ⊗ µX2).
Hence we have
I(X1 ∧X2) = Isym(X1, X2) = Isym(X1, X2)
as long as H(X1) > −∞ and H(X2) > −∞ (and X1, X2 are bounded). For this reason,
we gave the term “mutual information” to Isym.
Finally, some open problems are in order:
(1) Without the assumption H(Xi) > −∞ for 1 ≤ i ≤ n, does Isym(X1, . . . , Xn) =
Isym(X1, . . . , Xn) hold true?
8 F. HIAI AND D. PETZ
(2) More strongly, does the limit such as
log γ⊗nSN (∆sym,R(X1, . . . , Xn;N,m, δ))
log γ⊗nSN (∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N,m, δ))
exist as in Lemma 1.2?
(3) Without the assumption H(Xi) > −∞ for 1 ≤ i ≤ n, does Isym(X1, . . . , Xn) =
S(µ(X1,...,Xn), µX1⊗· · ·⊗µXn) hold true? Also, is Isym(X1, . . . , Xn) = 0 equivalent
to the independence of X1, . . . , Xn?
(4) Although the boundedness assumption for X1, . . . , Xn is rather essential in
the above discussions, it is desirable to extend the results in this section to
X1, . . . , Xn not necessarily bounded but having all moments.
2. The discrete case
Let Y be a finite set with a probability measure p. The Shannon entropy of p is
S(p) := −
p(y) log p(y).
For each sequence y = (y1, . . . , yN) ∈ Y
N , the type of y is a probability measure on Y
given by
νy(t) :=
Ny(t)
where Ny(t) := #{j : yj = t}, t ∈ Y .
The number of possible types is smaller than (N + 1)#Y . If ν is a type and TN(ν)
denotes the set of all sequences of type ν from YN , then the cardinality of TN(ν) is
estimated as follows:
(N + 1)#Y
eNS(ν) ≤ #TN (ν) ≤ e
NS(ν) (2.1)
(see [1, 12.1.3] and [2, Lemma 2.2]).
Let p be a probability meausre on Y . For each N ∈ N and δ > 0 we define ∆(p;N, δ)
to be the set of all sequences y ∈ YN such that |νy(t)−p(t)| < δ for all t ∈ Y . In other
words, ∆(p;N, δ) is the set of all δ-typical sequeces (with respect to the measure p).
Then the next lemma is well known.
Lemma 2.1.
S(p) = lim
log#∆(p;N, δ).
In fact, this easily follows from (2.1). Let PN,δ be the maximizer of the Shannon
entropy on the set of all types νy, y ∈ Y
N , such that |νy(t) − p(t)| < δ for all t ∈ Y .
We can use the Shannon entropy of the type class corresponding to PN,δ to estimate
the cardinality of ∆(p;N, δ):
(N + 1)−#YeNS(PN,δ) ≤ #∆(p;N, δ) ≤ eNS(PN,δ)(N + 1)#Y .
A NEW APPROACH TO MUTUAL INFORMATION 9
It follows that
log#∆(p;N, δ) = sup{S(q) : q is a probability meausre on Y
such that |q(t)− p(t)| < δ, t ∈ Y},
and the lemma follows.
We consider the case where p is the joint distribution of an n-tuple (X1, . . . , Xn)
of discrete random variables on (Ω,P). Throughout this section we assume that the
random variables X1, . . . , Xn have their values in a finite set X = {t1, . . . , td}.
Definition 2.2. Let p(X1,...,Xn) denote the joint distribution of (X1, . . . , Xn), which is
a measure on X n while the distribution pXi of Xi is a measure on X , 1 ≤ i ≤ n. We
write ∆(Xi;N, δ) for ∆(pXi;N, δ) and ∆(X1, . . . , Xn;N, δ) for ∆(p(X1,...,Xn);N, δ).
Next, we introduce the counterparts of Definitions 1.3 and 1.4 in the discrete variable
case.
Definition 2.3. The action of SN on X
N is similar to that on RN given in Defintion
1.3. For N ∈ N let XN≤ denote the set of all sequences of length N of the form
x = (t1, . . . , t1, t2, . . . , t2, . . . , td, . . . , td).
Oviously, such a sequence x is uniquely determined by (Nx(t1), . . . , Nx(td)) or the type
of x. That is, XN≤ is regarded as the set of all types from X
N . For each N ∈ N and
δ > 0 we denote by ∆sym(X1, . . . , Xn;N, δ) the set of all (σ1, . . . , σn) ∈ S
N such that
(σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;N, δ)
for some (x1, . . . ,xn) ∈ (X
n. Define
Isym(X1, . . . , Xn) := − lim
lim sup
log γ⊗nSN (∆sym(X1, . . . , Xn;N, δ)),
and Isym(X1, . . . , Xn) by replacing lim sup by lim inf. Moreover, for each 1 ≤ i ≤ n,
choose a sequence ξi = {ξi(N)} of ξi(N) = (ξi(N)1, . . . , ξi(N)N) ∈ X
≤ such that
νξi(N) → pXi as N → ∞. We then define ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N, δ),
Isym(X1, . . . , Xn : ξ1, . . . , ξn) and Isym(X1, . . . , Xn : ξ1, . . . , ξn) as in Definition 1.4.
Lemma 2.4. For any choices of approximating sequences ξ1, . . . , ξn one has
Isym(X1, . . . , Xn) = Isym(X1, . . . , Xn : ξ1, . . . , ξn),
Isym(X1, . . . , Xn) = Isym(X1, . . . , Xn : ξ1, . . . , ξn).
Proof. It suffices to show that for each δ > 0 there are a δ′ > 0 and an N0 ∈ N such
∆sym(X1, . . . , Xn;N, δ
′) ⊂ ∆sym(X1, . . . , Xn : ξ1(N), . . . , ξn(N);N, δ) (2.2)
for all N ≥ N0. Choose δ
′ > 0 so that 3ndn+1δ′ ≤ δ, where d = #X . Suppose
(σ1, . . . , σn) is in the left-hand side of (2.2) so that (σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;
N, δ′) for some (x1, . . . ,xn), xi = (xi1, . . . , xiN) ∈ X
≤ . Since
|ν(σ1(x1),...,σn(xn))(z1, . . . , zn)− p(X1,...,Xn)(z1, . . . , zn)| < δ
′, (z1, . . . , zn) ∈ X
n, (2.3)
10 F. HIAI AND D. PETZ
νxi(t) =
z1,...,zi−1,zi+1,...,zn∈X
ν(σ1(x1),...,σn(xn))(z1, . . . , zi−1, t, zi+1, . . . , zn), t ∈ X ,
pXi(t) =
z1,...,zi−1,zi+1,...,zn∈X
p(X1,...,Xn)(z1, . . . , zi−1, t, zi+1, . . . , zn), t ∈ X ,
it follows that
|νxi(t)− pXi(t)| < d
n−1δ′ (2.4)
for any 1 ≤ i ≤ n and t ∈ X . Now, choose an N0 ∈ N so that |νξi(N)(t)− pXi(t)| < δ
and hence
|νξi(N)(t)− νxi(t)| < 2d
n−1δ′ (2.5)
for any 1 ≤ i ≤ n and t ∈ X and for all N ≥ N0. Since
|(Nξi(N)(t1) + · · ·+Nξi(N)(tl))− (Nxi(t1) + · · ·+Nxi(tl))|
≤ |Nξi(N)(t1)−Nxi(t1)|+ · · ·+ |Nξi(N)(tl)−Nxi(tl)|
< 2Ndnδ′
for every 1 ≤ l ≤ d thanks to (2.5), it is easily seen that
j ∈ {1, . . . , N} : ξi(N)j 6= xij
< 2Ndn+1δ′
for any 1 ≤ i ≤ n. Hence we get
|ν(σ1(ξ1(N)),...,σn(ξn(N)))(z1, . . . , zn)− ν(σ1(x1),...,σn(xn))(z1, . . . , zn)|
∣#{j : ξ1(N)σ−1
(j) = z1, . . . , ξn(N)σ−1n (j) = zn}
−#{j : x1σ−1
(j) = z1, . . . , xnσ−1n (j) = zn}
#{j : ξi(N)j 6= xij} < 2nd
n+1δ′
so that thanks to (2.3)
|ν(σ1(ξ1(N)),...,σn(ξn(N)))(z1, . . . , zn)− p(X1,...,Xn)(z1, . . . , zn)| < 3nd
n+1δ′ ≤ δ
for every (z1, . . . , zn) ∈ X
n. Therefore, (σ1, . . . , σn) is in the right-hand side of (2.2),
as required. �
The next theorem is the discrete variable version of Theorem 1.6.
Theorem 2.5.
Isym(X1, . . . , Xn) = Isym(X1, . . . , Xn) = −S(X1, . . . , Xn) +
S(Xi).
Proof. For each sequence (N1, . . . , Nd) of integers Nl ≥ 0 with
l=1Nl = N , let
S(N1, . . . , Nd) denote the subgroup of SN consisting of products of permutations of
{1, . . . , N1}, {N1 + 1, . . . , N1 +N2}, . . . , {N1 + · · ·+Nd−1 + 1, . . . , N}, and let
SN/S(N1, . . . , Nd)
be the set of left cosets of S(N1, . . . , Nd). For each x ∈ X
≤ and σ ∈ SN we write
[σ]x for the left coset of S(Nx(t1), . . . , Nx(td)) containing σ. Then it is clear that
A NEW APPROACH TO MUTUAL INFORMATION 11
every s ∈ XN is represented as s = σ(x) with a unique pair (x, [σ]x) of x ∈ X
≤ and
[σ]x ∈ SN/S(Nx(t1), . . . , Nx(td)).
For any ε > 0 one can choose a δ > 0 such that for every 1 ≤ i ≤ n and every
probability measure p on X , if |p(t)−pXi(t)| < δ for all t ∈ X , then |S(p)−S(pXi)| < ε.
This implies that for each N ∈ N and 1 ≤ i ≤ n, one has |S(νx) − S(pXi)| < ε
whenever x ∈ ∆(Xi;N, δ). Notice that ∆sym(X1, . . . , Xn;N, δ/d
n−1) is the union of
[σ1]x1 × · · · × [σn]xn for all (x1, . . . ,xn; [σ1]x1 , . . . , [σn]xn) of xi ∈ X
≤ and [σi]xi ∈
SN/S(Nxi(t1), . . . , Nxi(td)) such that (σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;N, δ/d
n−1).
Now, suppose (x1, . . . ,xn) ∈ (X
n, (σ1, . . . , σn) ∈ S
N and (σ1(x1), . . . , σn(xn)) ∈
∆(X1, . . . , Xn;N, δ/d
n−1). Then, for each 1 ≤ i ≤ n we get xi ∈ ∆(Xi;N, δ), i.e.,
|νxi(t)− pXi(t)| < δ for all t ∈ X as (2.4). Hence we have
[σ1]x1 × · · · × [σn]xn
x∈∆(Xi;N,δ)
Nx(t)!
(2.6)
so that
#∆sym(X1, . . . , Xn;N, δ/d
≤ #∆(X1, . . . , Xn;N, δ/d
n−1) ·
x∈∆(Xi;N,δ)
Nx(t)!
Therefore,
log γ⊗nSN
∆sym(X1, . . . , Xn;N, δ/d
log#∆(X1, . . . , Xn;N, δ/d
x∈∆(Xi;N,δ)
logNx(t)!
logN !. (2.7)
For each 1 ≤ i ≤ n and for any x ∈ ∆(Xi;N, , δ), the Stirling formula yields
logNx(t)!−
logN !
Nx(t)
logNx(t)−
Nx(t)
− logN + 1 + o(1)
= −S(νx) + o(1) ≤ −S(pXi) + ε+ o(1) as N →∞ (2.8)
thanks to the above choice of δ > 0. Here, note that the o(1) in the above estimate
is uniform for x ∈ ∆(Xi;N, δ). Hence, by (2.7), (2.8) and by Lemma 2.1 applied to
p(X1,...,Xn) on X
n, we obtain
−Isym(X1, . . . , Xn) ≤ S(p(X1,...,Xn))−
S(pXi) + nε
and hence
Isym(X1, . . . , Xn) ≥ −S(X1, . . . , Xn) +
S(Xi). (2.9)
12 F. HIAI AND D. PETZ
Next, we prove the converse direction. For any ε > 0 choose a δ > 0 as above. For
N ∈ N let Ξ(N, δ/dn−1) be the set of all (x1, . . . ,xn) ∈ (X
n such that
(σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;N, δ/d
for some (σ1, . . . , σn) ∈ S
N . Furthermore, for each (x1, . . . ,xn) ∈ Ξ(N, δ/d
n−1), let
Σ(x1, . . . ,xn;N, δ/d
n−1) be the set of all
([σ1]x1 , . . . , [σn]xn) ∈
SN/S(Nxi(t1), . . . , Nxi(td))
such that (σ1(x1), . . . , σn(xn)) ∈ ∆(X1, . . . , Xn;N, δ/d
n−1). Then it is obvious that
#∆(X1, . . . , Xn;N, δ/d
n−1) ≤
(x1,...,xn)∈Ξ(N,δ/dn−1)
#Σ(x1, . . . ,xn;N, δ/d
n−1). (2.10)
When (x1, . . . ,xn) ∈ Ξ(N, δ/d
n−1), we get xi ∈ ∆(Xi;N, δ) as (2.4) for 1 ≤ i ≤ n.
Hence it is seen that
#Ξ(N, δ/dn−1) ≤
#∆(Xi;N, δ)
(N1, . . . , Nd) : Nl ≥ 0 is an integer in
N(pXi(tl)− δ), N(pXi(tl) + δ)
for 1 ≤ l ≤ d
< (2Nδ + 1)nd. (2.11)
For any fixed (x1, . . . ,xn) ∈ Ξ(N, δ/d
n−1), suppose ([σ1]x1 , . . . , [σn]xn) ∈ Σ(x1, . . . ,xn;
N, δ/dn−1); then we get
[σ1]x1 × · · · × [σn]xn
x∈∆(Xi;N,δ)
Nx(t)!
similarly to (2.6). Therefore,
#∆sym(X1, . . . , Xn;N, δ/d
([σ1]x1 ,...,[σn]xn )∈Σ(x1,...,xn;N,δ/d
[σ1]x1 × · · · × [σn]xn
≥ #Σ(x1, . . . ,xn;N, δ/d
n−1) ·
x∈∆(Xi;N,δ)
Nx(t)!
. (2.12)
By (2.10)–(2.12) we obtain
#∆(X1, . . . , Xn;N, δ/d
n−1) ≤
#∆sym(X1, . . . , Xn;N, δ/d
n−1) · (2Nδ + 1)nd
minx∈∆(Xi;N,δ)
t∈X Nx(t)!
A NEW APPROACH TO MUTUAL INFORMATION 13
so that
log#∆(X1, . . . , Xn;N, δ/d
log γ⊗nSN
∆sym(X1, . . . , Xn;N, δ/d
x∈∆(Xi;N,δ)
logNx(t)!
logN ! +
log(2Nδ + 1).
Since it follows similarly to (2.8) that
logNx(t)! +
logN ! ≤ S(pXi) + ε+ o(1) as N →∞
with uniform o(1) for all x ∈ ∆(Xi;N, δ), we obtain
S(p(X1,...,Xn)) ≤ −Isym(X1, . . . , Xn) +
S(pXi) + nε
by Lemma 2.1 again, and hence
Isym(X1, . . . , Xn) ≤ −S(X1, . . . , Xn) +
S(Xi). (2.13)
The conclusion follows from (2.9) and (2.13). �
In particular, the mutual information I(X1 ∧ X2) of X1 and X2 is equivalently ex-
pressed as
I(X1 ∧X2) = S(p(X1,X2), pX1 ⊗ pX2) = −S(p(X1,X2)) + S(pX1) + S(pX2)
= Isym(X1, X2) = Isym(X1, X2).
Similarly to the problem (2) mentioned in the last of Section 1, it is unknown whether
the limit
log γ⊗nSN
∆sym(X1, . . . , Xn;N, δ)
exists or not.
References
[1] T. M. Cover and J. A. Thomas, Elements of Information Theory, Second edition, Wiley-
Interscience, Hoboken, NJ, 2006.
[2] I. Csiszár and P. C. Shields, Information Theory and Statistics: A Tutorial, in “Foundations
and Trends in Communications and Information Theory,” Vol. 1, No. 4 (2004), 417-528, Now
Publishers.
[3] F. Hiai, T. Miyamoto and Y. Ueda, Orbital approach to microstate free entropy, preprint, 2007,
math.OA/0702745.
[4] F. Hiai and D. Petz, The Semicircle Law, Free Random Variables and Entropy, Mathematical
Surveys and Monographs, Vol. 77, Amer. Math. Soc., Providence, 2000.
[5] D. Voiculescu, The analogues of entropy and of Fisher’s information measure in free probability
theory, II, Invent. Math. 118 (1994), 411–440.
[6] D. Voiculescu, The analogue of entropy and of Fisher’s information measure in free probability
theory VI: Liberation and mutual free information, Adv. Math. 146 (1999), 101–166.
http://arxiv.org/abs/math/0702745
14 F. HIAI AND D. PETZ
Graduate School of Information Sciences, Tohoku University, Aoba-ku, Sendai 980-
8579, Japan
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, H-1053
Budapest, Reáltanoda u. 13-15, Hungary
	Introduction
	1. The continuous case
	2. The discrete case
	References
