Structure of random 312‐avoiding permutations1. Issue 3 (8th September 2015)

• Record Type: Journal Article
• Authors: Madras, Neal; Pehlivan, Lerna
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 599
• Page End: 631
• Publication Date: 2015-09-08
• Subjects: random permutation -- pattern‐avoiding permutation -- Dyck path -- asymptotic probability -- random walk; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20601
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We evaluate the probabilities of various events under the uniform distribution on the set of 312‐avoiding permutations of 1, …, N . We derive exact formulas for the probability that the i th element of a random permutation is a specific value less than i, and for joint probabilities of two such events. In addition, we obtain asymptotic approximations to these probabilities for large N when the elements are not close to the boundaries or to each other. We also evaluate the probability that the graph of a random 312‐avoiding permutation has k specified decreasing points, and we show that for large N the points below the diagonal look like trajectories of a random walk. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 599–631, 2016