Periodic words, common subsequences and frogs

2019/12/07 by Boris Bukh, Christopher Cox, Bukh, Boris +1
Mathematics · #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:60J10

paper · pdf · doi:10.48550/arxiv.1912.03510

43 pages, 4 figures, 2 tables

arxiv created 2021/06/04 · arxiv updated 2021/06/07

Abstract

Let W⁽ⁿ⁾ be the n-letter word obtained by repeating a fixed word W, and let R_n be a random n-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between W⁽ⁿ⁾ and R_n; in particular, we show that its expectation is γ_W n-O(√(n)) for an efficiently-computable constant γ_W. This is done by relating the problem to a new interacting particle system, which we dub "frog dynamics". In this system, the particles (`frogs') hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. In the special case when all symbols of W are distinct, we obtain an explicit formula for the constant γ_W and a closed-form expression for the stationary distribution of the associated frog dynamics. In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.

Related

• Frogs, hats and common subsequences
• Longest common subsequences between words of very unequal length
• Repetition-free longest common subsequence of random sequences
• Matching strings in encoded sequences
• Expected length of the longest common subsequence for large alphabets