On the optimal transition matrix for markov chain monte carlo sampling

Ting Li Chen, Wei Kuo Chen, Chii Ruey Hwang, Hui Ming Pai

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Let X be a finite space and let π be an underlying probability on X. For any real-valued function f defined on X, we are interested in calculating the expectation of f under π. Let X 0,X 1, . . .,X n, . . . be a Markov chain generated by some transition matrix P with invariant distribution p. The time average, 1/n σ n-1 k=0 f(X k), is a reasonable approximation to the expectation, Eπ[f(X)]. Which matrix P minimizes the asymptotic variance of 1/n σ n-1 k=0 f(X k)? The answer depends on f. Rather than a worst-case analysis, we will identify the set of P's that minimize the average asymptotic variance, averaged with respect to a uniform distribution on f.

Original languageEnglish (US)
Pages (from-to)2743-2762
Number of pages20
JournalSIAM Journal on Control and Optimization
Issue number5
StatePublished - Nov 9 2012


  • Asymptotic variance
  • Average-case analysis
  • Markov chain
  • Markov chain Monte Carlo
  • Nonreversibility
  • Rate of convergence
  • Reversibility
  • Worst-case analysis

Fingerprint Dive into the research topics of 'On the optimal transition matrix for markov chain monte carlo sampling'. Together they form a unique fingerprint.

Cite this