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.