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

DOI10.1214/21-EJP612arXiv1906.06544MaRDI QIDQ6320549FDOQ6320549

Authors: Clément Deslandes, Christian Houdré 

Publication date: 15 June 2019

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.

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)

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)