mixle.stats.rankings.mallows module

Mallows ranking distributions over permutations using Kendall tau distance.

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)

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:

• sigma0 (Sequence[int] | ndarray)

• theta (float)

• name (str | None)

• keys (str | None)

classmethod compute_capabilities()

Return compute-backend metadata for the Mallows distribution.

kendall_distance(x)

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

Parameters:

x (Sequence[int])

Return type:

int

density(x)

Return the probability of an ordering x.

Parameters:

x (Sequence[int])

Return type:

float

log_density(x)

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)

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

Parameters:

x (ndarray)

Return type:

ndarray

sampler(seed=None)

Return a sampler for drawing orderings from this distribution.

Parameters:

seed (int | None)

Return type:

MallowsSampler

enumerator()

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

Return type:

MallowsEnumerator

estimator(pseudo_count=None)

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()

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

Return type:

MallowsDataEncoder

class MallowsEnumerator(dist)

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)

Bases: DistributionSampler

Draw iid Mallows orderings via the Repeated Insertion Model.

Parameters:

• dist (MallowsDistribution)

• seed (int | None)

sample(size=None)

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)

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:

• dim (int)

• keys (str | None)

update(x, weight, estimate)

Accumulate weighted pairwise-precedence counts for one ordering.

Parameters:

• x (Sequence[int])

• weight (float)

• estimate (MallowsDistribution | None)

Return type:

None

initialize(x, weight, rng)

Initialize the sufficient statistics with one weighted ordering.

Parameters:

• x (Sequence[int])

• weight (float)

• rng (RandomState | None)

Return type:

None

seq_update(x, weights, estimate)

Accumulate weighted pairwise-precedence counts for encoded orderings.

Parameters:

• x (ndarray)

• weights (ndarray)

• estimate (MallowsDistribution | None)

Return type:

None

seq_initialize(x, weights, rng)

Initialize the sufficient statistics from encoded orderings.

Parameters:

• x (ndarray)

• weights (ndarray)

• rng (RandomState | None)

Return type:

None

combine(suff_stat)

Merge serialized precedence-count statistics into this accumulator.

Parameters:

suff_stat (tuple[float, ndarray])

Return type:

MallowsAccumulator

value()

Return the accumulated weight and pairwise-precedence matrix.

Return type:

tuple[float, ndarray]

from_value(x)

Restore the accumulator from serialized precedence-count statistics.

Parameters:

x (tuple[float, ndarray])

Return type:

MallowsAccumulator

key_merge(stats_dict)

Merge this accumulator into a keyed statistics dictionary.

Parameters:

stats_dict (dict[str, Any])

Return type:

None

key_replace(stats_dict)

Replace this accumulator from a keyed statistics dictionary.

Parameters:

stats_dict (dict[str, Any])

Return type:

None

acc_to_encoder()

Return an encoder compatible with the accumulated ordering dimension.

Return type:

MallowsDataEncoder

class MallowsAccumulatorFactory(dim, keys=None)

Bases: StatisticAccumulatorFactory

Factory for MallowsAccumulator.

Parameters:

• dim (int)

• keys (str | None)

make()

Create an empty Mallows accumulator.

Return type:

MallowsAccumulator

class MallowsEstimator(dim, theta=None, name=None, keys=None)

Bases: ParameterEstimator

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

Parameters:

• dim (int)

• theta (float | None)

• name (str | None)

• keys (str | None)

accumulator_factory()

Return a factory for Mallows sufficient-statistic accumulators.

Return type:

MallowsAccumulatorFactory

estimate(nobs, suff_stat)

Estimate the central permutation and dispersion from precedence counts.

Parameters:

• nobs (float | None)

• suff_stat (tuple[float, ndarray])

Return type:

MallowsDistribution

class MallowsDataEncoder(dim=None)

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)

Validate and encode orderings as a two-dimensional integer array.

Parameters:

x (Sequence[Sequence[int]])

Return type:

ndarray