论文标题
马尔可夫矩阵的嵌入问题
The embedding problem for Markov matrices
论文作者
论文摘要
表征离散随机变量的马尔可夫过程是否具有均匀的连续时间实现是一个困难的问题。在实践中，这个问题减少了决定何时可以将给定的马尔可夫矩阵写为某些速率矩阵的指数（Markov Generator）。这是文献中称为嵌入问题（Elfving37）的一个古老问题，该问题仅针对尺寸$ 2 \ tims 2 $或$ 3 \ times 3 $的矩阵解决。在本文中，我们解决了这个问题及相关问题，并以两种不同的方式获得结果。首先，对于任何大小的矩阵，我们就马尔可夫矩阵的频谱对Markov Generator的数量进行了绑定。基于此，我们建立了一个标准，用于确定是否可以嵌入通用的马尔可夫矩阵（不同的特征值），并提出了列出其所有马尔可夫生成器的算法。然后，我们的动机和启发受到DNA替代模型的最新结果，我们将重点放在$ 4 \ times 4 $案例中，并完全解决了任何马尔可夫矩阵的嵌入问题。在这种情况下，解决方案更加简洁，因为嵌入性是根据单个条件给出的。
Characterizing whether a Markov process of discrete random variables has an 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 (Elfving37), which has been only solved for matrices of size $2\times 2$ or $3\times 3$. In this paper, we address this problem and related questions and obtain results in 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 Markov matrix (different eigenvalues) 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 in the $4\times 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.
