From continuous to discrete: A No-U-Turn Sampler for permutations

We introduce a discrete-space analogue of the No-U-Turn Sampler on the symmetric group S n S_n , yielding a locally adaptive and reversible Markov chain Monte Carlo method for M a l l o w s ( d , σ 0 ) Mallows(d,σ _0) . Here d : S n × S n → [ 0 , ∞ ) d:S_n× S_n→ [0,∞ ) is any fixed distance on S n S_n , σ 0 ∈ S n σ _0∈ S_n is a fixed reference permutation, and the target distribution on S n S_n has mass function π ( σ ) ∝ e − β d ( σ , σ 0 ) π (σ )∝ e-β d(σ ,σ _0) where β > 0 β >0