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!
 A: 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$.
A: 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.
