# Linear combination of Random Variables less than Zero and Hoeffding's inequality

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.

• Awesome! Thanks! I should have added that $X_1$ and $X_2$ are independent and I have to assume in my problem that $E[X] > 0$. In any way, awesome job! Commented Aug 29, 2020 at 21:33
• @JFarias. Welcome to Cross Validated! Happy to help, but that sounds like this is a homework question rather than research or self-study. In the future, please see the cross validated guidelines about posting homework questions. Typically you need to show the work you've done and explain the approaches you've taken or are considering and then the community tries to give guidance and hints rather than working full solutions. I should have asked before answering and would have proceeded differently. Also, if the answer is satisfactory, please mark it as the solution. Thanks and welcome again! Commented Aug 29, 2020 at 21:58
• Oh, no, that's actually a simplified version of what I am doing for my research. The specific problem that I am looking into is when $X_1$ and $X_2$ are Dirichlet Random Variables (the random vectors) and I'm trying to check the probability that that linear combination leads to a valid prob. distribution, therefore with all its components greater than zero. The thing is that I wasn't able to figure it out not even on the described scenario, so I felt very dumb haha. I'll keep working on it, but your answer was very helpful! Also, yeah, I am new here, so I just marked the question as answered! Commented Aug 29, 2020 at 23:14
• Great! Happy to hear, sorry for the misunderstanding! Good luck! Commented Aug 29, 2020 at 23:16
• Thanks! I may eventually ask other questions here about that. Also, do you suggest a good book on concentration bounds? The Wainwright one seems very good, but would you also know another one? Commented Aug 29, 2020 at 23:20