Probabilty Bounds for non-negative random variables

Question

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!

Answer 1

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$.

Answer 2

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.