4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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)$. $\endgroup$
    – Mick
    Aug 9, 2020 at 6:50
  • $\begingroup$ 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? $\endgroup$
    – qp212223
    Aug 9, 2020 at 7:55
  • $\begingroup$ 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$. $\endgroup$
    – Mick
    Aug 9, 2020 at 9:47
  • $\begingroup$ @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). $\endgroup$
    – E-A
    Aug 9, 2020 at 16:52
  • $\begingroup$ 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. $\endgroup$
    – Mick
    Aug 9, 2020 at 18:42

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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] $\endgroup$
    – qp212223
    Aug 9, 2020 at 18:56
  • $\begingroup$ 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!] $\endgroup$
    – qp212223
    Aug 9, 2020 at 19:01
  • $\begingroup$ 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. $\endgroup$
    – qp212223
    Aug 9, 2020 at 19:22
  • $\begingroup$ 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 $\endgroup$
    – qp212223
    Aug 9, 2020 at 19:22
  • $\begingroup$ 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) $\endgroup$
    – E-A
    Aug 9, 2020 at 19:57
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Looks right! good job. $\endgroup$
    – E-A
    Aug 9, 2020 at 21:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .