And this: https://ac.els-cdn.com/0001870885900039/1-s2.0-0001870885900039-main.pdf?_ti... If the alphabet is binary, this is the same as the longest run of heads in a sequence of random coin tosses. On Sun, Mar 11, 2018 at 2:33 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Also this appears to be the first paper to treat this in depth: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid= D1DAD7AF91DC4FF714776A87560EF018?doi=10.1.1.667.4341&rep=rep1&type=pdf
On Sun, Mar 11, 2018 at 12:07 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Let S = {1, ..., s} , A = [1, ..., a] , |B| = b .
We seek expected length l = |L| of maximal increasing subsequence L of B selected from S , such that max(L) <= a .
Note L is not necessarily a subsequence of the M.I.S. of B ; however, a start might involve looking at
Jean-Christophe Breton, Christian Houdré "On the limiting law of the length of the longest common and increasing subsequences in random words" Stochastic Processes and their Applications, Elsevier, 2017, 127 (5), pp.1676-1720. https://hal.archives-ouvertes.fr/ccsd-01153127/
<< Abstract : Let X=(X_i)_{i≥1} and Y=(Y_i)_{i≥1} be two sequences of independent and identically distributed (iid) random variables taking their values, uniformly, in a common totally ordered finite alphabet. Let LCI_n be the length of the longest common and (weakly) increasing subsequence of X_1⋯X_n and Y_1⋯Y_n. As n grows without bound, and when properly centered and normalized, LCI_n is shown to converge, in distribution, towards a Brownian functional that we identify. >>
WFL
On 3/11/18, David Wilson <davidwwilson@comcast.net> wrote:
Let S be a finite set with |S| = s. Let A be a finite random sequence of elements from S with |A| = a. Let B be a finite random sequence of elements from S with |B| = b. What is the expected length f(s, a, b) of a longest common subsequence of A and B?
As an example, let A and B be finite sequences of 10 decimal digits with |A| = |B| = 10. Then S = set of decimal digits with |S| = 10.
Two possible values of A and B are A = (3,1,4,1,5,9,2,6,5,3) B = (1,4,1,4,2,1,3,5,6,2) A longest common subsequence of A and B is (1,4,1,2,5) of length 5.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun