Mixing under monotone censoring

2013/11/23 by Jian Ding, Ding, Jian, Elchanan Mossel +1 · 2 citations
Mathematics · #60J10 #68Q52 #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:60J10 #msc:68Q52

paper · pdf · doi:10.48550/arxiv.1311.5945

6 pages

openalex publication_date 2013/11/23 · arxiv created 2013/12/02 · arxiv updated 2013/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We initiate the study of mixing times of Markov chain under monotone censoring. Suppose we have some Markov Chain M on a state space Ω with stationary distribution π and a monotone set A ⊂ Ω. We consider the chain M' which is the same as the chain M started at some x ∈ A except that moves of M of the form x → y where x ∈ A and y ∉ A are \em censored and replaced by the move x → x. If M is ergodic and A is connected, the new chain converges to π conditional on A. In this paper we are interested in the mixing time of the chain M' in terms of properties of M and A. Our results are based on new connections with the field of property testing. A number of open problems are presented.

Cited by

• Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube
• On the Spectral Expansion of Monotone Subsets of the Hypercube

Related

• Elementary Bounds On Mixing Times for Decomposable Markov Chains
• Bounds on Lifting Continuous Markov Chains to Speed Up Mixing
• A Lower Bound on the Mixing Time of Uniformly Ergodic Markov Chains in Terms of the Spectral Radius
• Sharp Mixing Rates for Markov Chains on General Spaces with Unbounded Random Environments
• Quantitative Convergence Rates for Stochastically Monotone Markov Chains