Random Walks with the equality 1/2

Question

I have recently come across this probability question, but I don't have a clear idea of how to proceed with it. the question is as follows:

Consider a random walk on the integers starting at and with a probability of moving in either direction being $\frac {1}{2}$. What is the approximate probability of the walk being at a point in the interval $[-20,20]$ after 1000 moves?

Answer 1

Being inside the interval $[-20,20]$ in $1000$ moves requires you having at most $510$ steps to the right and at least $490$. It is the same question as saying if you toss $1000$ coins what is the probability of $490 \leq H \leq 510 $ This is clearly $\sum\limits_{i=490}^{510} 1000$ choose $i \cdot \frac{1}{2^{1000}} \approx 0.493$
Alternatively you could have modelled the number of heads as a Normal Distributed R.V with mean $500$ and variance $\sqrt{1000\cdot\frac{1}{2}\cdot\frac{1}{2}}^2 = \sqrt{250}^2 \approx 15.813^2$ And our condition is that we must be within $\frac{10}{15.813} \approx 0.63 $ standard deviations of the mean which a simple integral yields to be approximately 0.473

Answer 2

Let each step of the walk be given as $2 \times X_i - 1$, where $X_i \sim Bernoulli(0.5)$. So your position after $n$ steps is $\sum_{i = 0}^n (2 \times X_i - 1) = 2 \times \sum_{i = 0}^n X_i - n$.

So the probability of being in the range $[a, b]$ is $P(a \leq 2 \sum X_i - n \leq b) = P(\frac{a + n}{2} \leq \sum X_i \leq \frac{b + n}{2})$. That means we just have to do something with the distribution of a sum of Bernoulli variables, which hopefully you know something about?