Let $S_n$ be a simple random walk on $\mathbb{Z}$, starting from 0, and let $c>0$ be an integer. Show that $$ \mathbb{P}\left(\underset{1\leq j\leq n}{\max}|S_{j}|\geq c\right)\leq2\mathbb{P}\left(|S_{n}|\geq c\right) $$
I am struggling with this one for a while, still not sure how to start. My first intuition is to use markov inequallity, but I cant see exactly how. Any help would be highly appreciated.
Hint: Fix $n$ as a positive integer. Just look at the event $\{S_n\geq c\}$ for simplicity (the case $S_n\leq -c$ is similar). Let $M$ be the first time index $i$ such that $S_i\geq c$ (define $M=\infty$ if it never happens). Then $$\cup_{i=1}^n\{M=i, S_n\geq S_i\} \subseteq \{S_n\geq c\}$$ and notice by symmetry that $$P[S_n\geq S_i|M=i]\geq 1/2 \quad \forall i \in \{1, ..., n\} \quad (*)$$ Now you can prove that $$P[\cup_{i=1}^n\{M=i\}] \leq 2P[S_n\geq c]$$
This symmetry argument works whenever we have the following general scenario: $S_0=0$ and $$ S_n = \sum_{i=1}^n X_iV_i \quad \forall n \in \{0, 1, 2, ...\}$$ where $\{X_i\}_{i=1}^{\infty}$ and $\{V_i\}_{i=1}^{\infty}$ are mutually independent processes, $\{X_i\}_{i=1}^{\infty}$ are i.i.d. random variables of any distribution (possibly noninteger), $\{V_i\}_{i=1}^{\infty}$ are i.i.d. with $P[V_i=1]=P[V_i=-1]=1/2$. Then equation (*) applies.