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

DOI10.1214/21-EJP612MaRDI QIDQ6320549arXivFDO

Authors Clément Deslandes, Christian Houdré

Publication date 15 June 2019

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random matrices (algebraic aspects) (15B52) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Combinatorics on words (68R15)

Abstract: Let $(X_k{)}_{kgeq1}$ and $(Y_k{)}_{kgeq1}$ 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,\mathrm{...},X_n)$ and $(Y_1,\mathrm{...},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.

This page was built for publication: On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320549)