dit.algorithms

Various algorithms related to manipulating or measuring properties of distributions.

Classes

BaseAuxVarOptimizer

Base class that performs many methods related to optimizing auxiliary variables.

BaseConvexOptimizer

Implement convex optimization.

BaseNonConvexOptimizer

Implement non-convex optimization.

BaseOptimizer

Base class for performing optimizations.

Functions

cdf

Compute the cumulative distribution function P(X <= x).

central_moment

Compute the n-th central moment E[(X - mu)^n].

channel_capacity

Calculates the channel capacity from conditional distributions P(Y|X).

channel_capacity_cost

Capacity of a channel whose inputs carry a cost, under an average budget.

channel_capacity_joint

Compute the channel capacity from input_ to output.

commitment_capacity

The commitment capacity of a discrete memoryless channel [WNI03].

correlation

Compute the Pearson correlation matrix for a joint distribution.

covariance

Compute the covariance matrix for a joint distribution.

degrees_of_freedom

Returns the degrees of freedom of a marginal model: the number of free parameters needed to specify the maximum entropy distribution consistent with the marginals in structure.

expanded_samplespace

Returns a new distribution with an expanded sample space.

expectation

Compute E[f(X)] for an arbitrary callable f.

fit_marginal_lift_mixture

Fit a convex combination of lifts of marginals of order at most order.

fit_mixture_of_products

Fit a \(k\)-mixture of product distributions to dist by EM.

info_trim

Returns a new distribution with the minimal sufficient statistics of each random variable in rvs about all the other variables.

insert_join

Returns a new distribution with the join inserted at index idx.

insert_meet

Returns a new distribution with the meet inserted at index idx.

insert_mss

Inserts the minimal sufficient statistic of rvs about about into dist at index idx.

ipf_dist

Return the maximum entropy distribution consistent with the marginals from dist specified in rvs, computed via Iterative Proportional Fitting.

iqr

Compute the interquartile range (Q3 - Q1).

kurtosis

Compute the kurtosis (4th standardised moment).

lift_marginal

Lift a marginal on coordinates S to a full joint pmf.

m_projection

Project dist onto the order-order m-flat mixture family.

m_projection_eps_limit

Reverse-KL m-projection with symmetric \(P_\varepsilon\), taking \(\varepsilon \downarrow 0\) along eps_schedule.

m_projection_from_subsets

Project dist onto the m-flat family spanned by subsets.

marginal_lift_dists

Ladder of marginal-lift mixtures for orders \(0,\ldots,k_{\max}\).

marginal_maxent_dists

Return the marginal-constrained maximum entropy distributions.

maxent_dist

Return the maximum entropy distribution consistent with the marginals from dist specified in rvs.

maximal_equivocation

The maximal equivocation of a channel, max_p H[X | Y].

maximize_convex_function

Maximize a convex function over a polytope.

maximum

Return the largest outcome in the support (per index).

mean

Compute the mean (expected value) of a distribution.

median

Compute the median of a distribution.

mflat_design_matrix

Build the linear design matrix for the order-order m-flat family.

mflat_mprojection_dists

Return the m-flat projection ladder \(Q^{(0)},\ldots,Q^{(k_{\max})}\).

mflat_subsets_from_dependency

Downward-closed collection of index-tuples for an antichain dependency.

minimum

Return the smallest outcome in the support (per index).

mixture_of_products_dists

Fit the mixture-of-products ladder \(Q^{(1)},\ldots,Q^{(k_{\max})}\).

mode

Compute the modes of a distribution.

mss

mss_sigalg

Construct the sigma algebra for the minimal sufficient statistic of rvs about about.

nonredundant_inputs

The inputs of the non-redundant version of a channel [WNI03].

parallel_sweep

Run func(item, rng) for each item in items, in parallel when safe.

percentile

Compute the p-th percentile (0 <= p <= 100).

pruned_samplespace

Returns a new distribution with pruned sample space.

quantile

Compute the q-quantile of a distribution (0 <= q <= 1).

range_

Compute the range (maximum - minimum) of the support per index.

sibson_capacity

Sibson's capacity of order alpha, C_alpha = max_p I_alpha(X : Y).

skewness

Compute the skewness (3rd standardised moment).

spectral_entanglement_bound

The nominal spectral lower bound on the entanglement.

standard_deviation

Compute the standard deviation sqrt(Var(X)).

standard_moment

Compute the n-th standardised moment E[((X - mu)/sigma)^n].

support_biadjacency

The 0/1 biadjacency matrix of the support graph of a pair.

support_singular_values

The singular values of the support graph's biadjacency matrix.

symmetric_smooth

Symmetric full-support smoothing \(P_\varepsilon = (1-\varepsilon)P + \varepsilon U\).

variance

Compute the variance Var(X) = E[(X - mu)^2].

Reference

class BaseAuxVarOptimizer(dist, rvs=None, crvs=None)[source]

Bases: BaseNonConvexOptimizer

Base class that performs many methods related to optimizing auxiliary variables.

construct_joint(x)[source]

