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 for a pair 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 source tensions are \(\I{X_{-i} : W \mid X_i}\) and the leftover dependence is measured by the Dual Total Correlation \(\B{X_{0:n} \mid W}\), giving

\[\Ent{X_{0:n}} = \inf_{W} \left( \B{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 dual total correlation keeps the measure on the scale of the common informations: conditioning on the Gács-Körner meet lowers \(\B{}\) by exactly \(\K{}\), while it lowers the total correlation by \((n-1)\K{}\). With a total-correlation residual the three-variable giant bit would have a tension common information of 2 bits, more than its entropy. Because \(\B{X_{0:n} \mid W}\) is not affine in the Gray-Wyner rates, for \(n \geq 3\) the probe \(W\) is optimized directly rather than through the Gray-Wyner region.

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 dual total correlation gives a quantity that runs the same way as a common information:

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

For a pair \(\B{X : Y} = \I{X : Y}\). Using the Gács-Körner meet as the probe makes every source tension vanish and leaves a residual of \(\B{X_{0:n}} - \K{X_{0:n}}\), which sandwiches it:

\[\K{X_{0:n}} \leq \Tci{X_{0:n}} \leq \B{X_{0:n}}\]

For two variables this places it in the common-information ordering between the Gács-Körner common information and the mutual information. For three or more it is bounded above by the dual total correlation but is not known to be comparable with the CAEKL Mutual Information.

Computation

Two exact reductions are applied before any optimization (when no conditioning variables are given):

  • Split on the Gács-Körner meet. Adding the meet \(V\) to a probe leaves every source tension unchanged, since \(V\) is a function of each source, and lowers the residual by \(\H{V \mid W}\). So some optimal probe contains \(V\), and the entanglement is the average of the entanglements of the components, \(\Ent{X_{0:n}} = \sum_v p(v) \, \Ent{X_{0:n} \mid V = v}\).

  • Reduce to minimal sufficient statistics. Replacing a source by its minimal sufficient statistic about the other sources changes neither the entanglement nor the dual total correlation. This strips private randomness.

Without these, the optimizer must discover the meet and ignore private randomness inside a single probe, which it routinely fails to do on independent products.

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\{ B[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]. The multivariate residual is the dual total correlation, which puts E on the scale of the common informations.

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 dual total correlation that is not obstructed by tension,

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

a continuous relaxation of the Gacs-Korner common information obeying K <= Theta <= B [MR26a]. For a pair B is the mutual information.

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