# A probability concerning the maximum and minimum of a simple random walk

Let $$X_i$$ be i.i.d. such that $$\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$$. Let $$a\in \{1,2,....\}$$, now define the random walk, $$S_0=a$$ and $$S_n = a+\sum_{i=1}^n X_i$$ Now define the maximum and minimum of the random walk until time index $$n$$ as follows, $$M_n := \sup_{0\leq j \leq n } S_j,\ \ \ \ m_n:=\inf_{0\leq j\leq n} S_j$$ Let $$b\in\mathbb N \backslash \{0\}$$ and define $$k\in\mathbb N$$ such that $$0.

My question: how can I find $$\mathbb P(S_n=b, m_n\leq 0, M_n\geq k)$$

Trials. I wanted to use the reflection principle, so I first considered the cases where the maximum occurred first and where the minimum occured first. I know that both boil down to the same thing, by the duality theorem. So we can as well consider $$u:=\mathbb P(S_n=b, m_n\leq 0, M_n\geq k, \text{ minimum occurred first})$$ See Random walk example for the visualization of random walk I had in mind. So, I start with the blue path. It should cross zero, so I reflected there and got the red path. Then next I should cross the level $$-k$$, but when I get there I reflect again to get the green path. I finnally conclude $$u=\mathbb P(S_n = b-2k)$$

The problem is that I think that this is wrong. Because this finally lead to $$\mathbb P(S_n=b, m_n\leq 0, M_n\geq k)> \mathbb P(S_n=b, M_n\geq k)$$ which is completely nonsense. Sorry I skipped the calculations, but this is the reason I think it is wrong.

If people really want the calculations for $$\mathbb P(S_n=b, M_n\geq k)$$ then I can also write it, but I'm afraid it is too much.

• Do you mean $\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$? Sep 26 '18 at 18:17
• @d.k.o. Sorry was a mistake, should be $-1$, i edited Sep 26 '18 at 18:18

This is quite tricky! Let

• $$E_{u,d}$$ be the set of paths from $$a$$ to $$b$$ for which at some point $$S_i= k$$, and at some later point $$S_j= 0$$, where $$j> i$$.

• $$E_{d,u}$$ be the paths which which hit zero, and then at some later point hit $$k$$.

You want to count $$|E_{u,d}\cup E_{d,u}|$$ First, start by counting $$|E_{u,d}|$$. You do this by reflecting at the first time the path hits $$k$$. Since the original path hit zero at some point after this, the reflected path will hit $$2k$$ at some point after that, so you reflect again at the first after the first reflection point the path hits $$2k$$. The result is a path from $$0$$ to $$b+4k$$. There are $$\binom{n}{\frac12(n+4k+b-a)}$$ such paths.

Similarly, to count $$|E_{d,u}|$$, we reflect at the first time the path hits zero, and the the first time after that the reflected path hits $$-k$$. The result is a path from $$a$$ to $$b-2k$$.

However, we cannot just add $$|E_{u,d}|+|E_{d,u}|$$ to get the size of the union $$|E_{u,d}\cup E_{d,u}|$$. There are overlaps. Specifically, let

• $$E_{u,d,u}$$ be the set of paths which hit $$k$$, then at a later point hit $$0$$, then at a later point hit $$k$$.

• $$E_{d,u,d}$$ be the set of paths which hit $$0$$, then at a later point hit $$k$$, then at a later point hit $$0$$.

The paths in $$E_{u,d,u}$$ have been counted twice in the sum $$|E_{u,d}|+|E_{d,u}|$$, so they need to be subtracted out. You can count $$|E_{u,d,u}|$$ by applying the reflection principle twice. Same goes for $$|E_{d,u,d}|$$. The current sum is $$|E_{u,d}|+|E_{d,u}|-|E_{u,d,u}|-|E_{d,u,d}|$$ However, we are still not done. Defining $$E_{u,d,u,d}$$ similarly, paths in $$E_{u,d,u,d}$$ were counted twice in $$|E_{u,d}|+|E_{d,u}|$$, but then subtracted out twice in $$-|E_{u,d,u}|-|E_{d,u,d}|$$, so they need to be added back in.

It turns out that the pattern continues on exactly like this. Letting $$E_i=|E_{u,d,u,\dots}|$$, with $$i$$ symbols in the subscript, and letting $$F_i=|E_{d,u,d,\dots}|$$ with $$i$$ symbols, the final answer is $$\sum_{i=2}^{\lfloor n/k\rfloor+1} (-1)^{i}\Big(|E_i|+|F_i|\Big)$$ You can write $$|F_i|$$ and $$|E_i|$$ as a certain binomial coefficient by applying the reflection principle $$i$$ times, but I leave this part to you as keeping track of all those reflections is tedious.