Exact Common Information

The exact common information [KLEG14] is the entropy of the smallest variable \(V\) which renders all variables of interest independent:

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

Subadditivity of Independent Variables

Kumar et. al. [KLEG14] have shown that the exact common information of a pair of independent pairs of variables can be less than the sum of their individual exact common informations. Here we verify this claim:

In [1]: from dit.multivariate import exact_common_information as G

In [2]: d = dit.Distribution([(0,0), (0,1), (1,0)], [1/3]*3)

In [3]: d2 = d.__matmul__(d) # RTD doesn't use python 3

In [4]: print(d2)
Class:          Distribution
Alphabet:       (0, 1) for all rvs
Base:           linear
Outcome Class:  tuple
Outcome Length: 4
RV Names:       None

x              p(x)
(0, 0, 0, 0)   1/9
(0, 0, 0, 1)   1/9
(0, 0, 1, 0)   1/9
(0, 1, 0, 0)   1/9
(0, 1, 0, 1)   1/9
(0, 1, 1, 0)   1/9
(1, 0, 0, 0)   1/9
(1, 0, 0, 1)   1/9
(1, 0, 1, 0)   1/9

In [5]: 2*G(d)
Out[5]: 1.8365824892227227

In [6]: G(d2, [[0, 2], [1, 3]])
Out[6]: 1.752683838690199

API

exact_common_information(*args, **kwargs)

Computes the exact common information, min H[V] where V renders all rvs independent.

Parameters:
  • dist (Distribution) – The distribution for which the exact 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 exact common information. If None, then it 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.
  • rv_mode (str, None) – Specifies how to interpret rvs and crvs. Valid options are: {‘indices’, ‘names’}. If equal to ‘indices’, then the elements of crvs and rvs are interpreted as random variable indices. If equal to ‘names’, the the elements are interpreted as random variable names. If None, then the value of dist._rv_mode is consulted, which defaults to ‘indices’.
Returns:

ci – The exact common information.

Return type:

float