On the rate of convergence for the length of the longest common\n subsequences in hidden Markov models

2017/12/28 by Christian Houdré, Houdré, Christian, George Kerchev +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1712.09881

openalex publication_date 2017/12/28 · openalex created_date 2022/08/15 · openalex updated_date 2026/07/28

Abstract

Let (X, Y) = (X_n, Y_n)_{n \≥ 1} be the output process generated by a\nhidden chain Z = (Z_n)_{n \≥ 1}, where Z is a finite state, aperiodic,\ntime homogeneous, and irreducible Markov chain. Let LC_n be the length of the\nlongest common subsequences of X₁, \…, X_n and Y₁, \…, Y_n. Under\na mixing hypothesis, a rate of convergence result is obtained for\n\𝔼[LC_n]/n.\n

Related

• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distributions
• On Obtaining Sharp Bounds of the Rate of Convergence for a Class of Continuous-Time Markov Chains
• Asymptotics for the Length of the Longest Increasing Subsequence of Binary Markov Random Word
• Limit Theorems in Hidden Markov Models
• Stationary and Transition Probabilities in Slow Mixing, Long Memory Markov Processes