Large deviation for sum of dependent indicators

[Manan Sanghi]

Hi,

Let X_0, X_1, ... X_n be random variables NOT necessarily independent such
that
P[X_i = 1] = p_i and P[X_i = 0] = 1-p_i .

Let X = X_1 + X_2 + ... + X_n

In other words X is a sum of dependent random indicators.

Are there any large deviation results for X (ie P[ |X-E(X)| > t] < ?? )?
What if the indicators are identically distributed, ie p_1 = p_2 = ... =
p_n?

I will be grateful for any references, suggestions, comments, anything.

Thanks,
Manan

[Patrick Powers]

"Manan Sanghi" <ma...@cs.northwestern.edu> wrote in message news:<c6mhb7$dd0tb$1...@ID-210275.news.uni-berlin.de>...

> Hi,
>
> Let X_0, X_1, ... X_n be random variables NOT necessarily independent such
> that
> P[X_i = 1] = p_i and P[X_i = 0] = 1-p_i .
>
> Let X = X_1 + X_2 + ... + X_n
>
> In other words X is a sum of dependent random indicators.
>

You seem to think that the X_i having different means makes them
dependent, which is not the case. Instead, try P[X_i =1] = P[X_i
=1|X_j=1] iff X_i is independent of X_j.

> Are there any large deviation results for X (ie P[ |X-E(X)| > t] < ?? )?

Sure. Try p_i = 1-(1/i), and P[X_j=1|P_1=1] = 1.

> What if the indicators are identically distributed, ie p_1 = p_2 = ... =
> p_n?

This is not the definition of identically distributed. If the
variables are dependent then just about anything goes, so the
distributions could be quite different even though the means are the
same.