Let $X_1$ and $X_2$ be Uniform Random Variables and set $$X = aX_1 + bX_2, $$
with $a \geq 0$ and $b \leq 0$. I'd like to bound $P(X \leq 0)$ using Hoeffding's inequality. How do I do that?
P.S.: I know we can compute $P(X)$ exactly, but I'd like to use the Hoeffding's inequality here. It seems a very straight forward problem, but I do not know how to solve it...
Thanks!
Let $X_1 \sim U[c_1,d_1]$ and $X_2 \sim U[c_2,d_2]$ which implies that:
$aX_1 \sim U[ac_1,ad_1]$ and $bX_2 \sim U[bd_2,bc_2]$
We can't use the usual direction of hoeffding, but a variable $X$ is sub-gaussian if and only if $-X$ is thus: \begin{align} P(X \leq E[X] - t) \leq \exp(\frac{-t^2}{2\sigma^2}), \forall t \geq 0 \end{align} where $\sigma$ is the parameter of subgaussianity (See Wainwright Ch. 2, this looks like a previous version of the chapter https://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf). So in order to use this bound we need to set $t = E[X]$ and thus we need $E[X] = (a(c_1 + d_1) + b(c_2 + d_2))/2 \geq 0$. If this is true we proceed as follows:
Without assuming anything about the independence or dependence of $X_1$ and $X_2$ while we can't say what the distribution of X is, we can say that this random variable must be a bounded variable with support dominated by $[ac_1 + bd_2, ad_1 + bc_2]$. Bounded variables are necessarily sub-gaussian (the tail is measure zero) and it can be show that for bounded variables that the sub-gaussian parameter is at most $\sigma = (f-e)/2$ where $[e,f]$ is the support of the random variable (See Wainwright: High dimensional Statistics Ch. 2.1.2 for example). Thus:
\begin{align} P(X \leq 0) \leq \exp(\frac{-2(E[X])^2}{(a(d_1 - c_1) + b(c_2 - d_2))^2}) \end{align}
From the assumptions I've made we can't guarantee that $E[X] \geq 0$ however. If $E[X] \leq 0$ we can use the bound from below with Hoeffding's using the fact that for bounded random variables that $P(X \geq t + E[X]) \leq \exp(\frac{-2t^2}{(f-e)^2}), \forall t\geq 0$. Here we set $t = -E[X]$ which is positive when $E[X]$ is negative.
\begin{align} P(X \leq 0) &= 1 - P(X \geq 0)\\ &= 1 - P(X \geq E[X] - E[X])\\ &\geq 1 - \exp(\frac{-2E[X]^2}{(a(d_1 - c_1) + b(c_2 - d_2))^2}) \end{align}
So that uses Hoeffding. Again Hoeffding is all about exploiting knowledge of the tails and since for bounded variables the tails don't exist there are likely many sharper bounds than this one. Or just the more assumptions on how the variables are dependent and thus working directly with the mgf of X might be better.
If you assume that $X_1$ and $X_2$ are independent we can use the result that if $\sigma_1$ and $\sigma_2$ are sub-gaussian parameter then the subgaussian parameter of $X_1 + X_2$ is at most $\sqrt{\sigma_1^2 + \sigma_2^2}$ (again wainwright ch.2). In this case it implies that the subgaussian parameter for $X$ is $\sigma = \sqrt{(a(d_1-c_1))^2 + (b(c_2 - d_2))^2}$ as opposed to $a(d_1-c_1) + b(c_2 - d_2)$ and by the triangle inequality is strictly larger and thus sharpens the second inequality.
