Suppose we’re given a grid of say, 20 by 20, and on this grid we have an imaginary robot at some location (x,y). The robot can only walk forward until it reaches the edge, then
back up a randomly chosen number of steps, and then randomly turn left or right, and continue wandering.
If we also designate a distinct second point (a,b), then can it be proven that the robot will eventually reach this point? What “O” time should we expect…quadratic, cubic, exponential…?
The classic “Drunkard’s Walk” problem has the end distance varying in an exponential fashion. You’ve just gussied it up with “quantum steps” (since you specify right, left, etc.). Look in any good text of probability and statistics.
Search for “random walk” theories, probabilities, and algorithms. In short, random walk is a way of describing the motion of molecules in a gas given an initial position, a period of time, and an average “stride”. It is analogous to your robot example. The name Polya (or something similar) is sticking in the back of my head, too. IIRC, given a limited area, the probability that your robot will reach a specific location is 1.
There’s not really enough information as is. Is the robot equally likely to turn left and right? Is it equally likely to start out facing in any of the four directions? What’s the distribution of the number of steps it takes back? I’d assume uniformity here, but different distributions will give different answers.
It’s actually possible that the robot would never reach that point; it could alternate between legs of an L-shaped path forever (although the probability of this is vanishingly small, it’s non-zero for any finite number of steps).
It’s difficult to give a big-oh answer because I don’t know what input variable you want that in terms of. The distance between (x,y) and (a,b) seems to be the only variable in this situation, but as it’s bounded, that makes it a bit difficult to give a simple answer.
Now that I’ve said that, I do know how to model this, and might be able to give you an answer tonight (although I’d prefer to work with a slightly smaller grid than a 20x20 square).
It’s very close to 1 (and gets closer the more steps you take), but not quite there.
Quite right. that should have read “close to 1”. Thanks for the clarification.
In addition, you might be interested in reading about Markov chains (which should be in any good probability text), which would be a good approach to this type of problem.
That’s actually how I was going to model this. It gets a little tricky, as the minimum number of states needed for a 20x20 grid is 74, but in principle it should work.
Assuming that the random function I used is appropriate, then the robot is equally likely to turn left or right. I actually programmed this as an assignment in a Java programming course to which my company sent me. I began to question whether I’d always hit the goal point when I increased the size of the grid. I noticed then that the robot couldn’t seem to reach his goal…and now I think I know why that happened. The way I’d set it up, the maximum distance that the robot could back up was less than half the width of the grid. This meant that he would continually wander only within a margin whose width was the
same as the the maximum back-up distance; if the goal point was not within this margin then it would never be reached.
I suspect that if I make the appropriate adjustment to the maximum back-up distance, then it would work.
or…alternatively, place the goal point within the margin.
javaman: Assuming equal probabilities for left and right turns does make it a bit simpler. If I do try this, that’s what I’ll do.
No, the probability is exactly 1 (if the area is finite). A probability of 1 does not mean that every conceivable walk will hit the space, if there are an infinite number of possible walks (which, of course, there are).
Repeat: Probability-1 and ‘certainty’ are not the same thing. For instance, suppose you select a real number between 0 and 1, using a flat sampling. It is certain the number you pick will be real, and the probability that you will pick a real number is 1. (Certain always implies probability-1.) Now, what is the probability that the number you select is irrational? As a matter of fact, it’s also 1, despite the fact that there are an infinite number of rationals between 0 and 1; it’s not certain that the number you pick will be irrational, but the probability is 1 (so it’s pretty darned likely). In other words, your chances of picking a rational number are vanishingly small (0). If you don’t understand this, take a good second-year statistics course.
Let’s simplify things a bit:
If you flip a fair coin repeatedly, what is the probability that it will eventually come up heads?
Most people would agree that the coin is certain to eventually come up heads, and that the probability is one. Of course, there is no reason why the grid hypothetical should be seen any differently. As a practical matter of defining probabilities, this is a sensible approach.
Philisophically, the concept troubles me a little, but I’ll have to sleep on it.
The other question is whether probability 1 = certainty.
My instinct is that the two are the same.
Consider the example of a random number from the interval (0,1). Is it certain that the number is irrational? I would say YES. And here’s why I think so:
Any number in the interval (0,1) can be represented as a string of ones and zeros. Thus, 1/2 can be represented as 0.100000000000000 . . . (notice that I’m using binary)
Ironically, the choice of a random real number can be seen as an infinite sequence of coin flips.
Anyway, any rational number will eventually repeat a portion of itself, forever. But it seems to me that a series of coin flips will eventually (with certainty) foul up any pattern.
But please feel free to convince me otherwise. It’s been many years since I’ve studied this stuff.
1, obviously.
I’m not most people, and I disagree. There is nothing theoretically preventing a fair coin from coming up tails each time. The odds are horribly strongly against it, but that is not the same as certainty.
Let me rephrase it: Suppose as in my last post, you picked a real number between 0 and 1. Now suppose that number is rational. Again, there is nothing preventing the number from being rational; a rational number is just as real as an irrational number (for this argument’s sake). But the probability was 0 that you could pick a rational number! So one of the following must be true:
Which do you prefer? I’m guessing you prefer 2), but I’m not going to put words in your mouth. In theory I’m on the side of 1), although if someone came up to me, having picked a real number “at random” between 0 and 1, and it was rational (or even algebraic), I’d offhand say they need a new RNG 
You’re not the first one. When Cantor introduced set theory in the 1870’s, many people (including eminent mathematicians like Kronecker) were so adamantly opposed to his hypotheses that they drove him into an insane asylum. Set theory is now generally accepted as the foundation of all mathematics, although there are still large-ish schools of non-believers, even amoung mathematicians themselves. The objections are philosophical; nobody has come up with a logical proof that set theory is invalid, nor are they likely to.
Depends on your definition of “certainty”. There are certainly rational numbers between 0 and 1; there is certainly an infinite sequence of coin tosses that is all tails. But you’re most welcome to define “certainty” to be equivalent to “probability-1”; I choose not to.
And now we have to define “random” 
But I’m not going to; instead, I’m going to extend a virtual hand as an offer to agree to disagree. Because we’re really saying much the same thing in essence, and we’ve strayed way too far off-topic. If you would like to continue the discussion, please e-mail me and I’ll be glad to talk to you.
MrDeath: You are quite correct; thank you for introducing the necessary level of rigor here (and, incidentally, reminding me to think about these things).
For those who are still interested in the OP – I’ve come up with a 6-state Markov Chain that can be exploited to give the expected number of transitions that the robot makes before it hits the target point. This requires some simplifying assumptions, which I will explain at the time.
But it’s late here, and I didn’t get a whole lot of sleep last night, so I think it’s going to have to wait.
I agree. And I agree that if you define “certainty” consistently with the manner you described, the probability-1 is not the same thing as “certain.”
I also agree that we’ve wandered away from the OP (har har).
An issue that seems to have slipped past everybody while you’ve been arguing about the difference between probability 1 and certainty, is that the answer to the original post doesn’t depend on the grid being 20x20 or even on it being finite in size. The probability of reaching any specified point on a plane grid of infinite size is 1.
What’s possibly more surprising when you first start to think about random walks is that, while that’s true for walks along lines and across planes, it’s not true for random walks in an infinite 3-D space. For instance, the probability of returning to your starting point for a random walk on an infinite 3-D cubical lattice is only about 0.35. Such walks in different dimensions are very important in some areas of maths and physics and such differences can be crucial.
An accessable introduction to the subject is the pair of Martin Gardner columns reprinted in his Mathematical Circus.
bonzer: quite true. I still remember the lecture where my professor proved this fact for all dimensions higher than 1. That class could’ve gotten its own pit thread had I been here while taking it.
One other thing might be worth pointing out. The fact that a walk will hit every point in the plane is dependent on the walk being infinite. If the walk is finite, the probability that it will hit a given point approaches 1 as the walk increases in length.
bonzer:
I think you misread the OP (hell, I also misread it the first time around), it’s not quite the standard random walk. I’m really not trying to be picky here, but I wanted to point this out so ultrafilter in particular (cool name) doesn’t misread it as well and end up modeling the wrong problem by accident.
From the OP:
So, trivially, if we’re on an infinite plane, the probability of hitting any point is not one. There’s a probability of one that the robot will hit any point on the robot’s forward path, but, since an infinite plane has no edge for the robot to change its direction, obviously the probability the robot will hit any other point is zero.