Channel Order

dit.channelorder compares discrete memoryless channels. The preorders are Blackwell (output-degraded), input-degraded, less noisy, more capable, and Shannon inclusion [CT06]. Le Cam and KL deficiencies quantify how far a pair of channels is from comparability.

These comparisons are the layer used by the channel-order PIDs PID_Deg, PID_MC, and PID_Prec (see Partial Information Decomposition).

A noiseless identity channel Blackwell-dominates a binary symmetric channel of the same alphabet, but not conversely:

In [1]: import numpy as np

In [2]: from dit.channelorder import is_output_degraded, is_less_noisy

In [3]: identity = np.eye(2)

In [4]: bsc = np.array([[0.9, 0.1], [0.1, 0.9]])

In [5]: is_output_degraded(identity, bsc)
Out[5]: True

In [6]: is_output_degraded(bsc, identity)
Out[6]: False

In [7]: is_less_noisy(identity, bsc)
Out[7]: True

Arguments may be channel matrices (rows = inputs) or any format accepted by the module’s channel helpers, including lists of conditional Distribution objects.

Preorders

is_output_degraded(mu, kappa, atol=1e-08)[source]

Check whether kappa is output-degraded from mu.

Returns True when there exists a stochastic matrix lambda such that kappa = lambda ∘ mu (i.e. kappa_s = Σ_z lambda(·|z) mu_s(z) for every input s). This is the Blackwell order [1]: mu is at least as informative as kappa.

Parameters:

mu (array_like or list of Distribution or Distribution) – The dominating channel P(Z|S), shape (|S|, |Z|).
kappa (array_like or list of Distribution or Distribution) – The dominated channel P(Y|S), shape (|S|, |Y|).
atol (float) – Feasibility tolerance for the LP.

Return type:

bool

Notes

Solved as a linear program: for each output y of kappa, find lambda(y|z) >= 0 summing to 1 over y, such that for every input s: kappa_s(y) = Σ_z lambda(y|z) mu_s(z).

is_blackwell_sufficient(mu, kappa, atol=1e-08)

Check whether kappa is output-degraded from mu.

Returns True when there exists a stochastic matrix lambda such that kappa = lambda ∘ mu (i.e. kappa_s = Σ_z lambda(·|z) mu_s(z) for every input s). This is the Blackwell order [1]: mu is at least as informative as kappa.

Parameters:

mu (array_like or list of Distribution or Distribution) – The dominating channel P(Z|S), shape (|S|, |Z|).
kappa (array_like or list of Distribution or Distribution) – The dominated channel P(Y|S), shape (|S|, |Y|).
atol (float) – Feasibility tolerance for the LP.

Return type:

bool

Notes

Solved as a linear program: for each output y of kappa, find lambda(y|z) >= 0 summing to 1 over y, such that for every input s: kappa_s(y) = Σ_z lambda(y|z) mu_s(z).

is_input_degraded(mu_bar, kappa_bar, atol=1e-08)[source]

Check whether kappa_bar is input-degraded from mu_bar.

For channels with a common output alphabet, mu_bar ⊒^ideg kappa_bar iff each row of kappa_bar lies in the convex hull of the rows of mu_bar (Proposition 2 in [3]).

Parameters:

mu_bar (array_like or list of Distribution or Distribution) – The dominating reverse channel P(S|Z), shape (|Z|, |S|).
kappa_bar (array_like or list of Distribution or Distribution) – The dominated reverse channel P(S|Y), shape (|Y|, |S|).
atol (float) – Feasibility tolerance.

Return type:

bool

is_less_noisy(mu, kappa, atol=1e-06)[source]

Check whether mu is less noisy than kappa.

mu ⊒_ln kappa iff I(U;Z) >= I(U;Y) for every P(U,S) with U-S-YZ Markov (Definition 9 in [2]). Equivalently, I(S;Z) - I(S;Y) is concave in P(S) for the fixed channels [5, Eq. after Definition 9].

We check by finding the P(S) that maximizes I(S;Y)-I(S;Z) for every auxiliary channel P(S|U) (parameterized as a single extra variable U). If the maximum is <= atol, the order holds.

Parameters:

mu (array_like) – Channel P(Z|S).
kappa (array_like) – Channel P(Y|S).
atol (float) – Tolerance (default 1e-6; see is_more_capable()).

Return type:

bool

Notes

This is a stricter check than is_more_capable; by Proposition 3, is_less_noisy => is_more_capable but not vice-versa.

The implementation checks whether I(S;Y)-I(S;Z) is concave as a function of P(S) by searching for a P(S) that yields a positive gap while also checking against auxiliary channels of bounded size.

is_more_capable(mu, kappa, atol=1e-06)[source]

Check whether mu is more capable than kappa.

mu ⊒_mc kappa iff I(S;Z) >= I(S;Y) for every input distribution P(S) (Definition 8 in [2]).

Parameters:

mu (array_like) – Channel P(Z|S).
kappa (array_like) – Channel P(Y|S).
atol (float) – Tolerance: the order holds if max I(S;Y)-I(S;Z) <= atol. Defaults to 1e-6, comfortably above the residual noise of the non-convex multistart maximization and well below genuine order violations.

Return type:

bool

is_shannon_included(mu, kappa, atol=1e-08, niter=None)[source]

Check whether mu includes kappa in the Shannon sense.

mu ⊒_inc kappa iff there exists chi in the set Sigma (convex hull of product pre/post-channels) such that kappa = chi ∘_s mu (Definition 6, Proposition 1 in [4]).

The channels may have different input/output alphabets.

Parameters:

