仅运用一个特征向量计算可对角化转移矩阵的吸收马尔可夫链的平稳分布

Computing the Stationary Distribution of Absorbing Markov Chains with One Eigenvector of Diagonalizable Transition Matrices

吸收马尔可夫链是一种重要的统计模型,广泛地被用于众多学科中的算法建模,如在数字图像处理、网络分析等中.为了得到该模型的平稳分布,通常需要计算转移矩阵的逆,但是对于大型矩阵来说这仍然是比较困难且耗费计算量的.在本文中,对于含有两个吸收态的马尔可夫链,当其转移矩阵可对角化时,我们提出了一种简单方法来计算其平稳分布.在该方法中仅仅需要计算特征值1对应的一个特征向量即可.我们运用该方法,从矩阵的角度推导出了赌徒破产问题的相关概率.同时本方法也能够处理该问题的复杂扩展形式.事实上,本方案是对处理吸收马尔可夫链的通用方法的一个变种,因此在通用方法中也能够采用类似的技术来避免矩阵求逆运算.

An absorbing Markov chain is an important statistic model and widely used in algorithm modeling for many disciplines,such as digital image processing,network analysis and so on.In order to get the stationary distribution for such model,the inverse of the transition matrix usually needs to be calculated.However,it is still difficult and costly for large matrices.In this paper,for absorbing Markov chains with two absorbing states,we propose a simple method to compute the stationary distribution for models with diagonalizable transition matrices.With this approach,only an eigenvector with eigenvalue 1 needs to be calculated.We also use this method to derive probabilities of the gambler’s ruin problem from a matrix perspective.And,it is able to handle expansions of this problem.In fact,this approach is a variant of the general method for absorbing Markov chains.Similar techniques can be used to avoid calculating the inverse matrix in the general method.