PERIODIC WORDS, COMMON SUBSEQUENCES AND FROGS

• 成果类型: Article
• 署名作者: Bukh, Boris; Cox, Christopher
• 署名单位: Carnegie Mellon University; Iowa State University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/21-AAP1709
• 发表日期: 2022
• 页码: 1295-1332
• 关键词: expected length; longest

摘要

Let W-(n) 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-(n) and R-n; in particular, we show that its expectation is gamma(W)n - O (root n) for an efficiently-computable constant gamma(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 gamma(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.