Kamath-Anantharam Common Information

The Kamath-Anantharam common information [KA10] is a “dual” to the Gács-Körner Common Information constructed from the viewpoint of the Gray-Wyner source-coding system: it is the infimum of common-rate values \(R_0 \ge I(X;Y)\) for which every rate triple \((R_0, R_1, R_2)\) allowed by the elementary outer bound to the Gray-Wyner region is achievable.

Kamath and Anantharam show this quantity has a strikingly simple closed form. Define, for each \(y\) in the support of \(Y\), the conditional law \(\Phi^X_Y(y) = p(\cdot \mid Y=y)\), viewed as a random variable on \(Y\). Then

\[\begin{split}G(Y \to X) &= \H{\Phi^X_Y} \\ G(X \to Y) &= \H{\Phi^Y_X} \\ U(X; Y) &= \max\{ G(Y \to X), G(X \to Y) \}\end{split}\]

The asymmetric quantity \(\Phi^X_Y\) is exactly the minimal sufficient statistic of \(Y\) about \(X\) (Kamath & Anantharam 2010, Lemma 3.5(5)) — two values of \(Y\) collapse iff they induce the same conditional distribution over \(X\). So \(G(Y \to X)\) is the entropy of the partition of the alphabet of \(Y\) into “conditional-distribution-equivalent” classes.

For \(n > 2\) random variables, dit generalizes \(U\) analogously to how MSS Common Information extends:

\[U(X_{0:n}) = \max_i \H{\Phi^{X_{\setminus i}}_{X_i}}.\]

Worked example

The paper’s reference example (Section III-A) is the joint distribution

\[\begin{split}p(x, y) = \frac{1}{37} \begin{pmatrix} 4 & 0 & 0 & 0 \\ 0 & 9 & 2 & 3 \\ 0 & 12 & 3 & 4 \\ \end{pmatrix}\end{split}\]

with rows indexed by \(X \in \{a, b, c\}\) and columns by \(Y \in \{\alpha, \beta, \gamma, \delta\}\). Conditioning on \(Y\), the values \(\beta\) and \(\delta\) induce the same conditional distribution \(p(X \mid Y) = (0, 3/7, 4/7)\) and so collapse under \(\Phi^X_Y\); the other values are distinct. So \(\Phi^X_Y\) takes three values with probabilities \((4/37, 28/37, 5/37)\).

In [1]: from dit import Distribution as D

In [2]: from dit.multivariate import kamath_common_information as U

In [3]: from dit.multivariate import directed_kamath_common_information as G_dir

In [4]: outcomes = ['aα', 'bβ', 'bγ', 'bδ', 'cβ', 'cγ', 'cδ']

In [5]: pmf = [4/37, 9/37, 2/37, 3/37, 12/37, 3/37, 4/37]

In [6]: d = D(outcomes, pmf)

In [7]: G_dir(d, rvs=[1], about=[0])
Out[7]: 1.0414647631411194

In [8]: G_dir(d, rvs=[0], about=[1])
Out[8]: 1.3712481855145016

In [9]: U(d)
Out[9]: 1.3712481855145016

The conditional law \(\Phi^Y_X\) is injective on the support of \(X\) (all three rows of the joint matrix have distinct shape), so \(G(X \to Y) = \H{X}\) and \(U(X; Y) = G(X \to Y)\).

Properties

For two variables, \(U\) satisfies

\[\K{X : Y} \leq \I{X : Y} \leq \C{X : Y} \leq G(Y \to X) \leq \H{Y}\]

and likewise for \(G(X \to Y) \leq \H{X}\). The right-hand side bounds are tight on generic joint distributions, where no two columns of the joint matrix coincide as conditional laws and \(U(X; Y) = \max\{\H{X}, \H{Y}\}\).

API

kamath_common_information(dist, rvs=None, crvs=None)[source]

Calculates the Kamath-Anantharam dual common information U[X1:X2…] of the random variables in rvs.

For two variables this is

U(X; Y) = max{ G(Y -> X), G(X -> Y) }
= max{ H(Phi^X_Y), H(Phi^Y_X) },

the symmetric “dual” to the Gács-Körner common information introduced by Kamath & Anantharam (2010). It is generalized to n variables as

U(X_{0:n}) = max_i H(Phi^{X_{!=i}}_{X_i}),

the maximum entropy of the minimal sufficient statistic of one variable about all the others.

Parameters:

dist (Distribution) – The distribution from which the common information is calculated.
rvs (list, None) – A list of lists. Each inner list specifies the indexes of a random variable to compress via its minimal sufficient statistic about the rest. If None, then each single random variable is used.
crvs (list, None) – A single list of indexes specifying the random variables to condition on. If None, then no conditioning is performed.

Returns:

U – The Kamath-Anantharam dual common information.

Return type:

float

Raises:

ditException – Raised if rvs or crvs contain non-existant random variables.

directed_kamath_common_information(dist, rvs, about, crvs=None)[source]

Calculates the directed Kamath-Anantharam common information G(rvs -> about) = H(Phi^{about}_{rvs}), where Phi^{about}_{rvs} is the minimal sufficient statistic of rvs about about.

In the bivariate notation of Kamath & Anantharam (2010), this computes G(Y -> X) when called with rvs=Y, about=X. The variable on the tail of the arrow (rvs) is compressed via the minimal sufficient statistic; the variable on the head (about) is what that statistic preserves information about.

Parameters:

dist (Distribution) – The distribution from which the directed common information is calculated.
rvs (list) – The indexes (or names) of the random variables on the tail of the arrow. These are compressed to their minimal sufficient statistic about about.
about (list) – The indexes (or names) of the random variables on the head of the arrow. The minimal sufficient statistic preserves all information about these variables.
crvs (list, None) – The indexes of the random variables to condition on. If None, then no conditioning is performed.

Returns:

G – The directed Kamath-Anantharam common information.

Return type:

float

Raises:

ditException – Raised if rvs, about, or crvs contain non-existant random variables.