Random Subwords and Pipe Dreams

Abstract

Fix a probability $p\in (0,1)$. Let $s_i$ denote the transposition in the symmetric group ${\mathfrak{S}}_n$ that swaps $i$ and $i+1$. Given a word $\mathsf{w}$ over the alphabet $\{s_1,\dots ,s_{n-1}\}$, we can generate a random subword by independently deleting each letter of $\mathsf{w}$ with probability $1-p$. For a large class of starting words $\mathsf{w}$ -- including all alternating reduced words for the decreasing permutation -- we compute precise asymptotics (as $n\to \infty$) for the expected number of inversions of the permutation represented by the random subword. This result can also be seen as an asymptotic formula for the expected number of inversions of a permutation represented by a certain random (non-reduced) pipe dream. In the special case when $\mathsf{w}$ is the word $(s_{n-1})(s_{n-2}{s}_{n-1})\cdots (s_1{s}_2\cdots s_{n-1})$, we find that the expected number of inversions of the permutation represented by the random subword is asymptotically equal to \[\frac{2\sqrt{2}}{3\sqrtπ}\sqrt{\frac{p}{1-p}}\,n^{3/2};\] this settles a conjecture of Morales, Panova, Petrov, and Yeliussizov.

19 pages; 3 figures