Mutual Information Bounds for Lossy Common Information

Anderson de Andrade 1 · 2025

Read Mutual Information Bounds for Lossy Common Information by Anderson de Andrade 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04209.txt.

Introduction

Anderson de Andrade proves, in a 2025 paper, a bound separating two rival notions of shared information when some loss is allowed. The setting is the Gray-Wyner network, a classic model for sending common and private messages together. Wyner's lossy common information and the Gács-Körner version disagree on what counts as truly shared. De Andrade shows the mutual information between the targets sits between them as a dividing bound, extending a lossless-case result from the nineteen seventies.

Catalog record

CREATORAnderson de Andrade 1
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE11 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04209

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mutual Information Bounds for Lossy Common Information
Anderson de Andrade 1

Abstract
. We show the mutual information between the targets in a Gray-Wyner Network as a bound that separates Wyner’s lossy common information and Gács-Körner lossy common information. The results are a generalization of the lossless case presented by [ 6 ] . Keywords. common information, information theory



1.
Preliminaries

Let
X_{1}
and
X_{2}
be two random sources. In the Gray-Wyner Network
[
3
]
, an analysis transform
(Y_{0},Y_{1},Y_{2})=f(X_{1},X_{2})
produces common and private representations with corresponding rates
(R_{0},R_{1},R_{2})
. A synthesis transform
\hat{Z}_{1}=g_{1}(Y_{0},Y_{1})
and
\hat{Z}_{2}=g_{2}(Y_{0},Y_{2})
predicts the targets
Z_{1}
and
Z_{2}
of two dependent tasks, producing distortions
D_{1}=d_{1}(\hat{Z}_{1},Z_{1})
and
D_{2}=d_{2}(\hat{Z}_{2},Z_{2})
, respectively. The joint rate-distortion function
[
1
]
is given as
R_{X_{1},X_{2}}(D_{1},D_{2})
.

In this setting, we define Wyner’s lossy common information
[
5
,
6
]
as:

(1.1)

\displaystyle C(X_{1},X_{2};D_{1},D_{2})=\inf I(X_{1},X_{2};U),

where the infimum is over all joint densities
P(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2},U)
under the following Markov conditions:

(1.2)

\displaystyle\hat{Z}_{1}\leftrightarrow U\leftrightarrow\hat{Z}_{2},

(1.3)

\displaystyle(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow U,

and where
P(\hat{Z}_{1},\hat{Z}_{2}|X_{1},X_{2})\in\mathcal{P}^{X_{1},X_{2}}_{D_{1},D_{2}}
is any joint distribution that achieves the rate distortion function at
(D_{1},D_{2})
, i.e.,
I(X_{1},X_{2};\hat{Z}_{1},\hat{Z}_{2})=R_{X_{1},X_{2}}(D_{1},D_{2})
.

Gács-Körner lossy common information
[
5
,
2
]
is defined for this setting as:

(1.4)

\displaystyle K(X_{1},X_{2};D_{1},D_{2})=\sup I(X_{1},X_{2};V),

where the supremum is over all joint densities
(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2},V)
, such that the following Markov conditions are met:

(1.5)

\displaystyle X_{2}\leftrightarrow X_{1}\leftrightarrow V,

(1.6)

\displaystyle X_{1}\leftrightarrow X_{2}\leftrightarrow V,

(1.7)

\displaystyle X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow V,

(1.8)

\displaystyle X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow V,

where
P(\hat{Z}_{1}|X_{1})\in\mathcal{P}^{X_{1}}_{D_{1}}
and
P(\hat{Z}_{2}|X_{2})\in\mathcal{P}^{X_{2}}_{D_{2}}
are optimal rate-distortion encoders at
D_{1}
and
D_{2}
, respectively.

Recall that the interaction information
[
4
,
7
]
between random variables
X
,
Y
, and
Z
is given as:

(1.9)

\displaystyle I(X;Y;Z)=I(X;Y)-I(X;Y|Z),

and that the chain rule of mutual information
[
1
]
is defined as:

(1.10)

\displaystyle I(X;Z)=I(X;Y,Z)-I(X;Y|Z).

We derive the following corollary:

(1.11)

\displaystyle I(X;Y;Z)=I(X,Y;Z)-I(X;Z|Y)-I(Y;Z|X).

An outline of the proof is presented as follows:

(1.12)

\displaystyle I(X;Y;Z)

\displaystyle=\nicefrac{{1}}{{2}}\left[I(X;Z)-I(X;Z|Y)+I(Y;Z)-I(Y;Z|X)\right]

\displaystyle(\text{eq.~\ref{eq:ii} twice})

(1.13)

\displaystyle=I(X,Y;Z)-I(X;Z|Y)-I(Y;Z|X).

\displaystyle(\text{eq.~\ref{eq:chain-rule} twice})

2.
Main Result

Theorem 1
.

