# Is there a McDiarmid-type inequality for sequences with a finite range of dependence?

Let $X, X_1, X_2, \ldots, X_N$ be a sequence of identically distributed random variables with $0 \leq X \leq 1$.

We do not assume the sequence is iid, but rather allow the random variables to be dependent on their neighbors: we suppose that there exists $k\geq 1$ such that for every $I,J \subseteq \{ 1,\ldots, N\}$ satisfying $\min\{ |i-j| \,:\, i\in I,\, j\in J \} \geq k$, the collections $\{ X_i\,:\, i\in I\}$ and $\{ X_j \,:\, j\in J \}$ are independent. (It might help to just consider the case $k=2$.)

Let $f: \mathbb{R}^N \to \mathbb R$ be a Lipschitz function with Lipschitz constant one.

Here is my question: is there a good concentration inequality for $f(X_1,\ldots,X_N)$?

Let me recall two well-known facts:

1. If $k=1$, then the sequence is i.i.d., and we have McDiarmid's inequality, which states that: \begin{equation} \mathbb{P} \left[ \left| f(X_1,\ldots,X_N) - \mathbb E \left[ f(X_1,\ldots,X_N) \right] \right| > \lambda \right] \leq \exp \left( -\frac{2\lambda^2}{N} \right). \end{equation}

2. On the other hand, if $f(X_1,\ldots,X_N) = X_1 + \cdots+X_N$, then I can run the proof of Bernstein's inequalities (the usual exponential generating function argument) combined with a neat Holder inequality trick to prove a similar bound.

However, I am interested in general, non-affine, Lipschitz $f$, and the proof of McDiarmid's inequality uses a martingale argument that doesn't seem to work very well with my weaker independence assumption (the Holder trick doesn't seem to me to work). I have tried googling without success. Does a concentration inequality like McDiarmid's inequality survive? I would even be happy with something not quite as strong.

## 1 Answer

There are several versions of this type:

1) K. Marton has results for dependent variables. Maybe closest to what you ask (for convex functions $f$) is the paper of Samson: Samson paper

2) For a martingale difference based argument, see Kontorovich and Ramanan: Kontorovich-Ramanan paper

The references of these articles give more pointers...

• Thanks, Ofer. I am keeping my fingers crossed, but the Kontorovich-Ramanan paper might be just what I was after. – Scott Armstrong Dec 12 '13 at 22:08
• In case someone else besides me cares about this question, I would add that, in addition to the references above, one should not miss the PhD thesis of Sourav Chatterjee: arxiv.org/abs/math/0507526 Besides having the particular results I cared about, he explains things an order of magnitude better than I could find elsewhere (at least from the point of view of a novice like me). – Scott Armstrong Dec 22 '13 at 21:49