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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript n"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">S_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , yielding a locally adaptive and reversible Markov chain Monte Carlo method for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper M normal a normal l normal l normal o normal w normal s left-parenthesis d comma sigma 0 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">M</mml:mi> <mml:mi mathvariant="normal">a</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">w</mml:mi> <mml:mi mathvariant="normal">s</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>,</mml:mo> <mml:msub> <mml:mi> σ </mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {Mallows}(d,\sigma _0)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Here <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d colon upper S Subscript n Baseline times upper S Subscript n Baseline right-arrow left-bracket 0 comma normal infinity right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo> × </mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo stretchy="false"> → </mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">d:S_n\times S_n\to [0,\infty )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is any fixed distance on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript n"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">S_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma 0 element-of upper S Subscript n"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi> σ </mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo> ∈ </mml:mo> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\sigma _0\in S_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a fixed reference permutation, and the target distribution on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S Subscript n"> <mml:semantics> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">S_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has mass function <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="pi left-parenthesis sigma right-parenthesis proportional-to e Superscript minus beta d left-parenthesis sigma comma sigma 0 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> π </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> σ </mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ∝ </mml:mo> <mml:msup> <mml:mi>e</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mi> β </mml:mi> <mml:mi>d</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> σ </mml:mi> <mml:mo>,</mml:mo> <mml:msub> <mml:mi> σ </mml:mi> <mml:mn>0</mml:mn> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">\pi (\sigma )\propto e^{-\beta d(\sigma ,\sigma _0)}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="beta greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi> β </mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\beta &gt;0</mml:annotation> </mml:semantics> </mml:math> </inline-formula>