Tension Common Information

The Gács-Körner Common Information is brittle: it is determined entirely by the connected components of the support graph, so an arbitrarily small perturbation of the distribution can send it to zero. The tension common information [MR26a] is a continuous relaxation of it, built from the entanglement.

Entanglement

The entanglement of a pair measures how far its mutual information is from being extractable:

\[\Ent{X : Y} = \inf_{W} \left( \I{X : Y \mid W} + \I{X : W \mid Y} + \I{W : Y \mid X} \right)\]

This is the quantity on the right-hand side of the Makarychev-Makarychev-Romashchenko-Vereshchagin class of non-Shannon inequalities [MMRV02], and was studied by Zhang [Zha03] (writing it \(W(X, Y)\)) in connection with the approximate representability of mutual information. The name is due to [MR26a]; it is unrelated to quantum entanglement.

The three summands are exactly the coordinates of the region of tension, so the entanglement is the least coordinate-sum over that region — a single weighted-rate query on the The Gray-Wyner Network.

For \(n\) sources the tension coordinates are \(\I{X_{-i} : W \mid X_i}\) and \(\T{X_{0:n} \mid W}\), giving

\[\Ent{X_{0:n}} = \inf_{W} \left( \T{X_{0:n} \mid W} + \sum_i \I{X_{-i} : W \mid X_i} \right)\]

which reduces to the pairwise definition at \(n = 2\).

The entanglement vanishes exactly when the mutual information is Gács-Körner extractable, and attains \(\min\{\H{X \mid Y}, \H{Y \mid X}, \I{X : Y}\}\) when the pair is maximally non-extractable.

The tension common information

Because the entanglement is a deficiency, subtracting it from the total correlation gives a quantity that runs the same way as a common information:

\[\Tci{X_{0:n}} = \T{X_{0:n}} - \Ent{X_{0:n}}\]

Using the Gács-Körner meet as the probe makes every source tension vanish and leaves a residual of \(\T{X_{0:n}} - (n-1)\K{X_{0:n}}\), which sandwiches it:

\[(n - 1) \K{X_{0:n}} \leq \Tci{X_{0:n}} \leq \T{X_{0:n}}\]

Continuity

The distinguishing behaviour is what happens under perturbation. Consider a distribution whose support has two components, so that \(\K{X : Y} > 0\), and then add a single low-probability outcome bridging them:

In [1]: from dit.multivariate import gk_common_information as K, tension_common_information as Theta

In [2]: blocks = dit.Distribution(['00', '01', '10', '11', '22'], [0.2]*5)

In [3]: bridged = dit.Distribution(['00', '01', '10', '11', '22', '02'], [0.2, 0.2, 0.2, 0.2, 0.19, 0.01])

In [4]: K(blocks), K(bridged)
Out[4]: (0.7219280948873623, 0.0)

In [5]: Theta(blocks), Theta(bridged)

The Gács-Körner common information collapses to zero; the tension common information does not.

Fano plane

A pair uniform on the point-line incidences of the Fano plane is maximally non-extractable: its entanglement equals its mutual information, so its tension common information is zero.

In [6]: from dit.multivariate import entanglement, total_correlation

In [7]: lines = ['012', '034', '056', '136', '145', '235', '246']

In [8]: fano = dit.Distribution([p + str(i) for i, l in enumerate(lines) for p in l], [1/21]*21)

In [9]: total_correlation(fano), entanglement(fano)

This is certified spectrally: the Fano incidence graph is an expander, and spectral_entanglement_bound() reports its nominal bound. See The Gray-Wyner Network for the caveats around that bound.

API

entanglement(dist, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

Compute the entanglement.

The entanglement is the least total tension attainable by any probe W,

\[E(X_{0:n}) = \inf_W \Big\{ T[X_{0:n}|W] + \sum_i I[X_{-i}{:}W|X_i] \Big\},\]

which for a pair is inf_W I[X:Y|W] + I[X:W|Y] + I[W:Y|X] [MMRV02, MR26a, Zha03].

Parameters:

dist (Distribution) – The distribution for which the entanglement is computed.
rvs (list of lists, None) – The source groups. If None, each variable of dist is its own source.
crvs (list, None) – A single list of indexes specifying variables to condition on. If None, none are conditioned on.
niter (int, None) – Number of basin hops to perform during the optimization.
maxiter (int) – The number of iterations of the optimization subroutine to perform.
bound (int, None) – Bound the size of the probe variable.

Returns:

E – The entanglement.

Return type:

float

Examples

A pair whose mutual information is fully extractable has zero entanglement:

>>> from dit import Distribution
>>> from dit.multivariate import entanglement
>>> giant_bit = Distribution(['00', '11'], [1/2, 1/2])
>>> float(entanglement(giant_bit))
0.0

tension_common_information(dist, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

Compute the tension common information.

This is the portion of the total correlation that is not obstructed by tension,

\[\Theta(X_{0:n}) = T[X_{0:n}] - E(X_{0:n}),\]

a continuous relaxation of the Gacs-Korner common information obeying (n - 1) K <= Theta <= T [MR26a].

Parameters:

dist (Distribution) – The distribution for which the tension common information is computed.
rvs (list of lists, None) – The source groups. If None, each variable of dist is its own source.
crvs (list, None) – A single list of indexes specifying variables to condition on. If None, none are conditioned on.
niter (int, None) – Number of basin hops to perform during the optimization.
maxiter (int) – The number of iterations of the optimization subroutine to perform.
bound (int, None) – Bound the size of the probe variable.

Returns:

Theta – The tension common information.

Return type:

float

Examples

Unlike the Gacs-Korner common information, this does not collapse when the block structure of the support is perturbed:

>>> from dit import Distribution
>>> from dit.multivariate import gk_common_information, tension_common_information
>>> blocks = Distribution(['00', '01', '10', '11', '22'], [0.2] * 5)
>>> float(gk_common_information(blocks))
0.7219280948873623