Large deviations for permutations avoiding monotone patterns (Q504968)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Large deviations for permutations avoiding monotone patterns |
scientific article |
Statements
Large deviations for permutations avoiding monotone patterns (English)
0 references
18 January 2017
0 references
Summary: For a given permutation \(\tau\), let \(P_N^{\tau}\) be the uniform probability distribution on the set of \(N\)-element permutations \(\sigma\) that avoid the pattern \(\tau\). For \(\tau=\mu_k:=123\ldots k\), we consider \(P_N^{\mu_{k}}\) \((\sigma_I=J)\) where \(I\sim\gamma N\) and \(J\sim\delta N\) for \(\gamma, \delta \in (0,1)\). If \(\gamma+ \delta \neq 1\), then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of \(P_N^{\mu_{k}}(\sigma_I=J)^{1/N}\). We also observe that for \(\tau = \lambda_{k,\ell} := 12\ldots\ell k(k-1)\ldots(\ell+1)\) and \(\gamma+\delta<1\), the limit of \(P_N^{\tau}(\sigma_I=J)^{1/N}\) is the same as for \(\tau=\mu_k\).
0 references
random permutation
0 references
monotone pattern-avoiding permutation
0 references
left-to-right minimum
0 references
large deviations
0 references