2
$\begingroup$

As we know, if $X_1, ..., X_n$ are independent random variables bounded by the interval $[a_i, b_i]$ and $S_n = X_1 + ... + X_n$, the Hoeffding's inequality suggests the following. $P(S_n -E[S_n] \geq t) \leq \exp\bigg(-\frac{2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\bigg)$

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. I would like to have a Hoeffding's bound for $P(S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] \geq t)$.

My try:

$P(S_{n_1}+S_{n_2} -E[S_{n_1}+S_{n_2}] \geq t) \leq \exp\bigg(-\frac{2t^2}{\sum_{i=1}^{n_1}(d_i-c_i)^2 + \sum_{i=1}^{n_2}(f_i-e_i)^2}\bigg)$

I am wondering whether the above equation is correct.

$\endgroup$
  • 1
    $\begingroup$ I see no mistake as you still have a sequence of independent RVs. $\endgroup$ – user52227 Jun 1 '18 at 18:43
  • $\begingroup$ Thanks for the help! $\endgroup$ – Mike Kehoe Jun 1 '18 at 19:57

Your Answer

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

Browse other questions tagged or ask your own question.