Let us assume $X_1, ..., X_n$ are independent random variables bounded by the interval $[a_i, b_i]$ and $S_n = X_1 + ... + X_n$. When $|X_i - E[X_i]|\leq M$, the Bernstein's inequality suggests the following. It can be asumed that $M = \max_{i} \big\{b_i - E[X_i]\big\}$.

$$P(S_n - E[S_n] > t) \leq \exp\bigg(-\frac{t^2}{2\sum_{i=1}^{n}\operatorname{Var} (X_i) + \frac{2}{3} Mt}\bigg).$$

Now, I have a case where $Y_1, ..., Y_{n_1}$ are independent random variables bounded by the interval $[c_i, d_i]$ and $S_{n_1} = Y_1 + ... + Y_{n_1}$. In addition, $Z_1, ..., Z_{n_2}$ are independent random variables bounded by the interval $[e_i, f_i]$ and $S_{n_2} = Z_1 + ... + Z_{n_2}$. $Y_i$'s and $Z_i$'s are also independent. Let, $M_1 = \max_{i} \big\{d_i - E[Y_i]\big\}$ and $M_2 = \max_{i} \big\{f_i - E[Z_i]\big\}$. I would like to have a Bernstein's bound for $P(S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] > t)$.

My try:

$$P(S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] > t) \leq \exp\bigg(-\frac{t^2}{2\big[\sum_{i=1}^{n_1}\operatorname{Var} (Y_i)+ \sum_{i=1}^{n_2}\operatorname{Var} (Z_i)\big] + \frac{2}{3} [M_1 + M_2] t}\bigg).$$

I am wondering whether the above equation is correct.


I can think of at least two "direct applications" of Bernstein inequality, and they are different from yours. I wouldn't say yours is incorrect, but to me it is not a "direct application".

First Direct Application

Consider combining all $Y_i$ and all $Z_i$ as just one set. In short, this gives the term $\frac23 \max\{ M_1, M_2\}\cdot t\,$ instead of $\frac23 [ M_1 + M_2 ]\cdot t\,$ in your expression, with other terms all the same.

Since this is in the denominator of negative exponent, your $M_1 + M_2 > \max\{ M_1, M_2\}$ is more conservative, with the whole $\exp(-\text{blah})$ being larger.

Explanation below if needed:

Since $Y_i$ and $Z_i$ are independent within each set and to each other, along with the intervals $[c_i, d_i]$ and $[e_i, f_i]$ being distinct to begin with, we can combine $Y_i$ and $Z_i$ as just one set.

That is, we have a set for $i = 1,2,\ldots, (n_2+n_1)$ that shall be denoted $W_i$, which bounding intervals are $[c_i, d_i]$ for the first $n_1$ terms and $[e_{i-n_1}, f_{i-n_1}]$ for the remaining $i = 1+n_1,2+n_1,\ldots,n_2+n_1$. (the $c_i, d_i, e_i, f_i$ are given as in your question statement)

Thus, applying the definition (quoting your statement in the question post) $M = \max_{i} \big\{b_i - E[X_i]\big\}$, here we have the "relevant $M$" as $$\max\left\{ \max_{i=1\sim n_1} \big\{d_i - E[Y_i]\big\} ~, ~ \max_{i=1\sim n_2} \big\{f_i - E[Z_i]\big\} \right\} = \max\{ M_1, M_2\}$$

Second Direct Application

Consider the equivalent statement of the inequality in terms of the complement (CDF instead of the tail): $$P\left( S_{n_1} - E[S_{n_1}] \leq x \right) > \mathcal{P}_1(x) \equiv 1 - \exp\left[ -x^2 \left( 2\sum_{i=1}^{n_1}\operatorname{Var} (Y_i) + \frac{2}{3} M_1 x \right)^{-1} \right] \\ P\left( S_{n_2} - E[S_{n_2}] \leq x \right) > \mathcal{P}_2(x) \equiv 1 - \exp\left[ -x^2 \left( 2\sum_{i=1}^{n_2}\operatorname{Var} (Z_i) + \frac{2}{3} M_2 x \right)^{-1} \right] $$ again, all the $S_{n_1}$ etc are as defined by you.

The desired probability is a convolution-like integral, due to the direct product of probabilities from independence:

\begin{align*} P\left( S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] > t \right) &= 1 - P\left( S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] \leq t \right)\\ &= 1 - \int_{u = -\infty}^{ \infty} P\left( S_{n_1} -E[S_{n_1}] \leq t \right)\cdot P\left( S_{n_2} -E[S_{n_2}] \leq t-u \right)\,\mathrm{d} u \\ &\leq 1 - \int_{u = -\infty}^{ \infty} \mathcal{P}_1(u) \mathcal{P}_2(t-u) \,\mathrm{d} u \end{align*} Once you figure out the proper range for $t$ to replace the integration lower limit $-\infty$ and upper $\infty$, this integral is not difficult.

Anyway, this is what I consider a "direct application" of Bernstein inequality, and it's definitely not the same as yours.

  • $\begingroup$ Thanks for your response. I agree with the explanation. $\endgroup$ – Mike Kehoe Jun 7 '18 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.