The probability of avoiding consecutive patterns in the Mallows distribution

DOI10.1002/RSA.20776MaRDI QIDQ4961544zbMATH OpenOpenAlexFDO

Authors Harry Crane, Stephen DeSalvo, Sergi Elizalde

Publication date 25 October 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01370

zbMATH Keywords

consecutive patterninversionMallows distributionpermutationStein's method

Mathematics Subject Classification ID

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

Abstract: We use various combinatorial and probabilistic techniques to study growth rates for the probability that a random permutation from the Mallows distribution avoids consecutive patterns. The Mallows distribution behaves like a $q$-analogue of the uniform distribution by weighting each permutation $pi$ by $q^{inv(pi)}$, where $inv(pi)$ is the number of inversions in $pi$ and $q$ is a positive, real-valued parameter. We prove that the growth rate exists for all patterns and all $q>0$, and we generalize Goulden and Jackson's cluster method to keep track of the number of inversions in permutations avoiding a given consecutive pattern. Using singularity analysis, we approximate the growth rates for length-3 patterns, monotone patterns, and non-overlapping patterns starting with 1, and we compare growth rates between different patterns. We also use Stein's method to show that, under certain assumptions on $q$, the length of $sigma$, and $inv(sigma)$, the number of occurrences of a given pattern $sigma$ is well approximated by the normal distribution.

Recommendations

• Permutations avoiding a pattern of length three under Mallows distributions
• The length of the longest increasing subsequence of a random Mallows permutation
• Pattern avoidance for random permutations
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• Cycles in Mallows random permutations

Cited in

(22)

• Opportunity costs in the game of best choice
• The height of Mallows trees
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra
• Statistical enumeration of groups by double cosets
• A central limit theorem for descents of a Mallows permutation and its inverse
• Central limit theorems for patterns in multiset permutations and set partitions
• Weighted dependency graphs and the Ising model
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Pattern avoidance for random permutations
• Attacks and alignments: rooks, set partitions, and permutations
• Weighted games of best choice
• Cycles in Mallows random permutations
• Permutations avoiding a pattern of length three under Mallows distributions
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Moments of permutation statistics and central limit theorems
• Refined consecutive pattern enumeration via a generalized cluster method
• Limits of Mallows trees
• Thresholds for patterns in random permutations with a given number of inversions
• Classical patterns in Mallows permutations
• Logical limit laws for Mallows random permutations
• Tangled paths: a random graph model from Mallows permutations

This page was built for publication: The probability of avoiding consecutive patterns in the Mallows distribution

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