Construct the joint distribution.

Parameters:

x (np.ndarray) – An optimization vector.

Returns:

joint – The joint distribution resulting from the distribution passed in and the optimization vector.

Return type:

np.ndarray

construct_full_joint(x)[source]

Construct the joint distribution.

Parameters:

x (np.ndarray) – An optimization vector.

Returns:

joint – The joint distribution resulting from the distribution passed in and the optimization vector.

Return type:

np.ndarray

construct_random_initial()[source]

Construct a random optimization vector.

Returns:

x – A random optimization vector.

Return type:

np.ndarray

construct_uniform_initial()[source]

Construct a uniform optimization vector.

Returns:

x – A uniform optimization vector.

Return type:

np.ndarray

construct_copy_initial()[source]

Construct a copy optimization vector.

Returns:

x – A copy optimization vector.

Return type:

np.ndarray

construct_constant_initial()[source]

Construct a constant optimization vector.

Returns:

x – A constant optimization vector.

Return type:

np.ndarray

construct_initial()

Construct a random optimization vector.

Returns:

x – A random optimization vector.

Return type:

np.ndarray

construct_distribution(x=None, cutoff=1e-05)[source]

Construct the distribution.

Parameters:
  • x (np.ndarray, None) – An optimization vector. If None, use self._optima.

  • cutoff (float) – Ignore probabilities smaller than this.

Returns:

d – The original distribution, plus its auxiliary variables.

Return type:

Distribution

class BaseConvexOptimizer(dist, rvs=None, crvs=None)[source]

Bases: BaseOptimizer

Implement convex optimization.

class BaseNonConvexOptimizer(dist, rvs=None, crvs=None)[source]

Bases: BaseOptimizer

Implement non-convex optimization.

class BaseOptimizer(dist, rvs=None, crvs=None)[source]

Bases: object

Base class for performing optimizations.

abstractmethod construct_initial()[source]

Select the default method of generating an initial condition.

Returns:

x – An optimization vector.

Return type:

np.ndarray

construct_random_initial()[source]

Construct a random optimization vector.

Returns:

x – A random optimization vector.

Return type:

np.ndarray

construct_uniform_initial()[source]

Construct a uniform optimization vector.

Returns:

x – A uniform optimization vector.

Return type:

np.ndarray

optimize(x0=None, niter=None, maxiter=None, polish=1e-06, callback=False, rng=None)[source]

Perform the optimization.

Parameters:
  • x0 (np.ndarray) – An initial optimization vector.

  • niter (int) – The number of optimization iterations to perform.

  • maxiter (int) – The number of steps for an optimization subroutine to perform.

  • polish (float) – The threshold for valid optimization elements. If 0, no polishing is performed.

  • callback (bool) – Whether to use a callback to track the performance of the optimization. Generally, this should be False as it adds some significant time to the optimization.

  • rng (np.random.Generator, int, None) – An optional random number generator used for all randomness in this optimization (random initial conditions and the basin-hopping step). When None (default), the global np.random state is used, preserving backwards-compatible behavior. Supplying a per-task generator isolates parallel outer sweeps from one another.

Returns:

result – The result of the optimization.

Return type:

OptimizeResult

cdf(dist)[source]

Compute the cumulative distribution function P(X <= x).

For a 1-D distribution, returns (values, cumprobs) where values are the sorted unique outcomes and cumprobs are the corresponding cumulative probabilities.

For a multi-dimensional distribution, returns a list of (values, cumprobs) tuples, one per index (marginal CDF).

Parameters:

dist (Distribution)

Returns:

result – For 1-D: (values, cumprobs). For multi-D: [(values_0, cumprobs_0), …].

Return type:

tuple or list of tuples

central_moment(dist, n)[source]

Compute the n-th central moment E[(X - mu)^n].

Parameters:
Returns:

moments – The n-th central moment of each index of the outcomes.

Return type:

ndarray

channel_capacity(cdists, marginal=None, rtol=None, atol=None, maxiter=100000, method='accelerated', eliminate=False)[source]

Calculates the channel capacity from conditional distributions P(Y|X).

The capacity is computed with the Blahut-Arimoto algorithm [Ari72, Bla72], stopping once Blahut’s lower and upper bounds on the capacity agree to within tolerance, so the returned value is within max(atol, rtol * C) bits of the true capacity. Weakly symmetric [CT06] and square nonsingular channels are solved in closed form when the closed form certifies.

Parameters:
  • cdists (list, ndarray, Distribution) – A list of conditional distributions, a 2D array where rows are inputs and columns are outputs, or a conditional Distribution such as p(Y|X).

  • marginal (distribution | None) – The marginal distribution P(X). If provided, P*(X) is returned as a distribution object. If None, P*(X) is returned as a numpy array.

  • rtol (float or None) – Relative tolerance on the capacity. Defaults to ditParams[‘rtol’].

  • atol (float or None) – Absolute tolerance on the capacity, in bits. Defaults to ditParams[‘atol’].

  • maxiter (int) – Maximum number of Blahut-Arimoto iterations. A RuntimeWarning is raised if the bounds have not met by then.

  • method ({'accelerated', 'ba'}) – 'ba' is the classic iteration; 'accelerated' takes the step r <- r exp(mu D) of [MD04] with the adaptive mu = D(r_k || r_{k-1}) / D(q_k || q_{k-1}), falling back to the classic step whenever the mutual information would decrease.

  • eliminate (bool) – If True, iterate on a growing active set of inputs [Say00]. This helps when only a few of many inputs carry probability at capacity.

