Covariance and relaxation time in finite Markov chains. (1998) - Keilson, Julian
Abstract : The relaxation time T R E L of a finite ergodic Markov chain in continuous time, i.e., the time to reach ergodicity from some initial state distribution, is loosely given in the literature in terms of the eigenvalues λ j of the infinitesimal generator Q ¯ ¯ . One uses T R E L = θ − 1 where θ = min λ j ≠ 0 Re λ j [ − Q ¯ ¯ ] . This paper establishes for the relaxation time θ − 1 the theoretical solidity of the time reversible case. It does so by examining the structure of the quadratic distance d ( t ) to ergodicity. It is shown that, for any function f ( j ) defined for states j, the correlation function ρ f ( τ ) has the bound | ρ f ( τ ) | ≤ exp [ − π | τ | ] and that this inequality is tight. The argument is almost entirely in the real domain.