Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
type: Item
instance of: scholarly article
title: Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
zbMATH Open document ID: 1045.60073
DOI: 10.1016/S0304-4149(99)00101-5
author: Wai Kong Yuen
published in: Stochastic Processes and their Applications
publication date: 2004-09-07T00:00:00Z
review text: Let \(P\) be a transition probability kernel of a discrete-time Markov chain on \(\mathbb R^ {n}\) with an invariant probability measure \(\pi \). Suppose that \(P\) has the form \(P(x,dy) = \alpha (x)d\delta _ {x}(y) + p(x,y)\,dy\), \(\delta _ {x}\) being the point mass at \(x\), and that \(\pi \) has a density with respect to the Lebesgue measure. The kernel \(P\) defines a positivity preserving contraction on \(L^ 2(\pi )\), denoted again by \(P\). Assume that the Markov chain is reversible with respect to the measure \(\pi \), hence \(P\) is a self-adjoint operator on \(L^ 2(\pi )\). Set \(\lambda _ 0(P) = \inf \sigma (P_ {| \mathbf 1^ {\bot }})\), \(\lambda _ 1(P) = \sup \sigma (P_ {| \mathbf 1^ {\bot }})\) and \(\rho = \max ( | \lambda _ 0(P)| , | \lambda _ 1(0)| )\), where \(\sigma (B)\) denotes the spectrum of a linear operator \(B\). Define Cheeger's constant by \[ k = \inf _ {0<\pi (A)<1}\,{\int \mathbf 1_ {A}(x)P(x,\complement A) d\pi (x) \over \pi (A)\pi (\complement A)}. \] \textit{G. F. Lawler} and \textit{A. D. Sokal} [Trans. Am. Math. Soc. 309, No. 2, 557--580 (1988; Zbl 0716.60073)] proved that \(k^ 2/8 \leq 1-\lambda _ 1(P) \leq k\). It is well known that the spectral radius \(\varrho \) is closely related to the convergence rate to the invariant measure \(\pi \). A geometric argument is used to obtain lower bounds on \(\inf \sigma ((I-P)_ {| \mathbf 1^ \bot }) = 1-\lambda _ 1(P)\) and an upper bound on \(k\), consequently, to get bounds on \(\lambda _ 1(P)\) (and \(\rho \)). Moreover, results on comparison of spectral radii of two reversible Markov chains are proven and several examples are discussed in detail.
reviewed by: Jan Seidler
Mathematics Subject Classification ID: 60J05
zbMATH DE Number: 2098067
zbMATH Keywords: Markov chains
zbMATH Keywords: reversible measures
zbMATH Keywords: spectral radius
MaRDI profile type: Publication
cites work: On rates of convergence of stochastic relaxation for Gaussian and non- Gaussian distributions
cites work: Comparing sweep strategies for stochastic relaxation
cites work: Brownian motion and the fundamental frequency of a drum
cites work: Rates of convergence for everywhere-positive Markov chains
cites work: Q3223360
cites work: Q3995195
cites work: Comparison theorems for reversible Markov chains
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Sampling from log-concave distributions
cites work: Q4272795
cites work: Sampling-Based Approaches to Calculating Marginal Densities
cites work: A Markov chain on the symmetric group and Jack symmetric functions
cites work: Accelerating Gaussian diffusions
cites work: On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds
cites work: Approximating the Permanent
cites work: Q4146094
cites work: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
cites work: Computable bounds for geometric convergence rates of Markov chains
cites work: Diffusion of color in the simple exclusion process
cites work: Q4185363
cites work: Shift-coupling and convergence rates of ergodic averages
cites work: Geometric ergodicity and hybrid Markov chains
cites work: Rates of convergence for Gibbs sampling for variance component models
cites work: Minorization Conditions and Convergence Rates for Markov Chain Monte Carlo
cites work: Markov chain convergence: From finite to infinite
cites work: Q4340096
cites work: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains
cites work: Q4272782
cites work: Markov chains for exploring posterior distributions. (With discussion)
Recommended article: Explicit bounds for geometric convergence of Markov chains
Recommended article: Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rn
Recommended article: Computable bounds for geometric convergence rates of Markov chains
Recommended article: Convergence rates in geometricergodicity for discrete-time Markov chains
Recommended article: Geometric convergence rates for time-sampled Markov chains
Recommended article: Geometric Convergence Rates for Stochastically Ordered Markov Chains
description: scientific article; zbMATH DE number 2098067