On the Limiting Shape of Young Diagrams Associated with Markov Random Words

#### C. Houdre', T.J. Litherland

2020, v.26, Issue 5, 779-838

ABSTRACT

Let $(X_n)_{n \ge 0}$

be an irreducible, aperiodic, homogeneous

Markov chain, with state space

a totally ordered finite alphabet of size $m$.

Using combinatorial constructions and

weak invariance principles, we obtain

the limiting shape of the associated RSK Young diagrams

as a multidimensional Brownian functional. Since the

length of the top row of

the Young diagrams is also

the length of the longest weakly increasing

subsequences of $(X_k)_{1\le k \le n}$,

the corresponding limiting law follows.

We relate our results to a conjecture of

Kuperberg by providing, under a cyclic condition,

a spectral characterization of the Markov

transition matrix precisely characterizing when

the limiting shape is the spectrum of the

$m \times m$ traceless GUE. For each $m \ge 4$,

this characterization identifies a proper, non-trivial

class of cyclic transition matrices

producing such a limiting shape.

However, for $m=3$, all cyclic Markov chains

have such a limiting shape,

a fact previously only known for $m=2$.

For $m$ arbitrary, we also study

reversible Markov chains and obtain a characterization

of symmetric Markov chains for which the limiting shape

is the spectrum of the traceless GUE.

To finish, we explore, in this general setting,

connections between various limiting laws and

spectra of Gaussian random matrices, focusing in particular

on the relationship between the terminal points of the

Brownian motions, the diagonal terms of the random matrix, and

the scaling of its off-diagonal terms, a scaling we conjecture

to be a function of the spectrum of the covariance matrix

governing the Brownian motion.

Keywords: random words, longest weakly increasing subsequences, Brownian functionals, Functional Central Limit Theorem, Markov chains, Tracy\tire Widom distribution, Young diagrams, random matrices, GUE

COMMENTS

Please log in or register to leave a comment