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

DOI10.4310/JOC.2015.V6.N1.A8zbMATH Open1312.05011arXiv1312.3955MaRDI QIDQ2345772FDOQ2345772

Authors: Svante Janson, Brian Nakamura, Doron Zeilberger 

Publication date: 20 May 2015

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

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.

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

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

zbMATH Keywords

random permutationpermutation patternjoint asymptotic normalitymixed moments

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (22)

• 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
• Title not available (Why is that?)
• Reduced word enumeration, complexity, and randomization
• Patterns in random permutations
• Asymptotic normality of pattern counts in conjugacy classes

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)