Bousquet-Mélou, Mireille - The expected number of inversions after n adjacent transpositions

dmtcs:478 - Discrete Mathematics & Theoretical Computer Science, August 31, 2009, Vol. 12 no. 2
The expected number of inversions after n adjacent transpositions

Authors: Bousquet-Mélou, Mireille

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.


Source : oai:HAL:hal-00412143v1
Volume: Vol. 12 no. 2
Published on: August 31, 2009
Submitted on: March 26, 2015
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]


Share

Consultation statistics

This page has been seen 35 times.
This article's PDF has been downloaded 147 times.