Wandering on a two-dimensional grid?

Question

You are at the origin (0,0) of an x-y grid. You now randomly select a direction to move one unit, either up, down, left, or right, bringing you to (1,0), (0,1), (-1,0), or (0,-1). Repeat this an infinite number of times; for example, your random path may start (0,-1), (-1,-1), (-2,-1), (-2,0), (-2,1), (-3,1), etc.

Is your infinite path certain to contain the point (1,0)? In other words, are the odds 100% you will hit (1,0) eventually? If not, what are the odds?

Idleness has the same intuitive feel for this question as I do, that the odds have to be less than 100%. Unfortunately, our intuition is wrong (heh heh). However, Idleness did drop the hint about this sounding like the random walk problem. That gave me something to search on, which led me to the same site Scythian found.

So, the odds are 100%, as proven by a mathematician named Polya. From this it follows that eventually you will hit EVERY point eventually, since there is a probability > 0 you can get to the point. (If you can get there, then the 100% probability says you have to get back.) Weird concept.

Now I am wondering... cover the plane with triangles instead of squares. Then you have six options at each point instead of four. Are the odds you get back to your starting point still 100%?

Answer 1

I have trouble finding references, but Erdos proved that for a 1D lattice random walk, the probability of return to the origin (0,0) is certainity. The same is true for 2D lattice, as with your example, only that you've simply designated (1,0) as "the new origin" For 3D and higher dimensions, the probability of return is less than certainity. I'll try to find links to this subject.

Addendum: Okay, check this Wolfram site on Polya's random walk constants.

Answer 2

well the odds cant be 100% since theres an infinate number of points besides, but this is an interesitng problem which reminds me a lot of the random walk problem, which i studied and understood before but have since forgotten, you can find some link to that problem for sure.
Off the top of my head, I would think of a way to at least find boundries for the solution, by saying that after n steps, you are somewhere within an nxn square, and imagine we are simply selecting n points at random, with repitition allowed. This would seem to suggest that when you take the limit as n goes to infinity, the chance that you land on any point in particular is constantly decreasing at a rate slightly greater than n/n^2 - in fact zero!!..
Anyway, it would seem u have a greater chance to hit some given number closer to where you start than further. I suppose there is 1 way to actually land on the point for n = 1=1/4 probability + 0 ways with n = 2, + 2 ways with n = 3 (which is 2/4^3)so the sequence looks liek 1/4+0/4^2+2/4^3...this would certainly be a convergent series if you find the general pattern and would give you a way to calculate the probability.

Answer 3

For an infinit number of moves of course. No matter how small the probability of your landing there, it will have to occur in an infinite number of tries.