# Probabilty Bounds for non-negative random variables

I need help with the following question:

Let $$X_i$$ be independent, non-negative random variables, $$i \in \{1,...,n\}$$. I want to show that for all $$t > 0$$, $$P(S_n > 3t) \leq P(\max_{1 \leq i \leq n} X_i > t) + P(S_n >t)^2$$ where we define $$S_n \equiv \sum_{i = 1}^n X_i$$

My "attempt": I'm not really sure how to approach, but obviously we can say that $$P(S_n > 3t) = P(S_n > 3t, \max_{1 \leq i \leq n} X_i > t) + P(S_n > 3t, \max_{1 \leq i \leq n} X_i \leq t) \\ \leq P(\max_{1 \leq i \leq n} X_i > t) + \sum_{i=1}^n P(S_i > 3t, S_j \leq 3t \quad \forall j < i, \max_{i \leq n} X_i \leq t)$$ since we have that $$\{S_n > 3t\} = \bigcup_{i=1}^n \{S_i > 3t, S_j \leq 3t \quad \forall j < i\}$$ and this is a disjoint union, but I don't know where to go from here. Any help would be appreciated!

Let $$A_i(t)$$ denote the event $$\{S_i>t\}$$. As you already showed, it suffices to prove that $$\mathbb P(A_n(3t)\cap\{\max_{1\leqslant i\leqslant n}X_i\leqslant t\})\leqslant \mathbb P(A_n(t))^2$$.

First, observe that for all $$i\geqslant 2$$, $$B_i(t):=A_n(3t)\cap\{\max_{1\leqslant i\leqslant n}X_i\leqslant t\}\cap A_i(t)\cap A_{i-1}(t)^c\subset A_i(t)\cap A_{i-1}^c\cap \{S_n-S_i>t\}.$$ Indeed, if $$\omega$$ belongs to $$B_i(t)$$, it suffices to show that $$S_n(\omega)-S_i(\omega)>t$$. This follows from the fact that $$S_n(\omega)-S_i(\omega)=S_n(\omega)-S_{i-1}(\omega)-X_i(\omega)>3t-t-t.$$ Now, observe that the sets $$B_i(t)$$ are pairwise disjoint and their union is $$A_n(3t)\cap\{\max_{1\leqslant i\leqslant n}X_i\leqslant t\}$$. Therefore, using the inclusion we showed, we get $$\mathbb P(A_n(3t)\cap\{\max_{1\leqslant i\leqslant n}X_i\leqslant t\})\leqslant \sum_{i=2}^n\mathbb P\left(B_i(t)\right)\leqslant \sum_{i=2}^n\mathbb P\left(A_i(t)\cap A_{i-1}^c\cap \{S_n-S_i>t\}\right).$$ So far we did not use any of the assumptions. It is time to do it. First, since the random variables are independent, so are the events $$A:= A_i(t)\cap A_{i-1}^c$$ and $$B:=\{S_n-S_i>t\}$$. Hence, $$\mathbb P(A_n(3t)\cap\{\max_{1\leqslant i\leqslant n}X_i\leqslant t\})\leqslant \mathbb P\left(A_i(t)\cap A_{i-1}^c\right)\mathbb P\left( \{S_n-S_i>t\}\right).$$ Now, using the fact that $$X_i$$ are non-negative gives $$S_n-S_i\leqslant S_n$$ and we conclude using the fact that $$A_n(t)=\bigcup_{i=1}^nA_i(t)\cap A_{i-1}^c$$.

• Really great; thank you so much! Commented Jul 28, 2020 at 23:25

Write $$\tilde{X}_n = X_n \wedge t$$ and $$\tilde{S}_n = \sum_{k=1}^{n} \tilde{X}_k$$. Then we may write

$$\mathbb{P}(S_n > 3t) \leq \mathbb{P}(\max_{1\leq i \leq n} X_i > t) + \mathbb{P}(\tilde{S}_n > 3t).$$

Now define

$$N_1 = \inf\{n \geq 1 : \tilde{S}_n > t\} \qquad\text{and}\qquad N_2 = \inf\{n \geq 1 : \tilde{S}_{N_1 + n} - \tilde{S}_{N_1} > t\}.$$

Since $$\tilde{X}_k$$'s are at most $$t$$, $$\{\tilde{S}_n > 3t\} \subseteq \{ N_1 + N_2 \leq n\}$$. So

\begin{align*} \mathbb{P}(\tilde{S}_n > 3t) &\leq \mathbb{P}(N_1 + N_2 \leq n) \\ &= \sum_{k=1}^{n} \mathbb{P}( k + N_2 \leq n \mid N_1 = k) \mathbb{P}(N_1 = k) \\ &= \sum_{k=1}^{n} \mathbb{P}( \tilde{S}_n - \tilde{S}_k > t \mid N_1 = k) \mathbb{P}(N_1 = k) \end{align*}

By noting that $$\tilde{S}_n - \tilde{S}_k$$ is independent of $$\{N_1 = k\} = \{ \tilde{S}_k > t \geq \tilde{S}_{k-1} \}$$ and identically distributed as $$\tilde{S}_{n-k}$$, the last line is bounded from above by

\begin{align*} &\sum_{k=1}^{n} \mathbb{P}( \tilde{S}_{n-k} > t) \mathbb{P}(N_1 = k) \leq \sum_{k=1}^{n} \mathbb{P}( \tilde{S}_{n} > t) \mathbb{P}(N_1 = k) \\ &\hspace{2em} = \mathbb{P}( \tilde{S}_{n} > t)\mathbb{P}(N_1 \leq n) = \mathbb{P}(\tilde{S}_n > t)^2 \leq \mathbb{P}(S_n > t)^2. \end{align*}

This completes the proof.