Wyner Common Information

The Wyner common information [LXC10, Wyn75] measures the minimum amount of information necessary needed to reconstruct a joint distribution from each marginal.

\[\C{X_{0:n} | Y_{0:m}} = \min_{\ind X_{0:n} \mid Y_{0:m}, V} \I{X_{0:n} : V | Y_{0:m}}\]

Operationally, it is the smallest common rate on the minimum sum-rate face of the The Gray-Wyner Network; its lossy generalization is the lossy common information.

Binary Symmetric Erasure Channel

The Wyner common information of the binary symmetric erasure channel is known to be:

\[\begin{split}\C{X : Y} = \begin{cases} 1 & p < \frac{1}{2} \\ \H{p} & p \ge \frac{1}{2} \end{cases}.\end{split}\]

We can verify this:

In [1]: from dit.multivariate import wyner_common_information as C

In [2]: ps = np.linspace(1e-6, 1-1e-6, 51)

In [3]: sbec = lambda p: dit.Distribution(['00', '0e', '1e', '11'], [(1-p)/2, p/2, p/2, (1-p)/2])

In [4]: wci_true = [1 if p < 1/2 else dit.shannon.entropy(p) for p in ps]

In [5]: wci_opt = [C(sbec(p)) for p in ps]

In [6]: plt.plot(ps, wci_true, ls='-', alpha=0.5, c='b');

In [7]: plt.plot(ps, wci_opt, ls='--', lw=2, c='b');

In [8]: plt.xlabel(r'Probability of erasure $p$');

In [9]: plt.ylabel(r'Wyner common information $C[X:Y]$');

In [10]: plt.show()
The Wyner common information of the binary symmetric erasure channel.

API

wyner_common_information(dist, rvs=None, crvs=None, niter=None, maxiter=1000, polish=1e-06, bound=None, backend='numpy')

Computes the wyner common information, min I[X:V] such that V renders all X_i independent.

Parameters:

  • dist (Distribution) – The distribution for which the wyner common information will be computed.

  • rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables used to calculate the wyner common information. If None, then it is calculated over all random variables, which is equivalent to passing rvs=dist.rvs.

  • crvs (list, None) – A single list of indexes specifying the random variables to condition on. If None, then no variables are conditioned on.

  • niter (int > 0) – Number of basin hoppings to perform during the optimization.

  • maxiter (int > 0) – The number of iterations of the optimization subroutine to perform.

  • polish (False, float) – Whether to polish the result or not. If a float, this will perform a second optimization seeded with the result of the first, but with smaller tolerances and probabilities below polish set to 0. If False, don’t polish.

  • bound (int) – Bound the size of the Markov variable.

  • backend (str) – The optimization backend to use. One of 'numpy' (default), 'jax', or 'torch'.

Returns:

ci – The wyner common information.

Return type:

float