Probability inequality for independent random variables with symmetric distributions I'm trying to solve the following question, in particular part (b):


My solution so far:
Denote $\max_{k < n} |S_k| \equiv M_n$ and $A_k \equiv \{|S_k| > x, |S_j| \leq x \quad \forall j < k\}$.  Notice that the $A_k$ form a disjoint collection whose union is $\{M_n >x\}$.  Further, on $A_k$, we have $2x < 2|S_k| = |S_n + X_1 + ... + X_k - X_{k+1} - ... - X_n| \leq |S_n| + |S_n'(k)|$ where $S_n'(k) = X_1 + ... + X_k - X_{k+1} - ... - X_n$ and this implies that at least one of $|S_n|, |S_n'(k)|> x$
For part (a), we have $$P(M_n > x) = \sum_{k = 1}^n P(A_k) \leq \sum_{k=1}^n P(A_k, |S_n| > x) + P(A_k, |S_n'(k)| > x) \\ = 2 \sum_{k=1}^n P(A_k, |S_n| > x) \leq 2P(|S_n| >x)$$
where the second equality follows from the fact that $(X_1, ..., X_n)$ and $(X_1, ..., X_k, -X_{k+1}, ..., -X_{n})$ are equal in distribution.
I have no idea where to even begin for part (b).  Any help would be massively appreciated.
 A: First things first, there is a small (but important) typo in your problem. At least for part $b$, you really want to make sure that the max is over all $k \leq n$. To see it, consider taking $X_1 = X_2 = ... = X_{n-1} = 0$ and $X_n = 10$ w.p. 1/2 and $-10$ otherwise. Let $x = 1$, and $y=1$. The probability on the left is $0$, but the probability on the right is $1/2$.
So, let us try to prove the following statement:
$$P(\max_{k \leq n} S_k > x) \geq 2 P(S_n > x + 2y) - \sum_{i \in [n]} P(X_i > y)$$
As discussed in the comments, we will cut the left hand side into two halves:
$$P(\max_{k \leq n} S_k > x) = P(\max_{k \leq n} S_k > x, S_n < x) + P(\max_{k \leq n} S_k > x, S_n \geq x) $$
Let's handle the easy one first: $P(\max_{k \leq n} S_k > x, S_n \geq x) \geq P(S_n \geq x + 2y)$ since for every path $S_n$ that reaches $x + 2y$, it has to cross $x$ at some point (since $y > 0$),  and if it is larger than $x + 2y$, it is larger than $x$ as well.
Now, we need to show $P(\max_{k \leq n} S_k > x, S_n < x)  + \sum_{i \in [n]} P(X_i > y) \geq  P(S_n > x + 2y)$. The second summand is mostly there to make sure that we exclude all paths that have any $X_i > y$. To be precise, if we have
$$
\begin{equation}
\tag{*}
\label{one} 
P(S_n > x + 2y, \bigcap X_i \leq y) \leq P(\max_{k \leq n} S_k > x, S_n < x)
\end{equation}$$
we can finish the proof since
$$\begin{align}
P(S_n > x + 2y) &= P(S_n > x + 2y, \bigcup X_i > y) + P(S_n > x + 2y, \bigcap X_i \leq y) \\
& \leq P(\bigcup X_i > y) + P(\max_{k \leq n} S_k > x, S_n < x)\\
& \leq \sum_{i \in [n]} P(X_i > y) + P(\max_{k \leq n} S_k > x, S_n < x)
\end{align}$$
The following works for when $X_i$ are discrete for the intuition, the continuous case is below.
So, to show $(\ref{one})$, we look at the set $T_1$ of all the paths that reach to $x + 2y$ that don't have any upward jumps that are larger than $y$ and construct a one-to-one mapping $f$ into the set of paths $T_2$ that go above $x$, and end below $x$, where the mapped path also has the same probability (density, if continuous) This is the fundamental idea behind reflection principle.
Let $P_n = \{S_1, S_2, ..., S_n\}$ be one such path. Since $x > 0$, there is some first time $\tau \geq 1$ s.t. $S_\tau \geq x$, and $S_k > x $ for all $k \leq \tau$. Note that  $S_\tau \in [x, x+y)$ by $X_i$s boundedness. Now, we reflect the walk from $S_\tau$ onward to construct $P' = \{S'_1, ..., S'_n\}$ (where $S'_n = \sum_{i \in \tau} X_i - \sum_{i \in [\tau,n]} X_i)$. Since we know that finally $S_n > x + 2y$, reflecting along $S_\tau$, we must have $S'_n < x$. Note that this map is one-to-one onto its range, since $\tau$ is still recoverable from $P'$, which means we can go back to a unique $P$ given an instance of $P' = f(P)$ in the codomain of $f$ (it is an involution). We also note that the probability of $P$ equals the probability of $P'$ by the symmetry and independence assumptions.
Since this is an injection from $T_1$ into $T_2$, we have that $P(T_1) \leq P(T_2)$, which is what we wanted.
Proof of the continuous case:
For shorthand, let $B = \{\max_i X_i < y \}$, and let $\tau = \{ \min t: S_k > x \}$. Also, let $S_{(k)} = S_n - S_k$.
$$
\begin{align*}
P(S_n > x + 2y, B) &= \sum_{i=1}^{n-1} P(\tau = i, S_i + S_{(i)} > x + 2y, B) \\
&= \sum_{i=1}^{n-1} P(\tau = i, S_i + S_{(i)} > x + 2y, B) \\
&\leq \sum_{i=1}^{n-1} P(\tau = i, S_{(i)} > y, B) \\
&\leq \sum_{i=1}^{n-1} P(\tau = i, S_{(i)} > y, B) \\
&\leq \sum_{i=1}^{n-1} P(\tau = i, S_{(i)} < -y, B) \\
&\leq \sum_{i=1}^{n-1} P(\tau = i, S_i + S_{(i)} < (x + y) -y, B) \\
&\leq \sum_{i=1}^{n-1} P(\tau = i, S_n < x ) \\
\end{align*}
$$
where we heavily rely on the fact that $S_\tau \in [x, x+y)$ in lines 3 and 6.
A: \begin{align}
    P(\max_k S_k > x) \ge P(\max_k S_k > x+y) \quad (1) \\ = P(\max_k S_k > x+y, S_n > x + 2y) + P(\max_k S_k > x+y, S_n \leq x + 2y) \quad (2) \\ = P(S_n > x+ 2y) + P(\max_k S_k > x+y, S_n \leq x + 2y) \quad (3)
