Random Walk in 1-D (Q2)

**aman_cc** · May 4th 2010, 02:59 AM

Let at t=0 a drunkard be at x = 0
At each time interval he jumps +/- 1. So at t=1 he is at x = -1 OR at x = 1.

Given that at t = 2n , dunkard is back at x = 0.

So number of possible paths are $2nC_n$

Question
1. Of the above possible paths, how many paths are there such that the drunkard is always within 'a' units from the origin. i.e. |x|<=a for all t = 0,1,2,....2n.

Note: I was able to solve the case where instead of |x|<=a, we just had x<=a. (Using the reflection principle). But with |x| I don't seem to be getting anywhere

Any help here please?

**gmatt** · May 5th 2010, 10:57 AM

Originally Posted by aman_cc

Let at t=0 a drunkard be at x = 0
At each time interval he jumps +/- 1. So at t=1 he is at x = -1 OR at x = 1.

Given that at t = 2n , dunkard is back at x = 0.

So number of possible paths are $2nC_n$

Question
1. Of the above possible paths, how many paths are there such that the drunkard is always within 'a' units from the origin. i.e. |x|<=a for all t = 0,1,2,....2n.

Note: I was able to solve the case where instead of |x|<=a, we just had x<=a. (Using the reflection principle). But with |x| I don't seem to be getting anywhere

Any help here please?

Wouldn't the number of walks with x=0 at t=2n be exactly $\binom{2n}{n}$ . Here is my reasoning: you need exactly n +1 steps and exactly n -1 steps. In total there are 2n steps. If you choose n of these 2n steps to be +1 then the remaining steps must be -1. There are $\binom{2n}{n}$ ways of choosing those steps.

I'm not sure about the second part will think about it.

**undefined** · May 5th 2010, 11:00 AM

Originally Posted by gmatt

Wouldn't the number of walks with x=0 at t=2n be exactly $\binom{2n}{n}$ .

This is the same as what the OP had. It's just that the 2n wasn't subscripted or superscripted so it looked like the expression might refer to something else.

I'm also interested in solving the OP's main problem and am finding it difficult, don't know how much time I can put into it and whether I'd find the answer.

**gmatt** · May 5th 2010, 11:45 AM

Originally Posted by undefined

This is the same as what the OP had. It's just that the 2n wasn't subscripted or superscripted so it looked like the expression might refer to something else.

I'm also interested in solving the OP's main problem and am finding it difficult, don't know how much time I can put into it and whether I'd find the answer.

Wow, thanks for clearing that up, I thought the OP meant $C_n$ as a catalan number!

**aman_cc** · May 5th 2010, 07:23 PM

Originally Posted by gmatt

Wow, thanks for clearing that up, I thought the OP meant $C_n$ as a catalan number!

Sorry for the confusion. I meant $\binom{2n}{n}$ And indeed, I have been thinking on my original problem for couple of days but not going anywhere. Let's see.
Thanks

**gmatt** · May 5th 2010, 10:30 PM

Here is what I got so far.

The idea is to look for a (very complicated) recursion.

I'm going to consider vectors of the form

$ \left[ \binom{a}{b}, c, d \right] $

where

c - the current distance
d - the maximum distance observed so far.

The idea is then to use an extended version of pascals identity:

$ \left[ \binom{2n}{n}, 0, 0 \right] = \left[ \binom{2n-1}{n}, -1, 1 \right] + \left[ \binom{2n-1}{n-1}, 1, 1 \right] $

$ = \left[ \binom{2n-2}{n}, -2, 2 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-2}, 2, 2 \right] $

but clearly
$\left[ \binom{2(n-1)}{n-1}, 0, 1 \right]$ is a recursion on n-1!

In fact you only need to recurse on $\left[ \binom{2n-2}{n}, -2, 2 \right]$ , because the other side of the recursion tree is symmetric.

As you expand out the tree for $\left[ \binom{2n-2}{n}, -2, 2 \right]$ a miracle happens, all the terms you have computed before start reappearing all over the place, for the exact same values of c (thats important) but possibly different values of d (not important to the recursion, but still important in tallying up the number of paths of maximum length d.) So the entire thing starts to recurse, I haven't yet figured out the exact recursion but only the binomial and c are the important values when determining the recursion.

Well, this isn't complete by any stretch of the imagination but it may give some fuel for some better thoughts. Here is a picture of what the (basic) recursion tree looks like, obviously you would need to expand it out to get a better idea:

edit --- it may be unclear why I'm doing such a recursion, so I'll give an example

if you consider the case n=3 then compute the entire recursion tree using that identity until all leaf nodes in the recursion tree you construct are of the form $\left[ \binom{k}{k}, c, d \right]$ or $\left[ \binom{k}{0}, c, d \right]$ then that means to get the number of paths of maximum length d you sum up all the leaf nodes (they will all be equal to 1) where d is the desired value. For n = 3 this gives for d=1, 8, d=2, 10 and d = 3, 2.

**gmatt** · May 5th 2010, 10:56 PM

Forgot to include picture of recursion tree:

**aman_cc** · May 5th 2010, 11:22 PM

Originally Posted by gmatt

Here is what I got so far.

The idea is to look for a (very complicated) recursion.

I'm going to consider vectors of the form

$ \left[ \binom{a}{b}, c, d \right] $

where

c - the current distance
d - the maximum distance observed so far.

The idea is then to use an extended version of pascals identity:

$ \left[ \binom{2n}{n}, 0, 0 \right] = \left[ \binom{2n-1}{n}, -1, 1 \right] + \left[ \binom{2n-1}{n-1}, 1, 1 \right] $

$ = \left[ \binom{2n-2}{n}, -2, 2 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-2}, 2, 2 \right] $

