The expected number of inversions after n adjacent transpositions

2009/09/01 by Mireille Bousquet‐Mélou, Bousquet-Mélou, Mireille · 1 citation
Computer Science · Mathematics · #05A05 #05A15 #05A16 #60J10 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · doi:10.48550/arxiv.0909.0103

openalex publication_date 2009/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Random braids and random walks on finite groups

Related

• Expected length of a product of random reflections
• The inversion statistic in derangements and in other permutations with a prescribed number of fixed points
• Exact formula and asymptotic behavior for the expected number of inversions in a random permutation avoiding a pattern of length three
• Random Subwords and Pipe Dreams
• Thresholds for patterns in random permutations with a given number of inversions