Random Walk in 1-D

Consider a random walk in one dimension.

Consider a numberline with integers marked on it. A drunkard it at x=0 at t=0. At each time interval he jumps +1 or -1. i.e. at t=1 he can be at x=1 or x = -1

After t = n, let him be at x_n.

What is the probability that |x_n| =< a, where a is some +ve integer.

Any ideas to start on this?

Also I would later want to generalize it to include conditions like
1. x_n > a
2. x_n < b
and combine them using AND, OR.

So please advise. Thanks

Quote:

---

Originally Posted by aman_cc

Consider a random walk in one dimension.

Consider a numberline with integers marked on it. A drunkard it at x=0 at t=0. At each time interval he jumps +1 or -1. i.e. at t=1 he can be at x=1 or x = -1

After t = n, let him be at x_n.

What is the probability that |x_n| =< a, where a is some +ve integer.

Any ideas to start on this?

---

Let p be the probability that he takes a step to the right, then the probability of his being at position 2k-n after n steps is

$\displaystyle \mathrm{P}(X_n=2k-n)=\binom{n}{k}p^k (1-p)^{n-k}$

If p=1/2 this simplifies to $\displaystyle \mathrm{P}(X_n=2k-n)=\binom{n}{k}2^{-n}$, of course.

By setting x := 2k-n it follows from this that if $\displaystyle x\in \{-n,-n+1,\ldots, 0, 1, \ldots, n-1, n\}$, we have

$\displaystyle \mathrm{P}(X_n=x)=\begin{cases} \binom{n}{\frac{x+n}{2}}p^k(1-p)^{n-k}, & \text{if } x+n\text{ is even} \\
0,&\text{otherwise}
\end{cases}$

Given that, the probability that $\displaystyle |X_n|\leq a$ is

$\displaystyle \mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)$
(assuming that $\displaystyle a\in\{0,1,\ldots,n\}$).

Quote:

---

Originally Posted by Failure

Let p be the probability that he takes a step to the right, then the probability of his being at position 2k-n after n steps is

$\displaystyle \mathrm{P}(X_n=2k-n)=\binom{n}{k}p^k (1-p)^{n-k}$

If p=1/2 this simplifies to $\displaystyle \mathrm{P}(X_n=2k-n)=\binom{n}{k}2^{-n}$, of course.

By setting x := 2k-n it follows from this that if $\displaystyle x\in \{-n,-n+1,\ldots, 0, 1, \ldots, n-1, n\}$, we have

$\displaystyle \mathrm{P}(X_n=x)=\begin{cases} \binom{n}{\frac{x+n}{2}}p^k(1-p)^{n-k}, & \text{if } x+n\text{ is even} \\
0,&\text{otherwise}
\end{cases}$

Given that, the probability that $\displaystyle |X_n|\leq a$ is

$\displaystyle \mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)$
(assuming that $\displaystyle a\in\{0,1,\ldots,n\}$).

---

Really sorry but there is an errata in my question. The question is -
How may paths are there which start at
x = 0 (@ t = 0)
and end at
x = x_n (@ t = n)

so that you are never more than 'a' units away from the origin.

Sorry once again plz