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