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

Abstract

Let $(X_n{)}_{n\ge 0}$ be an irreducible, aperiodic, and homogeneous binary Markov chain and let $L{I}_n$ be the length of the longest (weakly) increasing subsequence of $(X_k{)}_{1\le k\le 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 $L{I}_n$ is the maximal eigenvalue of a $2\times 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.

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