Hoeffding's inequality for sums of pairs of random variables

Question

Let $X_1,\dotsc, X_n$ be $n$ i.i.d. random variables where $X_1 \in [a,b]$. Similarly, let $Y_1,\dotsc,Y_m$ be $m$ i.i.d. random variables where $Y_1 \in [c,d]$. Furthermore, $X_i$ and $Y_j$ are independent for all $i \in \{1,\dotsc,n\}$ and $j \in \{1,\dotsc,m\}$. Intuition tells me that for any $\delta \in (0,1)$ it should hold that: $$ \Pr \left (\mathbf{E}[X_1+Y_1] > \frac{1}{n} \sum_{i=1}^n X_i + \frac{1}{m} \sum_{i=1}^m Y_i - (b-a + d-c)\sqrt{\frac{\ln(1/\delta)}{2\min\{n,m\}}} \right )\geq 1-\delta. $$ How do I go about showing this? It really is true, right? Intuition says that it is true because if we paired up points, $X_i$ and $Y_i$ until we ran out of one type, we could get from Hoeffding's inequality that with probability at least $1-\delta$: $$ \mathbf{E}[X_1+Y_1] > \frac{1}{\min\{n,m\}} \left (\sum_{i=1}^{\min\{n,m\}} X_i+Y_i \right ) - (b+d - (a+c))\sqrt{\frac{\ln(1/\delta)}{2\min\{n,m\}}}. $$ The first equation is the same, except that it uses more samples of one of the random variables ($X$ or $Y$).

I have tried bounding $\mathbf{E}[X_1]$ and $\mathbf{E}[Y_1]$ independently and then using a union bound. I get the top equation, but with $\ln(2/\delta)$ rather than $\ln(1/\delta)$.

Answer 1

This inequality follows from Theorem 2 in Hoeffding's 1963 paper, and in fact Hoeffding's result yields a better bound. Indeed, Hoeffding's inequality can be written as \begin{equation} P(\sum Z_i<t)\ge1-\exp\Big(-\frac{2t^2}{\sum(B_i-A_i)^2}\Big), \tag{1} \end{equation} where $t$ is a nonnegative real number, the $A_i$'s and $B_i$'s are real numbers such that $A_i<B_i$, and the $Z_i$'s are independent zero-mean random variables such that $A_i\le Z_i\le B_i$ for all $i$.

Let now $Z_i:=\frac{X_i-EX_i}n$ for $i=1,\dots,n$ and $Z_i:=\frac{Y_{i-n}-EY_{i-n}}m$ for $i=n+1,\dots,n+m$, so that one may assume that $B_i-A_i=\frac{b-a}n$ for $i=1,\dots,n$ and $B_i-A_i=\frac{d-c}m$ for $i=n+1,\dots,n+m$, with \begin{equation} \sum(B_i-A_i)^2=\frac{(b-a)^2}n+\frac{(d-c)^2}m\le\frac{(b-a+d-c)^2}{\min(n,m)}; \end{equation} the latter inequality follows because $\frac1n\le\frac1{\min(n,m)}$, $\frac1m\le\frac1{\min(n,m)}$, and $(b-a)^2+(d-c)^2\le(b-a+d-c)^2$. Now the inequality in question follows from $(1)$ by taking there $$t=(b-a + d-c)\sqrt{\frac{\ln(1/\delta)}{2\min\{n,m\}}}.$$