mixle.stats.rankings.mallows module

Create, estimate, and sample from a Mallows distribution over permutations (Kendall’s tau).

Defines the MallowsDistribution, MallowsEnumerator, MallowsSampler, MallowsAccumulatorFactory, MallowsAccumulator, MallowsEstimator, and the MallowsDataEncoder classes for use with mixle.

Data type: List[int] (a full ranking/ordering of n items, given as a permutation of 0,…,n-1 where x[r] is the item placed at rank r, best first).

The Mallows model concentrates probability around a central permutation sigma0 with a dispersion theta >= 0:

p(sigma) = exp(-theta * d(sigma, sigma0)) / Z(theta),

where d is the Kendall tau distance (the number of discordant item pairs) and the normalizer has the closed form Z(theta) = prod_{i=1}^{n-1} (1 - phi^{i+1}) / (1 - phi) with phi = exp(-theta) (and Z = n! at theta = 0, the uniform distribution). Larger theta concentrates mass on sigma0.

Sampling uses the Repeated Insertion Model: the central items are inserted one at a time, each jumping back a geometric number of places, which produces an exact Mallows draw in O(n^2). Estimation recovers the central permutation by Copeland/Borda aggregation of the pairwise-precedence counts (the sufficient statistic) and fits theta by matching the mean Kendall distance to its closed-form expectation.

class MallowsDistribution(sigma0, theta=1.0, name=None, keys=None)[source]

Bases: SequenceEncodableProbabilityDistribution

Mallows distribution over permutations of 0,…,n-1 with central permutation sigma0 and dispersion theta.

Data type: List[int] (an ordering: a permutation of 0,…,n-1, best-ranked item first).

Parameters:
classmethod compute_capabilities()[source]
kendall_distance(x)[source]

Return the Kendall tau distance between ordering x and the central permutation.

Parameters:

x (Sequence[int])

Return type:

int

density(x)[source]

Return the probability of an ordering x.

Parameters:

x (Sequence[int])

Return type:

float

log_density(x)[source]

Return the log-probability of an ordering x (a permutation of 0,…,n-1).

Parameters:

x (Sequence[int])

Return type:

float

seq_log_density(x)[source]

Return vectorized log-probabilities for an (N, n) array of orderings.

Parameters:

x (ndarray)

Return type:

ndarray

sampler(seed=None)[source]

Return a sampler for drawing orderings from this distribution.

Parameters:

seed (int | None)

Return type:

MallowsSampler

enumerator()[source]

Return an exact finite enumerator over all orderings in decreasing probability order.

Return type:

MallowsEnumerator

estimator(pseudo_count=None)[source]

Return an estimator that keeps the item count fixed at this distribution’s n.

Parameters:

pseudo_count (float | None)

Return type:

MallowsEstimator

dist_to_encoder()[source]

Return the data encoder used by this distribution for vectorized methods.

Return type:

MallowsDataEncoder

class MallowsEnumerator(dist)[source]

Bases: DistributionEnumerator

Enumerate Mallows orderings in descending probability order, lazily.

Kendall distance is separable in the Lehmer code: an ordering’s distance is the sum of digits L_i in {0,...,n-1-i} (inversions contributed at each rank), each weighted -theta*L_i. So the support is a product over the digits and ProductEnumerator streams it in increasing distance (descending probability) without materializing the n! permutations; each digit tuple decodes (factorial number system) to a permutation of the identity, relabeled through the central permutation sigma0.

Parameters:

dist (MallowsDistribution)

class MallowsSampler(dist, seed=None)[source]

Bases: DistributionSampler

Draw iid Mallows orderings via the Repeated Insertion Model.

Parameters:

  • dist (MallowsDistribution)

  • seed (int | None)

sample(size=None)[source]

Draw orderings (permutations of 0,…,n-1); a single list when size is None.

Parameters:

size (int | None)

Return type:

list[int] | list[list[int]]

class MallowsAccumulator(dim, keys=None)[source]

Bases: SequenceEncodableStatisticAccumulator

Accumulate the weighted pairwise-precedence matrix for Mallows estimation.

precede[a, b] is the weighted number of orderings in which item a is ranked before item b; this is the sufficient statistic for both the central permutation (via Copeland scores) and the mean Kendall distance.

Parameters:
update(x, weight, estimate)[source]
Parameters:
Return type:

None

initialize(x, weight, rng)[source]
Parameters:
Return type:

None

seq_update(x, weights, estimate)[source]
Parameters:
Return type:

None

seq_initialize(x, weights, rng)[source]
Parameters:
Return type:

None

combine(suff_stat)[source]
Parameters:

suff_stat (tuple[float, ndarray])

Return type:

MallowsAccumulator

value()[source]
Return type:

tuple[float, ndarray]

from_value(x)[source]
Parameters:

x (tuple[float, ndarray])

Return type:

MallowsAccumulator

key_merge(stats_dict)[source]

Pool this accumulator’s statistics into stats_dict under its merge key.

The structural default implements the common single-key pattern: store the accumulator under self.keys the first time the key is seen, else combine into the one already there. Accumulators with several named keys (e.g. an HMM’s init/trans/state keys) or a non-accumulator stats payload override this. A keys of None (the default) is a no-op.

Parameters:

stats_dict (dict[str, Any])

Return type:

None

key_replace(stats_dict)[source]

Replace this accumulator’s statistics from the pooled stats_dict entry (see key_merge).

Parameters:

stats_dict (dict[str, Any])

Return type:

None

acc_to_encoder()[source]
Return type:

MallowsDataEncoder

class MallowsAccumulatorFactory(dim, keys=None)[source]

Bases: StatisticAccumulatorFactory

Factory for MallowsAccumulator.

Parameters:
make()[source]
Return type:

MallowsAccumulator

class MallowsEstimator(dim, theta=None, name=None, keys=None)[source]

Bases: ParameterEstimator

Estimator for the Mallows central permutation (Copeland aggregation) and dispersion theta.

Parameters:
accumulator_factory()[source]
Return type:

MallowsAccumulatorFactory

estimate(nobs, suff_stat)[source]
Parameters:
Return type:

MallowsDistribution

class MallowsDataEncoder(dim=None)[source]

Bases: DataSequenceEncoder

Encode a sequence of orderings (permutations of 0,…,n-1) into an (N, n) integer array.

Parameters:

dim (int | None)

seq_encode(x)[source]

Encode the iid observation sequence x for vectorized evaluation.

Parameters:

x (Sequence[Sequence[int]])

Return type:

ndarray