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.

• Consider $P(\max_k S_k>x) \geq P(\max_k S_k >x+y)$, and use reflection principle to compute $P(\max_k S_k>x+y, S_n<y) = P(S_n > x+2y)$.
– Mick
Aug 9 '20 at 6:50
• We can split $P(\max_k S_k > x+y) = P(\max_k S_k > x+y, S_n < y) + P(\max_k S_k > x+y, S_n \ge y)$. I'm not sure how you get that equality, as I compute the following: $$P(\max_k S_k > x+y, S_n < y) = \sum_{k = 1}^{n-1} P(S_k > x + y, S_j \leq x+y \quad \forall j < k, S_n < y) \\ = \sum_{k = 1}^{n-1} P(S_k > x + y, S_j \leq x+y \quad \forall j < k, S_n < y, S_n'(k) > 2x + y)$$ but I can't go further than this. The reflection principle is sort of unknown to me at the moment. Could you please elaborate? Aug 9 '20 at 7:55
• Reflection principle is the following: consider you are given an arbitrary trajectory $S_n(\omega)$ s.t. $\max_k S_k(\omega)>x+y$ and $S_n(\omega)<y$. Let $k_0 :=\inf\{k: S_k (\omega)=x+y\}$. Such $k_0$ exists and $k_0\leq n$. Then reflect the tail of the trajectory after step $k_0$ on the horizontal line at height $x+y$. You will end up with a trajectory $S_n'(\omega)$ with $S_n' (\omega)> x+ 2y$.
– Mick
Aug 9 '20 at 9:47
• @Mick you have a typo in both your comments which is probably why OP was confused. (If you reflect a path that hits x+y and goes below y along x+y, you will get a path that gets to 2x + y (just look at the gap between x+y and y) Also, since this is not a continuous time continuous process, your $k_0$ may not exist; you need to replace it by a $\geq$ sign, in which case you need to care where your process is at $k_0$ (Thus there is no obvious slackness in the problem; feel free to read my answer if my comment is unclear).
– E-A
Aug 9 '20 at 16:52
• Yes, this way $k_0$ only exists if $x,y$ are integers, which I silently assumed, and it should be $S_n' <x$. But this was supposed to be a hint, not a precise statement, anyways thanks for pointing it out.
– Mick
Aug 9 '20 at 18:42

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

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

• I think I have a method that works without the latter technical argument you provided here, although yours is an excellent answer: $$P(\max_{k \leq n} S_k > x) \ge P(\max_{k \leq n} S_k > x + y) \\ = P(\max_{k \leq n} S_k > x + y, S_n > x + 2y) + P(\max_{k \leq n} S_k > x + y, S_n \leq x + 2y) \\ = P(S_n > x + 2y) + P(\max_{k \leq n} S_k > x + y, S_n \leq x + 2y)$$ so we only have deal with the second term. $$P(\max_{k \leq n} S_k > x + y, S_n \leq x + 2y) \\ \ge \sum_{k=1}^n P( S_k > x + y, S_j \leq x + y \forall j < k, S_n \leq x + 2y, \max_k X_k \leq y) \quad (E)$$ [will be continued] Aug 9 '20 at 18:56
• I claim that the event inside the parentheses is implied by the event $$\{S_k > x+y, S_ j \leq x+ y, \max_k X_k \leq y, S_n'(k) > x+2y\}$$ since $S_n + x+2y < S_n + S_n'(k) = 2S_{k-1} + 2X_k \leq 2(x + y) + 2y$ which would imply $S_n < x+ 2y$ as required. Now we have $$(E) \ge \sum_k \bigg( P(S_k > x+y, S_j \leq x +y, j <k, S_n'(k) > x+2y) \\ - P(S_k > x+y, S_j \leq x +y, j <k, S_n'(k) > x+2y, \max_k X_k >y \bigg)$$ Notice that $P(S_k > x+y, S_j \leq x +y, j <k, S_n'(k) > x+2y) = P(S_k > x+y, S_j \leq x +y, j <k, S_n > x+2y)$ by the symmetry of the $X_k$ [will be further continued, sorry!] Aug 9 '20 at 19:01
• and that $-P(S_k > x+y, S_j \leq x +y, j <k, S_n'(k) > x+2y, \max_k X_k >y) \ge -P(S_k > x+y, S_j \leq x +y, j <k, \max_k X_k >y)$ $$\implies (E) \ge P(\max_k S_k > x+y, S_n > x+2y) - P(\max_k S_k > x+y, \max_k X_k > y) \ge P(S_n > x+2y) - P(\max_k X_k > y)$$ and we are done. Aug 9 '20 at 19:22
• If you have time to read this (no worries if you don't lol), does this seem correct? I think this was @Mick's hint Aug 9 '20 at 19:22
• I added the continuous case after inspired by your formatting; you can read that and we can go over it. If you can compress yours and format it as a separate answer, I can comment on it (it is right now a bit too clunky for me to read over it) Either way, provided that you are using the fact that X_k are bounded to establish that when the process first exceeds x it will be between x + y and (so you can reflect from there, it should be OK)
– E-A
Aug 9 '20 at 19:57

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

• Looks right! good job.
– E-A
Aug 9 '20 at 21:22