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

Let $(X_n)_{n\ge 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\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 $LI_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.

No reviews yet.

No comments yet.