A math checkerboard question

A math checkerboard question

Suppose you have an infinite row of squares and two checkers. The checkers take turns responding to coin tosses; heads a checker moves right and tails a checker moves left.
Wherever the checkers begin, eventually, given an infinite time, they will meet. Obviously. After all there is infinite time.
Now suppose you have, instead of a row of squares, an infinite checkerboard and a 1-8 spinner.

Checker movements are determined by the spinner: 1 means move straight ahead; 2 means move diagonal ahead right, etc.
Wherever the checkers begin, eventually, given an infinite time, they will meet. Obviously. After all her is an infinite time.
Now the point. Suppose we have an infinite number of infinite checkerboards on top of one another and an appropriate device for determining checker movement.
Wherever the checkers begin, eventually, given an infinite time, they will meet. Obviously. After all there is an infinite time
Well, No. I have read that, on an infinity of infinite checkerboards on top of one another, the checkers will never meet, even in infinite time.
I don’t understand this. How can it be? There is an infinite time and yet the checker never meet. How can this be?

Some background information https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

No, not obviously. Infinite time is not a sufficient condition. After all, if one checker always moved right and the other always moved left, they’d never meet, even given infinite time.

We’ve had long threads beating this issue to death, such as Assuming an Infinite amount of time, are all things inevitable? or Given infinity, is everything imaginable inevitable?

When we discussed the straight line scenario last year I wrote a program to input starting positions and assigned random left/right movements to the two pieces. I was actually surprised at how fast they could came together when started at varying distances. I had the program print (to the screen) the maximum and minimum distances apart. It would update them as it ran and also list how many iterations the new max and min had required. Fascinating to watch, I would start it at say, 1000 units apart and the max and min would update. It might drift until they were 20,000 apart for awhile then in a matter of 15 seconds they would crash together. I don’t have the programming skills to make it a visual output, that would have been neat.


Here’s a very simple intuition. After t steps you can, very fuzzily, expect one checker to reside somewhere inside the hyperball of radius k/√t centered on the other checker. If those points are all equally likely, the probability the two checkers coincide after t steps is the reciprocal of the hypervolume of that hyperball, i.e. (k’√t)[sup]N[/sup] where N is the dimensionality of the hyperball — 2 for your checkerboard, 3 for your stack of checkerboards.

We need not worry what k or k’ is, because all we want to know is if collision is a virtual certainty or not.

The number of collisions after an infinite amount of time is
k’√1[sup]N[/sup] + k’√2[sup]N[/sup] + k’√3[sup]N[/sup] + k’√4[sup]N[/sup] +…

When N = 2 this infinite sum is k’ (1 + 1/2 + 1/3 + 1/4 + 1/5 + …) which is infinite. For larger N, the series converges to a finite sum. Q.E.D.

(I think I’ve posted this argument before at SDMB.)


Ouch! I divided where I should have multiplied and vice vers; even though the final result was correct. Corrections in red:

To put it as simply as possible: With the three-dimensional (or higher) case, the longer you wait, the more opportunity they have to meet… but also, the longer you wait, the further apart (on average) they are, such that meeting becomes less and less likely.

Yes, but the average distance also increases for the 1D and 2D cases.

Yes, but in those cases it’s not enough to overcome the infinite time.

To be clear, I wasn’t trying to show how you can calculate that the cutoff would be between 2 and 3 dimensions. I was just trying to motivate the idea that there could be a cutoff at all, to refute the “but infinity” argument.

This is the second time Steven Estes asked this question this year. The first was back in March.

And I see you gave an argument there similar to mine of why 2 is the largest dimension for which the drunkard is guaranteed to find his way home. Both arguments are based on the well-known fact that ζ(s÷2) converges when s > 2.

(And I think there may be yet another thread on this topic since, as I was typing in my explanation upthread, I felt I’d done it before!)