# Bound mgf of a sum of dependent random variables

Let $$X_1, \dots, X_n$$ be dependent Bernoulli r.v. such that $$\mathbb{E}[X_i]=p_i, i=1,\dots,n$$. I want to find a tight bound to the mgf of the sum of such random variables, i.e. a bound $$B$$ function of some random variables $$Y_1, \dots, Y_n$$ (note that $$Y_i$$ may also be equal to $$X_i, i=1,\dots,n$$) s.t., $$$$(1) \text{ } \mathbb{E}[e^{ \lambda \sum_i X_i} ] \leq B.$$$$

For negative associated random variables, i.e. variables $$X,Y$$ for which $$Cov(X,Y) \le 0$$, it holds that $$\mathbb{E}[e^{ \lambda (X+Y)} ] \le \mathbb{E}[e^{ \lambda X} ] \mathbb{E}[e^{ \lambda Y} ] (\bigstar)$$; unfortunately the variables $$X_1, \dots, X_n$$ are not negative associated. In general, appling $$(\bigstar)$$ to the lhs in $$(1)$$ leads to a incorrect result thus it is not true that $$\mathbb{E}[e^{ \lambda \sum_i X_i} ] \leq \prod_i \mathbb{E}[e^{ \lambda X_i}]$$ for the considered random variables $$X_1, \dots, X_n$$. Is there a way to obtain the desired bound $$B$$ with other techniques? Any refrence will be very useful!

• If you don't have any additional info about the dependence among the $X_j$'s, there seems rather little you can possibly say...? The "worst" case (IMHO) is when $X_1 = X_2 = \dots = X_n$ in which case lhs is really big: lhs $= p e^{\lambda n}$. Perhaps using a bound involving covariance would help... but even that is doubtful since it is easy to make the $X_j$'s pairwise independent (s.t. covariance $=0$ and doesn't give you any info) but not mutually independent. Jan 3, 2020 at 14:12
• If the $X_i$ are independent then \begin{align} \mathbb E[e^{\lambda\sum_{i=1}^n X_i}] &= \prod_{i=1}^n \mathbb E[e^{\lambda X_i}]\\ &= \prod_{i=1}^n (1-\lambda + \lambda p_i)\\ &\leqslant \sup_{1\leqslant i\leqslant n} (1-\lambda + \lambda p_i)^n\\ &= \sup_{1\leqslant i\leqslant n} \sum_{k=0}^n \binom nk (1-\lambda)^k(\lambda p_i)^{n-k}, \end{align} but I am not sure when the $X_i$ are dependent. Jan 3, 2020 at 14:19
• Alternatively we have the upper bound $$\sup_{1\leqslant i\leqslant n} \frac1{1-n(\lambda(p_i-1))^n}$$ for $$\lambda\geqslant\sup_{1\leqslant i\leqslant n}\frac{-1}{p_i-1}.$$ Jan 3, 2020 at 14:30
• Hi @Math1000, thanks for the suggestion unfortunately the inequality $\mathbb{E}[e^{\lambda \sum_i X_i}] \le \prod_i \mathbb{E}[e^{\lambda X_i}]$ leads to a incorrect result, thus cannot be used on the variables I'm considering Jan 3, 2020 at 23:20
• Hi @antkam, unfortunately the dependecies are unknown, so the only possible thing you suggest is to bound $\mathbb{E}[e^{\lambda \sum_i X_i}]$ by $\max_i{p_i} e^{\lambda n}$? Jan 3, 2020 at 23:27

If you know the $$p_i$$'s, which are marginal probabilities, but don't have any info on the (mutual) dependence, then I think the "worst case" $$E[e^{\lambda \sum_i X_i}]$$ happens when the variables are "as aligned as possible" in a sense.

To be precise, by "worst case" I mean maximum $$E[e^{\lambda \sum_i X_i}]$$ (since you're interested in upperbounds), for a given $$\lambda > 0$$. And by "as aligned as possible" I mean this:

• Without loss, assume $$p_1 \le p_2 \le \dots \le p_n$$.

• The r.v.s satisfy: events $$(X_1 = 1) \subseteq (X_2 = 1) \subseteq \dots \subseteq (X_n = 1)$$.

In this case, the sample space is partitioned into $$n+1$$ (mutually exclusive) events $$\{F_k\}$$, indexed by $$k= n - \sum_i X_i =$$ no. of variables with value $$0$$:

$$F_k := \bigcap_{1\le j \le k} (X_j = 0) \cap \bigcap_{k < j \le n} (X_j = 1), ~~~~\text{for } k \in \{0, 1, 2, \dots, n\}$$

E.g. $$F_0 = \{\text{no } X_i = 0\} = \{\text{all } X_i = 1\} = (X_1 = 1)$$ and $$P(F_0) = p_1$$, and $$F_1 = \{\text{exactly one } X_i = 0\} = \{\text{only } X_1 = 0\} = (X_1 = 0, X_2 = 1)$$ and $$P(F_1) = p_2 - p_1$$.

More generally, writing $$f_k = P(F_k)$$ and these events have probabilities

$$(f_0, f_1, f_2, \dots, f_n) = (p_1, p_2 - p_1, p_3 - p_2, \dots, p_n - p_{n-1}, 1-p_n)$$

respectively, and finally:

$$E[e^{\lambda \sum_i X_i}] = \sum_{k=0}^n f_k e^{\lambda (n-k)}$$