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 '20 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 '20 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 '20 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 '20 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 '20 at 18:42
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 '20 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 '20 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 '20 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 '20 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 '20 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 '20 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.