Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary). The flip probability is $\delta$, i.e., $\Pr[X_{i+1} = -x\,|\,X_i = x] = \delta$ for $x\in\{-1,1\}$. I'm interested in exponentially tight bounds on the tail of $ |\frac{1}{n}\sum_{i=1}^nX_i| $.
If $ \delta $ is very close to $1/2$, then $X_i$'s are weakly dependent and we would expect that $|\frac{1}{n}\sum_{i=1}^nX_i|$ is very close to $0$. Therefore, the rare event is $|\frac{1}{n}\sum_{i=1}^nX_i|\ge\epsilon$. There are many bounds in the literature on the tail $\Pr[|\frac{1}{n}\sum_{i=1}^nX_i|\ge\epsilon]$.
If $\delta$ is very close to $0$, then $X_i$'s are strongly dependent and we would expect that $|\frac{1}{n}\sum_{i=1}^nX_i|$ is very close to $1$. Therefore, the rare event is $|\frac{1}{n}\sum_{i=1}^nX_i|\le1-\epsilon$. I'm interested in obtaining exponentially tight upper bounds on the tail $\Pr[|\frac{1}{n}\sum_{i=1}^nX_i|\le1-\epsilon]$. (Note that this looks like anti-concentration on the face of it, but I'm not sure if it's appropriate to call it so, since we're not lower bounding the probability of rare events.)
I looked into the literature and it seems that most existing bounds (e.g., Theorem 1.2 here) behave well in the weakly dependent regime but behave poorly in the strongly dependent regime. In particular, for the specific parameter regime in my original context, I couldn't even find a bound that beats a trivial union bound: $$\Pr\left[\left|\frac{1}{n}\sum_{i=1}^nX_i\right|\le1-\epsilon\right]\le\Pr\left[\left|\frac{1}{n}\sum_{i=1}^nX_i\right|<1\right] = \Pr\left[\exists i,\,X_i\ne X_{i+1}\right]\le n\cdot\delta.$$ Here I think of $n$ as something like $\frac{1}{\delta}(\log\frac{1}{\delta})^{-3}$.
My questions are:
- What is the actual scaling of the above tail as a function of $n$ and $\delta$?
- More generally, how much is known about large deviation of strongly dependent Markov chains?