On the Asymptotic Statistics of the Number of Occurrences of Multiple Permutation Patterns
By Svante Janson, Brian Nakamura, Doron Zeilberger. 2013
48 citations recorded by the source corpus.
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 $\tau$, the random variables $X_{\sigma}$ and $X_{\tau}$ 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.
Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/5df65b84c3d78dce21a964802e12324533cdd5a1
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Discrete Mathematics and Combinatorics
In Mathematical Physics
Citations in the corpus
- The Brownian limit of separable permutations (2016, methodology): “approach, also of importance for our work, is that of Janson [9], following earlier works by several authors [1, 2, 3, 7, 10, 14]: it consists in studying the (normalized) number of occurrences of any given pattern π in a uniform random permutation σ avoiding τ , and in finding its limiting distribu”
- Universal limits of substitution-closed permutation classes (2017, background): “• Janson, Nakamura and Zeilberger [33] considered higher moments and joint moments, rigourously when C = S, and also empirically for various classes C.”