Let $S_n$ be a symmetric, simple random walk starting at $0$. Find
$$
P(30 \leq \max(S_k)_{k \leq 100} < 40)
$$
So basically I want to find the probability that a simple random walk of length 100 at least once touches the line of 30 and does not cross or touch the line of 40.
Could anyone give me a hand or solve this? I wish I could show my attempt but there isn't much to show.
Best Answer
(Edited. Sorry for the calculation mistakes committed earlier.)
You can apply the reflection principle to find out the probability $$\mathbb{P}\left(\max_{1\le i\le 100} S_i < M,\ S_{100} = 2k\right),$$ where $2k < M.$ Consider it's complement, i.e. the event where it touches the line $y=M.$ Take the part till the first time it touches that line, and reflect it in that line, so that $(0,0)$ goes to $(0, 2M).$ Now you can easily see that $$\mathbb{P}\left(\max_{1\le i\le 100} S_i \geq M,\ S_{100} = 2k\right) = 2^{-100}\binom{100}{50+k-M}.$$ Here we have $2k<M$ and we need $k\geq M -50$ for the binomial coefficient to be positive (let's assume $M>0,$ then we would have $k\geq M-50>-50.$)
Now take $M=2\ell.$ Hence $$\mathbb{P}\left(\max_{1\le i\le 100} S_i < 2\ell\right)=\sum_{-50\le k<M/2}\mathbb{P}(S_{100}=2k) - \sum_{M-50\leq k < M/2} - \mathbb{P}\left(\max_{1\le i\le 100} S_i \geq 2\ell,\ S_{100}=2k\right)$$ which can be evaluated as $$2^{-100}\left[\sum_{k=-50}^{\ell-1} \binom{100}{50+k} -\sum_{k=M-50}^{\ell-1} \binom{100}{50+k-M}\right].$$ Using this, you can evaluate $\mathbb{P}(30\leq \max_{1\le k\le 100} S_k < 40).$