Mallows and generalized Mallows model for matchings (Q1740522)

This paper studies the Mallows model, which is an exponential model depending on the definition of a distance for permutations. It is specified by the location parameter \(\sigma_0\) and a dispersion parameter \(\theta\). The generalized Mallows model uses \(k\) spread parameters \(\theta_j\), each affecting a particular position of the permutation. For both Mallows model and the generalized version under the Hamming distance, the paper proposes efficient sampling and learning methods. Expressions for the computation of the partition function of the models, the expectation, the marginal and conditional probabilities are derived. As for the learning process, it is shown the way to estimate the parameters of a sample from a Mallows model in polynomial time. The paper proposes an efficient learning algorithm and shows that the estimated parameters are asymptotically unbiased estimators of the real ones. Numerical examples are provided to illustrate the theoretical results.