The expected number of inversions after n adjacent transpositions

Abstract

We give a new expression for the expected number of inversions in the product of n random adjacent transpositions in the symmetric group S_{m+1}. We then derive from this expression the asymptotic behaviour of this number when n scales with m in various ways. Our starting point is an equivalence, due to Eriksson et al., with a problem of weighted walks confined to a triangular area of the plane.

Keywords

• permutations
• markov chains
• inversions
• 05a05, 05a15, 05a16, 60j10
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [math.math-pr] mathematics [math]/probability [math.pr]