Asymptotics for the Length of the Longest Increasing Subsequence of Binary Markov Random Word

2011/10/06 by Christian Houdré, Houdré, Christian, Trevis J. Litherland +1
Mathematics · #05A16 #60C05 #60F05 #60F17 #60G15 #60G17 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:05A16 #msc:60C05 #msc:60F05 #msc:60F17 #msc:60G15 #msc:60G17

paper · pdf · doi:10.48550/arxiv.1110.1324

To appear in: Malliavin Calculus and Stochastic Analysis: A Festschrift in Honor of David Nualart

arxiv created 2012/08/23 · arxiv updated 2012/08/27

Abstract

Let (X_n)_{n≥ 0} be an irreducible, aperiodic, and homogeneous binary Markov chain and let LI_n be the length of the longest (weakly) increasing subsequence of (X_k)_{1≤ k ≤ n}. Using combinatorial constructions and weak invariance principles, we present elementary arguments leading to a new proof that (after proper centering and scaling) the limiting law of LI_n is the maximal eigenvalue of a 2 × 2 Gaussian random matrix. In fact, the limiting shape of the RSK Young diagrams associated with the binary Markov random word is the spectrum of this random matrix.

Related

• On the Limiting Shape of Young Diagrams Associated With Markov Random Words
• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• On the Limiting Shape of Markovian Random Young Tableaux
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions
• Random Words, Toeplitz Determinants and Integrable Systems. I