For the Markov chain
(X_{1},X_{2})\to(\hat{Z}_{1},\hat{Z}_{2})
, yielding distortions
D_{1}
and
D_{2}
, we have:

(2.1)

\displaystyle K(X_{1},X_{2};D_{1},D_{2})\leq I(\hat{Z}_{1};\hat{Z}_{2})\leq C(X_{1},X_{2};D_{1},D_{2}),

with equality on both sides if and only if we can represent
X_{1}
and
X_{2}
as
X_{1}=(X^{\prime}_{1},W)
and
X_{2}=(X^{\prime}_{2},W)
, such that these Markov conditions hold:

(2.2)

\displaystyle\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2},

(2.3)

\displaystyle(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W.

Proof.

Declaring the Markov chain condition in the theorem statement:

(2.4)

\displaystyle(X_{1},X_{2})\to(\hat{Z}_{1},\hat{Z}_{2}),

we show for the RHS that:

(2.5)

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})

\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};U)+I(\hat{Z}_{1};\hat{Z}_{2}|U)

\displaystyle(\text{\text{eq.~\ref{eq:ii}}})

(2.6)

\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};U)

\displaystyle(\text{cond.~\ref{wci:cond-1}})

(2.7)

\displaystyle=I(\hat{Z}_{1},\hat{Z}_{2};U)-I(\hat{Z}_{1};U|\hat{Z}_{2})-I(\hat{Z}_{2};U|\hat{Z}_{1})

\displaystyle(\text{eq.~\ref{eq:ii-break-down}})

(2.8)

\displaystyle\leq I(\hat{Z}_{1},\hat{Z}_{2};U)

\displaystyle\left(I(X;Y|Z)\geq 0\right)

(2.9)

\displaystyle=I(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2};U)-I(X_{1},X_{2};U|\hat{Z}_{1},\hat{Z}_{2})

\displaystyle(\text{eq.~\ref{eq:chain-rule}})

(2.10)

\displaystyle=I(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2};U)

\displaystyle(\text{cond.~\ref{wci:cond-2}})

(2.11)

\displaystyle=I(X_{1},X_{2};U)+I(\hat{Z}_{1},\hat{Z}_{2};U|X_{1},X_{2})

\displaystyle(\text{eq.~\ref{eq:chain-rule}})

(2.12)

\displaystyle=I(X_{1},X_{2};U).

\displaystyle(\text{cond.~\ref{eq:cond-base}})

Thus:

(2.13)

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})\leq I(X_{1},X_{2};U)

\displaystyle\implies\inf I(\hat{Z}_{1};\hat{Z}_{2})\leq\inf I(X_{1},X_{2};U)

(2.14)

\displaystyle\implies I(\hat{Z}_{1};\hat{Z}_{2})\leq C(X_{1},X_{2};D_{1},D_{2}),

\displaystyle(\text{eq.~\ref{eq:wci}})

where the infimum is over the same conditions as in
1.1
.

To prove the LHS, we have:

(2.15)

\displaystyle I(X_{1},X_{2};V)

\displaystyle=I(X_{1};V)+I(X_{2};V|X_{1})

\displaystyle(\text{eq.~\ref{eq:chain-rule}})

(2.16)

\displaystyle=I(X_{1};V)

\displaystyle(\text{cond.~\ref{eq:gkci-markov-1}})

(2.17)

\displaystyle=I(X_{1};X_{2};V)+I(X_{1};V|X_{2})

\displaystyle(\text{\text{eq.~\ref{eq:ii}}})

(2.18)

\displaystyle=I(X_{1};X_{2};V)

\displaystyle(\text{cond.~\ref{eq:gkci-markov-2}})

(2.19)

\displaystyle=I(X_{1},\hat{Z}_{1};X_{2},\hat{Z}_{2};V)

\displaystyle(\text{conds.~\ref{eq:cond-base},~\ref{eq:gkci-markov-1},~\ref{eq:gkci-markov-2}})

(2.20)

\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};V)

\displaystyle(\text{conds.~\ref{eq:gkci-markov-3},~\ref{eq:gkci-markov-4}})

(2.21)

\displaystyle\leq I(\hat{Z}_{1};\hat{Z}_{2}).

Equation
2.19
was derived by noting that for any random variables
X
,
Y
, and
Z
, we have
I(X,Y;Z)\geq I(X;Z)
. However, in our case, since
\hat{Z}_{1}
and
\hat{Z}_{2}
are derived by
X_{1}
and
X_{2}
, and because
X_{1}
and
X_{2}
have the same information about
V
, we have equality. Formally:

(2.22)

\displaystyle\left[(X_{1},X_{2})\to\hat{Z}_{1}\right]\land\left[X_{2}\leftrightarrow X_{1}\leftrightarrow V\right]

\displaystyle\implies I(X_{1};X_{2};V)=I(X_{1},\hat{Z}_{1};X_{2};V),

(2.23)

\displaystyle\left[(X_{1},X_{2})\to\hat{Z}_{2}\right]\land\left[X_{1}\leftrightarrow X_{2}\leftrightarrow V\right]

