 Forum index » Science and Technology » Math » Recreational
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 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. 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 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 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... 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 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. 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
 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? 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" 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.  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Wed Mar 20, 2019 7:05 am | All times are GMT Forum index » Science and Technology » Math » Recreational
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics reference books for formulaes in stochastic analysis and ... Michael11 Math 0 Thu Jul 20, 2006 12:38 am spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am random walk on graph Eric B num-analysis 1 Thu Jul 13, 2006 7:23 pm Period of random number generators DGoncz@aol.com Math 9 Thu Jul 13, 2006 1:48 am Order Statistic in Random Process/Random Sequence fan_bai@yahoo.com Math 0 Mon Jul 10, 2006 5:03 pm