Markov chain decomposition for convergence rate analysis
type: Item
instance of: scholarly article
title: Markov chain decomposition for convergence rate analysis
zbMATH Open document ID: 1017.60080
author: Neal Madras
author: Dana Randall
published in: The Annals of Applied Probability
publication date: 2003-05-06T00:00:00Z
review text: The authors consider a reversible Markov chain on a state space \(\Omega\) and estimate its special gap. Let \(P(x,dy)\) be the transition probability kernel of a Markov chain that is reversible with respect to a probability density. The authors describe the ``pieces'' of the chain \(P\). Let \(A_1,\dots, A_m\) be subsets of \(\Omega\) such that \(\bigcup A_i=\Omega\). For each \(i= 1,\dots, m\), the authors define a new Markov chain on \(A_i\). The transition kernel \(P_{[A_i]}\) of the new chain is \[ P_{[A_i]}(x,B)= P(x,B)+ 1_{[x\in B]} P(x, A^c_i),\qquad x\in A_i,\;B\subset A_i.\tag{1} \] Now they define \[ Z:= \sum^m_{i=1} \pi[A_i]\tag{2} \] and the ``maximum overlap'' \(\Theta\) of the covering \([A_1,\dots, A_m]\) by \[ \Theta:= \max_{x\in\Omega}\|i: x\in A_i\|.\tag{3} \] Then \[ 1\leq Z\leq\Theta.\tag{4} \] Also they introduce a crude model of the movement of the original chain among the ``pieces''. They consider a state space \(a_1,\dots, a_m\) of \(m\) points representing our \(m\) pieces and define the transition probabilities for a discrete Markov chain on this finite state space: \[ P_H(a_i, a_j)= {\pi[A_i, A_j]\over \Theta\pi[A_i]}\quad\text{and}\quad P_H(a_i, a_i)= 1-\sum_{j\neq i} P_H(a_i, a_j).\tag{5} \] To describe the rate of convergence to equilibrium, the authors use the spectral gap. For example the first theorem presented is Theorem 1.1 (State decomposition theorem). With the equations (1)--(5) it results \[ \text{Gap}(P)\geq {1\over\Theta^2} \text{Gap}(P_H(\min\text{ Gap } P_{[A_i]})),\qquad i= 1,\dots, m. \] Section 2 treats simulated tempering. Section 3 is devoted to the Metropolis algorithm and umbrella sampling. Section 4 is entitled ``State decomposition''. Section 5 treats density decomposition. The last part of the note contains an appendix, in which the authors consider the Caraciolo-Pelissetto-Sokal result and the Madras-Piccioni result.
Mathematics Subject Classification ID: 60J05
Mathematics Subject Classification ID: 65C40
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1906189
zbMATH Keywords: Markov chain
zbMATH Keywords: Monte Carlo
zbMATH Keywords: spectral gap
zbMATH Keywords: Metropolis-Hastings algorithm
zbMATH Keywords: simulated tempering
zbMATH Keywords: decomposition
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1026915617
OpenAlex ID: W2161269121
cites work: Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids
cites work: Comparison techniques for random walk on finite groups
cites work: Comparison theorems for reversible Markov chains
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Annealing Markov Chain Monte Carlo with Applications to Ancestral Inference
cites work: Q3961338
cites work: Approximating the Permanent
cites work: Q4231920
cites work: Markov chain algorithms for planar lattice structures
cites work: Q4527036
cites work: Fast convergence of the Glauber dynamics for sampling independent sets
cites work: Q4249733
cites work: Importance sampling for families of distributions
cites work: Q4693177
cites work: Q4249734
cites work: Geometric ergodicity and hybrid Markov chains
cites work: Geometric L2 and L1 convergence are equivalent for reversible Markov chains
cites work: Q3135094
cites work: Exponential convergence to equilibrium for a class of random-walk models
cites work: A note on Metropolis-Hastings kernels for general state spaces
cites work: Q3140234
DOI: 10.1214/AOAP/1026915617
description: scientific article; zbMATH DE number 1906189