Clustering of consecutive numbers in permutations under a Mallows distribution

Abstract

Let \(A^{(n)}_{l;k}\subset S_n\) denote the set of permutations of \([n]\) for which the set of \(l\) consecutive numbers \(\{k, k+1,\cdots, k+l-1\}\) appears in a set of consecutive positions. Under the uniformly random measure \(P_n\) on \(S_n\), one has \(P_n(A^{(n)}_{l;k})\sim\frac{l!}{n^{l-1}}\) as \(n\to\infty\). In this paper we consider the probability of the clustering of consecutive numbers under Mallows distributions \(P_n^q\), \(q>0\). Because of a duality, it suffices to consider \(q\in(0,1)\). In particular, we show that for fixed \(q\), \(\lim_{l\to\infty}\lim_{n\to\infty}P_n^q(A^{(n)}_{l;k_n})=\big(\prod_{i=1}^\infty(1-q^i)\big)^2,\ \text{if}\ \lim_{n\to\infty}\min(k_n,n-k_n)=\infty\), and that for \(q_n=1-\frac c{n^\alpha}\), with \(c>0\) and \(\alpha\in(0,1)\), \(P_n^q(A^{(n)}_{l;k_n})\) is on the order \(\frac1{n^{\alpha(l-1)}}\), uniformly over all sequences \(\{k_n\}_{n=1}^\infty\). Thus, letting \(N^{(n)}_l=\sum_{k=1}^{n-l+1}1_{A^{(n)}_{l;k}}\) denote the number of sets of \(l\) consecutive numbers appearing in sets of consecutive positions, we have \begin{equation*} \lim_{n\to\infty}E_n^{q_n}N^{(n)}_l=\begin{cases}\infty,\ \text{if}\ l<\frac{1+\alpha}\alpha;\\ 0,\ \text{if} \ l>\frac{1+\alpha}\alpha. \end{cases}. \end{equation*}