random walk with absolute value

Question

Given a simple random walk with $S_0 = 0$ and p = q = $\frac{1}{2}$. Find $P(|S_n| \leq 1)$ for n = 1, 2, 3..., N where N is an even number. Any hints or ideas?

Answer 1

Hints:

1. $\ S_n\ $ is odd when $\ n\ $ is odd, and even when $\ n\ $ is even.

2. If $\ S_n = m\ $ then $\ \frac{m+n}{2}\ $ of the first $\ n\ $ steps must have been to the right and $\ \frac{n-m}{2}\ $ of them must have been to the left.

3. The number of rightward steps among the first $\ n\ $ follows a binomial distribution with parameters $\ n\ $ and $\frac{1}{2}\ $.
4. If $\ \left\vert S_n\right\vert\le 1\ $ and $\ n\ $ is even then $\ S_n\ $ must be $\ 0\ $. If $\ \left\vert S_n\right\vert\le 1\ $ and $\ n\ $ is odd then $\ S_n\ $ must be either$\ +\hspace{-0.3em}1\ $ or $\ -\hspace{-0.3em}1\ $.