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<a,b<k$.

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.

  • $\begingroup$ Do you mean $\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$? $\endgroup$
    – d.k.o.
    Sep 26 '18 at 18:17
  • $\begingroup$ @d.k.o. Sorry was a mistake, should be $-1$, i edited $\endgroup$ 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.


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.