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

O m e g a

with stationary distribution

p i

and a monotone set

A s u b s e t O m e g a

. We consider the chain

M^{'}

which is the same as the chain

M

started at some

x i n A

except that moves of

M

of the form

x o y

where

x i n A

and

y o t i n A

are {em censored} and replaced by the move

x o x

. If

M

is ergodic and

A

is connected, the new chain converges to

p i

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.

Recommendations

Cited In (1)

This page was built for publication: Mixing under monotone censoring