You have an infinite line made up of one-inch units. Two checkers are on two of the units. The players alternate tossing a coin. Heads, the player moves his checker one unit to the left. Tails, one unit to the right.
As you would expect, given infinite time, the checkers will eventually land on the same unit.
Now assume that, instead of a line, we have a checkerboard with one inch squares. Same rules, instead of a coin an eight-numbered spinner is used, so that a checker can move right/left, up/done, or to one of the four diagonals.
Again, as you would expect, eventually, with infinite time, the checkers will land on the same square.
HOWEVER: I have read that in three dimensions (say an infinite number of infinite checkerboards on top of each other), two-thirds of the time the checkers will NEVER* meet.
A mathematician told me it’s true (though it wasn’t his area and he didn’t know why).
How can this be? They have *infinite *time.
Yes, everything I’ve found confirms that this is true but that there is no simple way to explain why. (One cite, from the Wikipedia article on random walks: “In 1921 George Pólya proved that the person almost surely will in a 2-dimensional random walk, but for 3 dimensions or higher, the probability of returning to the origin decreases as the number of dimensions increases. In 3 dimensions, the probability decreases to roughly 34%.”)
The part that seems to be troubling you is the idea that it’s something that might not happen even given infinite time.
From a mathematical standpoint, the answer to this is No. Since today is (still barely) Pi Day, I will use Pi as an example. The digits of Pi go on forever; its decimal expansion is infinite. Does mean that, given enough time, any particular string of digits (like, for example, your social security number) will appear within the digits of Pi? Not necessarily. That would be the case if Pi is what is called “normal”; but it is not known whether this is in fact true of Pi.
More dimensions mean your checkers have more room to get away from each other. You are basically just considering random walks on certain graphs, and the probability that such a walk returns to the origin. Pólya proved that this occurs with probability 1 on Z and Z[sup]2[/sup], and with some probability strictly between 0 and 1 in higher dimensions. In your formulation, the spaces are slightly different, but similar methods should apply (analysis of generating functions).
Mathworld has a table of the probabilities for dimensions 3 through 8 here: Pólya's Random Walk Constants -- from Wolfram MathWorld
As the number of dimensions goes up, the probability of returning to the starting point decreases.
OK, most of the time, the checkers will be getting further apart, since there’s more ways for them to get further apart than to get closer together. Which means that, on average, if you’re a long time into the game, you’re probably a large distance apart. Which means that if you don’t meet up quickly, then it gets increasingly unlikely that you will.
By the way, it’s an irrelevant distraction to have two checkers taking turns moving. The problem is identical if we just have one checker and one tile on the board marked as the destination.
True, and that’s helpful … but we also have infinite space and that’s what kills your idea … this problem as some similarities to the Knight’s tour problem in chess, except the chess board is bound …
Which means, this is the same problem as the ‘(one marker) random walk returning to the origin’, except starting some distance away from the origin (the direction doesn’t matter). And – I think but am willing to find out from someone who’s going on more than random intuition – the displaced start is irrelevant, since there’s a clearly non-zero chance the marker will end up that distance away from the origin in a finite number of steps.
This makes a bit of sense to me. In one dimension, the odds are quite good that a wandering checker will end up first on one side of the origin and then back on the other side which means it has to cross the origin square to get there. In two dimensions, the odds are quite good that it will cross from one quadrant to another but there are ways to do it without crossing the origin. In three dimensions, the number of paths that take you from one octant to another, without touching the origin, multiply. The higher the dimensions, the more numerous such paths become. But in one dimension, there are no such paths at all.
Even better, notice the fact that the one- and two- dimensional cases can be considered as subsets of the three-dimensional case. Picture an infinite 3D grid of transparent boxes with tokens that jump randomly from one box to an adjacent box. Let (x1,y1,z1) be the coordinates of the first token, and (x2,y2,z2) the coordinates of the second token. In three-dimensions, we score 3D a point when when x1=x2 and y1=y2 and z1=z2 at precisely the same time. For two-dimensions, ignore the z component and just pay attention to x and y. We score a 2D point when x1=x2 and y1=y2 but we don’t care about z1 and z2. For one dimension, ignore y and z and just pay attention to x. We score a 1D point when x1=x2 and we don’t care what happens to y and z. That’s even easier. Obviously, the fewer dimensions that we have to match, the easier it is to score points. And, conversely, the more dimensions we add, the harder it is to score points.
The thing that I find counterintuitive here is the fact that p(2) is 1 (certain to return to the origin), rather than a probability larger than p(3) but less than 1.
Agreed. I think some of the earlier posts are minimizing the counterintuitiveness of Polya’s result. It makes a certain amount of intuitive sense that the probability decreases with increasing dimension, but it’s quite surprising that the change from certainty to non-certainty happens at dimension 3. What’s fundamentally different about 3 dimensions compared to 2? (Which is essentially the OP’s question.)
I’m not sure anything is fundamentally different between 2D and 3D: it’s just that quantity has a quality all its own.
As an illustration, if the checker is 2 spaces from the origin in 1D, it has a 25% chance of arriving at the origin in 2 turns. And a 50% chance of moving closer to the origin in 1 turn.
For 2D, it has a (1/8)^2= only 1.5625% chance of hitting the origin in 2 turns. And a 37.5% chance of moving closer to the origin in 1 turn.
For 3D, it has a (1/26)^2 = 0.1479% chance of hitting the origin in 2 turns. And a 34.62% chance of moving closer to the origin in 1 turn.
I can’t visualize 4D. Yes, yes there is infinite time. But against that there is infinite space in 1D vs 2D vs 3D.
I agree. For any finite number of steps, n, I suspect you’ll get a p(1,n)>p(2,n)>p(3,n)… >0 - it just so happens that for n infinite, both p(1) and p(2) top out at 1 (they can’t go higher, after all).
If you can actually count the number of loops, then you are in good shape. E.g., the 1-d drunkard’s walk case has 2[sup]n[/sup] paths of length n starting from the origin, and the number of these that are at the origin after 2k steps is (2k choose k). For positive n, how many paths of length n arrive at the origin only at the end? These are the coefficients of x[sup]n[/sup] in the series expansion of 1-sqrt(1-4x[sup]2[/sup]), so the drunkard has probability 1/2 of arriving home after 2 steps, 1/8 after 4 steps, then 1/16, 5/128, etc. The infinite sum of these probabilities is 1; it is worth going through this to convince yourself of the fact that the drunkard will almost surely return home in this case.
So one way to approach the problem is to analyse the asymptotic growth of the number of loops as a function of the length; this will be some combinatorial function with the number of dimensions as a parameter. Calculations will not be so easy in higher dimensions and for non-square lattices, but you can see how it might be that the probability will be 1 up to some critical dimension, after which it will decrease. For instance, in Jonathan Novak’s short note in which he studies the generating function, he winds up relating it to the convergence or divergence of the integral of t[sup]-d/2[/sup] from N (some arbitrary number) to infinity.
To try to put it more clearly, consider the probability that the random walk is at the origin after n steps. If this probability decreases fast enough, the probability of getting home will be less than 1. If it decreases slowly, it will be 1. In high dimensions, there are too many ways for long paths to wander off, and therefore the probability of a long path ending where it started is small.