mu (array_like) – Channel P(Z|S), shape (|S|, |Z|).
kappa (array_like) – Channel P(Y|S'), shape (|S'|, |Y|).
atol (float) – Residual threshold below which the inclusion is declared.
niter (int, optional) – Number of random restarts. Defaults to 20.

Return type:

bool

Notes

This is a heuristic non-convex check. True is reliable, but False may be a false negative.

When |S'| == |S|, the Blackwell order implies Shannon inclusion, so is_output_degraded() is tried first as a fast path.

blackwell_order_joint(dist, S, Y, Z)[source]

Check the Blackwell order from a joint distribution.

Returns True if P(Z|S) ⊒ P(Y|S) (i.e. Z is at least as informative about S as Y).

Parameters:

dist (Distribution) – A joint distribution over (S, Y, Z).
S (list) – Indices/names of the input variable(s).
Y (list) – Indices/names of the first output.
Z (list) – Indices/names of the second output.

Return type:

bool

Deficiencies

Le Cam deficiency is zero if and only if the first channel output-degrades to the second. KL variants weight the gap by an input distribution.

le_cam_deficiency(mu, kappa)[source]

Le Cam deficiency of mu with respect to kappa.

\[\delta(\mu, \kappa) = \inf_{\lambda \in \mathcal{M}(Z;Y)} \sup_{s \in S} \|\lambda \circ \mu_s - \kappa_s\|_{\mathrm{TV}}\]

Equals zero iff mu output-degrades to kappa (Blackwell order).

Parameters:

mu (array_like) – Channel P(Z|S), shape (|S|, |Z|).
kappa (array_like) – Channel P(Y|S), shape (|S|, |Y|).

Returns:

Non-negative deficiency value.

Return type:

float

Notes

Formulated as a linear program with variables lambda(y|z) and epsilon (the worst-case TV distance).

le_cam_distance(mu, kappa)[source]

Le Cam distance between mu and kappa.

\[\Delta(\mu, \kappa) = \max\bigl(\delta(\mu, \kappa),\; \delta(\kappa, \mu)\bigr)\]

This is a pseudometric on channels with a common input alphabet.

Parameters:

mu (array_like) – Channel P(Z|S).
kappa (array_like) – Channel P(Y|S).

Return type:

float

weighted_le_cam_deficiency(mu, kappa, pi)[source]

Weighted Le Cam deficiency of mu w.r.t. kappa.

\[\delta_\pi(\mu, \kappa) = \inf_{\lambda} \mathbb{E}_{s \sim \pi} \|\lambda \circ \mu_s - \kappa_s\|_{\mathrm{TV}}\]

Parameters:

mu (array_like) – Channel P(Z|S), shape (|S|, |Z|).
kappa (array_like) – Channel P(Y|S), shape (|S|, |Y|).
pi (array_like) – Input marginal P(S), length |S|.

Return type:

float

output_kl_deficiency(mu, kappa)[source]

Output KL deficiency of mu with respect to kappa.

\[\delta_o(\mu, \kappa) = \inf_{\lambda \in \mathcal{M}(Z;Y)} \sup_{s \in S} D(\kappa_s \| \lambda \circ \mu_s)\]

Parameters:

mu (array_like) – Channel P(Z|S), shape (|S|, |Z|).
kappa (array_like) – Channel P(Y|S), shape (|S|, |Y|).

Return type:

float

Notes

Solved as a minimax problem via multi-start convex optimization over the stochastic matrix lambda.

weighted_output_kl_deficiency(mu, kappa, pi)[source]

Weighted output KL deficiency of mu w.r.t. kappa.

\[\delta^\pi_o(\mu, \kappa) = \min_{\lambda \in \mathcal{M}(Z;Y)} D(\kappa \| \lambda \circ \mu \mid \pi_S) = \min_\lambda \sum_s \pi(s)\, D(\kappa_s \| \lambda \circ \mu_s)\]

Parameters:

mu (array_like) – Channel P(Z|S), shape (|S|, |Z|).
kappa (array_like) – Channel P(Y|S), shape (|S|, |Y|).
pi (array_like) – Input marginal P(S), length |S|.

Return type:

float

Notes

Convex in lambda and solved via multi-start optimization. Related to the Blackwell order: equals zero iff mu output-degrades to kappa.

weighted_output_kl_deficiency_joint(dist, S, Y, Z)[source]

Weighted output KL deficiency from a joint distribution.

Extracts P(Y|S) (kappa), P(Z|S) (mu), and P(S) (pi) from the joint, then computes the weighted output KL deficiency.

Parameters:

dist (Distribution) – A joint distribution.
S (list) – Input variable indices/names.
Y (list) – First output variable indices/names.
Z (list) – Second output variable indices/names.

Returns:

delta^pi_o(mu, kappa) – cost of approximating P(Y|S) from P(Z|S) via output randomization.

Return type:

float

weighted_input_kl_deficiency(mu_bar, kappa_bar, pi)[source]

Weighted input KL deficiency of mu_bar w.r.t. kappa_bar.

\[\delta^\pi_i(\bar\mu, \bar\kappa) = \min_{\bar\lambda \in \mathcal{M}(Y;Z)} \sum_y \pi(y)\, D\bigl(\bar\kappa_y \| \sum_z \bar\lambda(z|y)\,\bar\mu_z\bigr)\]

For channels with a common output alphabet, this quantifies the cost of approximating kappa_bar from mu_bar via input randomization.

Parameters:

mu_bar (array_like) – Reverse channel P(S|Z), shape (|Z|, |S|).
kappa_bar (array_like) – Reverse channel P(S|Y), shape (|Y|, |S|).
pi (array_like) – Marginal P(Y), length |Y|.

Return type:

float