2D random walk probability to reach a target - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:16:15Z http://mathoverflow.net/feeds/question/40392 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target 2D random walk probability to reach a target Lakshmi 2010-09-28T23:09:34Z 2010-10-15T18:37:12Z <p>Hello Steve,and others thanks.</p> <p>I was not able to get reference on heat equation which was suggested earlier.</p> <p>Also the links that was proposed on wike are general and nothing rigours for 2D discrete random walk.</p> <p>As everyone asked about the question was not clear. All I am looking is analytical approach to solve the 2D, symmetric, unbiased,discrete random walk within a bounded first quadrant regions. The boundary are reflecting boundary. The particle starts at location (x1,y1) and the target is at location b (x2,y2), the particle has to reach within time interval "T".</p> <p>The same condition i wanted to continuous random walk. The reflecting boundaries can be considered here as optional. </p> <p>First i want to consider for unbounded 2-D random walk, Symmetric random walk. Then i want to consider bounded 1st quadrant random walk.</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/40658#40658 Answer by Lakshmi for 2D random walk probability to reach a target Lakshmi 2010-09-30T18:52:00Z 2010-09-30T18:52:00Z <p>So far i have done the simulation using discrete, and continuous. I am interested in both discrete and continous random walk patterns</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/40664#40664 Answer by Steven Heston for 2D random walk probability to reach a target Steven Heston 2010-09-30T19:31:56Z 2010-09-30T19:31:56Z <p>I presume that "2D random walk" means a two-dimensional Wiener process. The process will eventually come arbitrarily close to the origin (or any other point) an infinite number of times.</p> <p>Without more structure, I can only recommend solving numerically. You must solve the two-dimensional heat equation imposing an absorbing boundary condition that is one in the "specified location" and a terminal condition that is zero everywhere else. This will give the probability of hitting the "specified location" before the terminal time. This is pretty easy and accurate to program using finite differences.</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/40681#40681 Answer by Huck Bennett for 2D random walk probability to reach a target Huck Bennett 2010-09-30T22:42:44Z 2010-09-30T22:42:44Z <p>An important property of a simple symmetric random walk on $\mathbb{Z}^2$ is that it's recurrent. This means that the process almost surely (with probability 1) returns to any given point $(x,y) \in \mathbb{Z}^2$ infinitely many times. This is especially interesting because 2 is the highest dimension for which this holds. A SSRW on $\mathbb{Z}^d$ for $d \geq 3$ is transient, meaning that with positive probability it will not return to some state.</p> <p>This difference between discrete random walks in dimensions two and three leads to the famous probability saying, "It's better to get drunk in Nebraska than Manhattan."</p> <p>I see that Steven above mentioned the analogous result for the continuous case (i.e. Wiener process/Brownian motion).</p> <p>Here are some useful links:</p> <p><a href="http://mathworld.wolfram.com/RandomWalk2-Dimensional.html" rel="nofollow">http://mathworld.wolfram.com/RandomWalk2-Dimensional.html</a></p> <p><a href="http://en.wikipedia.org/wiki/Random_walks" rel="nofollow">http://en.wikipedia.org/wiki/Random_walks</a> - Check out the table at the bottom</p> <p><a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf" rel="nofollow">http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter12.pdf</a> - This provides a nice in depth discussion of the properties of discrete random walks, including in the 2D case.</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/40707#40707 Answer by Ori Gurel-Gurevich for 2D random walk probability to reach a target Ori Gurel-Gurevich 2010-10-01T03:44:20Z 2010-10-01T04:17:34Z <p>Suppose for the moment that we're talking about a SRW on $\mathbb{Z}^2$ and the target is the origin. Suppose that you're interested in the time interval $[0,T]$, meaning that you're asking about the distribution of the first hitting time of the origin, denoted $\tau$.</p> <p>Then, very roughly, when you start at distance $r$ from the origin, the probability to hit the origin before getting to distance $\sqrt{T}$ from the origin is about $$\frac{\log(r)}{\log(\sqrt{T})} ,$$</p> <p>in which case it takes about $T$ steps. So this is roughly the probability to not hit the origin before time $T$, when $T >> r^2$. For $T &lt;&lt; r^2$ this probability is close to 1.</p> <p>I hope this helps. It would be useful if you focused the question a bit more.</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/41720#41720 Answer by Wadim Zudilin for 2D random walk probability to reach a target Wadim Zudilin 2010-10-10T22:51:18Z 2010-10-10T22:51:18Z <p>Some history and the latest news about continuous 2D random walk are discussed in <a href="http://www.carma.newcastle.edu.au/~jb616/walkstalk.pdf" rel="nofollow">this talk by Jonathan Borwein</a>; results about discrete random walk on different lattices are surveyed in <a href="http://dx.doi.org/10.1088/1751-8113/42/23/232001" rel="nofollow">Tony Guttmann's paper</a>.</p> http://mathoverflow.net/questions/40392/2d-random-walk-probability-to-reach-a-target/42300#42300 Answer by Lakshmi for 2D random walk probability to reach a target Lakshmi 2010-10-15T15:43:40Z 2010-10-15T15:43:40Z <p>Hello Steve,and others thanks.</p> <p>I was not able to get reference on heat equation which was suggested earlier.</p> <p>Also the links that was proposed on wike are general and nothing rigours for 2D discrete random walk.</p> <p>As everyone asked about the question was not clear. All I am looking is analytical approach to solve the 2D, symmetric, unbiased,discrete random walk within a bounded first quadrant regions. The boundary are reflecting boundary. The particle starts at location (x1,y1) and the target is at location b (x2,y2), the particle has to reach within time interval "T".</p> <p>The same condition i wanted to continuous random walk</p> <p>Thanks again Lakshmi.</p>