Returns:

  • cc (float) – The channel capacity.

  • marginal_opt (distribution or ndarray) – The optimal marginal P*(X).

channel_capacity_cost(cdists, cost, budget, rtol=None, atol=None, maxiter=100000, method='accelerated')[source]

Capacity of a channel whose inputs carry a cost, under an average budget.

Computes C(B) = max { I[X : Y] : E[cost(X)] <= B } through Blahut’s Lagrangian form [Bla72]: for a multiplier s >= 0 the iteration maximizes I[X : Y] - s E[cost(X)] (the offset divergences D(P_x || q) - s cost(x) keep the bound-gap certificate), and C(B) = min_s max_p I - s (E[cost] - B). The multiplier is found by root-finding E[cost] = B.

Parameters:
  • cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().

  • cost (array_like) – The cost of each input, in the same order as the channel’s rows.

  • budget (float) – The maximum average cost.

  • rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].

  • atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].

  • maxiter (int) – Maximum Blahut-Arimoto iterations per value of the multiplier.

  • method ({'accelerated', 'ba'}) – As in channel_capacity().

Returns:

  • cc (float) – The cost-constrained capacity, in bits.

  • pmf (np.ndarray) – An input distribution achieving it. If the optimal input at the final multiplier is not unique its cost may differ slightly from budget.

  • s (float) – The Lagrange multiplier, in bits per unit cost; the slope of C(B). 0 when the budget does not bind and inf when only the cheapest inputs are affordable.

Raises:

ditException – If the budget is below the cheapest input’s cost.

channel_capacity_joint(dist, input_, output, marginal=False)[source]

Compute the channel capacity from input_ to output.

Parameters:
  • dist (Distribution) – The joint distribution.

  • input (iterable) – The random variables that are the input of the channel.

  • output (iterable) – The random variables that are the output of the channel.

  • marginal (bool) – Whether to return the marginal distribution. Defaults to False.

commitment_capacity(cdists, rtol=None, atol=None, maxiter=100000, redundancy_tol=1e-09)[source]

The commitment capacity of a discrete memoryless channel [WNI03].

This is the largest rate at which Alice can commit to a message through the channel: Bob learns almost nothing about it until she reveals it, and she cannot reveal a different message, except with vanishing probability. Unlimited noiseless two-way communication is allowed on the side. Winter, Nascimento and Imai show that it is the maximal equivocation of the channel once its redundant inputs are removed:

C_com = max_p H[X | Y], with p ranging over inputs of the non-redundant channel.

See nonredundant_inputs() and maximal_equivocation(). The commitment capacity is zero exactly when the output of the non-redundant channel determines its input; every other channel allows bit commitment. It is also a lower bound on the rate at which the channel allows coin tossing.

Parameters:
  • cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().

  • rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].

  • atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].

  • maxiter (int) – Maximum number of iterations. A RuntimeWarning is raised if the bounds have not met by then.

  • redundancy_tol (float) – Passed to nonredundant_inputs() as atol. The commitment capacity is not continuous in the channel: inputs closer than this count as one. For instance, the binary symmetric channel’s commitment capacity H_b(p) tends to one bit as p tends to 1/2, but at p = 1/2 its two inputs coincide and it is zero.

Returns:

  • cc (float) – The commitment capacity, in bits.

  • pmf (np.ndarray) – An optimal input distribution. It is zero on redundant inputs.

correlation(dist)[source]

Compute the Pearson correlation matrix for a joint distribution.

For a distribution over d random variables, returns a d x d matrix where entry (i, j) is Cor(Xi, Xj) = Cov(Xi, Xj) / (sigma_i * sigma_j).

Parameters:

dist (Distribution)

Returns:

cor

Return type:

ndarray, shape (d, d)

covariance(dist)[source]

Compute the covariance matrix for a joint distribution.

For a distribution over d random variables, returns a d x d matrix where entry (i, j) is Cov(Xi, Xj).

For a 1-D distribution the result is a 1x1 array containing the variance.

Parameters:

dist (Distribution)

Returns:

cov

Return type:

ndarray, shape (d, d)

degrees_of_freedom(dist, structure=None)[source]

Returns the degrees of freedom of a marginal model: the number of free parameters needed to specify the maximum entropy distribution consistent with the marginals in structure.

This is the “complexity” of a reconstructability-analysis model. It is the rank of the marginal constraint matrix (which includes the normalization constraint) minus one for that normalization constraint.

