While it doesn’t really answer why, 3 dimensions is the cutoff point for a number of phenomena, so it’s not really surprising that there would be a hard cutoff there. You can’t make stable gravitational orbits in geometry with more than 3 dimensions, for example.
Well, that depends on what model you’re using for n-dimensional gravity. There’s no one simple, clear answer for that.
I’m not following this. If there are 2 checkers each on a different square on a line, 1000 squares apart and the 2 coin tosses are separate events, then the results are:
(Each one moving left or right)
L - L: no change, 1000 apart
R - R: no change, 1000 apart
L - R: further apart, 1002 apart
R - L closer together, 998 apart
I don’t see anything in that which leads to them having to end up on the same square. I figure you are just going to say, “It’s infinity, dammit, you didn’t play long enough”. I will readily admit that infinity is a comfortable concept to you theoretical guys, but a figment of imagination to us practical guys. It’s like all the people who prove mathematically that time travel is possible. That’s a great concept but it ain’t gonna happen.
Now I do have a good idea on how to test this. I have to run right now, I’ll be back later to see if anyone wants to take up the challenge.
Dennis
Presumably, the difference you’re noting is that the OP formulates things (at least in the 2d case) so that we can move along diagonals as well? I.e., instead of picking a particular coordinate at random and then flipping a coin for whether to -1 or +1 that coordinate, we flip -1, 0, +1 coins for EACH coordinate (and if the result is all 0s, we retry till it isn’t). No one else in the thread seems to have taken note of this potentially important distinction.
But I suspect the OP meant to be describing the traditional former, and just accidentally described the latter instead, especially as the OP gave the same traditional “about one third” (actually slightly higher) probability for 3d…
Here’s a very simple way to think about the problem, though it still doesn’t make it obvious how to solve it in higher dimensions:
As Chronos noted, rather than thinking of two pieces moving relative to each other, we can think of one piece moving relative to some fixed “origin”.
What’s the probability that you ever return back home to the origin, starting from some other position P? (This is described by some function from positions to probabilities). Well, in your first move, you have an equal chance of getting to any of P’s neighbors, and then the probability you ever return home from thereon out is the probability of returning home from that neighbor. So the return probability from P is the average of the return probabilities from P’s neighbors. [Except for that at the origin itself, the return probability is, by fiat, 100%].
This puts tight constraints on the kind of function this can be. (In fact, by general theory I’ve spelt out on this board before, we actually know that the return probability function is the SMALLEST function which is everywhere >= 0 and satisfies this recurrence.)
In 1d, it’s easy enough to see that the only function of this form is the constantly 1 function, so the return probability is 100% from everywhere. (If each position’s return probability is the average of its neighbors’, then these probabilities simply change linearly as we move away from the origin. To avoid eventually going negative, they mustn’t decrease. Thus, they must be constantly 100%).
In higher dimensions, it’s not quite so simply immediate to understand the behavior of solutions to this recurrence, but still, that may throw some perspective on things.
Is it significant that the roaming space is limited? In a checkerboard you’re limited to 8 x 8; in a nD checkerboard you’d be presumably limited to 8[sup]n[/sup]. The Wikipedia article mentions boundaries but simply gives the probability of hitting the boundary.
What troubles me is that it would seem that what would apply in three dimensions would apply in two. You could view the whole thing in two dimensions, with there just being an additional step of choosing to move 0. Then you can also see that one dimension as just moving along a line, with more chances for a 0 move.
So the only thing I can see is that the addition of the 0 move is what makes it not 100% likely.
In one dimension the probability of a randomly being back at the starting point after exactly 2n moves is proportional to 1/sqrt(2n) as 2n becomes large. The probability of ever returning to the starting point is related to the sum over n from 1 to infinity of 1/sqrt(2n), and the sum diverging means the probability of returning to the starting point is 1. In two dimensions, probability of both the x and y coordinates simultaneously being the same as the starting value is proportional to (1/sqrt(2n))^2=1/(2n). The sum of 1/(2n) diverges so probability of returning to starting point is 1. In three dimensions probability is related to (1/sqrt(2n))^3= 1/(2nsqrt(2n)). The sum of 1(2nsqrt(2n)) converges, and the sums for the higher dimensions converge too.
Whether diagonal steps or only orthogonal steps are permitted changes the proportionality constant in the sums, but not the 1/sqrt(2n) factor. The 1/sqrt(2n), 1/(2n), or 1/(2n*sqrt(2n)) proportionality factors can be proven by enumerating all the ways of returning to the starting point after 2n steps and taking limit for large n, or the sum of all the motions can be approximated by a normal distribution with the Central Limit Theorem.
You have a 100% chance of returning back to the same XY coordinates as where you started (or for two people to land on the same XYZ coordinates as each other, if you prefer that framing), but that doesn’t mean you have a 100% chance of returning back to the same XYZ coordinates as where you started (or for two people to land on the same XYZ coordinates as each other, if you prefer that framing). You may well only ever end up strictly above or below where you started (/the other person) without hitting it on the dot.