Mixing time bounds via bottleneck sequences. (English) Zbl 1403.60060
Summary: We provide new upper bounds for mixing times of general finite Markov chains. We use these bounds to show that the total variation mixing time is robust under rough isometry for bounded degree graphs that are roughly isometric to trees.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60J27 | Continuous-time Markov processes on discrete state spaces |
References:
| [1] | Aldous, D., Some inequalities for reversible Markov chains, J. Lond. Math. Soc, 25, 564-576, (1982) · Zbl 0489.60077 · doi:10.1112/jlms/s2-25.3.564 |
| [2] | Aldous, D., James, A.F.: Reversible Markov chains and random walks on graphs (2002). Unfinished monograph, recompiled 2014. http://www.stat.berkeley.edu/ aldous/RWG/book.html |
| [3] | Benjamini, I.: Coarse geometry and randomness. In: École d’Été de Probabilités de Saint-Flour XLI—2011. Lecture Notes in Mathematics, vol. 2100. Springer, Berlin (2013) · Zbl 1282.05001 |
| [4] | Diestel, R., Müller, M.: Connected tree-width. Combinatorica. http://arxiv.org/abs/1211.7353 (to appear) |
| [5] | Ding, J.; Lee, JR; Peres, Y., Cover times, blanket times, and majorizing measures, Ann. Math., 175, 1409-1471, (2012) · Zbl 1250.05098 · doi:10.4007/annals.2012.175.3.8 |
| [6] | Ding, J.; Peres, Y., Sensitivity of mixing times, Electron. Commun. Probab., 18, 1-6, (2013) · Zbl 1307.60051 · doi:10.1214/ECP.v18-2765 |
| [7] | Fountoulakis, N.; Reed, BA, Faster mixing and small bottlenecks, Probab. Theory Relat. Fields, 137, 475-486, (2007) · Zbl 1113.60073 |
| [8] | Goel, S.; Montenegro, R.; Tetali, P., Mixing time bounds via the spectral profile, Electron. J. Probab, 11, 1-26, (2006) · Zbl 1109.60061 · doi:10.1214/EJP.v11-300 |
| [9] | Griffiths, S.; Kang, R.; Oliveira, R.; Patel, V., Tight inequalities among set hitting times in Markov chains, Proc. Am. Math. Soc., 142, 3285-3298, (2014) · Zbl 1300.60083 · doi:10.1090/S0002-9939-2014-12045-4 |
| [10] | Hermon, J.: On sensitivity of uniform mixing times. Ann. Inst. Henri Poincaré Probab. Stat. http://arxiv.org/abs/1607.01672 (to appear) |
| [11] | Hermon, J., Peres, Y.: A characterization of \({L}_2\) mixing and hypercontractivity via hitting times and maximal inequalities. Probab. Theory Relat. Fields. http://arxiv.org/abs/1609.07557 (to appear) · Zbl 1403.60067 |
| [12] | Jerrum, M., Sinclair, A.: Conductance and the rapid mixing property for markov chains: the approximation of permanent resolved. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 235-244. ACM (1988) |
| [13] | Kozma, G., On the precision of the spectral profile, ALEA, 3, 321-329, (2007) · Zbl 1162.60335 |
| [14] | Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009) · Zbl 1160.60001 |
| [15] | Lovász, L., Kannan, R.: Faster mixing via average conductance. In: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing · Zbl 1345.60078 |
| [16] | Lovász, L., Winkler, P.: Efficient stopping rules for Markov chains. In: Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, pp. 76-82. ACM (1995) · Zbl 0921.60062 |
| [17] | Moon, JW, Random walks on random trees, J. Aust. Math. Soc., 15, 42-53, (1973) · Zbl 0265.60065 · doi:10.1017/S144678870001274X |
| [18] | Morris, B.; Peres, Y., Evolving sets, mixing and heat kernel bounds, Probab. Theory Relat. Fields, 133, 245-266, (2005) · Zbl 1080.60071 · doi:10.1007/s00440-005-0434-7 |
| [19] | Oliveira, RI, Mixing and hitting times for finite Markov chains, Electron. J. Probab., 17, 1-12, (2012) · Zbl 1251.60059 |
| [20] | Peres, Y.; Sousi, P., Mixing times are hitting times of large sets, J. Theor. Probab., 42, 1-32, (2013) · Zbl 1323.60094 |
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.
