Closed-Form Expressions for the Normalizing Constants of the Mallows Model and Weighted Mallows Model on Combinatorial Domains

This paper expands the Mallows model for use in combinatorial domains. The Mallows model is a popular distribution used to sample permutations around a central tendency but requires a unique normalizing constant for each distance metric used in order to be computationally efficient. In this paper, closed-form expressions for the Mallows model normalizing constant are derived for the Hamming distance, symmetric difference, and the similarity coefficient in combinatorial domains. Additionally, closed-form expressions are derived for the normalizing constant of the weighted Mallows model in combinatorial domains. The weighted Mallows model increases the versatility of the Mallows model by allowing granular control over likelihoods of individual components in the domain. The derivation of the closed-form expression results in a reduction of the order of calculations required to calculate probabilities from exponential to constant.