Parameters:
  • dist (distribution) – The distribution defining the sample space and the marginal values.

  • structure (sequence, None) – A sequence whose elements are also sequences, each specifying a marginal (a “projection”) to constrain, e.g. [[0, 1], [1, 2]] for AB:BC. If None, the independence model (each variable on its own) is used.

Returns:

df – The degrees of freedom of the model.

Return type:

int

Examples

>>> d = dit.uniform_distribution(3, 2)
>>> dit.algorithms.degrees_of_freedom(d, [[0, 1], [2]])
4
>>> dit.algorithms.degrees_of_freedom(d, [[0, 1], [1, 2]])
5
expanded_samplespace(d, alphabets=None, union=True)[source]

Returns a new distribution with an expanded sample space.

Expand the sample space so that it is the Cartesian product of the alphabets for each random variable.

Parameters:
  • d (distribution) – The distribution used to create the pruned distribution.

  • alphabets (list) – A list of alphabets, with length equal to the outcome length in d. Each alphabet specifies the alphabet to be used for a single index random variable. The sample space of the new distribution will be the Cartesian product of these alphabets.

  • union (bool) – If True, then the alphabet for each random variable is unioned. The unioned alphabet is then used for each random variable.

Returns:

ed – The distribution with an expanded sample space.

Return type:

distribution

expectation(dist, f=None)[source]

Compute E[f(X)] for an arbitrary callable f.

When f is None this is equivalent to mean().

Parameters:
  • dist (Distribution) – The distribution.

  • f (callable or None) – A function that maps an outcome to a numeric value (scalar or array). If None, the identity function is used.

Returns:

result – The expected value E[f(X)].

Return type:

float or ndarray

fit_marginal_lift_mixture(dist, order, mode='uniform', n_init=12, rng=0)[source]

Fit a convex combination of lifts of marginals of order at most order.

Returns:

result – Keys dist, labels, alpha, L2.

Return type:

dict

fit_mixture_of_products(dist, k, *, n_init=12, maxiter=200, tol=1e-10, rng=0)[source]

Fit a \(k\)-mixture of product distributions to dist by EM.

Parameters:
  • dist (Distribution) – Target joint.

  • k (int) – Number of mixture components.

  • n_init (int) – Random restarts and EM iteration cap.

  • maxiter (int) – Random restarts and EM iteration cap.

  • tol (float) – Log-likelihood convergence tolerance.

  • rng (np.random.Generator, int, None) – Source of randomness for the restarts.

Returns:

result – Keys dist (fitted Distribution), pi, conds, I_xv (\(I(X;V)\) under data-weighted responsibilities), H_v, loglik.

Return type:

dict

info_trim(dist, rvs=None)[source]

Returns a new distribution with the minimal sufficient statistics of each random variable in rvs about all the other variables.

Parameters:
  • dist (Distribution) – The distribution contiaining the random variables from which the joint minimal sufficent statistic will be computed.

  • rvs (list) – A list of random variables to be compressed into minimal sufficient statistics.

insert_join(dist, idx, rvs, support_only=False)[source]

Returns a new distribution with the join inserted at index idx.

The join of the random variables in rvs is constructed and then inserted into at index idx.

Parameters:
  • dist (Distribution) – The distribution which defines the base sigma-algebra.

  • idx (int) – The index at which to insert the join. To append the join, set idx to be equal to -1 or dist.outcome_length().

  • rvs (list) – A list of lists. Each list specifies a random variable to be met with the other lists. Each random variable can defined as a series of unique indexes. Multiple random variables can use the same index. For example, [[0, 1], [1, 2]].

  • support_only (bool) – If True, only consider outcomes with non-zero probability.

Returns:

d – The new distribution with the join at index idx.

Return type:

Distribution

insert_meet(dist, idx, rvs, support_only=False)[source]

Returns a new distribution with the meet inserted at index idx.

The meet of the random variables in rvs is constructed and then inserted into at index idx.

Parameters:
  • dist (Distribution) – The distribution which defines the base sigma-algebra.

  • idx (int) – The index at which to insert the meet. To append the meet, set idx to be equal to -1 or dist.outcome_length().

  • rvs (list) – A list of lists. Each list specifies a random variable to be met with the other lists. Each random variable can defined as a series of unique indexes. Multiple random variables can use the same index. For example, [[0,1],[1,2]].

  • support_only (bool) – If True, only consider outcomes with non-zero probability.

Returns:

d – The new distribution with the meet at index idx.

Return type:

Distribution

insert_mss(dist, idx, rvs, about=None)[source]

Inserts the minimal sufficient statistic of rvs about about into dist at index idx.

Parameters:
  • dist (Distribution) – The distribution which defines the base sigma-algebra.

  • idx (int) – The location in the distribution to insert the minimal sufficient statistic.

  • rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.

  • about (list) – A list of random variables for which the minimal sufficient static will retain all information about.

Returns:

d – The distribution dist modified to contain the minimal sufficient statistic.

Return type:

Distribution

Examples

