Random adjacent transposition shuffle

ID: random-adjacent-transposition-shuffle

On the symmetric group , this Markov chain chooses uniformly from the identity and the adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities to existing neighbours.

New to topics? Read the docs here!