### Mixing under monotone censoring

**Jian Ding**

*(University of Chicago)*

**Elchanan Mossel**

*(UC Berkeley)*

#### 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'$ 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'$ 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.

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

Pages: 1-6

Publication Date: July 20, 2014

DOI: 10.1214/ECP.v19-3157

#### References

- D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
- Ellis, Richard S.; Newman, Charles M. Limit theorems for sums of dependent random variables occurring in
statistical mechanics.
*Z. Wahrsch. Verw. Gebiete*44 (1978), no. 2, 117--139. MR0503333 - Ellis, Richard S.; Newman, Charles M.; Rosen, Jay S. Limit theorems for sums of dependent random variables occurring in
statistical mechanics. II. Conditioning, multiple phases, and
metastability.
*Z. Wahrsch. Verw. Gebiete*51 (1980), no. 2, 153--169. MR0566313 - Fortuin, C. M.; Kasteleyn, P. W.; Ginibre, J. Correlation inequalities on some partially ordered sets.
*Comm. Math. Phys.*22 (1971), 89--103. MR0309498 - Goldreich, Oded; Goldwasser, Shafi; Lehman, Eric; Ron, Dana; Samorodnitsky, Alex. Testing monotonicity.
*Combinatorica*20 (2000), no. 3, 301--337. MR1774842 - Jerrum, Mark; Sinclair, Alistair. Approximating the permanent.
*SIAM J. Comput.*18 (1989), no. 6, 1149--1178. MR1025467 - Lawler, Gregory F.; Sokal, Alan D. Bounds on the $L^ 2$ spectrum for Markov chains and Markov
processes: a generalization of Cheeger's inequality.
*Trans. Amer. Math. Soc.*309 (1988), no. 2, 557--580. MR0930082 - 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 - Rubinfeld, Ronitt; Sudan, Madhu. Robust characterizations of polynomials with applications to program
testing.
*SIAM J. Comput.*25 (1996), no. 2, 252--271. MR1379300

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