>>> d = Xor()
>>> print(insert_mss(d, -1, [0], [1, 2]))
Class:          Distribution
Alphabet:       ('0', '1') for all rvs
Base:           linear
Outcome Class:  str
Outcome Length: 4
RV Names:       None
x      p(x)
0000   0.25
0110   0.25
1011   0.25
1101   0.25
ipf_dist(dist, rvs, tol=1e-10, maxiter=10000, sparse=True, return_status=False)[source]

Return the maximum entropy distribution consistent with the marginals from dist specified in rvs, computed via Iterative Proportional Fitting.

Parameters:
  • dist (Distribution) – The distribution whose marginals should be matched.

  • rvs (list of lists) – The marginals from dist to constrain. Each inner list specifies a set of random variables (a marginal “projection”) to hold fixed, e.g. [[0, 1], [1, 2]] for the structure AB:BC.

  • tol (float) – The convergence tolerance. Iteration stops once the largest deviation of any constrained marginal from its target falls below tol.

  • maxiter (int) – The maximum number of IPF cycles to perform.

  • sparse (bool) – Whether the returned distribution should be sparse or dense.

  • return_status (bool) – If True, return a (me, converged) tuple, where converged is True iff the final marginal deviation fell below tol within maxiter cycles. IPF converges only linearly on cyclic structures with induced structural zeros, so callers that need an exact answer should check this flag and fall back to a convex optimizer when it is False.

Returns:

  • me (Distribution) – The maximum entropy distribution.

  • converged (bool) – Only returned when return_status is True (see above).

iqr(dist)[source]

Compute the interquartile range (Q3 - Q1).

Parameters:

dist (Distribution)

Returns:

iqr

Return type:

ndarray

kurtosis(dist, excess=True)[source]

Compute the kurtosis (4th standardised moment).

Parameters:
  • dist (Distribution)

  • excess (bool) – If True (default), return excess kurtosis (subtract 3 so that a normal distribution has kurtosis 0). If False, return the raw 4th standardised moment.

Returns:

kurt

Return type:

ndarray

lift_marginal(outs, pmf, alph, S, mode='uniform')[source]

Lift a marginal on coordinates S to a full joint pmf.

Parameters:
  • outs – Dense Cartesian table for the joint.

  • pmf – Dense Cartesian table for the joint.

  • alph – Dense Cartesian table for the joint.

  • S (tuple of int) – Variable indices of the marginal.

  • mode ({'uniform', 'product'}) – How to extend off S.

m_projection(dist, order, nrestarts=16, maxiter=3000, warm_start=None, criterion='reverse_kl', eps=None)[source]

Project dist onto the order-order m-flat mixture family.

Parameters:
  • dist (Distribution) – The target distribution \(P\).

  • order (int) – Maximum ANOVA order kept in \(\mathcal{M}_{\mathrm{order}}\).

  • nrestarts (int) – Optimizer controls.

  • maxiter (int) – Optimizer controls.

  • warm_start (Distribution or None) – Optional warm start.

  • criterion ({'reverse_kl', 'forward_kl', 'jsd'}) – Projection objective.

  • eps (float or None) – For reverse_kl, weight in \(P_\varepsilon=(1-\varepsilon)P+\varepsilon U\). Defaults to 1e-8 when None.

Returns:

q

Return type:

Distribution

m_projection_eps_limit(dist, subsets=None, order=None, eps_schedule=(0.0001, 1e-06, 1e-08), nrestarts=16, maxiter=3000, warm_start=None)[source]

Reverse-KL m-projection with symmetric \(P_\varepsilon\), taking \(\varepsilon \downarrow 0\) along eps_schedule.

m_projection_from_subsets(dist, subsets, nrestarts=16, maxiter=3000, warm_start=None, criterion='reverse_kl', eps=None)[source]

Project dist onto the m-flat family spanned by subsets.

marginal_lift_dists(dist, k_max=None, mode='uniform', n_init=12, rng=0)[source]

Ladder of marginal-lift mixtures for orders \(0,\ldots,k_{\max}\).

Order 0 is the uniform distribution. Order \(n\) includes the full joint as a block and recovers \(P\) exactly.

marginal_maxent_dists(dist, k_max=None)[source]

Return the marginal-constrained maximum entropy distributions.

Parameters:
  • dist (distribution) – The distribution used to constrain the maxent distributions.

  • k_max (int) – The maximum order to calculate.

Returns:

dists – A list of distributions, where the i`th element is the maxent distribution with the `i-size marginals fixed.

Return type:

list

maxent_dist(dist, rvs, x0=None, maxiter=1000, sparse=True, method='ipf')[source]

Return the maximum entropy distribution consistent with the marginals from dist specified in rvs.

