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


1 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\}}}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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