Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general $p$-shifted distributions

DOI10.1214/22-EJP812arXiv2008.07215MaRDI QIDQ6347209

Ross G. Pinsky

Publication date: 17 August 2020

Abstract: Let $A_{l;k}^{(n)}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 probability measure $P_n$ on $S_n$, one has $P_n(A_{l;k}^{(n)})simfracl!n^{l-1}$ as $noinfty$. In one part of this paper we consider the probability of clustering of consecutive numbers under Mallows distributions $P_n^q$, $q>0$. Because of a duality, it suffices to consider $qin(0,1)$. We show that for $q_n=1-fracc{n}^{a}lpha$, with $c>0$ and $alphain(0,1)$, $P_n^q(A_{l;k_n}^{(n)})$ is on the order $frac1n^{alpha(l-1)}$, uniformly over all sequences ${k_n}_{n=1}^{i}nfty$. Thus, letting $N_l^{(n)}=su{m}_{k=1}^{n-l+1}{1}_{A_{l;k}^{(n)}}$ denote the number of sets of $l$ consecutive numbers appearing in sets of consecutive positions, we have �egin{equation*} lim_{n oinfty} E_n^{q_n}N^{(n)}_l = �egin{cases}infty, ext{if} l<frac{1+alpha}alpha;\ 0, ext{if} l>frac{1+alpha}alpha. end{cases}. end{equation*} We also consider the cases $alpha=1$ and $alpha>1$. In the other part of the paper we consider general $p$-shifted distributions, of which the Mallows distribution is a particular case. We calculate explicitly the quantity $li{m}_{loinfty}limin{f}_{noinfty}{P}_n^q(A_{l;k_n}^{(n)})=li{m}_{loinfty}limsu{p}_{noinfty}{P}_n^q(A_{l;k_n}^{(n)})$ in terms of the $p$-distribution. When this quantity is positive, we say that super-clustering occurs. In particular, super-clustering occurs for the Mallows distribution with parameter $qeq1$. We also give a new characterization of $p$-shifted distributions.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

This page was built for publication: Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general $p$-shifted distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347209)