# Bernstein inequality

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{\left(\frac{-t^2}{2\sum_{i=1}^{n}\operatorname{Var} (X_i) + \frac{2}{3} Mt}\right)}.$$

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:

\begin{align} &P(S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] > t) \\ &\leq \exp{\left(\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}\right)}. \end{align}

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.

##### Formal justification of the above if needed:

Since $$Y_i$$ and $$Z_i$$ are independent within each set and to each other, along with the upper bounds $$d_i$$ and $$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*} &\phantom{{}={}} 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 not the same as the one presented (unless there's some more steps pushing the inequality in a way I cannot imagine).

• Thanks for your response. I agree with the explanation. Jun 7, 2018 at 4:54