\displaystyle\implies I(X_{1};X_{2};V)=I(X_{1};X_{2},\hat{Z}_{2};V).

Due to conditions
1.7
and
1.8
,
X_{1}
and
X_{2}
can be respectively dropped.
Finally, we have:

(2.24)

\displaystyle I(X_{1},X_{2};V)\leq I(\hat{Z}_{1};\hat{Z}_{2})

\displaystyle\implies\sup I(X_{1},X_{2};V)\leq\sup I(\hat{Z}_{1};\hat{Z}_{2})

(2.25)

\displaystyle\implies K(X_{1},X_{2};D_{1},D_{2})\leq I(\hat{Z}_{1};\hat{Z}_{2}),

\displaystyle(\text{eq.~\ref{eq:gkci}})

where the supremum is over the same conditions as in
1.4
.

To obtain equality on the RHS, condition
2.31
together with condition
2.2
establishes that:

(2.26)

\displaystyle I(\hat{Z}_{1};W|\hat{Z}_{2})=I(\hat{Z}_{2};W|\hat{Z}_{1})=0.

Plugging this result (equation
2.26
) in equation
2.7
and continuing the same analysis yields:

(2.27)

\displaystyle I(\hat{Z}_{1},\hat{Z}_{2};W)-I(\hat{Z}_{1};W|\hat{Z}_{2})-I(\hat{Z}_{2};W|\hat{Z}_{1})=I(X_{1},X_{2};W)

(2.28)

\displaystyle\implies

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=I(X_{1},X_{2};W)

(2.29)

\displaystyle\implies

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=\inf I(X_{1},X_{2};U)

(2.30)

\displaystyle\implies

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=C(X_{1},X_{2};D_{1},D_{2}),

where the infimum is over the same conditions as in
1.1
. Note that
W
is achieved by the infimum.

To obtain equality on the LHS, first note that the representation requirements
X_{1}=(X^{\prime}_{1},W)
and
X_{2}=(X^{\prime}_{2},W)
establish the following Markov condition:

(2.31)

\displaystyle X_{1}\rightarrow W\leftarrow X_{2},

implying that
W
can only carry information that is mutual between
X_{1}
and
X_{2}
such that:

(2.32)

\displaystyle I(X_{1};X_{2})-I(X_{1};X_{2}|W)=H(W).

Also note that due to conditions
2.2
and
2.31
, the sufficient condition
2.3
implies conditions
1.7
and
1.8
:

(2.33)

\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]

(2.34)

\displaystyle\implies

\displaystyle\left\{(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\iff\left[X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow W\right]\land\left[X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow W\right]\right\}.

This is because the information that is common between
\hat{Z}_{1}
and
\hat{Z}_{2}
must also be common between
X_{1}
and
X_{2}
:

(2.35)

\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]\land

\displaystyle\implies\left[\hat{Z}_{1}\leftrightarrow X_{1}\leftrightarrow\hat{Z}_{2}\right],

(2.36)

\displaystyle\left[(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\right]\land\left[\hat{Z}_{1}\leftrightarrow X_{1}\leftrightarrow\hat{Z}_{2}\right]

\displaystyle\implies\left[X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow W\right],

(2.37)

\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]\land

\displaystyle\implies\left[\hat{Z}_{1}\leftrightarrow X_{2}\leftrightarrow\hat{Z}_{2}\right],

(2.38)

\displaystyle\left[(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\right]\land\left[\hat{Z}_{1}\leftrightarrow X_{2}\leftrightarrow\hat{Z}_{2}\right]

\displaystyle\implies\left[X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow W\right].

Lastly, due to condition
2.2
, we have equality in Equantion
2.21
. Hence, putting it all together, we have:

(2.39)

\displaystyle I(\hat{Z}_{1};\hat{Z}_{2};W)=I(\hat{Z}_{1};\hat{Z}_{2})

\displaystyle\implies I(X_{1};X_{2};W)=I(\hat{Z}_{1};\hat{Z}_{2})

\displaystyle(\text{conds.~\ref{eq:cond-equal-1},~\ref{eq:lhs-eq-implication}})

(2.40)

\displaystyle\implies\sup I(X_{1};X_{2};V)=I(\hat{Z}_{1};\hat{Z}_{2})

(2.41)

\displaystyle\implies K(X_{1},X_{2};D_{1},D_{2})=I(\hat{Z}_{1};\hat{Z}_{2}),

where the supremum is over the same conditions as in
1.4
. Note that
W
is achieved by the supremum.

If either, condition
2.3
or
2.31
, is not met, more than
I(\hat{Z}_{1};\hat{Z}_{1})
is present in
W
and equality is not achieved in equation
2.8
. If condition
2.2
is not met, not all mutual information between
\hat{Z}_{1}
and
\hat{Z}_{2}
is placed on
W
and equality is not achieved in equation
2.21
.

Read the complete text