Abstract
Sampling permutations from S_n is a fundamental problem from probability
theory. The nearest neighbor transposition chain \cal{M}}_{nn} is known to
converge in time \Theta(n^3 \log n) in the uniform case and time \Theta(n^2) in
the constant bias case, in which we put adjacent elements in order with
probability p \neq 1/2 and out of order with probability 1-p. Here we consider
the variable bias case where we put adjacent elements x<y in order with
probability p{x,y} and out of order with probability 1-p_{x,y}. The problem of
bounding the mixing rate of M_{nn} was posed by Fill and was motivated by the
Move-Ahead-One self-organizing list update algorithm. It was conjectured that
the chain would always be rapidly mixing if 1/2 \leq p_{x,y} \leq 1 for all x <
y, but this was only known in the case of constant bias or when p_{x,y} is
equal to 1/2 or 1, a case that corresponds to sampling linear extensions of a
partial order. We prove the chain is rapidly mixing for two classes: "Choose
Your Weapon," where we are given r_1,..., r_{n-1} with r_i \geq 1/2 and
p_{x,y}=r_x for all x<y (so the dominant player chooses the game, thus fixing
his or her probability of winning), and "League Hierarchies," where there are
two leagues and players from the A-league have a fixed probability of beating
players from the B-league, players within each league are similarly divided
into sub-leagues with a possibly different fixed probability, and so forth
recursively. Both of these classes include permutations with constant bias as a
special case. Moreover, we also prove that the most general conjecture is false
by constructing a counterexample where 1/2 \leq p_{x,y} \leq 1 for all x< y,
but for which the nearest neighbor transposition chain requires exponential
time to converge.