Artigo Acesso aberto

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

2015; Electronic Journal of Combinatorics; Volume: 6; Issue: 1–2 Linguagem: Inglês

10.4310/joc.2015.v6.n1.a8

ISSN

2156-3527

Autores

Svante Janson, Brian Nakamura, Doron Zeilberger,

Tópico(s)

Stochastic processes and statistical mechanics

Resumo

We study statistical properties of the random variables X σ (π), the number of occurrences of the pattern σ in the permutation π.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 σ and τ , the random variables X σ and X τ 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.

Referência(s)