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., \begin{equation} (1) \text{ } \mathbb{E}[e^{ \lambda \sum_i X_i} ] \leq B.\end{equation}

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!

  • $\begingroup$ 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. $\endgroup$
    – antkam
    Jan 3, 2020 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – Math1000
    Jan 3, 2020 at 14:19
  • $\begingroup$ 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}.$$ $\endgroup$
    – Math1000
    Jan 3, 2020 at 14:30
  • $\begingroup$ 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 $\endgroup$
    – Paradox
    Jan 3, 2020 at 23:20
  • $\begingroup$ 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}$? $\endgroup$
    – Paradox
    Jan 3, 2020 at 23:27

1 Answer 1


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)} $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .