高阶马尔科夫链的张量模型高阶马尔科夫链的张量模型 黎稳黎稳华南师范大学数学科学学院华南师范大学数学科学学院广州，广州，510631Joint work with Prof. Michael Ng and LB Cui 提纲提纲o引言引言o关于张量模型平稳分布存在与唯一性关于张量模型平稳分布存在与唯一性o求解张量模型平稳分布的迭代法求解张量模型平稳分布的迭代法o平稳分布的扰动分析平稳分布的扰动分析o数值例子数值例子 一、引言一、引言： Markov链的研究有非常悠久的历史，在建模以及链的研究有非常悠久的历史，在建模以及分析实系统时，分析实系统时，Markov链的应用非常广泛，例如对链的应用非常广泛，例如对制制造系统，随机自动化网络（造系统，随机自动化网络（SAMs），排队系统，生物），排队系统，生物信息工程，数据序列、网页排序以及其他和计算有关的信息工程，数据序列、网页排序以及其他和计算有关的应用和网络决策分析等等应用和网络决策分析等等, Markov链模型能作出很好链模型能作出很好的预测和优化计划等作用的预测和优化计划等作用 在某些应用研究中，在某些应用研究中，例如在生物信息学中例如在生物信息学中，不同基，不同基因之间的相互作用构成了复杂的细胞活动。
对作用于细因之间的相互作用构成了复杂的细胞活动对作用于细胞、组织和器官的基因共同性研究在生物信息学中是一胞、组织和器官的基因共同性研究在生物信息学中是一个重要的课题代替独立看待单细胞，全局的或历史性个重要的课题代替独立看待单细胞，全局的或历史性的观点在理解细胞作用和控制大量正常功能运作的机制的观点在理解细胞作用和控制大量正常功能运作的机制中显得越来越重要中显得越来越重要通过概率布尔网络通过概率布尔网络(PBN)建立基因建立基因调控网络模型，调控网络模型，利用实际的数据推断利用实际的数据推断网络结构和网络结构和 参数参数这有助于我们理解基因网络和理解网络中不同这有助于我们理解基因网络和理解网络中不同的基因的作用的基因的作用然后提出基因干预的治疗或基因控制然后提出基因干预的治疗或基因控制策略策略然而，网络的规模随基因数量的增长而呈指数然而，网络的规模随基因数量的增长而呈指数阶增长一个阶增长一个PBN可以建立有关可以建立有关Markov模型模型，进而利，进而利用该用该Markov链模型分析该网络链模型分析该网络; 在信用危机模型在信用危机模型中的中的应用中，信用等级在信用危机分析和建模中非常重要。
应用中，信用等级在信用危机分析和建模中非常重要以往建立信用等级和他们之间的转移的常规的方法就以往建立信用等级和他们之间的转移的常规的方法就是是Markov链模型及其概率转移矩阵当今链模型及其概率转移矩阵当今 人们面临的人们面临的问题越来越复杂，复杂的事物通常可以用问题越来越复杂，复杂的事物通常可以用高维数据来高维数据来刻画 最近，最近，高阶非负张量用于建立高阶高阶非负张量用于建立高阶Markov链模型链模型，，这给研究这给研究Markov链带来新的具有挑战性的课题链带来新的具有挑战性的课题 因此，对因此，对Markov过程及其应用的研究至今仍然是过程及其应用的研究至今仍然是数学及许多领域的研究热点，其研究在生物、医学、数学及许多领域的研究热点，其研究在生物、医学、计算机科学、数据分析和数学等各方面都要重要的理计算机科学、数据分析和数学等各方面都要重要的理论和实践意义论和实践意义 1、、 Markov链模型链模型 给定一个Markov链过程x(t)，设它在离散的时间段t = 1, 2, 3, . . .内在状态空间S = {1, 2, . . . , m}内取值， 的概率只和 有关。
一个Markov过程是由它的概率转移矩阵 刻画的，其中， (1)这时，P 是列和为1的非负矩阵 对某些数据序列进行分析时， 一阶Markov模型不能满足进一步的分析要求，因为在时刻t的概率与它前面的n 个时刻有关，即需要求如下概率:Raftery于1985年给出了估计方法： 2、高阶非负张量模型、高阶非负张量模型 对高阶Markov模型的分析也可以利用高阶非负张量的有关理论，所谓m阶n维非负张量指 张量有非常重要的应用. 这里，我们比较感兴趣的是与高阶Markov链有关的非负张量的谱理论，张和祁给出张量谱理论的很好的综述张量的H-特征值和特征向量定义为 ： 其中而Z-特征值和特征向量定义: (see Chang and Zhang, manuscript, 2012).文[Ng,Qi, Zhou, SIMAX, 2009]指出，对某些数据系列建立高阶Markov模型时通常可以计算如下高阶转移概率：（5） 在模型（2）和（4）中， 的值分别由某些 的线性组合近似得到。
由非负张量的关于H-特征值的Perron-Frobenius定理知道[N-Q-Z，09]可以直接利用非负张量（5）来计算有关概率分布向量 对计算高阶张量的在时刻t概率分布 [Qi，2012]等给出了如下模型: （6） 其中，P满足（5），且 则平稳概率分布向量可以通过如下模型得到： （7） 其中 对模型（7）我们有如下需要解决的问题：（a）模型（7）的解向量，即平稳分布x是存在吗？唯一吗？ 如果不唯一，什么情况下唯一？（b）保证唯一性条件下，如何给出（7）平稳概率分布向量 的求解算法？（c） 如何给出（7）的敏感性（扰动）分析？ 二、关于模型（二、关于模型（7）平稳分布存在唯一性）平稳分布存在唯一性1、存在性：文存在性：文[Li, Ng, 2011]定理定理2.2 (p.21) 给出了对给出了对不可约非负张量，方程（不可约非负张量，方程（7）的存在性证明，即）的存在性证明，即: 2、唯一性：文、唯一性：文[Li, Ng, 2011]给出了如果概率转移张量给出了如果概率转移张量P没有任何没有任何限制，（限制，（7）的解不是唯一的（）的解不是唯一的（p. 24 Remark 1）。
对方程（）对方程（7）文）文[Li,Ng, 2011]首次给出了唯一性的充分条件（见首次给出了唯一性的充分条件（见Theorems 2.3 and 2.4, p. 22--35），即），即 注记注记 1 定理2.3与2.4所给出的条件不是必要的（see Remark 5 p. 35）；注记注记 2 对m=3，n=2，文[Chang and Zhang]和[Hu,Qi,2011]分别给出 方程（7）的解是唯一的，另外他们也给出了唯一性的另外一些充分 条件注记注记 3 实际上，（7）为张量的Z_1 特征值问题 Chang and Zhang给出 了Z_1 和Z_2 特征值问题的关系 问题问题 ：1、非负概率转移张量的不可约性是否是（、非负概率转移张量的不可约性是否是（7）有唯一）有唯一 平稳分布的条件？平稳分布的条件？2、能否给出有唯一解的充分必要条件？、能否给出有唯一解的充分必要条件？3、模型（、模型（6）的概率分布有极限的充分必要条件是什）的概率分布有极限的充分必要条件是什 么？么？ 注：注：问题1对一般非负矩阵来说是对的，许多数值例子 也表明问题的答案是肯定的！而对非负矩阵来说， 唯一性的充分必要条件是基本类等于最后类（注： 类、基本类、最后类的定义可以参考[BP，1979] 三、求解（三、求解（7）平稳分布的迭代法）平稳分布的迭代法 如下是考虑第一节中的问题（如下是考虑第一节中的问题（b），即：保证唯一），即：保证唯一性条件下，如何给出（性条件下，如何给出（7）平稳概率分布向量的求解算）平稳概率分布向量的求解算法？我们给出迭代法如下（见法？我们给出迭代法如下（见LN2011）：）： 注记注记1： t+1步迭代得到的向量x_{t+1} 不必单位化处理。
需讨论的问题是需讨论的问题是：(a) 在（7）有唯一解的条件下，上述算法是否收敛？(b) 如果不收敛，收敛条件是什么？(c) 收敛率如何给出？效果如何？ 问题(a)是否定的， 例如取3阶2维不可约概率转移张量（见p.35, Remark 5）, 有唯一解（1/2，1/2）^{T}, 但算法选取初值为（0，1）^{T}，则算法不收敛尽管可以存在收敛的子序列，但该子序列不一定收敛到（7）的解 对问题(b)和(c) 当满足唯一性条件下，算法收敛：证明见定理3.1和3.2（p.44—49）. 问题问题：（1）算法除了给出的收敛条件以外还有更算法除了给出的收敛条件以外还有更 好的收敛条件？好的收敛条件？ （（2）寻找更好的算法？）寻找更好的算法？ 四、概率平稳分布的扰动分析四、概率平稳分布的扰动分析1、基础、基础 （1）、什么是扰动分析？）、什么是扰动分析？ （（2）、通常扰动分析研究什么？）、通常扰动分析研究什么？ （（3）、问题扰动的形式：加法与乘法）、问题扰动的形式：加法与乘法2、结果、结果：本节给出的结果是在唯一性条件下给出了本节给出的结果是在唯一性条件下给出了 （（7）的系数张量变化对平稳分布的影响，即）的系数张量变化对平稳分布的影响，即 注记注记：1、由给出的界可以看出问题的解对唯一性条件非常、由给出的界可以看出问题的解对唯一性条件非常 敏感，后面的数值例子图敏感，后面的数值例子图2-7也说明这点也说明这点; 2、界可以取到等号成立（见、界可以取到等号成立（见p66 III））;3、绝对扰动与相对扰动一致、绝对扰动与相对扰动一致. 3、一阶、一阶Markov链的扰动分析情况链的扰动分析情况o问题：问题：对一般的非负张量，H-和Z-矩阵的最大特征对扰动界如何给出？ 五、算例五、算例参考论文参考论文：：[1] W Li, M. Ng, Existence and uniqueness of stationary probability vector of a transition probability tensor, BUHK，，2011[2] W Li, Lu-Bin Cui, M. Ng, Perturbation bound for the Perron vector of a transition probability tensor, BUHK，，2011 。