IIIT Hyderabad Publications |
|||||||||
|
Bounding Mixing Time of a Makov Chain : Optimization of Quadratic FormsAuthors: Garimella Ramamurthy Date: 2015-06-10 Report no: IIIT/TR/2015/51 AbstractIn this research paper, a lower bound on the second largest eigenvalue of a symmetric stochastic matrix is derived. Also, an interesting upper bound on the smallest eigenvalue of a symmetric stochastic matrix is derived. The results are utilized to estimate the rate of convergence of transient probability distribution of a Discrete Time Markov Chain ( DTMC ) to the equilibrium probability distribution. Thus the mixing time of a DTMC is estimated. The results are also extended to Continuous Time Markov Chains ( CTMCs ). Full report: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |