A Modified Arnoldi Iteration for Transition Probability Matrices of Reversible Markov Chains.
Joseph M. U. Chong · ScholarSpace (University of Hawaii at Manoa) · 2018
Reversible Markov chains are used for modeling many physical and network phenomena. The second largest eigenvalue magnitude of the transition probability matrix gives a upper bound on the mixing time of a reversible Markov chain, but is incalculable for large transition probability matrices using typical eigenvalue algorithms. We present the Modified Arnoldi iteration - a modification of the Arnoldi iteration for reversible Markov chains that utilizes sample estimates where matrix operations may be infeasible, thereby being a possible option when usual algorithms are nonviable.