# Measure concentration for weakly dependent random variables

For an application quite alien to probability theory, I'd like to have a kind of measure concentration estimate, in the following spirit. Suppose that to every $1\le i,j\le n$ there corresponds a zero-mean random variable $X_{ij}$, all of them being identically distributed and taking values in $[-1,1]$. Let $S$ denote the normalized sum of all these $n^2$ random variables: $S:=(X_{11}+\dotsb+X_{nn})/n$. I want to conclude that under some week dependence assumption (to be stated immediately), one has $${\mathsf P}(|S|>\tau) <C e^{-\gamma\tau},\quad \tau\ge 1,$$ with some absolute constants $C,\gamma>0$. (I originally hoped to prove that this probability is $O(e^{-\gamma\tau^2})$, but Carl noticed that this is too optimistic.) Indeed, I may be happy with some slightly weaker estimate, or even with an estimate like ${\mathsf E} |S|^p\le(Mp)^p$ with an absolute constant $M$.)

Now, the weak dependence assumption just mentioned is that, viewing the $X_{ij}$ as the entries of a matrix, if several of them are dependent, then one can create a closed aligned loop in the matrix with the corresponding entries being the vertices of the loop. In particular,

• the variables are independent pairwise and in triples;
• any four of them are independent, unless their indices form a rectangle in the matrix;
• any system of the variables no two of which are in the same column or in the same row is independent.

In general, I wonder whether this weak dependence assumption has ever been studied, and what conclusions can be drawn from it. Thanks in advance for any suggestions or pointers!

• A terminological quibble: the result you seek is really nothing like the bound in the Berry-Esseen inequality. You're really looking for a version of something like Hoeffding's inequality for weakly dependent random variables. One such famous result is Azuma's inequality, though your dependence assumption sounds quite different from the martingale-type assumptions in Azuma. I suggest taking a look at the recent book by Boucheron, Lugosi, and Massart. – Mark Meckes Jul 30 '13 at 14:40
• It looks like the moment method should give fairly good results in this setting, of similar strength to what this method gives for the operator norm of random matrices (in which somewhat similar independence structures appear); see e.g. Section 4 of terrytao.wordpress.com/2010/01/09/… – Terry Tao Jul 30 '13 at 14:57
• @Mark: the reason to mention Berry-Esseen is that the estimate I originally hoped for matches the estimate for the tail of a normal distribution, predicted by BE. But now that I changed the target estimate, it is definitely more logical to speak about measure concentration. – Seva Jul 30 '13 at 16:44
• @Seva: BE only predicts such a tail estimate for $\tau$ of order smaller than $\sqrt{\log n}$; otherwise the BE error estimate swamps the normal tail. – Mark Meckes Aug 1 '13 at 2:27

How about this example? All $X_{ij}$ are $\pm 1$, conditional on an even number of $+1$ at the corners of each rectangle. All entries are thus determined by the first row and column, and if these are all $+1$, the entire matrix is $+1$ and so has $S=n$ with probability $2^{-2n+1}$. Hence any bound must have $e^{-\gamma \tau}$ rather than $e^{-\gamma \tau^2}$.