Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). (Q1877387)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). |
scientific article |
Statements
Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). (English)
0 references
7 September 2004
0 references
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.
0 references
Markov chains
0 references
reversible measures
0 references
spectral radius
0 references
0 references
0 references
0 references