Numerical Estimation of the Second Largest Eigenvalue of a Reversible Markov Transition Matrix

Candidate: Kranthi Gade

Advisor: Jonathan Goodman

We discuss the problem of finding the second largest eigenvalue of an operator
that defines a reversible Markov chain. The second largest eigenvalue governs
the rate at which the statistics of the Markov chain converge to equilibrium.
Scientific applications include understanding the very slow dynamics of some
models of dynamic glass. Applications in computing include estimating the rate
of convergence of Markov chain Monte Carlo algorithms.

Most practical Markov chains have state spaces so large that direct or even
iterative methods from linear algebra are inapplicable. The size of the state
space, which is the dimension of the eigenvalue problem, grows exponentially
with the system size. This makes it impossible to store a vector (for sparse methods),
let alone a matrix (for dense methods). Instead, we seek a method that uses only
time correlation from samples produced from the Markov chain itself.

In this thesis, we propose a novel Krylov subspace type method to estimate
the second eigenvalue from the simulation data of the Markov chain using test
functions which are known to have good overlap with the slowest mode. This
method starts with the naive Rayleigh quotient estimate of the test function and
refines it to obtain an improved estimate of the second eigenvalue. We apply
the method to a few model problems and the estimate compares very favorably with
the known answer. We also apply the estimator to some Markov chains occuring in
practice, most notably in the study of glasses. We show experimentally that our
estimator is more accurate and stable for these problems compared to the existing
methods.