Strong stationary duality for Möbius monotone Markov chains : examples

• Autorzy: Lorek P. , Szekli R.
• Języki publikacji: EN

Abstrakty

EN

We construct strong stationary dual chains for nonsymmetric random walks on square lattice, for random walks on hypercube and for some Ising models on the circle. The strong stationary dual chains are all sharp and have the same state space as original chains.We use Möbius monotonicity of these chains with respect to some natural orderings of the corresponding state spaces. This method provides an alternative way to study mixing times for studied models.

Słowa kluczowe

EN

Markov chains; stochastic monotonicity; eigenvalues; Möbius monotonicity; strong stationary duality; strong stationary times; separation distance; mixing time; Ising model; hypercube

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2016
• Tom: Vol. 36, Fasc. 1
• Strony: 75--97
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Lorek P.

• Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland

autor

Szekli R.

• Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland

Bibliografia

• [1] D. J. Aldous, Finite-time implications of relaxation times for stochastically monotone processes, Probab. Theory Related Fields 77 (1988), pp. 137-145.
• [2] D. J. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), pp. 333-348.
• [3] D. J. Aldous and P. Diaconis, Strong uniform times and finite random walks, Adv. In Appl. Math. 8 (1987), pp. 69-97.
• [4] P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA, 1988.
• [5] P. Diaconis and J. A. Fill, Strong stationary times via a new form of duality, Ann. Probab. 18 (1990), pp. 1483-1522.
• [6] P. Diaconis and J. A. Fill, Examples for the theory of strong stationary duality with countable state spaces, Probab. Engrg. Inform. Sci. 4 (1990), pp. 157-180.
• [7] P. Diaconis and L. Miclo, On times to quasi-stationarity for birth and death processes, J. Theoret. Probab. 22 (2009), pp. 558-586.
• [8] P. Diaconis and L. Saloff-Coste, Separation cut-offs for birth and death chains, Ann. Appl. Probab. 16 (4) (2006), pp. 2098-2122.
• [9] J. Ding, E. Lubetzky, and Y. Peres, The mixing time evolution of Glauber dynamics for the mean-field Ising model, Comm. Math. Phys. 289 (2009), pp. 725-764.
• [10] J. Ding and Y. Peres, Mixing time for the Ising model: A uniform lower bound for all graphs, Ann. Inst. H. Poincaré Probab. Statist. 47 (4) (2011), pp. 1020-1028.
• [11] J. Ding and Y. Peres, Mixing time for the Ising model: A uniform lower bound for all graphs, arXiv: 0909.5162v2 [math.PR] (2013).
• [12] J. A. Fill, The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof, J. Theoret. Probab. 22 (2009), pp. 543-557.
• [13] J. A. Fill, On hitting times and fastest strong stationary times for skip-free and more general chains, J. Theoret. Probab. 22 (3) (2009), pp. 587-600.
• [14] J. A. Fill and V. Lyzinski, Hitting times and interlacing eigenvalues: a stochastic approach using intertwinings, J. Theoret. Probab. 27 (3) (2014), pp. 954-981.
• [15] T. P. Hayes and A. Sinclair, A general bound for mixing of single-site dynamics on graphs, Ann. Appl. Probab. 17 (3) (2007), pp. 931-952.
• [16] T. Huillet and S. Martinez, On Möbius duality and coarse-graining, J. Theoret. Probab., doi: 10.1007/s10959-014-0569-5 (2014).
• [17] D. A. Levin, M. Luczak, and Y. Peres, Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability, Probab. Theory Related Fields 146 (2010), pp. 223-265.
• [18] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2009.
• [19] P. Lorek and R. Szekli, Strong stationary duality for Möbius monotone Markov chains, Queueing Syst. 71 (2012), pp. 79-95.
• [20] P. Lorek and R. Szekli, Computable bounds on the spectral gap for unreliable Jackson networks, Adv. in Appl. Probab. 47 (2) (2015), arXiv: 1101.0332 [math.PR].
• [21] E. Lubetzky and A. Sly, Cutoff for the Ising model on the lattice, Invent. Math. 191 (2013), pp. 719-755.
• [22] J. G. Propp and D. B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures Algorithms 9 (1) (1996), pp. 223-252.
• [23] G.-C. Rota, On the foundations of combinatorial theory, I. Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete 2 (1964), pp. 340-368.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).