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

dmtcs:478 - Discrete Mathematics & Theoretical Computer Science, August 31, 2009, Vol. 12 no. 2 - https://doi.org/10.46298/dmtcs.478
The expected number of inversions after n adjacent transpositionsArticle

Authors: Mireille Bousquet-Mélou ORCID

    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: Permutations,Markov chains,inversions,05A05, 05A15, 05A16, 60J10,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[MATH.MATH-PR] Mathematics [math]/Probability [math.PR]

    Consultation statistics

    This page has been seen 268 times.
    This article's PDF has been downloaded 292 times.