3
$\begingroup$

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:

  1. What is the actual scaling of the above tail as a function of $n$ and $\delta$?
  2. More generally, how much is known about large deviation of strongly dependent Markov chains?
$\endgroup$
3
  • 1
    $\begingroup$ Did you try the second moment? Its asymptotics seems to be computable, and it yields some bounds on tail probabilities. $\endgroup$ Jan 4, 2022 at 22:36
  • 4
    $\begingroup$ It seems you are interested in the regime $n\delta\to0$. Then isn't the answer (to first order) simply $n\delta(1-\epsilon)$? The dominant contribution comes when there is exactly one flip, which occurs after the first $n\epsilon/2$ steps and before the last $n\epsilon/2$ steps. Realisations involving two or more flips are much less likely than realisations involving one flip (with probability on the order of $(n\delta)^2$). $\endgroup$ Jan 5, 2022 at 1:22
  • 1
    $\begingroup$ Is the 'expander chernoff bound' relevant? In particular, there are markov chain generalizations of the chernoff bound with concentration depending on the mixing time. See corollary 1.3 here: arxiv.org/pdf/1906.07260.pdf $\endgroup$ Jan 5, 2022 at 2:03

1 Answer 1

0
$\begingroup$

You have a $2\times 2$ Markov transition matrix, and you said you want the uniform distribution to be stationary. So the matrix is symmetric, and the off-diagonal element is $\delta$, which you say is small. Note that whether or not you have a switch at any given step are IID Bernoulli-$\delta$ random variables because you have just the 2-state symmetric Markov chain. So conditional on $k$ switches, their distribution is uniform in the interval. You are taking $n\ll \delta^{-1}$. Let $\lambda = n \delta$ which is supposed to be small. The probability to have $0$ switches is $(1-\delta)^n$ which is approximately $e^{-n\delta}$ if $\delta$ is small. Conditional on having $0$ switches, we know $n^{-1} \sum_{i=1}^{n} \mathsf{X}_i$ is 1. But if we condition on having exactly $k$ switches for a $k>1$,then the conditional distribution of $n^{-1} \sum_{i=1}^{n} \mathsf{X}_i$ is not particularly concentrated near $1$ just because of the symmetry of where the switches occur. That is probably why the subset inequality is going to be your best bet, here.

Incidentally, concentration-of-measure is just a term. It does seem to represent the general phenomenon which is most simply demonstrated in the weak law of large numbers for averages of IID random variables. But for Markov chains at times much larger than their mixing times, they have some similar properties to IID random variables. There is large deviation theory for them (which you can find by looking up Donsker and Varadhan). But you are right that for times much less than the mixing time, the actual distribution of which state the Markov chain is in may be concentrated near its starting position.

If $n$ is large and $\lambda = n\delta$ is not too big, then you can approximate well by considering a Poisson process, even if $\lambda$ is very small. Setting $\mathsf{T}_1,\mathsf{T}_2,\dots$ to be the times where the process jumps from one state to the opposite, and rescaling $\mathsf{T}_i/n$ gives an approximation to a Poisson point process on $[0,1]$ with parameter $\lambda$.

In the Poisson process, the probability to have $0$ switches by time 1 is $e^{-\lambda}$. The probability to have exactly $k$ switches in the Poisson approximation is $e^{-\lambda} \lambda^k/k!$.

The question seems interesting and natural about the conditional distribution of the random variable you considered and I suspect it is well-known. But I did not immediately find it when I looked. Let $\mathsf{Y}_n = (1 + n^{-1} \sum_{i=1}^n \mathsf{X}_i)/2$ which gives the fraction of time spent in state $1$ as opposed to $-1$. Then the approximation for these random variables, $\mathsf{Y}$, is obtained by taking a Poisson-$\lambda$ point process up to time $1$ and for each $t$ asking how many Poisson events happened prior to $t$. Then you count the total measure of times $t$ such that the number of Poisson events prior to time $t$ is an even number $\{0,2,4,\dots\}$.

It seems like if you condition on exactly $k$ jumps for $k \in \{0,1,2,\dots\}$ you get a Beta distribution $B(a,b)$ where: $a = \lfloor k/2 \rfloor +1$ and $b=\lceil k/2\rceil$. Let us interpret $B(1,0)$ to be the point-mass at $1$. This seems to follow from the symmetry condition of the endpoints somewhat similarly to the usual stars-and-stripes problem. (Sorry for not knowing a good reference.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.