Parameters:
  • dist (Distribution) – The distributions whose marginals should be matched.

  • rvs (list of lists) – The marginals from dist to constrain.

  • x0 (np.ndarray) – Initial condition for the scipy optimizer. Ignored when method is ‘ipf’, which always starts from the uniform distribution.

  • maxiter (int) – The number of optimization iterations to perform. Used only by the scipy optimizer; IPF uses its own convergence tolerance.

  • sparse (bool) – Whether the returned distribution should be sparse or dense.

  • method (str) – The algorithm used to compute the maximum entropy distribution. ‘ipf’ (the default) uses Iterative Proportional Fitting, which is typically far faster than the convex optimizer. IPF converges only linearly on cyclic structures with induced structural zeros, so when it fails to converge within its iteration budget this falls back to the scipy optimizer to preserve accuracy. ‘scipy’ (also accepts ‘slsqp’) forces the scipy convex optimizer.

Returns:

me – The maximum entropy distribution.

Return type:

Distribution

maximal_equivocation(cdists, rtol=None, atol=None, maxiter=100000)[source]

The maximal equivocation of a channel, max_p H[X | Y].

The equivocation is concave in the input. For an input r with output q = rP, its gradient is g_x = -log2 r(x) - D(P_x || q), and the r-average of g is H[X | Y]. So every input certifies H[X | Y] <= max_p H[X | Y] <= max_x g_x, and the iteration r(x) ∝ 2^(-D(P_x || q)), an alternating maximization in the style of Blahut-Arimoto, stops once the two bounds agree to within max(atol, rtol * value) bits. It never decreases the equivocation. Inputs whose output supports overlap are solved together, and separately from the others.

This is the secrecy capacity of a wiretap channel [Wyn75a] whose legitimate receiver sees the input noiselessly and whose eavesdropper sees it through the channel. Unlike commitment_capacity(), it counts redundant inputs.

Parameters:
  • cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().

  • rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].

  • atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].

  • maxiter (int) – Maximum number of iterations. A RuntimeWarning is raised if the bounds have not met by then.

Returns:

  • value (float) – The maximal equivocation, in bits.

  • pmf (np.ndarray) – An input distribution attaining it.

maximize_convex_function(f, A_ineq, b_ineq, A_eq=None, b_eq=None)[source]

Maximize a convex function over a polytope. This function uses the fact that the maximum of a convex function over a polytope will be achieved at one of the extreme points of the polytope.

The maximization is done by taking a system of linear inequalities, using the pypoman library to create a list of extreme points, and then evaluating the objective function on each point.

Parameters:
  • f (function) – Objective function to maximize

  • A_ineq (matrix) – Specifies inequalities matrix, should be num_inequalities x num_variables

  • b_ineq (array) – Specifies inequalities vector, should be num_inequalities long

  • A_eq (matrix) – Specifies equalities matrix, should be num_equalities x num_variables

  • b_eq (array) – Specifies equalities vector, should be num_equalities long

Returns:

  • optimal_extreme_point (np.ndarray) – The extreme point at which the maximum is attained.

  • maximum_function_value (float) – The maximum value of f.

maximum(dist)[source]

Return the largest outcome in the support (per index).

Parameters:

dist (Distribution)

Returns:

maxs

Return type:

ndarray

mean(dist)[source]

Compute the mean (expected value) of a distribution.

Parameters:

dist (Distribution)

Returns:

means – The mean of each index of the outcomes.

Return type:

ndarray

median(dist)[source]

Compute the median of a distribution.

Parameters:

dist (Distribution)

Returns:

medians – The median of each index of the outcomes.

Return type:

ndarray

mflat_design_matrix(alphabets, order)[source]

Build the linear design matrix for the order-order m-flat family.

Columns are indicator features \(1_{x_S = a}\) for every subset \(S\) with \(|S| \le\) order and every assignment a on the corresponding alphabets. Any pmf in \(\mathcal{M}_{\mathrm{order}}\) is then \(q = A\theta\) for some coefficient vector θ (subject to nonnegativity and normalization of q).

Parameters:
  • alphabets (sequence of sequences) – The alphabet of each variable.

  • order (int) – Maximum interaction order kept in the additive pmf expansion.

Returns:

  • A (np.ndarray, shape (n_outcomes, n_features)) – Design matrix over the Cartesian product of alphabets.

  • outcomes (list of tuple) – Row-aligned Cartesian outcomes.

mflat_mprojection_dists(dist, k_max=None, nrestarts=16, maxiter=3000, criterion='reverse_kl', eps=None, eps_schedule=None)[source]

Return the m-flat projection ladder \(Q^{(0)},\ldots,Q^{(k_{\max})}\).

mflat_subsets_from_dependency(dependency, index_map=None)[source]

Downward-closed collection of index-tuples for an antichain dependency.

For a node \(\pi\), the m-flat family is spanned by additive components on every nonempty \(S \subseteq T\) for some block \(T \in \pi\) (plus a constant).

Parameters:
  • dependency (iterable of iterables) – Lattice node: an antichain of variable blocks (names or indices).

  • index_map (dict or None) – Map from block element → integer coordinate index. Defaults to identity.

Returns:

subsets – Sorted index tuples, all nonempty.

Return type:

frozenset of tuple

minimum(dist)[source]

Return the smallest outcome in the support (per index).

Parameters:

dist (Distribution)

Returns:

mins

Return type:

ndarray

