Mixing times for uniformly ergodic Markov chains. (English) Zbl 0941.60080
Summary: Consider the class of discrete time, general state space Markov chains which satisfy a “uniform ergodicity under sampling” condition. There are many ways to quantify the notion of “mixing time”, i.e., time to approach stationarity from a worst initial state. We prove results asserting equivalence (up to universal constants) of different quantifications of mixing time. This work combines three areas of Markov theory which are rarely connected: the potential-theoretical characterization of optimal stopping times, the theory of stability and convergence to stationarity for general-state chains, and the theory of surrounding mixing times for finite-state chains.
MSC:
| 60J05 | Discrete-time Markov processes on general state spaces |
References:
| [1] | Aldous, D. J., Some inequalities for reversible Markov chains, J. London Math. Soc. (2), 25, 564-576 (1982) · Zbl 0489.60077 |
| [2] | Aldous, D. J.; Fill, J. A., Reversible Markov Chains and Random Walks on Graphs (1997), Book in preparation |
| [3] | Baxter, J. R.; Chacon, R. V., Stopping times for recurrent Markov processes, Illinois J. Math., 20, 467-475 (1976) · Zbl 0335.60036 |
| [4] | Bayer, D.; Diaconis, P., Trailing the dovetail shuffle to its lair, Ann. Appl. Probab, 2, 294-313 (1992) · Zbl 0757.60003 |
| [5] | Chung, F. R.K.; Graham, R. L., Stratified random walks on the \(n\)-cube, (Technical report (1996), Univ. Pennsylvania) · Zbl 0886.60068 |
| [6] | Dellacherie, C.; Meyer, P.-A., Probabilités et Potentiel: Théorie Discrète du Potentiel (1983), Hermann: Hermann Paris · Zbl 0526.60001 |
| [7] | Diaconis, P., Group Representations in Probability and Statistics (1988), Institute of Mathematical Statistics: Institute of Mathematical Statistics Hayward, CA · Zbl 0695.60012 |
| [8] | Diaconis, P., The cut-off phenomenon in finite Markov chains, (Proc. Nat. Acad. Sci. USA, 93 (1996)), 1659-1664 · Zbl 0849.60070 |
| [9] | Diaconis, P.; Fill, J. A., Strong stationary times via a new form of duality, Ann. Probab., 18, 1483-1522 (1990) · Zbl 0723.60083 |
| [10] | Diaconis, P.; Saloff-Coste, L., Nash inequalities for finite Markov chains, J. Theoret. Probab., 9, 459-510 (1996) · Zbl 0870.60064 |
| [11] | Diaconis, P.; Saloff-Coste, L., Walks on generating sets of groups, Probab. Theory Related Fields, 105, 393-421 (1996) · Zbl 0847.60081 |
| [12] | Dinges, H., Stopping sequences, (Séminaire de Probabilités VIII. Séminaire de Probabilités VIII, Lecture Notes in Math., vol. 381 (1974), Springer: Springer Berlin), 27-36 · Zbl 0287.60054 |
| [13] | Frieze, A.; Kannan, R.; Polson, N., Sampling from log-concave distributions, Ann. Appl. Probab., 4, 812-837 (1994) · Zbl 0813.60060 |
| [14] | Goldstein, S., Maximal coupling, Z. Wahrsch. Verw. Gebiete, 46, 193-204 (1979) · Zbl 0398.60097 |
| [15] | Jerrum, M.; Sinclair, A., Approximating the permanent, SIAM J. Comput., 18, 1149-1178 (1989) · Zbl 0723.05107 |
| [16] | Kannan, R.; Lovász, L.; Simonovits, M., Random walks and an \(O(n^5)\) volume algorithm, Random Struct. Alg., 8 (1997), to appear · Zbl 0895.60075 |
| [17] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0089.13704 |
| [18] | Lindvall, T., Lectures on the Coupling Method (1992), Wiley: Wiley New York · Zbl 0760.60078 |
| [19] | Lovász, L.; Simonovits, M., Random walks in a convex body and an improved volume algorithm, Random Struct. Alg., 4, 359-412 (1993) · Zbl 0788.60087 |
| [20] | Lovász, L.; Winkler, P., Efficient stopping rules for Markov chains, (Proc. 27th ACM Symp. Theory of Computing (1995)), 76-82 · Zbl 0921.60062 |
| [21] | Lovász, L.; Winkler, P., Fast mixing in a Markov chain (1997), In preparation |
| [22] | Lovász, L.; Winkler, P., Reversal of Markov chains and the forget time (1997), In preparation |
| [23] | Meyn, S. P.; Tweedie, R. L., Markov Chains and Stochastic Stability (1993), Springer: Springer Berlin · Zbl 0925.60001 |
| [24] | Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039 |
| [25] | Nummelin, E., General Irreducible Markov Chains and Non-Negative Operators (1984), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0551.60066 |
| [26] | Orey, S., Limit Theorems for Markov Chain Transition Probabilities (1971), Van Nostrand: Van Nostrand Princeton, NJ · Zbl 0295.60054 |
| [27] | Pitman, J. W., Occupation measures for Markov chains, Adv. Appl. Probab., 9, 86 (1977) · Zbl 0389.60053 |
| [28] | Revuz, D., Remarks on the filling scheme for recurrent Markov chains. Duke Math. J. 45, 681, 689.; Revuz, D., Remarks on the filling scheme for recurrent Markov chains. Duke Math. J. 45, 681, 689. · Zbl 0395.60059 |
| [29] | Revuz, D., Markov Chains (1984), North-Holland: North-Holland Amsterdam · Zbl 0539.60073 |
| [30] | Rost, H., The stopping distributions of a Markov process, Invent. Math., 14, 1-16 (1971) · Zbl 0225.60025 |
| [31] | Sinclair, A. J., Algorithms for Random Generation and Counting (1993), Birkhauser: Birkhauser Basel · Zbl 0780.68096 |
| [32] | Syski, R., Passage Times for Markov Chains (1992), IOS Press: IOS Press Amsterdam · Zbl 0804.60065 |
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.