\end{align}
We focus on the second term on line (3) from here.
Define $A_k = \{S_k > x+y, S_j \leq x +y \quad \forall j \in \{1, ..., k-1\} \}$ and $S_n'(k) \equiv X_1 + ... + X_k - X_{k+1} - ... - X_n$. \begin{align}P(\max_k S_k > x+y, S_n \leq x + 2y) \ge \sum_k P(A_k, S_n \leq x + 2y, \max_k X_k \leq y) \quad (4) \\ \ge \sum_k P(A_k, S_n'(k) > x + 2y, \max_k X_k \leq y) \quad (5) \end{align}
We get the inequality from (4) to (5) by noting that if $A_k, S'_n(k) > x+ 2y, \max_k \leq y$ holds, we have $$S_n + x+ 2y < S_n + S_n'(k) = 2S_{k-1} + 2X_k \leq 2x + 2y + 2y \implies S_n < x + 2y$$
Now (5) is equal to \begin{align}
    \sum_k \bigg( P(A_k, S_n'(k) > x + 2y) - P(A_k, S_n'(k) > x + 2y, \max_k X_k > y)\bigg) \quad (6) \\
    = \sum_k \bigg( P(A_k, S_n > x + 2y) - P(A_k, S_n'(k) > x+2y, \max_k X_k > y) \bigg) \quad (7) \\ \ge P(\max_k S_k > x+y, S_n > x+2y) - P(\max_k X_k > y) \quad (8) \\ \ge P(S_n > x+2y) - \sum_k P(X_k > y) \quad (9)
\end{align}
where we obtain (7) from (6) by noting the equality in distribution of $(X_1, ..., X_n)$ and $(X_1, ..., X_k, -X_{k+1}, ..., -X_n)$ and (8) from (7) as $A_k \cap \{S_n'(k)> x, \max_k X_k > y\} \subseteq A_k \cap \{\max_k X_k > y\}$ and summing over the disjoint $A_k$.  Combining (9) with (3) yields the desired inequality.