mixture_of_products_dists(dist, k_max=None, *, n_init=12, maxiter=200, tol=1e-10, rng=0, early_stop=True, kl_tol=1e-08)[source]

Fit the mixture-of-products ladder \(Q^{(1)},\ldots,Q^{(k_{\max})}\).

Parameters:
Returns:

  • dists (list of Distribution) – dists[k-1] is the MLE in \(\mathcal{F}_k\).

  • meta (list of dict) – Per-k diagnostics (I_xv, H_v, loglik, pi, conds).

mode(dist)[source]

Compute the modes of a distribution.

Parameters:

dist (Distribution)

Returns:

modes – A list of arrays, one for each index of the outcomes. Each array contains the modes of that index.

Return type:

list of ndarray

mss(dist, rvs, about=None, int_outcomes=True)[source]
Parameters:
  • dist (Distribution) – The distribution which defines the base sigma-algebra.

  • rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.

  • about (list) – A list of random variables for which the minimal sufficient static will retain all information about.

  • int_outcomes (bool) – If True, then the outcomes of the minimal sufficient statistic are relabeled as integers instead of as the atoms of the induced sigma-algebra.

Returns:

d – The distribution of the minimal sufficient statistic.

Return type:

Distribution

Examples

>>> d = Xor()
>>> print(mss(d, [0], [1, 2]))
Class:    Distribution
Alphabet: (0, 1)
Base:     linear
x   p(x)
0   0.5
1   0.5
mss_sigalg(dist, rvs, about=None)[source]

Construct the sigma algebra for the minimal sufficient statistic of rvs about about.

Parameters:
  • dist (Distribution) – The distribution which defines the base sigma-algebra.

  • rvs (list) – A list of random variables to be compressed into a minimal sufficient statistic.

  • about (list) – A list of random variables for which the minimal sufficient static will retain all information about.

Returns:

mss_sa – The induced sigma-algebra of the minimal sufficient statistic.

Return type:

frozenset of frozensets

Examples

>>> d = Xor()
>>> mss_sigalg(d, [0], [1, 2])
frozenset({frozenset(),
           frozenset({'000', '011'}),
           frozenset({'101', '110'}),
           frozenset({'000', '011', '101', '110'})})
nonredundant_inputs(cdists, atol=1e-09)[source]

The inputs of the non-redundant version of a channel [WNI03].

An input is redundant when its output distribution is a convex combination of the other inputs’ output distributions, since it can then be simulated by randomizing over them. Removing every redundant input leaves one input for each vertex of the convex hull of the output distributions. Of several inputs with the same output distribution, the first is kept.

Each input is tested with a linear program for the l1 distance from its output distribution to the convex hull of the others’, from the last input to the first and against the inputs still present.

Parameters:
  • cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().

  • atol (float) – An input counts as redundant when its output distribution is within this l1 distance of the convex hull of the others’.

Returns:

inputs – The indices of the remaining inputs, in increasing order.

Return type:

np.ndarray

parallel_sweep(func, items, *, base_seed=None)[source]

Run func(item, rng) for each item in items, in parallel when safe.

Each task gets its own numpy.random.Generator seeded deterministically (from base_seed, or a single draw from the global np.random state when base_seed is None) so that workers never race the global RNG and results are reproducible with respect to a seeded np.random. The serial and parallel paths consume the same per-task generators, so a sweep produces identical results regardless of DIT_OPT_JOBS.

Results are returned in input order, so max / min / append over them stay deterministic.

Parameters:
  • func (callable) – Called as func(item, rng) where rng is a Generator.

  • items (iterable) – The independent work items.

  • base_seed (int, np.random.Generator, None) – Seed offset for the per-task generators. A Generator contributes one draw; if None, a seed is drawn once (serially) from the global np.random state.

Returns:

results – [func(item, rng) for item in items] in input order.

Return type:

list

percentile(dist, p)[source]

Compute the p-th percentile (0 <= p <= 100).

Equivalent to quantile(dist, p / 100).

Parameters:
Returns:

result

Return type:

ndarray

pruned_samplespace(d, sample_space=None)[source]

Returns a new distribution with pruned sample space.

The pruning is such that zero probability outcomes are removed.

Parameters:
  • d (distribution) – The distribution used to create the pruned distribution.

  • sample_space (set) – A list of outcomes with zero probability that should be kept in the sample space. If None, then all outcomes with zero probability will be removed.

Returns:

pd – The distribution with a pruned sample space.

Return type:

distribution

quantile(dist, q)[source]

Compute the q-quantile of a distribution (0 <= q <= 1).

Uses the “lower” interpolation method: returns the largest outcome x such that P(X <= x) <= q, averaging with the next outcome when P(X <= x) == q exactly (matching median() behaviour).

For multi-dimensional distributions, operates on the marginal of each index independently.

Parameters:
Returns:

quantiles

Return type:

ndarray

range_(dist)[source]

Compute the range (maximum - minimum) of the support per index.

(Named range_ to avoid shadowing the built-in range.)

Parameters:

dist (Distribution)

Returns:

r

Return type:

ndarray

