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

random permutationpermutation patternjoint asymptotic normalitymixed moments

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

(22)

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

Describes a project that uses

Uses Software

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

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)