Random walk on monotone subsets of $\{0,1\}^n$

Workshop introduction

In general, we will use the following notation in the problem list. We consider aperiodic irreducible Markov chains on a state space, $\Omega$ with unique invariant (stationary) distribution $\pi$. In the discrete time setting we allow the matrix $(P)_{x,y\in\Omega}$ with $P_{xy}=P(x,y)$ to denote the transition matrix of the Markov chain.

A chain is reversible if $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in\Omega$. $Q(x,y)=\pi(x)P(x,y)$ is the edge measure on $(x,y)$. We denote by $t_{\mbox{mix}}$ the total variation mixing time defined as

and set $t_{\mbox{mix}}=t_{\mbox{mix}}(\epsilon)$, where the total variation distance

Question context

Let $A\subset \{0,1\}^n$ be a monotone subset of the hypercube: for all $x\in A$, if $y$ satisfies $y_i\geq x_i$ for all $1\leq i\leq n$, then $y\in A$. The random walk picks a coordinate at random, flip it, and accepts the move only if it remains in $A$.

Historical workshop record. Current open/solved status has not been independently reassessed.

Status note in the source

Ding and Mossel (2014) showed that

where $\mathbb{P}(\cdot)$ is the uniform probability on $\{0,1\}^n$.