Mixing under monotone censoring

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 $\Omega$ with stationary distribution $\pi$ and a monotone set $A\subset \Omega$. We consider the chain $M^{\prime }$ which is the same as the chain $M$ started at some $x\in A$ except that moves of $M$ of the form $x\to y$ where $x\in A$ and $y\notin A$ are {\em censored} and replaced by the move $x\to x$. If $M$ is ergodic and $A$ is connected, the new chain converges to $\pi$ conditional on $A$. In this paper we are interested in the mixing time of the chain $M^{\prime }$ 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.

arXiv comment6 pages