The Computation For The Mean First Passage Times Of Markov Chains

As we all know,the mean first passage matrix is one of the essential ingredients of finite Markov Chains,which is widely used to study the dynamic performance of macro and micro networks.Their theoretical expression and numerical calculation have always been one of the research directions.For the finite irreducible Markov Chains,it’s important to design effective methods for calculating the mean first passage times.There are many methods to solve this problem,such as rank one update,finite calculation,analytical expression and polynomial iterations and etc.These methods are related to the generalized inverse,group inverse,except the iterative method.For the finite irreducible Markov Chains,this article does more research for the new finite method and iterative method.Firstly,we construct the new finite method,which uses dimensionality reduction to convert the calculation for the group inverse of the Markov chains transfer matrix to solve a few equations.And then,we construct the mean first passage matrix directly.Secondly,we construct the new iterative method.The main idea is that we ascribe the computation of the mean first passage times to a class of convergent or semi-convergent linear system of equations.And then,we construct two kinds of iterative method.1.we construct the non-parameter iterative method based on definition equations of the mean first passage matrix.Furthermore,we prove the semi-convergence of the new method and get the explicit formats.2.we construct a kind of Krylov subspace iterative methods based on definition equations of the mean first passage matrix and prove the convergence.Finally,we make comparison with classical methods and new methods con-structed by us through a few numerical examples,which verify the effectiveness and stability of these iterative methods at the same time.As far as we know,the methods studied in this article are our innovation points.