|
|
| 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 |
|
 |
matt271829-news@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
|
|
|
matt271829-news@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 |
|
|
matt271829-news@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: | matt271829-news@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
|
|
|
matt271829-news@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: |
matt271829-news@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 |
|
|
matt271829-news@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...
matt271829-news@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 Sat Jun 24, 2017 8:49 am | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Recreational
