Large deviations for permutations avoiding monotone patterns

Abstract: For a given permutation

a u

, let

P_{N}^{a u}

be the uniform probability distribution on the set of

N

-element permutations

s i g m a

that avoid the pattern

a u

. For

a u = m u_{k} := 123 c d o t s k

, we consider

P_{N}^{m u_{k}} (s i g m a_{I} = J)

where

I s i m g a m m a N

and

J s i m d e l t a N

for

g a m m a, d e l t a i n (0, 1)

. If

g a m m a + d e l t a e q 1

then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of

P_{N}^{m u_{k}} (s i g m a_{I} = J)^{1 / N}

. We also observe that for

a u = l a m b d a_{k, e l l} := 12 l d o t s e l l k (k - 1) l d o t s (e l l + 1)

and

g a m m a + d e l t a < 1

, the limit of

P_{N}^{a u} (s i g m a_{I} = J)^{1 / N}

is the same as for

a u = m u_{k}

.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (12)

This page was built for publication: Large deviations for permutations avoiding monotone patterns