Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T01:15:26.975Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Limit theorems Combinatorial probability Combinatorics

Published online by Cambridge University Press:  30 July 2019

C. Houdré  and
G. Kerchev
C. Houdré*
Affiliation:
Georgia Institute of Technology
G. Kerchev*
Affiliation:
Georgia Institute of Technology
*
*Postal address: School of Mathematics, Georgia Institute of Technology, 686 Cherry Street Atlanta, GA 30332-0160, USA.
*Postal address: School of Mathematics, Georgia Institute of Technology, 686 Cherry Street Atlanta, GA 30332-0160, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Let (X, Y) = (Xn, Yn)n≥1 be the output process generated by a hidden chain Z = (Zn)n≥1, where Z is a finite-state, aperiodic, time homogeneous, and irreducible Markov chain. Let LCn be the length of the longest common subsequences of X1,..., Xn and Y1,..., Yn. Under a mixing hypothesis, a rate of convergence result is obtained for E[LCn]/n.

Keywords

Longest common subsequencerate of convergencehidden Markov modelHoeffding inequalitymixing condition

MSC classification

Primary: 60C05: Combinatorial probability 05A05: Permutations, words, matrices
Secondary: 60F10: Large deviations
Type
Research Papers
Information
Journal of Applied Probability , Volume 56 , Issue 2 , June 2019 , pp. 558 - 573
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alexander, K. (1994). The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Prob. 4, 1074–1082.CrossRefGoogle Scholar
Berbee, H. C. P. (1979). Random Walks with Stationary Increments and Renewal Theory. Mathematical Centre Tracts, 112. Mathematisch Centrum, Amsterdam.Google Scholar
Bradley, R. (1983) Approximation theorems for strongly mixing random variables. Michigan Math. J. 30, 69–81.Google Scholar
Bradley, R. (2005) Basic properties of strong mixing conditions. A survey and some open questions. Prob. Surveys 2, 104–144.CrossRefGoogle Scholar
Bradley, R. (2007). Introduction to Strong Mixing Conditions, Vol. 1. Kendrick Press, Heber City, UT.Google Scholar
ChváTal, V. and Sankoff, D. (1975). Longest common subsequences of two random sequences. J. Appl. Prob. 12, 306–315.CrossRefGoogle Scholar
Doeblin, W. (1938). Exposé de la théorie des chaînes simples constantes de Markoff à un nombre fini d’états, Revue Math. de l’Union Interbalkanique 2, 77–105.Google Scholar
Doukhan, P. (1994). Mixing. Properties and Examples. Lecture Notes Statist., 85. Springer, New York.Google Scholar
Durbin, R., Eddy, S., Krogh, A. and Mitchison, G. (1998). Biological Sequence Analysis. Cambridge University Press.CrossRefGoogle Scholar
Feller, W. (1968). An Introduction to Probability Theory and its Applications, Vol. 1, 3rd edn. John Wiley, New York.Google Scholar
Goldstein, S. (1979). Maximal coupling. Z. Wahrsch. verw. Gebiete 46, 193–204.CrossRefGoogle Scholar
Lember, J., Matzinger, H. and Torres, F. (2012). The rate of convergence of the mean score in random sequence comparison. Ann. Appl. Prob. 22, 1046–1058.CrossRefGoogle Scholar
Levin, D., Peres, Y. and Wilmer, E. (2008). Markov Chains and Mixing Times. AMS, Providence, RI.CrossRefGoogle Scholar
Paulin, D. (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electron. J. Prob. 20, no. 79.CrossRefGoogle Scholar
Rhee, W. (1995). On rates of convergence for common subsequences and first passage time. Ann. Appl. Prob. 5, 44–48.CrossRefGoogle Scholar
Rio, E. (2017) Asymptotic Theory of Weakly Dependent Random Processes. Probability Theory and Stochastic Modelling, 80. Springer, Berlin.CrossRefGoogle Scholar
Roberts, G. and Rosenthal, J. (2004) General state space Markov chains and MCMC algorithms. Prob. Surveys 1, 20–71.CrossRefGoogle Scholar
Steele, M. (1982). Long common subsequences and the proximity of two random strings. SIAM J. Appl. Math. 42, 731–737.CrossRefGoogle Scholar
Steele, M. (1997). Probability Theory and Combinatorial Optimization. SIAM, Philadelphia, PA, 18–21.CrossRefGoogle Scholar
Thorisson, H. (2000). Coupling, Stationarity and Regeneration. Probability and its Applications. Springer, New York.CrossRefGoogle Scholar