Correction to: “Speeding up Markov chains with deterministic jumps”. (English) Zbl 1474.60178
From the text: This article [the authors, ibid. 178, No. 3–4, 1193–1214 (2020; Zbl 1468.60088)] was inadvertently published in Volume 178(3–4) December 2020, when it should have been published in the special issue honouring Professor Harry Kesten.
Springer Nature apologizes for this inconvenience.
Springer Nature apologizes for this inconvenience.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60J22 | Computational methods in Markov chains |
Citations:
Zbl 1468.60088References:
| [1] | Anderson, HC; Diaconis, P., Hit and run as a unifying device, J. Soc. Francaise Statist., 148, 5-28 (2007) · Zbl 1441.60002 |
| [2] | Avena, L.; Güldaş, H.; van der Hofstad, R.; den Hollander, F., Mixing times of random walks on dynamic configuration models, Ann. Appl. Probab., 28, 4, 1977-2002 (2018) · Zbl 1402.60013 · doi:10.1214/17-AAP1289 |
| [3] | Benaïm, M.; Le Borgne, S.; Malrieu, F.; Zitt, P-A, Qualitative properties of certain piecewise deterministic Markov processes, Ann. Inst. Henri Poincaré Probab. Stat., 51, 3, 1040-1075 (2015) · Zbl 1325.60123 · doi:10.1214/14-AIHP619 |
| [4] | Boardman, S., Saloff-Coste, L.: The hit-and-run version of top-to-random (2020, in preparation) |
| [5] | Bordenave, C., Lacoin, H.: Cutoff at the entropic time for random walks on covered expander graphs (2018). Preprint arXiv:1812.06769 |
| [6] | Bordenave, C., Qiu, Y., Zhang, Y.: Spectral gap of sparse bistochastic matrices with exchangeable rows with application to shuffle-and-fold maps (2018). Preprint arXiv:1805.06205 |
| [7] | Breuillard, E.; Varjú, P., Irreducibility of random polynomials of large degree, Acta Math., 223, 2, 195-249 (2019) · Zbl 1459.11079 · doi:10.4310/ACTA.2019.v223.n2.a1 |
| [8] | Breuillard, E., Varjú, P.: Cut-off phenomenon for the ax+b Markov chain over a finite field (2019). Preprint arXiv:1909.09053 |
| [9] | Chung, FRK; Diaconis, P.; Graham, RL, Random walks arising in random number generation, Ann. Probab., 15, 3, 1148-1165 (1987) · Zbl 0622.60016 · doi:10.1214/aop/1176992088 |
| [10] | Conchon-Kerjan, G.: Cutoff for random lifts of weighted graphs (2019). Preprint arXiv:1908.02898 |
| [11] | Constantin, P.; Kiselev, A.; Ryzhik, L.; Zlatoš, A., Diffusion and mixing in fluid flow, Ann. Math. (2), 168, 2, 643-674 (2008) · Zbl 1180.35084 · doi:10.4007/annals.2008.168.643 |
| [12] | Diaconis, P.: Group representations in probability and statistics. Institute of Mathematical Statistics, Hayward, CA (1988) · Zbl 0695.60012 |
| [13] | Diaconis, P., Some things we’ve learned (about Markov chain Monte Carlo), Bernoulli, 19, 4, 1294-1305 (2013) · Zbl 1412.60109 · doi:10.3150/12-BEJSP09 |
| [14] | Diaconis, P., Probabilizing Fibonacci Numbers. Connections in Discrete Mathematics (2018), Cambridge: Cambridge University Press, Cambridge · Zbl 1431.11027 |
| [15] | Diaconis, P.; Graham, R., An affine walk on the hypercube. Asymptotic methods in analysis and combinatorics, J. Comput. Appl. Math., 41, 1-2, 215-235 (1992) · Zbl 0754.60074 · doi:10.1016/0377-0427(92)90251-R |
| [16] | Diaconis, P.; Graham, R., Binomial coefficient codes over GF(2). A collection of contributions in honour of Jack van Lint, Discret. Math., 106/107, 181-188 (1992) · Zbl 0754.94020 · doi:10.1016/0012-365X(92)90545-Q |
| [17] | Diaconis, P.; Holmes, S.; Neal, RM, Analysis of a nonreversible Markov chain sampler, Ann. Appl. Probab., 10, 3, 726-752 (2000) · Zbl 1083.60516 · doi:10.1214/aoap/1019487508 |
| [18] | Diaconis, P.; Miclo, L., On the spectral analysis of second-order Markov chains, Ann. Fac. Sci. Toulouse Math. (6), 22, 3, 573-621 (2013) · Zbl 1302.60103 · doi:10.5802/afst.1383 |
| [19] | Diaconis, P.; Saloff-Coste, L., Moderate growth and random walk on finite groups, Geom. Funct. Anal., 4, 1, 1-36 (1994) · Zbl 0795.60005 · doi:10.1007/BF01898359 |
| [20] | Diaconis, P.; Shahshahani, M., Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18, 1, 208-218 (1987) · Zbl 0617.60009 · doi:10.1137/0518016 |
| [21] | Diaconis, P.; Sturmfels, B., Algebraic algorithms for sampling from conditional distributions, Ann. Stat., 26, 1, 363-397 (1998) · Zbl 0952.62088 · doi:10.1214/aos/1030563990 |
| [22] | Ding, J., Peres, Y.: Sensitivity of mixing times. Electron. Commun. Probab.18(88), 6 pp (2013) · Zbl 1307.60051 |
| [23] | Eberhard, S., Varjú, P.: Mixing time of the Chung-Diaconis-Graham random process (2020). Preprint arXiv:2003.08117 · Zbl 1478.60201 |
| [24] | Ganguly, S., Peres, Y.: Permuted random walk exits typically in linear time. In: ANALCO14—Meeting on Analytic Algorithmics and Combinatorics, pp. 74-81. SIAM, Philadelphia (2014) · Zbl 1430.05117 |
| [25] | Gerencsér, B.; Hendrickx, JM, Improved mixing rates of directed cycles by added connection, J. Theoret. Probab., 32, 2, 684-701 (2019) · Zbl 1485.05164 · doi:10.1007/s10959-018-0861-x |
| [26] | Greenhalgh, A.: On a model for random random-walks on finite groups (1990). Unpublished manuscript · Zbl 0872.60053 |
| [27] | Guralnick, RM; Müller, P., Exceptional polynomials of affine type, J. Algebra, 194, 2, 429-454 (1997) · Zbl 0911.11049 · doi:10.1006/jabr.1997.7028 |
| [28] | Hermon, J., On sensitivity of uniform mixing times, Ann. Inst. Henri Poincaré Probab. Stat., 54, 1, 234-248 (2018) · Zbl 1396.60085 · doi:10.1214/16-AIHP802 |
| [29] | Hermon, J., Peres, Y.: On sensitivity of mixing times and cutoff. Electron. J. Probab. 23, Paper No. 25, 34 pp (2018) · Zbl 1387.60112 |
| [30] | Hermon, J., Sly, A., Sousi, P.: Universality of cutoff for quasi-random graphs (2020). Preprint arXiv:2008.08564 |
| [31] | Hildebrand, M., A survey of results on random random walks on finite groups, Probab. Surv., 2, 33-63 (2005) · Zbl 1189.60016 · doi:10.1214/154957805100000087 |
| [32] | Hildebrand, M., A lower bound for the Chung-Diaconis-Graham random process, Proc. Am. Math. Soc., 137, 4, 1479-1487 (2009) · Zbl 1159.60008 · doi:10.1090/S0002-9939-08-09687-1 |
| [33] | Kapfer, SC; Krauth, W., Irreversible local Markov chains with rapid convergence towards equilibrium, Phys. Rev. Lett., 119, 24, 240603 (2017) · doi:10.1103/PhysRevLett.119.240603 |
| [34] | Lubetzky, E.; Peres, Y., Cutoff on all Ramanujan graphs, Geom. Funct. Anal., 26, 4, 1190-1216 (2016) · Zbl 1351.05208 · doi:10.1007/s00039-016-0382-7 |
| [35] | Lubetzky, E.; Sly, A., Cutoff phenomena for random walks on random regular graphs, Duke Math. J., 153, 3, 475-510 (2010) · Zbl 1202.60012 · doi:10.1215/00127094-2010-029 |
| [36] | Malrieu, F., Some simple but challenging Markov processes, Ann. Fac. Sci. Toulouse Math. (6), 24, 4, 857-883 (2015) · Zbl 1333.60185 · doi:10.5802/afst.1468 |
| [37] | Neal, R.M.: Improving asymptotic variance of mcmc estimators: non-reversible chains are better (2004). Preprint arXiv:math/0407281 |
| [38] | Neville, R., III.: On lower bounds of the Chung-Diaconis-Graham random process. Ph.D. thesis, State University of New York at Albany (2011) |
| [39] | Ottino, JM, The Kinematics of Mixing: Stretching, Chaos, and Transport (1989), Cambridge: Cambridge University Press, Cambridge · Zbl 0721.76015 |
| [40] | Pymar, R.; Sousi, P., A permuted random walk exits faster, ALEA Lat. Am. J. Probab. Math. Stat., 11, 1, 185-195 (2014) · Zbl 1295.60084 |
| [41] | Rallabandi, B.; Wang, C.; Hilgenfeldt, S., Analysis of optimal mixing in open-flow mixers with time-modulated vortex arrays, Phys. Rev. Fluids, 2, 6, 064501 (2017) · doi:10.1103/PhysRevFluids.2.064501 |
| [42] | Wilson, DB, Random random walks on \({\mathbb{Z}}_2^d\), Probab. Theory Related Fields, 108, 4, 441-457 (1997) · Zbl 0896.60034 · doi:10.1007/s004400050116 |
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.
