On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions

Abstract

Let $(X_k{)}_{k\ge 1}$ and $(Y_k{)}_{k\ge 1}$ be two independent sequences of i.i.d. random variables, with values in a finite and totally ordered alphabet ${\mathcal{A}}_m:=\{1,\dots ,m\}$, and having respective probability mass function $p_1^X,\dots ,p_m^X$ and $p_1^Y,\dots ,p_m^Y$. Let $LC{I}_n$ be the length of the longest common and weakly increasing subsequences in $(X_1,...,X_n)$ and $(Y_1,...,Y_n)$. Once properly centered and normalized, $LC{I}_n$ is shown to have a limiting distribution which is expressed as a functional of two independent multidimensional Brownian motions.

To appear in Electronic Journal of Probability

References in corpus (1)

• On the limiting law of the length of the longest common and increasing subsequences in random words