Function-specific mixing time and concentration

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 $(X_n)$ be a stationary Markov chain on a finite state space $\Omega$ and $f\colon\Omega\to [-1,1]$. Consider

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

Status note in the source

• This is known for $\delta=\varepsilon^2$, Maxim Rabinovich, Aaditya Ramdas, Michael I. Jordan, and Martin J. Wainwright (2016).

• In the reversible case, this holds with $t_f$ replaced by $t_{\text{REL}}$ (Gilman, 1998).

• Allan Sly's counterexample for $\delta=1/4$: let $\Omega$ be a segment of length $N$. For all $1\leq i\leq N$, $f(i)=\pm 1$. In each local neighborhood, the number of $1$'s is approximately equal to the number of $-1$'s, but there is a fraction $1/100$ more $1$'s on the right side and a fraction $1/100$ more $-1$'s on the left side.

• Roberto Oliveira's progress: it holds with $\delta=\varepsilon/2$. Let $t=t_f(\varepsilon/2)$ and assume $n=kt$. Then \begin{eqnarray*} S_n &=&\frac{1}{t}\sum_{\ell=1}^t\frac{1}{k} \sum_{i=0}^{k-1} f(X_{it+\ell}), . \end{eqnarray*} Let $\theta\geq 0$. By convexity of $x\mapsto \exp(\theta x)$, \begin{eqnarray*} \mathbb{E}\left[\mathrm{e}^{\theta (S_n-\mathbb{E}\pi f)}\right]&\leq & \frac{1}{t}\sum{\ell=1}^t \mathbb{E}\left[\mathrm{e}^{\theta \frac{1}{k} \sum_{i=0}^{k-1} (f(X_{it+\ell})-\mathbb{E}\pi f)}\right], . \end{eqnarray*} Now, by definition of $t$, $\mathbb{E}_\pi f\geq \mathbb{E}\left[f(X_{it+\ell})\big|X_\ell,X_{t+\ell},\dots,X_{(i-1)t+\ell}\right]-\varepsilon/2$. And by Hoeffding's inequality, \begin{eqnarray*} \mathbb{E}\left[\mathrm{e}^{\theta (S_n-\mathbb{E}\pi f)}\right]&\leq & \frac{1}{t}\sum_{\ell=1}^t \mathrm{e}^{\frac{\theta\varepsilon}{2}}\mathbb{E}\left[\mathrm{e}^{\theta \frac{1}{k} \sum_{i=0}^{k-1} \left(f(X_{it+\ell})-\mathbb{E}\left[f(X_{it+\ell})\big|X_\ell,\dots,X_{(i-1)t+\ell}\right]\right)}\right]\ &\leq & \mathrm{e}^{\frac{\theta^2}{2k}+\frac{\theta\varepsilon}{2}}, . \end{eqnarray*} Applying the same arguments to $\theta<0$, one obtains \begin{eqnarray*} \mathbb{P}\left(\Big| S_n-\mathbb{E} S_n\Big| \geq\varepsilon\right)&\leq& 2\exp\left(-\frac{k\varepsilon^2}{8}\right), , \end{eqnarray*}