Exit time tails from pairwise decorrelation in hidden Markov chains, with applications to dynamical percolation

Alan Hammond (University of Oxford)
Elchanan Mossel (University of California, Berkeley)
Gábor Pete (Technical University of Budapest)


Consider a Markov process $\omega_t$ at stationarity and some event $\mathcal{C}$ (a subset of the state-space of the process). A natural measure of correlations in the process is the pairwise correlation $\mathbb{P}[\omega_0,\omega_t \in \mathcal{C}] - \mathbb{P}[\omega_0 \in \mathcal{C}]^2$. A second natural measure is the probability of the continual occurrence event $\big\{ \omega_s \in \mathcal{C}, \, \forall \, s \in [0,t] \big\}$. We show that for reversible Markov chains, and any event $\mathcal{C}$, pairwise decorrelation of the event $\mathcal{C}$ implies a decay of the probability of the continual occurrence event $\big\{ \omega_s \in \mathcal{C}\, \forall \, s \in [0,t] \big\}$ as $t \to \infty$. We provide examples showing that our results are often sharp.

Our main applications are to dynamical critical percolation. Let $\mathcal{C}$ be the left-right crossing event of a large box, and let us scale time so that the expected number of changes to $\mathcal{C}$ is order 1 in unit time. We show that the continual connection event has superpolynomial decay. Furthermore, on the infinite lattice without any time scaling, the first exceptional time with an infinite cluster appears with an exponential tail.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-16

Publication Date: August 22, 2012

DOI: 10.1214/EJP.v17-2229


  • M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 132--140, 1987.
  • Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David. Derandomized graph products. Comput. Complexity 5 (1995), no. 1, 60--75. MR1319493 http://www.tau.ac.il/~nogaa/PDFS/derand5.pdf
  • Alon, Noga; Spencer, Joel H. The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdős. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, 2000. xviii+301 pp. ISBN: 0-471-37046-0 MR1885388
  • Benjamini, Itai; Kalai, Gil; Schramm, Oded. Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Études Sci. Publ. Math. No. 90 (1999), 5--43 (2001). MR1813223 arXiv:math.PR/9811157
  • Carne, Thomas Keith. A transmutation formula for Markov chains. Bull. Sci. Math. (2) 109 (1985), no. 4, 399--405. MR0837740
  • Garban, Christophe; Pete, Gábor; Schramm, Oded. The Fourier spectrum of critical percolation. Acta Math. 205 (2010), no. 1, 19--104. MR2736153 arXiv:0803.3750
  • C. Garban, G. Pete, and O. Schramm. Pivotal, cluster and interface measures for critical planar percolation. Preprint, arXiv:1008.1378
  • C. Garban, G. Pete, and O. Schramm. The scaling limits of dynamical and near-critical percolation. In preparation.
  • C. Garban and J. E. Steif. Lectures on noise sensitivity and percolation. In: Probability and statistical physics in two and more dimensions (D. Ellwood, C. Newman, V. Sidoravicius and W. Werner, ed.). Proceedings of the Clay Mathematical Institute Summer School and XIV Brazilian School of Probability (Buzios, Brazil), Clay Mathematics Proceedings 15 (2012), 49--154. arXiv:1102.5761
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Häggström, Olle; Peres, Yuval; Steif, Jeffrey E. Dynamical percolation. Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), no. 4, 497--528. MR1465800
  • A. Hammond, G. Pete, and O. Schramm. Local time on the exceptional set of dynamical percolation, and the Incipient Infinite Cluster. Preprint, arXiv:1208.3826
  • Hoory, Shlomo; Linial, Nathan; Wigderson, Avi. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439--561 (electronic). MR2247919 http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
  • Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937 http://pages.uoregon.edu/dlevin/MARKOV/
  • R. Lyons, with Y. Peres. Probability on trees and networks. Book in preparation, present version is at http://mypage.iu.edu/~rdlyons.
  • Mossel, Elchanan; O'Donnell, Ryan; Regev, Oded; Steif, Jeffrey E.; Sudakov, Benny. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Israel J. Math. 154 (2006), 299--336. MR2254545 arXiv:math.PR/0410560
  • Schramm, Oded; Smirnov, Stanislav. On the scaling limits of planar percolation. With an appendix by Christophe Garban. Ann. Probab. 39 (2011), no. 5, 1768--1814. MR2884873 arXiv:1101.5820
  • Schramm, Oded; Steif, Jeffrey E. Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2) 171 (2010), no. 2, 619--672. MR2630053 arXiv:math.PR/0504586
  • Smirnov, Stanislav; Werner, Wendelin. Critical exponents for two-dimensional percolation. Math. Res. Lett. 8 (2001), no. 5-6, 729--744. MR1879816 arXiv:math.PR/0109120
  • Steif, Jeffrey E. A survey of dynamical percolation. Fractal geometry and stochastics IV, 145--174, Progr. Probab., 61, Birkhäuser Verlag, Basel, 2009. MR2762676 arXiv:0901.4760
  • Varopoulos, Nicholas Th. Long range estimates for Markov chains. Bull. Sci. Math. (2) 109 (1985), no. 3, 225--252. MR0822826
  • Werner, Wendelin. Lectures on two-dimensional critical percolation. Statistical mechanics, 297--360, IAS/Park City Math. Ser., 16, Amer. Math. Soc., Providence, RI, 2009. MR2523462 arXiv:0710.0856

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.