On the asymptotic statistics of the number of occurrences of multiple permutation patterns

DOI10.4310/JOC.2015.V6.N1.A8MaRDI QIDQ2345772zbMATH OpenFDO

Authors Svante Janson, Brian Nakamura, Doron Zeilberger

Publication date 20 May 2015

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

joint asymptotic normalitymixed momentspermutation patternrandom permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: We study statistical properties of the random variables $X_{sigma}(pi)$, the number of occurrences of the pattern $sigma$ in the permutation $pi$. We present two contrasting approaches to this problem: traditional probability theory and the ``less traditional computational approach. Through the perspective of the first one, we prove that for any pair of patterns $sigma$ and $au$, the random variables $X_{sigma}$ and $X_{au}$ are jointly asymptotically normal (when the permutation is chosen from $S_n$). From the other perspective, we develop algorithms that can show asymptotic normality and joint asymptotic normality (up to a point) and derive explicit formulas for quite a few moments and mixed moments empirically, yet rigorously. The computational approach can also be extended to the case where permutations are drawn from a set of pattern avoiders to produce many empirical moments and mixed moments. This data suggests that some random variables are not asymptotically normal in this setting.

Recommendations

• Patterns in random permutations avoiding some sets of multiple patterns
• Patterns in random permutations
• The number of occurrences of patterns in a random tree or forest permutation
• Patterns in random permutations avoiding some other patterns
• A Central Limit Theorem for Vincular Permutation Patterns

Cited in

(27)

• The Brownian limit of separable permutations
• Renewal theory for asymmetric \(U\)-statistics
• Symbolic moment calculus. I: Foundations and permutation pattern statistics
• Hidden words statistics for large patterns
• Statistics on multipermutations and partial \(\gamma\)-positivity
• Stable characters from permutation patterns
• Reduced word enumeration, complexity, and randomization
• Central limit theorems for patterns in multiset permutations and set partitions
• Universal limits of substitution-closed permutation classes
• Patterns in random permutations avoiding some sets of multiple patterns
• Patterns in random permutations
• Positivity of permutation pattern character polynomials
• scientific article; zbMATH DE number 4022354 (Why is no real title available?)
• Patterns in random permutations avoiding some other patterns
• Permutations, moments, measures
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• Patterns in random permutations avoiding the pattern 132
• Asymptotic normality for -dependent and constrained -statistics, with applications to pattern matching in random strings and permutations
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Asymptotic normality of pattern counts in conjugacy classes
• Moments of permutation statistics and central limit theorems
• Thresholds for patterns in random permutations with a given number of inversions
• A geometric approach to conjugation-invariant random permutations
• Classical patterns in Mallows permutations
• Pattern-based tests for two-dimensional copulas
• How balanced can permutations be?
• Counting occurrences of patterns in permutations

Describes a project that uses

Uses Software

• MahonianStat
• SMCper
• P123
• F123
• F1234
• P1234
• P12345
• P123456
• F12345

This page was built for publication: On the asymptotic statistics of the number of occurrences of multiple permutation patterns

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