I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support. I am attempting to use the method of bounded differences as an amateur. In general, most presentations of this method promise to handle arbitrary dependences between random variables but all worked out examples involve independent random variables.

In particular, let $$X_0, \ldots, X_n$$ be a sequence of random variables wherein

$$ X_0 = \left\{ \begin{array}{cc} 1 & \mbox{with probability}\ \frac{1}{2} \\ -1 & \mbox{with probability}\ \frac{1}{2} \\ \end{array}\right. \,,$$

and $X_{i+1} = X_i$ for $i \geq 0$. In other words, $X_i$s for $i \geq 1$ are "very highly correlated" with $X_0$. :-)

We are looking at $\sum_{i=0}^n X_i $ and with probability $\frac{1}{2}$ each it can be either $\pm (n+1)$.

Let us apply the method of bounded differences to the summation with the Doob martingale sequence (I am blindly following the presentation in [1] here :-)

$$ Y_i = \mathbb{E}\left( \sum_{j=0}^n X_j\ |\ X_0, \ldots, X_{i-1} \right)\,.$$

We can show that $$|Y_{i+1} - Y_i| \leq 1\,.$$

Applying Azuma's theorem gives us the "concentration result"

$$ \mathbb{E}( Y_n \geq t ) \leq \exp\left( \frac{ -2t^2}{ n } \right) $$

Clearly I am wrong! This is the same as the Chernoff Hoeffding bound for the iid case! I am wondering where I went wrong. Very grateful for your help!

[1] Dubhashi and Panconesi, Concentration of measure for the analysis of randomized algorithms.

Resolution: it seems to be resolved thanks to the comments below from @alpoge. The mistake here is $Y_0 = \mathbb{E}(\sum X_i) = 0$. But $Y_1 = Y_2= \cdots = Y_n = (n+1) X_0$ and therefore, when applying Azuma's theorem, the denominator will be something like

$$\mathbb{P}( Y_n \geq t) \leq \exp\left( \frac{-t^2}{2(n+1)^2} \right) $$

Now the bounds obtained are much weaker and consistent with having $Y_n$ being $n+1$ with probability $\frac{1}{2}$ and $-(n+1)$ with probability $\frac{1}{2}$.

The lesson is then when the method of bounded difference is applied to sums of dependent random variables, care should be taken to calculate $\mathbb{E}(X_j | X_0,\ldots, X_{j-1})$ carefully when $X_{j}$ could be dependent on $X_0,\ldots, X_{j-1}$. It is tempting to equate this to $\mathbb{E}(X_j)$.