The embedding problem for Markov matrices
Casanellas i Rius, Marta (Universitat Politècnica de Catalunya. Departament de Matemàtiques)
Fernández-Sánchez, Jesus (Universitat Politècnica de Catalunya. Departament de Matemàtiques)
Roca-Lacostena, Jordi (Universitat Politècnica de Catalunya. Departament de Matemàtiques)
Data: |
2023 |
Resum: |
Characterizing whether a Markov process of discrete random variables has a homogeneous continuous-time realization is a hard problem. In practice, this problem reduces to deciding when a given Markov matrix can be written as the exponential of some rate matrix (a Markov generator). This is an old question known in the literature as the embedding problem [11], which has been solved only for matrices of size 2 × 2 or 3 × 3. In this paper, we address this problem and related questions and obtain results along two different lines. First, for matrices of any size, we give a bound on the number of Markov generators in terms of the spectrum of the Markov matrix. Based on this, we establish a criterion for deciding whether a generic (distinct eigenvalues) Markov matrix is embeddable and propose an algorithm that lists all its Markov generators. Then, motivated and inspired by recent results on substitution models of DNA, we focus on the 4 × 4 case and completely solve the embedding problem for any Markov matrix. The solution in this case is more concise as the embeddability is given in terms of a single condition. |
Resum: |
Characterizing whether a Markov process of discrete random variables has a homogeneous continuous-time realization is a hard problem. In practice, this problem reduces to deciding when a given Markov matrix can be written as the exponential of some rate matrix (a Markov generator). This is an old question known in the literature as the embedding problem [11], which has been solved only for matrices of size 2 × 2 or 3 × 3. In this paper, we address this problem and related questions and obtain results along two different lines. First, for matrices of any size, we give a bound on the number of Markov generators in terms of the spectrum of the Markov matrix. Based on this, we establish a criterion for deciding whether a generic (distinct eigenvalues) Markov matrix is embeddable and propose an algorithm that lists all its Markov generators. Then, motivated and inspired by recent results on substitution models of DNA, we focus on the 4 × 4 case and completely solve theembedding problem for any Markov matrix. The solution in this case is more concise as the embeddability is given in terms of a single condition. |
Drets: |
Tots els drets reservats. |
Llengua: |
Anglès |
Document: |
Article ; Versió publicada |
Matèria: |
Markov matrix ;
Markov generator ;
Embedding problem ;
Rate identifiability |
Publicat a: |
Publicacions matemàtiques, Vol. 67 Núm. 1 (2023) , p. 411-445 (Articles) , ISSN 2014-4350 |
Adreça original: https://raco.cat/index.php/PublicacionsMatematiques/article/view/412705
DOI: 10.5565/PUBLMAT6712308
El registre apareix a les col·leccions:
Articles >
Articles publicats >
Publicacions matemàtiques
Registre creat el 2023-02-14, darrera modificació el 2023-11-29