# 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) K. Marton has results for dependent variables. Maybe closest to what you ask (for convex functions $f$) is the paper of Samson: Samson paper