Distribution of the shape of Markovian random words (Q1885323)

The paper concerns the statistical analysis of the shape of random words over a finite alphabet. Given an alphabet \(\mathcal A\) of a fixed size \(k\), let \(\mathcal {W(A,N)}\) be the set of all words of length \(\mathcal N\) using alphabet \(\mathcal A\). We can define the uniform probability distribution on the set \(\mathcal {W(A,N)}\). After the introduction of an ordering on the set \(\mathcal A\) we can ask the following question: what is the length of the longest weakly increasing subsequence? This is a crucial question related with a fundamental result of \textit{K. Johansson} [Ann. Math. (2) 153, No. 1, 259--296 (2001; Zbl 0984.15020)], stating that the shape \(\lambda\) of the semi-standard tableau of a random word in \(k\) letters is asymptotically given by the distribution of the spectrum of a random traceless \(k\times k\) Gaussian unitary ensemble matrix. \textit{G. Kuperberg} [Methods Appl. Anal. 9, No. 1, 99--118 (2002; Zbl 1028.60007)] conjectured that this result remains valid for a certain form of the Markovian letter generator. The authors prove this conjecture for an alphabet with \(k=2\) letters.