Random Walk in 1-D

Printable View

May 3rd 2010, 12:40 AM
aman_cc

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
May 3rd 2010, 07:39 AM
Failure

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

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

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

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

$\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} \\<br /> 0,&\text{otherwise}<br /> \end{cases}$

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

$\mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)$
(assuming that $a\in\{0,1,\ldots,n\}$ ).
May 3rd 2010, 10:14 AM
aman_cc

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

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

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

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

$\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} \\<br /> 0,&\text{otherwise}<br /> \end{cases}$

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

$\mathrm{P}(|X_n|\leq a) = \sum_{x=-a}^a\mathrm{P}(X_n=x)$
(assuming that $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