Geometric inequalities for the eigenvalues of concentrated Markov chains
The article is devoted to the estimation of the spectral gap of an ergodic reversible Markov chain defined on a finite set. Let \(P(i,j)\) be the transition matrix, \(\pi\) be the stationary distribution of the chain. Then, by Theorem 3.1, if for some \(i^*\), \(\pi(i^*)>v^2\), then the second eigenvalue of \(P\) is \(\lambda_2^2\leq 1-K^2\varphi^2\), where \(v\approx 0.701\) is an absolute constant, \[ K=1-\sqrt{1-\pi(i^*)}(1+\sqrt{\pi(i^*)}), \] \(\varphi\) is the global symmetric isoperimetric constant of the chain. As a corollary one has \(\forall i\) \[ \|P^k(i,\cdot)-\pi(\cdot)\|^2_{\text{TV}}\leq {1-\pi(i)\over 4\pi(i)} (1-K^2\varphi^2)^k, \] where \(\|\cdot\|_{\text{TV}}\) is the total variance norm. This and other similar results are applied to estimate the confidence level of Metropolis-Hastings algorithm approximations to the absolute minimum of some function \(H\). It is noted that these results provide much slow convergence than estimates based on Poincaré's inequalities. But they works even if \(\min_{H(i)\not=H(j)}|H(i)-H(j)|\to 0\) when Poincaré's inequalities fail.
- Geometric bounds for eigenvalues of Markov chains
- A quantitative McDiarmid's inequality for geometrically ergodic Markov chains
- Subgaussian concentration inequalities for geometrically ergodic Markov chains
- Explicit bounds for geometric convergence of Markov chains
- Hoeffding's inequalities for geometrically ergodic Markov chains on general state space
- scientific article; zbMATH DE number 1531952
- The geometry of Markov chain limit theorems
- A quantitative McDiarmid's inequality for geometrically ergodic Markov chains
- Consistent estimation of the spectrum of trace class data augmentation algorithms
- Cheeger inequalities for absorbing Markov chains
- On the Convergence of Reversible Markov Chains
- Improved bounds for the large-time behaviour of simulated annealing
- Distributions of values of indefinite forms and higher-order spectral estimates for finite Markov chains.
- Eigenvalue inequalities for the Markov diffusion operator
This page was built for publication: Geometric inequalities for the eigenvalues of concentrated Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4503207)
