9
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Azuma gives you a bound on the probability that Y_n - Y_0 is large, no? (Here it's 0.) $\endgroup$
    – alpoge
    Oct 9, 2015 at 19:59
  • 2
    $\begingroup$ Not quite, $Y_0 = 0$ and $Y_n = (n+1) X_0$ right? But between your previous comment that you just modified, and Edgar's comment below, I think I can see a mistake. $Y_1$ is already $(n+1) X_0$. So the difference $| Y_{i} - Y_{i-1} | = 0$ for $i \geq 2$ but $|Y_{1} - Y_{0}| = 2 (n+1)$. The result will be different. Is that the mistake? $\endgroup$
    – Sriram S
    Oct 9, 2015 at 20:00
  • 4
    $\begingroup$ Sorry, I keep indexing wrong! Yeah it's as I said in the comment I deleted --- the bound on the increments doesn't hold for Y_1 - Y_0. The general bound is Prob.(Y_k - Y_0\geq t)\leq \exp(-t^2/(2\sum_{i=1}^k ||Y_i - Y_{i-1}||_\infty^2)). Applying this you get a denominator that is order n^2, rather than order n. $\endgroup$
    – alpoge
    Oct 9, 2015 at 20:55
  • 1
    $\begingroup$ (I'm certainly no expert so the bound above is probably not optimal --- e.g. the constant in the exponential is probably suboptimal.) $\endgroup$
    – alpoge
    Oct 9, 2015 at 20:57
  • 1
    $\begingroup$ If you would like, please add a solution. Otherwise, I have added a resolution to my post. thanks once again! The nice thing is that this gives the same answer as another paper I am reading by Jansen that uses the chromatic number of the dependence graph. So I am much happier! $\endgroup$
    – Sriram S
    Oct 10, 2015 at 0:45

1 Answer 1

Reset to default
3
$\begingroup$

What if we work it out? All of $X_j$ are equal to $X_0$, in particular measurable with respect to $X_0$. So $$ \sum_{i=0}^n X_i = (n+1)X_0, \\ Y_i = (n+1)X_0\qquad\text{for all } i \\ Y_{i+1}-Y_i = 0 $$ Certainly bounded differences...

What other hypotheses are there?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks! I am actually translating a much more complicated situation into a "toy problem" that I have posted. In general, there are no other hypotheses. I still do not see where I went wrong. $\endgroup$
    – Sriram S
    Oct 9, 2015 at 18:19
  • 4
    $\begingroup$ Except that $Y_0$ is not $(n+1)X_0$, it is the constant 0. Now apply Azuma's theorem using all the differences including the very large difference $|Y_1-Y_0|$. (This is much the same as alpoge's comment above.) $\endgroup$
    – Brendan McKay
    Oct 9, 2015 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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