Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words

Details Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words

2011-10-06

arxiv.org/abs/1110.1324v1

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotics for the Length of Longest Increasing Subsequences of Binary Markovian Random Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181972