Constructing optimal transition matrix for Markov chain Monte Carlo

The notion of asymptotic variance has been used as a means for gauging the performance of Markov chain Monte Carlo (MCMC) methods. For an effective MCMC simulation, it is imperative to first construct a Markov model with minimal asymptotic variance. The construction of such a stochastic matrix with prescribed stationary distribution as well as optimal asymptotic variance amounts to an interesting variationally constrained inverse eigenvector problem. Cast against a specially defined oblique coordinate system, the worst-case analysis of the asymptotic variance can be formulated as a problem of minimizing the logarithmic 2-norm of a restricted resolvent matrix over a convex and compact monoid. Based on this framework, this paper proposes employing global optimization techniques as a general instrument for numerical construction of optimal transition matrices. Numerical experiments manifest the complexity of the underlying problem. First, new global solutions different from the conventional structure characterized in the literature are found across the board for reversible problems. Second, local solutions with high frequencies of occurrence appear widespread for nonreversible problems. In all, the approach via the global optimization techniques is a feasible and practical means for numerical construction of the optimal Markov chain.