Author 
Message 
Bob111 science forum Guru Wannabe
Joined: 13 Jan 2006
Posts: 115

Posted: Sat Jun 03, 2006 11:22 pm Post subject:
2D random walk, first visit to "next" row



Howdy,
The recent thread on 3D random walks reminds me of a 2D random walk
problem I've not been able to solve.
Start at (0,0) on a 2D grid. For each step, choose (with equal
probability) one of the current point's 8 neighbors. Stop the first
time you get to some point (x,1). What is the probability distribution
over y?
I know I could simulate this, but I'm interested in a closed form
result.
Bob H 

Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Wed Jun 07, 2006 11:15 am Post subject:
Re: 2D random walk, first visit to "next" row



Bob wrote:
Quote:  Howdy,
The recent thread on 3D random walks reminds me of a 2D random walk
problem I've not been able to solve.
Start at (0,0) on a 2D grid. For each step, choose (with equal
probability) one of the current point's 8 neighbors. Stop the first
time you get to some point (x,1). What is the probability distribution
over y?
I know I could simulate this, but I'm interested in a closed form
result.
Bob H

I don't really understand the question. Does "the first time you get to
some point (x,1)" mean the first time you hit the line y = 1 (assuming,
I suppose, a square grid with separation 1/n, for some integer n)? But
then what does the "probability distribution over y" mean? The first
time you hit some point (x,1) we will have y = 1, so the answer is
trivial and that can't be what you mean. Maybe you mean the probability
distribution over x  in other words, what is the distribution of the
value of x the first time you hit the line y = 1. I'm guessing though. 

Back to top 


Bob111 science forum Guru Wannabe
Joined: 13 Jan 2006
Posts: 115

Posted: Sun Jun 11, 2006 1:53 am Post subject:
Re: 2D random walk, first visit to "next" row



matt271829news@yahoo.co.uk wrote:
Quote:  I don't really understand the question. Does "the first time you get to
some point (x,1)" mean the first time you hit the line y = 1

Yes.
Quote:  (assuming, I suppose, a square grid with separation 1/n, for some integer n)?

I meant the latiice of points (x, y), where x and y are integers.
Observe, though, that y will never be greater than 1.
Quote:  But then what does the "probability distribution over y" mean? The first
time you hit some point (x,1) we will have y = 1, so the answer is
trivial and that can't be what you mean. Maybe you mean the probability
distribution over x  in other words, what is the distribution of the
value of x the first time you hit the line y = 1. I'm guessing though.

