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$ – Daniel Parry 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$ – Lluis Masanes Oct 15 '15 at 11:26
  • $\begingroup$ Presumably $\lambda > 1$? $\endgroup$ – Robert Israel 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$ – Liviu Nicolaescu 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$ – 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$.

  • $\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$ – Lluis Masanes Oct 16 '15 at 15:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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