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.


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...

  • $\begingroup$ Thanks, Ofer. I am keeping my fingers crossed, but the Kontorovich-Ramanan paper might be just what I was after. $\endgroup$ – user5678 Dec 12 '13 at 22:08
  • $\begingroup$ 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). $\endgroup$ – user5678 Dec 22 '13 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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