1
$\begingroup$

I have a set of dependent Bernoulli variables $X_i$ for $i \le N$, with probability $\epsilon$ for the event $X_i=1$.

I want to bound the probability that $\sup_i X_i \ge 1$, i.e., I want to know what is the probability that all of them are 0.

I can't use Bernstein's inequality (with $\sum_i X_i \ge 1$ which is equivalent to $\sup_i X_i \ge 1$) because the variables are dependent.

In fact, I can't use Bernstein's inequality because it contains a term of the form $N \epsilon$, and I do not have $\epsilon = o(N)$, which means that the probability is going to be very large.

However, my variables are very much dependent. So, another way to approach it is to use bound the probability $P(X_1 = 1 \cup X_2 = 1 \ldots \cup X_N = 1)$. A simple union bound won't help again because $\epsilon$ is not $o(N)$. However, I was hoping there are some standard ways to define dependence, or make assumptions about dependence, such that this probability is small. I am willing to make some reasonable assumptions here about the dependence.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Depending on the assumptions you're willing to make, one useful refinement of the union bound is the Bonferroni inequalities: en.wikipedia.org/wiki/… $\endgroup$
    – Mark Meckes
    Oct 4, 2010 at 15:11
  • 1
    $\begingroup$ Also, Bernstein-like inequalities hold under martingale dependence assumptions; see for example en.wikipedia.org/wiki/Azuma%27s_inequality It's hard to say what will be useful here without some more detail about what kind of dependence assumptions are acceptable to you. $\endgroup$
    – Mark Meckes
    Oct 4, 2010 at 15:14
  • 1
    $\begingroup$ Sure, Mark, but a martingale difference sequence of Bernoulli's is independent. It is hard to make sense of this question. Since the OP hasn't clarified, I vote to close. $\endgroup$
    – Bill Johnson
    Oct 5, 2010 at 1:02
  • $\begingroup$ Good point, Bill, and more generally the dependency structure among Bernoullis can't be terribly complicated, so in such a case the Bonferroni inequalities are particularly likely to be useful. But it's impossible to be sure without clarification. I think, though, that it's worth waiting at least 24 hours for clarification before closing, just on general principle. (It's entirely academic to me, since I don't have sufficient rep to vote for closing.) $\endgroup$
    – Mark Meckes
    Oct 5, 2010 at 12:24
  • 1
    $\begingroup$ The assumptions depend on the applications you have in mind. If you really have no applications in mind and are just trying to state an abstract result, then the best assumption is probably : $P(\cup A_i)$ is small enough". Note that if $N\epsilon$ is large and if you want the probability of the union to be small you require strong assumptions on the dependence. It would be nice to have at least non trivial examples (other that all the $A_i$ are equal for example) to make sure that your result is non trivial. $\endgroup$
    – Hugh J
    Oct 8, 2010 at 9:06

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.