zbMATH — the first resource for mathematics

On the asymptotic statistics of the number of occurrences of multiple permutation patterns. (English) Zbl 1312.05011
Summary: 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 approach, 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.

MSC:
 05A05 Permutations, words, matrices
Software:
F12345; F1234; SMCper; P1234; P123; MahonianStat; P12345; F123; P123456
Full Text: