Mixing under monotone censoring

Jian Ding (University of Chicago)
Elchanan Mossel (UC Berkeley)


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


  • 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

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