×

Expectations for nonreversible Markov chains. (English) Zbl 0946.60067

The paper is concerned with a Markov chain \(X=(X_n, n\geq 0)\), taking values in a compact separable metric space \(S\) and let \(P(x,A)\) be its transitional probability which is supposed to be irreducible, i.e., for each upon set \(U\subset S\) and each \(x\in S\), there exists \(k\geq 1\) such that \(P^k(x, U)>0\). Let \(\mu\) be the invariant measure for \(P(\cdot,\cdot)\) and \(f\) be the continuous mapping of \(S\) into \([0,1]\). Denote \(\mu_f= \int_Sf(x) \mu(dx)\) and let \({\mathbf P}_x\) signify the conditional probability provided \(X_0=x\). Let the operator \(P\) be generated by the kernel \(P(\cdot,\cdot)\) by the usual way: \(Pf (x) =\int_Sf(y) P(x,dy)\). The author is interested in obtaining bounds uniform in the staring point \(x\) for \({\mathbf P}_x\{n^{-1} \sum^n_{k=1} f(X_k)-\mu_f\geq \varepsilon\}\). The main result is as follows: \[ \inf_x{\mathbf P}_x \left\{n^{-1} \sum^n_{k=1} f(X_k)-\mu_f \geq\varepsilon \right\}\leq \exp\bigl\{-n \beta \varepsilon^2(1- \varepsilon)2^8 \bigr\}, \] where \(\beta\) is, roughly speaking, the square root of the distance between zero and the remainder part of the spectrum of the operator \(P-I\).

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anantharam, V., A large deviation approach to error exponents in source coding and hypothesis testing, IEEE Trans. Inform. Theory, 36, 938-943 (1990) · Zbl 0707.94004
[2] Besag, J.; Green, P. J., Spatial statistics and Bayesian computation, J. Roy. Statist. Soc. Ser. B, 55, 25-37 (1993) · Zbl 0800.62572
[3] Csiszár, I.; Cover, T. M.; Choi, B., Conditional limit theorems under Markov conditioning, IEEE Trans. Inform. Theory, 33, 788-801 (1987) · Zbl 0628.60037
[4] Dembo, A.; Zeitouni, O., Large Deviations Techniques and Applications (1993), Jones & Bartlett: Jones & Bartlett Boston · Zbl 0793.60030
[5] Diaconis, P.; Saloff-Coste, L., Comparison theorems for reversible Markov chains, Ann. Appl. Probab., 3, 696-730 (1992) · Zbl 0799.60058
[6] Diaconis, P.; Saloff-Coste, L., Nash inequalities for finite Markov chains, J. Theoret. Probab., 9, 459-510 (1996) · Zbl 0870.60064
[7] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 1, 36-61 (1991) · Zbl 0731.60061
[8] Dinwoodie, I. H., A probability inequality for the occupation measure of a reversible Markov chain, Ann. Appl. Probab., 5, 37-43 (1995) · Zbl 0829.60022
[9] Dinwoodie, I. H., A bound on the rate of convergence for the discrete Gibbs sampler, Probab. Engrg. Inform. Sci., 9, 211-215 (1995) · Zbl 1335.60139
[10] Fill, J. A., Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab., 1, 62-87 (1991) · Zbl 0726.60069
[11] Gantmacher, F. R., Matrix Theory (1959), Chelsea: Chelsea New York · Zbl 0085.01001
[12] Gillman, D., A Chernoff bound for random walks on expander graphs, Proceedings of the 34th Symposium on Foundations of Computer Science (1993), IEEE Comput. Soc: IEEE Comput. Soc Los Alamitos
[13] Kato, T., Perturbation Theory for Linear Operators (1966), Springer-Verlag: Springer-Verlag New York · Zbl 0148.12601
[14] Krein, M. G.; Rutman, M. A., Linear operators leaving invariant a cone in a Banach space, Amer. Math. Soc. Transl. (1950), Amer. Math. Soc: Amer. Math. Soc Providence, p. 1-128 · Zbl 0030.12902
[15] Lawler, G. F.; Sokal, A. D., Bounds on the \(L^2\), Trans. Amer. Math. Soc., 309, 557-580 (1988) · Zbl 0716.60073
[16] Meyn, S. P.; Tweedie, R. L., Computable bounds for geometric convergence rates of Markov chains, Ann. Appl. Probab., 4, 981-1011 (1994) · Zbl 0812.60059
[17] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge Univ. Press: Cambridge Univ. Press New York · Zbl 0849.68039
[18] Rellich, F., Störungstheorie der Spektralzerlegung, IV, Math. Ann., 117, 356-382 (1940) · JFM 66.0551.02
[19] Smith, A. F.M.; Roberts, G. O., Bayesian computation via the Gibbs sampler and related Markov chain Monte Carlo methods, J. Roy. Statist. Soc. Ser. B, 55, 3-23 (1993) · Zbl 0779.62030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.