but clearly
$\left[ \binom{2(n-1)}{n-1}, 0, 1 \right]$ is a recursion on n-1!

In fact you only need to recurse on $\left[ \binom{2n-2}{n}, -2, 2 \right]$ , because the other side of the recursion tree is symmetric.

As you expand out the tree for $\left[ \binom{2n-2}{n}, -2, 2 \right]$ a miracle happens, all the terms you have computed before start reappearing all over the place, for the exact same values of c (thats important) but possibly different values of d (not important to the recursion, but still important in tallying up the number of paths of maximum length d.) So the entire thing starts to recurse, I haven't yet figured out the exact recursion but only the binomial and c are the important values when determining the recursion.

Well, this isn't complete by any stretch of the imagination but it may give some fuel for some better thoughts. Here is a picture of what the (basic) recursion tree looks like, obviously you would need to expand it out to get a better idea:

edit --- it may be unclear why I'm doing such a recursion, so I'll give an example

if you consider the case n=3 then compute the entire recursion tree using that identity until all leaf nodes in the recursion tree you construct are of the form $\left[ \binom{k}{k}, c, d \right]$ or $\left[ \binom{k}{0}, c, d \right]$ then that means to get the number of paths of maximum length d you sum up all the leaf nodes (they will all be equal to 1) where d is the desired value. For n = 3 this gives for d=1, 8, d=2, 10 and d = 3, 2.

Well thanks for so much effort. I will have to read your approach carefully. I seem to have heard that this can be solved using the principle of reflection (refer to ballot problem). So I'm working on those lines. Let's see - will post my approach as well once I'm little convinced about it.

**gmatt** · May 6th 2010, 11:15 PM

So after much deliberation, I think I have arrived at the answer.

I do not have the time to explain it in the amount of detail that it deserves so I will not attempt to explain it tonight, I will just present the answer and say that I arrived at it using inclusion-exclusion along with the reflection principle you mentioned.

Before I present the answer, I need to make clear that I use the convention

$ \binom{n}{k} = 0 $

for all $k<0$ .

Let $m=a+1$ .
The number of walks with distance $\le a$ at all times is given by

$ \binom{2n}{n}+2 \sum _{k=1} ^\infty (-1)^k \binom{2n}{n- k m}. $

I will explain in much more detail tomorrow why this is true, since it will take several detailed diagrams to describe how the reflections work and where the inclusion-exclusion principle comes into play. Unfortunately I fear explaining this may take several hours.

**gmatt** · May 6th 2010, 11:22 PM

Originally Posted by gmatt

So after much deliberation, I think I have arrived at the answer.

I do not have the time to explain it in the amount of detail that it deserves so I will not attempt to explain it tonight, I will just present the answer and say that I arrived at it using inclusion-exclusion along with the reflection principle you mentioned.

Before I present the answer, I need to make clear that I use the convention

$ \binom{n}{k} = 0 $

for all $k<0$ .

Let $m=a+1$ .
The number of walks with distance $\le a$ at all times is given by

$ \binom{2n}{n}+2 \sum _{k=1} ^\infty (-1)^k \binom{2n}{n- k m}. $

I will explain in much more detail tomorrow why this is true, since it will take several detailed diagrams to describe how the reflections work and where the inclusion-exclusion principle comes into play. Unfortunately I fear explaining this may take several hours.

As a quick corollary

let $a=0,m=1$ then we have that

$ \binom{2n}{n} = 2 \sum _{k=1} ^\infty (-1)^{k+1} \binom{2n}{n- k} = 2 \sum _{k=1} ^n (-1)^{k+1} \binom{2n}{n- k} $

since we know that for any $n$ we must have that the number of walks with distance always $\le a = 0$ is 0.

**aman_cc** · May 7th 2010, 01:07 AM

Originally Posted by gmatt

As a quick corollary

let $a=0,m=1$ then we have that

$ \binom{2n}{n} = 2 \sum _{k=1} ^\infty (-1)^{k+1} \binom{2n}{n- k} = 2 \sum _{k=1} ^n (-1)^{k+1} \binom{2n}{n- k} $

since we know that for any $n$ we must have that the number of walks with distance always $\le a = 0$ is 0.

Thanks a lot !!! I'm in no hurry so you don't need to stretch yourself to write down the whole explanation. Let me go over your answer carefully.
I also seem to be hitting in some direction. Will post my result today/tomorrow. Thanks yet again

**gmatt** · May 8th 2010, 01:18 AM

Okay,

I made some figures tonight but unfortunately don't have enough time to explain them, I'll just attach them for now and add an explanation the next day hopefully.

**gmatt** · May 10th 2010, 12:25 AM

Okay, here is a very detailed explanation of what is going on.

I wrote it up as a document, because I did not want to struggle with any limitations this forum imposes.

Tell me if you have any questions.

Can be downloaded at : http://sites.google.com/site/garamatt/dlw.pdf

Also added as an attachment.

Ps. I don't know how to delete a post but would like to delete my previous post.

**aman_cc** · May 10th 2010, 12:45 AM

Originally Posted by gmatt

Okay, here is a very detailed explanation of what is going on.

I wrote it up as a document, because I did not want to struggle with any limitations this forum imposes.

Tell me if you have any questions.

Can be downloaded at : http://sites.google.com/site/garamatt/dlw.pdf

Also added as an attachment.

Ps. I don't know how to delete a post but would like to delete my previous post.

Thanks a lot - Let me readup your document

Thread: Random Walk in 1-D (Q2)

LinkBack

Thread Tools

Display

Random Walk in 1-D (Q2)

Similar Math Help Forum Discussions

Random walk

Random Walk

an almost random walk SP

Random Walk in 1-D

Random walk

Search Tags