The expected number of inversions after n adjacent transpositionsArticleAuthors: Mireille Bousquet-Mélou

0000-0002-2863-8300
Mireille Bousquet-Mélou
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.
Volume: Vol. 12 no. 2
Published on: August 31, 2009
Imported on: March 26, 2015
Keywords: 05A05, 05A15, 05A16, 60J10, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], [en] Permutations, Markov chains, inversions