Expected length of a product of random reflections

Sjöstrand, Jonas

doi:10.1090/S0002-9939-2012-11283-3

Expected length of a product of random reflections
HTML articles powered by AMS MathViewer

by Jonas Sjöstrand PDF

Proc. Amer. Math. Soc. 140 (2012), 4369-4380 Request permission

Abstract:

We present a simple formula for the expected number of inversions in a permutation of size $n$ obtained by applying $t$ random (not necessarily adjacent) transpositions to the identity permutation. More generally, for any finite irreducible Coxeter group belonging to one of the infinite families (type A, B, D, and I), an exact expression is obtained for the expected length of a product of $t$ random reflections.

References

Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
Mireille Bousquet-Mélou, The expected number of inversions after $n$ adjacent transpositions, Discrete Math. Theor. Comput. Sci. 12 (2010), no. 2, 65–88. MR 2676666
Niklas Eriksen, Expected number of inversions after a sequence of random adjacent transpositions—an exact expression, Discrete Math. 298 (2005), no. 1-3, 155–168. MR 2163446, DOI 10.1016/j.disc.2004.09.015
Niklas Eriksen and Axel Hultman, Estimating the expected reversal distance after a fixed number of reversals, Adv. in Appl. Math. 32 (2004), no. 3, 439–453. MR 2041958, DOI 10.1016/S0196-8858(03)00054-X
Niklas Eriksen and Axel Hultman, Expected reflection distance in $G(r,1,n)$ after a fixed number of reflections, Ann. Comb. 9 (2005), no. 1, 21–33. MR 2135773, DOI 10.1007/s00026-005-0238-y
Henrik Eriksson, Kimmo Eriksson, and Jonas Sjöstrand, Expected number of inversions after a sequence of random adjacent transpositions, Formal power series and algebraic combinatorics (Moscow, 2000) Springer, Berlin, 2000, pp. 677–685. MR 1798262
Andreas Jönsson, Evolutionary fixed point distance problems, master’s thesis, University of Gothenburg, 2009.
Emma Troili, Förväntade avstånd i Coxetergrupper [Expected distances in Coxeter groups], master’s thesis, KTH, 2002, in Swedish.