Pattern avoidance for random permutations
From MaRDI portal
Abstract: Using techniques from Poisson approximation, we prove explicit error bounds on the number of permutations that avoid any pattern. Most generally, we bound the total variation distance between the joint distribution of pattern occurrences and a corresponding joint distribution of independent Bernoulli random variables, which as a corollary yields a Poisson approximation for the distribution of the number of occurrences of any pattern. We also investigate occurrences of consecutive patterns in random Mallows permutations, of which uniform random permutations are a special case. These bounds allow us to estimate the probability that a pattern occurs any number of times and, in particular, the probability that a random permutation avoids a given pattern.
Recommendations
- Patterns in random permutations avoiding some sets of multiple patterns
- Patterns in random permutations avoiding some other patterns
- Permutations avoiding a pattern of length three under Mallows distributions
- The probability of avoiding consecutive patterns in the Mallows distribution
- Patterns in random permutations avoiding the pattern 321
Cited in
(19)- A central limit theorem for descents of a Mallows permutation and its inverse
- Patterns in random permutations avoiding some sets of multiple patterns
- Permutation statistics and multiple pattern avoidance
- Pattern avoidance of generalized permutations
- Pattern avoidance in flattened permutations
- Non-overlapping permutation patterns
- scientific article; zbMATH DE number 5831716 (Why is no real title available?)
- Matchings up to permutations in sequences of independent trials
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- The probability of avoiding consecutive patterns in the Mallows distribution
- Large deviations for permutations avoiding monotone patterns
- Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
- Rational generating series for affine permutation pattern avoidance
- Cycles in Mallows random permutations
- Permutations avoiding a pattern of length three under Mallows distributions
- An alternative proof for the expected number of distinct consecutive patterns in a random permutation
- Thresholds for patterns in random permutations with a given number of inversions
- Pattern avoidance by even permutations
- Logical limit laws for Mallows random permutations
This page was built for publication: Pattern avoidance for random permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560196)
