Consider the sum of $n$ identically distributed, but not necessarily independent random variables $X_1\dots X_n$; I am trying to prove some concentration bounds on the sum based on concentration bounds for the individual $X_i$ (with concentration bounds, I mean upper bounds on the probability of exceeding some threshold at least as large as the expectation).

Now, since I do not have independence, I can’t apply anything like a Chernoff-Hoeffding bound; but I had naively hoped, since intuitively the worst case is that all the $X_i$ are perfectly correlated, that I could prove for $c\geq E[X_1]$ something like $Pr[\frac{1}{n}(X_1+\dots+X_n)\geq c] \leq Pr[X_1\geq c]$. While this is true for perfectly correlated variables, it is not true in general: e.g. assuming $X_1$ and $X_2$ are independent $0-1$ variables with expectation $0.1$ the probability that $\frac{1}{2}(X_1+X_2) > 0.3$ is $1-(0.9)^2=0.19$, almost twice the probability that $X_1 \geq 0.3$, which is $0.1$ (note how I’ve been conservative with the inequality signs). I briefly wondered whether this might due to the discrete nature of the variables in this example (so the inequality $Pr[\frac{1}{n}(X_1+\dots+X_n)\geq c] \leq Pr[X_1\geq c]$ would hold for $c$ equal to some value that $X_1$ can actually take, rather than an "intermediate" value), but again, this does not seem to be the case. I’d be surprised if nobody had faced a similar problem before, so I’m asking:

Are there any known (non-trivial) upper bounds on the probability that the average of identically distributed dependent random variables exceeds a certain threshold equal to or greater than the expectation, given corresponding bounds on the individual variables? Or, more formally, if $X_1,\dots,X_n$ are identically distributed but not necessarily independent random variables, can I find a non-trivial $f(x)\geq Pr[\frac{1}{n}(X_1+\dots+X_n) \geq x]$ given $g(x)\geq Pr[X_1\geq x]$ for $x \geq E[X_1]$?

  • 1
    $\begingroup$ As a rule of thumb, when you try to broaden your horizons from independent to dependent random variables, you want to start off with weakly dependent random variables. Arbitrary dependence is not tractable in most cases. $\endgroup$
    – Ian
    Mar 23 '17 at 15:25
  • $\begingroup$ You might be interested in the following preprint: arxiv.org/abs/1507.06871 $\endgroup$ Jun 5 '17 at 0:59

Let's take an example with $n=2$ where $X_1$ is $0$ or $1$ each with probability $\frac12$ and $X_2=1-X_1$ so identically distributed. We then have $\Pr[X_1+X_2=1]=1$

then if $0 \lt c \lt \frac12$: $\Pr[X_1\geq c]=\frac12$ and $\Pr[(X_1+\dots+X_n)\geq n\cdot c]=1$

while if $\frac12 \lt c \lt 1$: $\Pr[X_1\geq c]=\frac12$ and $\Pr[(X_1+\dots+X_n)\geq n\cdot c]=0$

which suggests that non-trivial bounds on the distribution of the sum may be difficult to find

  • $\begingroup$ Hmmm, I think this misses the point, though I may not have been sufficiently clear (I've bolded an edit to make it clearer). I'm looking for bounds on the probability of exceeding a threshold at least as high as the expectation, and I'd be very happy with something that told me that exceeding the threshold for the average of the variables is at least as hard as exceeding that same threshold for a single variable ... which is not the case in general, but it's certainly the case in this example. $\endgroup$
    – Anonymous
    Mar 23 '17 at 12:48
  • $\begingroup$ When you say "expectation", do you mean $c=E[X_i]$ or just $n\cdot c$ for arbitrary $c$ or perhaps $\frac1n \Pr[(X_1+\dots+X_n)\geq n\cdot c]$? $\endgroup$
    – Henry
    Mar 23 '17 at 12:50
  • $\begingroup$ I am interested in arbitrary $c$ at least as large as the expectation. Basically questions like "How likely is that the sum exceeds 1.2 times its expectation", if I have the corresponding answers on the individual $X_i$. $\endgroup$
    – Anonymous
    Mar 23 '17 at 12:54
  • $\begingroup$ In my case, they are non-negative; but it seems really irrelevant since the answer if I add or subtract a given constant to all $X_i$ does not appear to change. $\endgroup$
    – Anonymous
    Mar 23 '17 at 13:00
  • $\begingroup$ If $c$ is greater than the expectation, then the probability that the sum is greater than or equal to $n\cdot c$ can be $0$. If $c$ is equal to the expectation, then the probability that the sum is greater than or equal to $n\cdot c$ can arbitrarily small though positive; it can also be $1$. That leaves the question of $c$ greater than the expectation and an upper bound on the probability: Markov's inequality gives an upper bound for non-negative random variables, though there may be others. $\endgroup$
    – Henry
    Mar 23 '17 at 14:16

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.