You guessed right.
So you start out at (0,0), and you take a random walk where at any step
you have a probability of 1/8 of stepping to each of the 8 neighbors of
your cerrent location on the grid (I suppose, technically, that this
means the grid includes diagonals with slope 1 and 1).
Thanks for your interest. Any thoughts on how to solve this?
Obviously the distribution for the first visit to y=1 is such that
p(x=k) = p(x=k). On the first step we have a 3/8 chance of hitting
y=1, a 2/8 chance of just shifting the result left or right, and a 3/8
chance of going to y=1. Consider the step to (0,1), from which if we
have something like p(x) = (p*p)(x) (weighted by 1/ where * means
convolution. I know I'm playing sloppy with notation here. Hopefully
not so sloppy that my meaning is missed.
Bob H 

Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Mon Jun 12, 2006 10:34 am Post subject:
Re: 2D random walk, first visit to "next" row



Bob wrote:
Quote:  matt271829news@yahoo.co.uk wrote:
I don't really understand the question. Does "the first time you get to
some point (x,1)" mean the first time you hit the line y = 1
Yes.
(assuming, I suppose, a square grid with separation 1/n, for some integer n)?
I meant the latiice of points (x, y), where x and y are integers.
Observe, though, that y will never be greater than 1.
But then what does the "probability distribution over y" mean? The first
time you hit some point (x,1) we will have y = 1, so the answer is
trivial and that can't be what you mean. Maybe you mean the probability
distribution over x  in other words, what is the distribution of the
value of x the first time you hit the line y = 1. I'm guessing though.
You guessed right.
So you start out at (0,0), and you take a random walk where at any step
you have a probability of 1/8 of stepping to each of the 8 neighbors of
your cerrent location on the grid (I suppose, technically, that this
means the grid includes diagonals with slope 1 and 1).
Thanks for your interest. Any thoughts on how to solve this?
Obviously the distribution for the first visit to y=1 is such that
p(x=k) = p(x=k). On the first step we have a 3/8 chance of hitting
y=1, a 2/8 chance of just shifting the result left or right, and a 3/8
chance of going to y=1. Consider the step to (0,1), from which if we
have something like p(x) = (p*p)(x) (weighted by 1/ where * means
convolution. I know I'm playing sloppy with notation here. Hopefully
not so sloppy that my meaning is missed.
Bob H

No joy with this I'm afraid. I obtained a nasty slowly converging
infinite sum for p(x), but nothing better so far... 

Back to top 


Bob111 science forum Guru Wannabe
Joined: 13 Jan 2006
Posts: 115

Posted: Tue Jun 13, 2006 2:22 am Post subject:
Re: 2D random walk, first visit to "next" row



matt271829news@yahoo.co.uk wrote:
Quote:  No joy with this I'm afraid. I obtained a nasty slowly converging
infinite sum for p(x), but nothing better so far...

OK. Thanks for giving it a try. 

Back to top 


Peter Webb science forum Guru Wannabe
Joined: 05 May 2005
Posts: 192

Posted: Fri Jun 16, 2006 4:49 pm Post subject:
Re: 2D random walk, first visit to "next" row



"Bob" <me13013@hotmail.com> wrote in message
news:1150165378.885885.195060@g10g2000cwb.googlegroups.com...
Quote: 
matt271829news@yahoo.co.uk wrote:
No joy with this I'm afraid. I obtained a nasty slowly converging
infinite sum for p(x), but nothing better so far...
OK. Thanks for giving it a try.

Isn't this a thinly veiled version of a 1D walk?
Movements left or right (along x) have no effect. You have a 3/8 chance of
going up, and a 3/8 chance of goinf down. Forget about moves left or right,
the remaining moves have exactly the same effect as a 1D walk. On average,
2/8 of walks will do nothing  they just increment the "count". So the
probability is 4/3 * p(x), where p(x) is the 1D distribution. Or is this the
trivial case you are referring to, or have I missed something? 

Back to top 


matt271829news@yahoo.co. science forum Guru
Joined: 11 Sep 2005
Posts: 846

Posted: Fri Jun 16, 2006 10:07 pm Post subject:
Re: 2D random walk, first visit to "next" row



Peter Webb wrote:
Quote:  "Bob" <me13013@hotmail.com> wrote in message
news:1150165378.885885.195060@g10g2000cwb.googlegroups.com...
matt271829news@yahoo.co.uk wrote:
No joy with this I'm afraid. I obtained a nasty slowly converging
infinite sum for p(x), but nothing better so far...
OK. Thanks for giving it a try.
Isn't this a thinly veiled version of a 1D walk?
Movements left or right (along x) have no effect. You have a 3/8 chance of
going up, and a 3/8 chance of goinf down. Forget about moves left or right,
the remaining moves have exactly the same effect as a 1D walk. On average,
2/8 of walks will do nothing  they just increment the "count". So the
probability is 4/3 * p(x), where p(x) is the 1D distribution. Or is this the
trivial case you are referring to, or have I missed something?

I think the original post suffered from a typo, which may have caused
the confusion. As I understand it, the problem is actually to find the
distribution of the x coordinate the first time the walk hits the line
y = 1. So, movements left or right very much do have an effect. If
there was no left/right movement then we would have the trivial result
p(x) = 1 for x = 0, and p(x) = 0 for x <> 0. 

Back to top 


Google


Back to top 



The time now is Wed Mar 21, 2018 12:45 pm  All times are GMT

