Summing dependent random variables with unknown joint cdf

Question

Suppose that X_1, X_2,... X_5000 are discrete and dependent non-identically distributed random variables, whose marginal distributions are known, but whose joint distribution is not known.

Is there a way to estimate bounds for the cumulative distribution function P(X_1 + X_2 + ... +X_1000 ≤ a)? Which conditions would need to be met?

I tried this with two Bernoulli variables. Let X and Y be Bernoulli with P(X=1) = $p_1$ and P(Y=1) = $p_2$ and we're looking for $P(X + Y <= n)$ where $n = 0,1,2$.

{X + Y = n} can be written as union of disjoint events {X = k,Y = n-k}, $0 \leq k \leq n$. Then $P(X + Y = n) = \sum_{k=0}^n P(X = k,Y = n-k)$ and we can compute

$P(X + Y = 0) = P(X = 0,Y = 0) = P(X = 0|Y = 0) \cdot (1-p_2)$

$P(X + Y = 1) = P(X = 0,Y = 1) + P(X = 1,Y = 0)$ $= P(X = 0|Y = 1) \cdot p_2 + P(X = 1,Y = 0)\cdot(1-p2)$

$P(X + Y = 2) = P(X=0,Y=2) + P(X=1,Y=1) + P(X=2,Y=0)$ $= 0 + P(X=1|Y=1) \cdot p_2 + 0$

I guess we could compute a number of possible joint distributions by assuming different conditional probability tables, but that doesn't seem very useful and I get stuck here.

Answer 1

For your simple example with two dependent Bernoulli random variables with parameters $p_1$ and $p_2$ (where we assume without loss of generality that $p_1 \geq p_2$, and also that $p_1+p_2 \leq 1$),

$$P\{X+Y = 2\} = P\{X = 1, Y = 1\} \in [0, p_2]$$ where if $P\{X+Y = 2\}$ has the minimum possible value $0$, then it must be that

$$P\{X+Y=2\} = 0, \quad P\{X+Y=1\} = p_1+p_2,\quad P\{X+Y=0\} = 1-p_1-p_2$$

while if $P\{X+Y = 2\}$ has the maximum possible value $p_2$, then it must be that

$$P\{X+Y=2\} = p_2, \quad P\{X+Y=1\} = p_1-p_2,\quad P\{X+Y=0\} = 1-p_1$$

and more generally, if $P\{X+Y = 2\}$ has value $x \in [0,p_2]$, then it must be that

$$P\{X+Y=2\} = x, \quad P\{X+Y=1\} = p_1+p_2-2x,\quad P\{X+Y=0\} = 1-(p_1+p_2-x).$$

So you see that bounds of the kind you seek would be difficult to obtain when you are working with thousands of random variables; unless there is some structure to the problem that can be exploited.