Union bound for sum

60 Views Asked by At

Suppose we have $$\Pr (a_\ell \leq b_\ell) \leq 1-\delta_\ell$$ for $\ell = 1,\dots L$. Is it possible to use Union bound to show $$\Pr (\sum_{\ell = 1}^L a_\ell \leq \sum_{\ell = 1}^Lb_\ell) \leq 1-\sum_{\ell = 1}^L\delta_\ell,$$ or $$\Pr (\sum_{\ell = 1}^L a_\ell \leq L \max_{\ell} b_\ell) \leq 1-L \max_{\ell}\delta_\ell.$$ Here $a_\ell$ are arbitrary, $b_\ell$ are non-negative, and $0<\delta_\ell <1$. Additionally, if helps we can assume $b_\ell$ can grow with $\log \frac{1}{\delta_\ell}$.