✦ LIBER ✦

On Increasing Subsequences of Random Permutations

✍ Scribed by Jeong Han Kim

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 292 KB
Volume: 76
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1996.0095

No coin nor oath required. For personal study only.

✦ Synopsis

Let L n be the length of a longest increasing subsequence in a random permutation of [1, ..., n]. It is known that the expected value of L n is asymptotically equal to 2 -n as n gets large. This note derives upper bound on the probability that L n &2 -n exceeds certain quantities. In particular, we prove that L n &2 -n is at most order n 1Â6 with high probability. Our main result is an isoperimetric upper bound of the probability that L n &2 -n exceed %n 1Â6 , which suggests that the variance V[L n ] might be n 1Â3 . We also find an explicit lower bound of the function ;(c) := &lim n Ä (1Ân) log Pr(L n &2 -n>c -n), c>0, defined by D. Aldous and P. Diaconis.

📜 SIMILAR VOLUMES

The number of increasing subsequences of

The number of increasing subsequences of the random permutation

✍ V Lifschitz; B Pittel 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 729 KB

The number of permutations containing ex

The number of permutations containing exactly one increasing subsequence of length three

✍ John Noonan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 287 KB

It is proved that the number of permuations on {I, 2, ... , n} with exactly one increasing subsequence of length 3 is ~(ntn3) [0,0,1,6,27,110,429, ... (Sloane A3517)]. Given a permutaion a E Sn, an abc subsequence is a set of three elements, a(i), aU), a(k), with a(i) < aU) < a(k) and i < j < k. It

Ascending subsequences of permutations a

Ascending subsequences of permutations and the shapes of tableaux

✍ Herbert S Wilf 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 117 KB

On the Law of The Iterated Logarithm for

On the Law of The Iterated Logarithm for Rapidly Increasing Subsequences

✍ Rainer Schwabe; Allan Gut 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB

The usual law of the iterated logarithm states that the partial sums Sn of independent and identically distributed random variables can be normalized by the sequence an = d -, such that limsup,,, &/a, = t/z a. 9.. As has been pointed out by GUT (1986) the law fails if one considers the limsup along

Law of iterated logarithm for random sub

Law of iterated logarithm for random subsequences

✍ R. Vasudeva; G. Divanji 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 389 KB

The Number of Permutations with Exactlyr

The Number of Permutations with Exactlyr132-Subsequences IsP-Recursive in the Size!

✍ Miklós Bóna 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 152 KB

Proving a first nontrivial instance of a conjecture of Noonan and Zeilberger we Ž . show that the number S n of permutations of length n containing exactly r r subsequences of type 132 is a P-recursive function of n. We show that this remains true even if we impose some restrictions on the permutati