Estimating the spectral gap of a trace-class Markov operator

Qian Qin, James P. Hobert, Kshitij Khare

Research output: Contribution to journalArticle

Abstract

The utility of a Markov chain Monte Carlo algorithm is, in large part, determined by the size of the spectral gap of the corresponding Markov operator. However, calculating (and even approximating) the spectral gaps of practical Monte Carlo Markov chains in statistics has proven to be an extremely difficult and often insurmountable task, especially when these chains move on continuous state spaces. In this paper, a method for accurate estimation of the spectral gap is developed for general state space Markov chains whose operators are non-negative and trace-class. The method is based on the fact that the second largest eigenvalue (and hence the spectral gap) of such operators can be bounded above and below by simple functions of the power sums of the eigenvalues. These power sums often have nice integral representations. A classical Monte Carlo method is proposed to estimate these integrals, and a simple sufficient condition for finite variance is provided. This leads to asymptotically valid confidence intervals for the second largest eigenvalue (and the spectral gap) of the Markov operator. In contrast with previously existing techniques, our method is not based on a near-stationary version of the Markov chain, which, paradoxically, cannot be obtained in a principled manner without bounds on the spectral gap. On the other hand, it can be quite expensive from a computational standpoint. The efficiency of the method is studied both theoretically and empirically.

Original languageEnglish (US)
Pages (from-to)1790-1822
Number of pages33
JournalElectronic Journal of Statistics
Volume13
Issue number1
DOIs
StatePublished - Jan 1 2019

Fingerprint

Trace Class Operators
Markov Operator
Spectral Gap
Largest Eigenvalue
Markov chain
State Space
Monte Carlo Markov Chain
Power Sum
Sums of Powers
Markov Chain Monte Carlo Algorithms
Operator
Integral Representation
Monte Carlo method
Confidence interval
Non-negative
Trace
Valid
Statistics
Eigenvalue
Eigenvalues

Keywords

  • Data augmentation algorithm
  • Eigenvalues
  • Hilbert-Schmidt operator
  • Markov chain
  • Monte Carlo

Cite this

Estimating the spectral gap of a trace-class Markov operator. / Qin, Qian; Hobert, James P.; Khare, Kshitij.

In: Electronic Journal of Statistics, Vol. 13, No. 1, 01.01.2019, p. 1790-1822.

Research output: Contribution to journalArticle

Qin, Qian ; Hobert, James P. ; Khare, Kshitij. / Estimating the spectral gap of a trace-class Markov operator. In: Electronic Journal of Statistics. 2019 ; Vol. 13, No. 1. pp. 1790-1822.
@article{197b2555eff34fcdbe4d6fe0c31d788d,
title = "Estimating the spectral gap of a trace-class Markov operator",
abstract = "The utility of a Markov chain Monte Carlo algorithm is, in large part, determined by the size of the spectral gap of the corresponding Markov operator. However, calculating (and even approximating) the spectral gaps of practical Monte Carlo Markov chains in statistics has proven to be an extremely difficult and often insurmountable task, especially when these chains move on continuous state spaces. In this paper, a method for accurate estimation of the spectral gap is developed for general state space Markov chains whose operators are non-negative and trace-class. The method is based on the fact that the second largest eigenvalue (and hence the spectral gap) of such operators can be bounded above and below by simple functions of the power sums of the eigenvalues. These power sums often have nice integral representations. A classical Monte Carlo method is proposed to estimate these integrals, and a simple sufficient condition for finite variance is provided. This leads to asymptotically valid confidence intervals for the second largest eigenvalue (and the spectral gap) of the Markov operator. In contrast with previously existing techniques, our method is not based on a near-stationary version of the Markov chain, which, paradoxically, cannot be obtained in a principled manner without bounds on the spectral gap. On the other hand, it can be quite expensive from a computational standpoint. The efficiency of the method is studied both theoretically and empirically.",
keywords = "Data augmentation algorithm, Eigenvalues, Hilbert-Schmidt operator, Markov chain, Monte Carlo",
author = "Qian Qin and Hobert, {James P.} and Kshitij Khare",
year = "2019",
month = "1",
day = "1",
doi = "10.1214/19-EJS1563",
language = "English (US)",
volume = "13",
pages = "1790--1822",
journal = "Electronic Journal of Statistics",
issn = "1935-7524",
publisher = "Institute of Mathematical Statistics",
number = "1",

}

TY - JOUR

T1 - Estimating the spectral gap of a trace-class Markov operator

AU - Qin, Qian

AU - Hobert, James P.

AU - Khare, Kshitij

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The utility of a Markov chain Monte Carlo algorithm is, in large part, determined by the size of the spectral gap of the corresponding Markov operator. However, calculating (and even approximating) the spectral gaps of practical Monte Carlo Markov chains in statistics has proven to be an extremely difficult and often insurmountable task, especially when these chains move on continuous state spaces. In this paper, a method for accurate estimation of the spectral gap is developed for general state space Markov chains whose operators are non-negative and trace-class. The method is based on the fact that the second largest eigenvalue (and hence the spectral gap) of such operators can be bounded above and below by simple functions of the power sums of the eigenvalues. These power sums often have nice integral representations. A classical Monte Carlo method is proposed to estimate these integrals, and a simple sufficient condition for finite variance is provided. This leads to asymptotically valid confidence intervals for the second largest eigenvalue (and the spectral gap) of the Markov operator. In contrast with previously existing techniques, our method is not based on a near-stationary version of the Markov chain, which, paradoxically, cannot be obtained in a principled manner without bounds on the spectral gap. On the other hand, it can be quite expensive from a computational standpoint. The efficiency of the method is studied both theoretically and empirically.

AB - The utility of a Markov chain Monte Carlo algorithm is, in large part, determined by the size of the spectral gap of the corresponding Markov operator. However, calculating (and even approximating) the spectral gaps of practical Monte Carlo Markov chains in statistics has proven to be an extremely difficult and often insurmountable task, especially when these chains move on continuous state spaces. In this paper, a method for accurate estimation of the spectral gap is developed for general state space Markov chains whose operators are non-negative and trace-class. The method is based on the fact that the second largest eigenvalue (and hence the spectral gap) of such operators can be bounded above and below by simple functions of the power sums of the eigenvalues. These power sums often have nice integral representations. A classical Monte Carlo method is proposed to estimate these integrals, and a simple sufficient condition for finite variance is provided. This leads to asymptotically valid confidence intervals for the second largest eigenvalue (and the spectral gap) of the Markov operator. In contrast with previously existing techniques, our method is not based on a near-stationary version of the Markov chain, which, paradoxically, cannot be obtained in a principled manner without bounds on the spectral gap. On the other hand, it can be quite expensive from a computational standpoint. The efficiency of the method is studied both theoretically and empirically.

KW - Data augmentation algorithm

KW - Eigenvalues

KW - Hilbert-Schmidt operator

KW - Markov chain

KW - Monte Carlo

UR - http://www.scopus.com/inward/record.url?scp=85068958213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068958213&partnerID=8YFLogxK

U2 - 10.1214/19-EJS1563

DO - 10.1214/19-EJS1563

M3 - Article

AN - SCOPUS:85068958213

VL - 13

SP - 1790

EP - 1822

JO - Electronic Journal of Statistics

JF - Electronic Journal of Statistics

SN - 1935-7524

IS - 1

ER -