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.

  • $\begingroup$ Plese be a bit more elaborate on what appears to be your :"rotation condition" are you reversing the random variables or just rotating them? $\endgroup$ Oct 15 '15 at 11:14
  • $\begingroup$ 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. $\endgroup$ Oct 15 '15 at 11:26
  • $\begingroup$ Presumably $\lambda > 1$? $\endgroup$ Oct 15 '15 at 15:45
  • $\begingroup$ 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? $\endgroup$ Oct 15 '15 at 17:43
  • 1
    $\begingroup$ 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. $\endgroup$ 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$.

  • $\begingroup$ Thanks, this counter-example is very useful. Do you think there is also a counter-example if we use the more general the exponential decay of correlations condition written in the newer version of the question? $\endgroup$ Oct 16 '15 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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