sibson_capacity(cdists, order, rtol=None, atol=None, maxiter=100000)[source]

Sibson’s capacity of order alpha, C_alpha = max_p I_alpha(X : Y).

Sibson’s alpha-mutual information is

I_alpha(X : Y) = alpha / (alpha - 1) log2 sum_y (sum_x p(x) P(y|x)^alpha)^(1/alpha),

and its maximum over inputs equals the Rényi radius min_q max_x D_alpha(P_x || q) [Csiszar95]. Every input r therefore gives the bounds I_alpha(r) <= C_alpha <= max_x D_alpha(P_x || q_r), where q_r is Sibson’s optimal output for r. The iteration r <- r exp(mu D_alpha(P_x || q_r)) with mu = max(1, alpha) reduces to Blahut-Arimoto at alpha = 1; the step is halved whenever I_alpha would decrease, and the iteration stops once the bounds meet.

Parameters:
  • cdists (list, ndarray, Distribution) – The channel, in any form accepted by channel_capacity().

  • order (float) – The order alpha > 0. 1 gives the Shannon capacity and numpy.inf the maximal leakage capacity log2 sum_y max_x P(y|x).

  • rtol (float or None) – Relative tolerance. Defaults to ditParams[‘rtol’].

  • atol (float or None) – Absolute tolerance in bits. Defaults to ditParams[‘atol’].

  • maxiter (int) – Maximum number of iterations.

Returns:

  • cc (float) – The capacity of order alpha, in bits.

  • pmf (np.ndarray) – An optimal input distribution.

skewness(dist)[source]

Compute the skewness (3rd standardised moment).

Measures asymmetry of the distribution. Zero for symmetric distributions, positive for right-skewed, negative for left-skewed.

Parameters:

dist (Distribution)

Returns:

skew

Return type:

ndarray

spectral_entanglement_bound(dist, rvs=None, crvs=None)[source]

The nominal spectral lower bound on the entanglement.

Matveev & Romashchenko [MR26b] bound the entanglement of a pair uniform on its support from below by

\[E(X, Y) \geq \min\{ I[X{:}Y],\ 2\log(\lambda_1 / \lambda_2) \} - O(\log H[XY]),\]

which is what certifies that expander-like supports are maximally non-extractable. This function returns the nominal term min{I, 2 log(lambda_1 / lambda_2)} only.

Warning

The suppressed O(log H[XY]) slop is not a formality; it dominates at small alphabets. The uniform distribution on an 8-cycle has entanglement about 0.67 bits against a nominal bound of 1.00. Use this to compare pairs or to reason asymptotically, never as a pointwise certificate.

Parameters:
  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two variables. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on.

Returns:

bound – The nominal bound, in bits. Infinite spectral gap (a support with only one nonzero singular value, i.e. a complete bipartite graph on each component) returns the mutual information.

Return type:

float

standard_deviation(dist)[source]

Compute the standard deviation sqrt(Var(X)).

Parameters:

dist (Distribution)

Returns:

std

Return type:

ndarray

standard_moment(dist, n)[source]

Compute the n-th standardised moment E[((X - mu)/sigma)^n].

Parameters:
Returns:

moments

Return type:

ndarray

support_biadjacency(dist, rvs=None, crvs=None)[source]

The 0/1 biadjacency matrix of the support graph of a pair.

Parameters:
  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two variables. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on. Conditioning variables are folded into both sides, so the support graph is that of the coalesced pair.

Returns:

matrix – The 0/1 matrix, with a one wherever the pair has positive probability.

Return type:

np.ndarray

support_singular_values(dist, rvs=None, crvs=None)[source]

The singular values of the support graph’s biadjacency matrix.

Parameters:
  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two variables. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on.

Returns:

sigmas – The singular values, in decreasing order.

Return type:

np.ndarray

Examples

The Fano plane’s point-line incidence graph is biregular of degree three, so its top singular value is three:

>>> import numpy as np
>>> from dit import Distribution
>>> lines = ['012', '034', '056', '136', '145', '235', '246']
>>> outcomes = [(str(p), str(i)) for i, line in enumerate(lines) for p in line]
>>> fano = Distribution(outcomes, [1 / 21] * 21)
>>> float(np.round(support_singular_values(fano)[0], 10))
3.0
symmetric_smooth(dist, eps)[source]

Symmetric full-support smoothing \(P_\varepsilon = (1-\varepsilon)P + \varepsilon U\).

Here \(U\) is uniform on the Cartesian product of the alphabets. This preserves permutation symmetries of dist (e.g. W).

Parameters:
  • dist (Distribution)

  • eps (float) – Mixture weight on the uniform. Must satisfy 0 <= eps < 1. eps=0 returns a dense copy of dist (still sparse if dist is).

Returns:

smoothed – Dense linear distribution on the Cartesian sample space.

Return type:

Distribution

variance(dist)[source]

Compute the variance Var(X) = E[(X - mu)^2].

Parameters:

dist (Distribution)

Returns:

var – The variance of each index of the outcomes.

Return type:

ndarray