< List of probability distributions
The Mallows distribution, or Mallows model, is an exponential probability distribution over permutations, based on distances. Introduced in the mid-1950s by Mallows [1], it is perhaps the most popular member of the distance-based ranking models.
The distribution can be viewed as like a normal distribution for permutations: given a center permutation with the highest probability value (π0) and a parameter for spread (θ,) the model defines a distribution for all permutations [2].
Mallows distribution properties
The Mallows distribution is a probability distribution that satisfies, for all rankings π ∈ 𝕊n:
Rankings π0 and θ ≥ 0 are the model parameters, φ (0) is a normalizing constant [3]. The variable d is the distance in 𝕊n, which can be one of many distances including those defined by Kendall, Cayley, or Spearman [4]. However, the most popular method for defining distance is Kendall–Tau, which is the number of pairwise disagreements between any two rankings.
If θ = 0, a uniform distribution is obtained; for θ = +∞, Mallows model assigns probabilities equal to 1 to π0 and zero for the remaining permutations [5].
Key challenges in using the Mallows distribution are the exponential support size and the absence of a closed-form expression for choice probabilities [6].
References
[1] Mallows CL (1957) Non-null ranking models. Biometrika 44(1):
114–130.
[2] Chierichetti et. al. Mallows Models for Top-k Lists
[3] Recent Trends in Applied Artificial Intelligence. 26th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2013, Amsterdam, The Netherlands, June 17-21, 2013, Proceedings. p. 104.
[4] Fligner & Verducci. Distance based ranking models. Journal of the Royal Statistical Society 48(3), 359-369 (1986).
[5] Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 15th European Conference, ECSQARU 2019, Belgrade, Serbia, September 18-20, 2019, Proceedings. p. 353.
[6] Desir et. al. Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice. OPERATIONS RESEARCH. Vol. 69, No. 4, July–August 2021 pp. 1206–1227.