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. 



Is there a McDiarmid-type inequality for sequences with a finite range of dependence?
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](http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.aop/1019160125)


2) For a martingale difference based argument, see Kontorovich and Ramanan:
[Kontorovich-Ramanan paper](http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aop/1229696598)


The references of these articles give more pointers...


