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



Hoeffding's inequality for sums of pairs of random variables
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\}}}.$$


