How to calculate the probability of 1 dimensional symmetric random walk to escape the ball?

Question

I'm struggling to calculate escaping probability of symmetric random walk with 1 dimension. How to calculate the probability of symmetric random walk to exit the ball with radius n^{x} centered 0 after n steps? Is there a paper related to this one? I'm sorry for my poor English.

Answer 1

Let $S_{n}=\sum_{j=1}^{n} X_{j}$ be the position of the random walk on the number line.

The number of different walks of n steps where each step is +1 or −1 is $2^{n}$. For the simple random walk, each of these walks is equally likely. In order for $S_{n}$ to be equal to a number k it is necessary and sufficient that the number of +1 in the walk exceeds those of −1 by k. It follows +1 must appear $\frac{n + k}{2}$ times among n steps of a walk, hence the number of walks which satisfy $S_{n} = k$ equals the number of ways of choosing (n + k)/2 elements from an n element set. Notice that n+k must be even since n=j+k+j where j is the number of -1 steps, so $n+k = 2j + 2k$ and we get the formula.

$$P(S_{n}=k) = \frac{n!}{(n-\frac{n+k}{2})!(\frac{n+k}{2})!2^{n}}$$

Using a symmetry we get $P(S_{n}=k)=P(S_{n}=-k)$.

So for n and k even:

$$P(|S_{n}|\leq k) = \sum^{k/2}_{j=0}2 P(S_{n} = 2j) - P(S_{n} = 0) = - \frac{n!}{2^{n}(\frac{n}{2}!)^{2}} + 2\sum^{k/2}_{j=0} \frac{n!}{(n-\frac{n+2j}{2})!(\frac{n+2j}{2})!2^{n}}$$