# Large deviations for sums of random variables whose correlation function decays exponentially

Let $X_1, \ldots, X_N$ be a string random variables taking values $X_i \in [-1,1]$ and jointly distributed according $P(X_1, X_2, \ldots, X_{N-1}, X_N)$, which is invariant under cyclic permutations of the variables, that is $P(X_1, X_2, \ldots, X_{N-1}, X_N) = P(X_2, X_3, \ldots, X_N, X_1)$. For simplicity let $\langle X_i \rangle=0$. We assume that these random variables are weakly dependent in the sense that their correlation function decays exponentially $$\left| \langle X_1 X_2 \cdots X_r\, X_{l+1} X_{l+2} \cdots X_{l+r} \rangle - \langle X_1 X_2 \cdots X_r \rangle \langle X_{l+1} X_{l+2} \cdots X_{l+r} \rangle \right| \leq e^{-\min\{l-r,\, N-l-r\}/\xi}$$ where $\xi >0$ is the correlation length and $l>r>0$ and $r+l < N$ are integers. In particular, this implies the usual $\left|\langle X_i X_j \rangle \right| \leq e^{-|i-j|/\xi}$ from which it follows that the variance is proportional to $N$.

I am looking for a bound on ${\rm prob}\{X_1+\cdots + X_N \geq \mu \sqrt{N}\} \leq \epsilon (\mu, N)$ like the exponential Chebyshev or Hoeffding inequalities, but for the weakly dependent case described above. This has been shown in two sub-cases, namely, when the string is a Markov chain, and when the distribution $P$ has a matrix product structure.

• Plese be a bit more elaborate on what appears to be your :"rotation condition" are you reversing the random variables or just rotating them? – Daniel Parry Oct 15 '15 at 11:14
• Sorry, I meant a rotation, not a reflection: $P(X_1, X_2, \ldots, X_{N-1}, X_N) = P(X_2, X_3, \ldots, X_N, X_1)$. In physics this is called translation invariant with periodic boundary conditions. – Lluis Masanes Oct 15 '15 at 11:26
• Presumably $\lambda > 1$? – Robert Israel Oct 15 '15 at 15:45
• Could you explain 1). What do you mean by the probability of fluctuations and 2). What is the function $P$ in the definition of the cyclic invariance? Is it an arbitrary function? Is it only a polynomial? – Liviu Nicolaescu Oct 15 '15 at 17:43
• If I understand correctly, $X_i$ here are random variables taking values $\in [-1,1]$, $P$ is their joint probability distribution which is invariant under cyclic permutations of the variables, and "fluctuations" means variance. I.e. he wants a central-limit-like theorem, but relaxing the iid condition. – Toby Cubitt Oct 15 '15 at 18:46

There is no general bound with exponential decay just assuming decay of correlations. Consider this distribution: with probability $1/(N+1)$ all $X_i=$, and with probability $N/(N+1)$ there are exactly $(N-1)/2$ which are $+1$ and $(N+1)/2$ which are $-1$ (assume that $N$ is odd). Naturally, this distribution is invariant under any permutation and you can check that it is pairwise independent, that is, there is no correlation at all. Yet, with probability $1/(N+1)$ the sum is equal to $N$.