The drunkard knight's ride

Start with an empty chessboard. Place a knight on a corner square. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?

My thread title is a takeoff of what mathematicians call "the drunkard's walk."

I'll note that the mean number of moves does not have to be an integer. To use a simpler situation to illustrate, suppose all the paths a piece can move on a grid have lengths

2
2
2
3
4

The mean is 13/5 for this hypothetical case; not an integer.

That said, I'll tell you that the knight problem's mean is an integer.
🙂

Originally posted by Paul Dirac II
Start with an empty chessboard. Place a knight on a corner square. Move the knight at random by choosing uniformly from the legal knight-moves at each step. What is the mean number of moves until the knight returns to the starting square?

It's a hard one. I can't off-hand see a way to analyse it; I might have to run a simulation and see what I get.

Originally posted by Paul Dirac II
I'll note that the mean number of moves does not have to be an integer. To use a simpler situation to illustrate, suppose all the paths a piece can move on a grid have lengths

2
2
2
3
4

I'd be surprised to find a knight returning home in exactly 3 moves...

Originally posted by Shallow Blue
I'd be surprised to find a knight returning home in exactly 3 moves...

😵 I was not imagining a knight specifically when I wrote, "To use a simpler situation to illustrate, suppose all the paths a piece can move on a grid have lengths."

Monte Carlo in a computer program could tell you something like 37.03, and you could safely figure the answer to be 37 based on what I said about the answer being an integer. In fact, that is why I gave that hint. That would have been my own approach to solving this.

That said, I have read of a completely different approach that can be done with paper and pencil. More hints in that direction will be given in the next few days.

Originally posted by Paul Dirac II
My thread title is a takeoff of what mathematicians call "the drunkard's walk."

I'll note that the mean number of moves does not have to be an integer. To use a simpler situation to illustrate, suppose all the paths a piece can move on a grid have lengths

2
2
2
3
4

The mean is 13/5 for this hypothetical case; not an integer.

That said, I'll tell you that the knight problem's mean is an integer.
🙂

The number of paths back is infinite and also there are an infinite
number of paths (of infinite steps) which do not return. Does a
"mean" have a meaning in that case?

Originally posted by wolfgang59
The number of paths back is infinite and also there are an infinite
number of paths (of infinite steps) which do not return. Does a
"mean" have a meaning in that case?

Sharp question!

We are straying from my published source, so I will have to freelance it here. 😕

I will claim that for really long paths--ones for which the number of moves greatly exceeds the number of squares (64) on the board, there comes a "point of diminishing returns," so to speak.

For a specific example of what I mean, one possible route back to chessboard square a1 is:

a1 -> b3 -> a1

There is also:

a1 -> b3 -> c1 -> b3 -> c1 -> b3 ... (a million more cycles between squares c1 & b3)... -> a1.

I think you will agree that in the first thousand times you "play the game" by putting the knight on a1 and tallying how long it takes to come back, there will be several instances of the first path above, but almost certainly none of the second path. Do you see this?

The longest, most complicated paths make their contribution to the mean, but their contribution drops off in likelihood "fast enough" with increasing path length that they don't drive the end result to infinity, as it happens.

To all: feel free to disagree with what I just wrote, since as I say I am writing this off the top of my head, and I am not a mathematician.

If the knight is K steps from home and there is 1 way back (underestimate)
Then there is a 1/N chance he will return home in the next K steps, where N is some large number of other paths.

However every time the knight is K steps from home he could go home in he next K steps with a chance of 1/N

After enough chances it will become very unlikely the knight is still out, so I agree, there is a non-infinite average path.

If you allow the knight to continue moving after returning home, the average distance the knight is from home after N movies converges to 3.33 for all squares on the chess board.

I calculated this by labeling each square with the distance to home, and then iteratively evaluating the average distance to home after the next move (using a spreadsheet).

By always zeroing out the "average distance to home after next move" for the a1 square, the "average distance to home after next move" for squares b3 and c2 converges toward what appears to be a value of ~2.6

The values for these squares for the first 10 moves are:
1.0, 1.67, 2.15, 2.38, 2.45, 2.56, 2.54, 2.6, 2.57, 2.61...

For the first move, it is quite obvious that there is a 1/6 chance that the knight returns home after the next move.

I don't know what to do with this series, but the fact that the average distance from square a1 after N moves converges seems helpful

A thank-you to iamatiger and forkedknight for the additional insights.

I should clarify something about my second post which might confuse. I was assuming that each of the five paths were equally likely to occur, thereby getting 13/5 as the mean.

If we imagine that in fact that final path of length 4 was only half as likely to happen as any one of the others, I believe the mean would be (2+2+2+3+ 4/2)/5 = 11/5.

I'll drop a pretty heavy hint on the "book solution" tomorrow.

To clarify a bit more...

If we "played the game" five times and noted that the path lengths happened to be (in any order) 2, 2, 2, 3, 4, we calculate "experimentally" that the mean is 13/5.

If instead we convince ourselves that there are only five paths the piece could take (rather than the infinity of paths available in the actual knight problem) having lengths 2, 2, 2, 3, 4, and we convince ourselves that the last path has half the chance of happening as compared to any of the other four equally-likely paths, we calculate "theoretically" that the mean is 11/5.

One expects that the experimental approach would have a mean that converges to the theoretical mean when the game is played enough times, such as by a computer program.

Originally posted by Paul Dirac II
To clarify a bit more...

If we "played the game" five times and noted that the path lengths happened to be (in any order) 2, 2, 2, 3, 4, we calculate "experimentally" that the mean is 13/5.

If instead we convince ourselves that there are only five paths the piece could take (rather than the infinity of paths available in the actual knight problem ...[text shortened]... ges to the theoretical mean when the game is played enough times, such as by a computer program.

Well, I have now run this a couple of times, and I've come to the following conclusions:

- The mode is indeed, as was obvious from the start, 2, which is also the minimum. It seems that very small numbers are also slightly more common than higher ones, but after that, I can't at a glance see if very high is predictably less common than any merely high count, though in aggregate it does seem to hold.
- The maximum isn't in the millions; of course, in theory that's a possibility, but the highest I've seen was 1390. Tours in the high decades and low hundreds are common; high hundreds are not unheard of.
- The running average rambled all over the 140s in all experiments, with somewhat of a predilection for the higher ones, but looked like it refused to approach any single value more closely than the others. One time it veered into the low 150s but quickly dropped again; another time it stayed in the low 140s for a while but after a while got back up - and then down again.
- There is no indication in my (smallish; a couple of runs of roughly thousand tours each) experiment that the final value, if there is a fixed one, ends up being an integer. If forced to pick, I'd choose 148 and 149, with no idea which it is.

Originally posted by Shallow Blue
If forced to pick, I'd choose 148 and 149, with no idea which it is.

I was hoping someone would put in the effort to run this on a computer. Thanks!

The book answer is in triple digits. Neither of your answers is the right one, but you're in the ballpark.

The book's solution consists of two parts. I'll go through Part 1 today and see if anybody can solve it, and then I'll go through Part 2 tomorrow.

Part 1 should take you less than 15 minutes to figure out. The number it generates will be used in Part 2 to crank out (in a trivial amount of time) the final answer, which will be the mean average.

Network theory (a.k.a. graph theory) is a branch of mathematics that looks at points joined by arcs. The arcs (at least in our case of the knight, for which moves are reversible) are undirected--that is, they do not have arrows on them. The points are usually termed "vertices" and the arcs are usually termed "edges," so I will go with that terminology.

Represent the 8x8 chessboard squares with vertices, one vertex for each square. Represent a knight move like c5-->e6 by drawing an edge between the vertices that represent c5 and e6. Do this until each of the 64 vertices has its complete set of edges attached to it.

The number needed for tomorrow's Step 2 is the number of edges you find this graph to have.

My source has no diagrams; it just tells what the number of edges is. I wanted to verify the number on my own, so I drew an 8 x 8 array of pencil dots (though a network is abstract enough that I didn't have to draw it in such a squarish way) and started connecting the dots ("vertices" ) with arcs ("edges" ) in ways that the knight moves connect chess squares. [Side note: this website inserted smilies until I put a space between the quote mark and the trailing parenthesis in the previous sentence.]

My plan was to finish all the edges and then put a colored marker dot on each edge, one-by-one, while counting. But my sketch got too messy, and I abandoned this in favor of a more arithmetical approach.

From the point of view of the knight, there are several categories of chessboard squares. One category is the (four) corner squares, because each of them is represented by a node having two edges meeting it. Another category is the (eight) perimeter squares abutting corner squares, because each of them is represented by a node having three edges meeting it.

I figured out all the categories and toted up edges, being careful to account for any edges that might be counted more than once by this method. My result agreed with the book.

Feel free to tell us what you get as your Part 1 result. If you can figure out what Part 2 of the problem is, go ahead and solve for the mean. Otherwise, I'll see you tomorrow. 🙂

Can this be solved as if it was a probability problem?

Each square has a distinct probability that a knight will land on it on the next move. This can be calculated from the possible knight positions that will lead to it. Corner squares have 2 squares leading to them, and centre squares have 8.

The matrix looks like this:

23444432
34666643
46888864
46888864
46888864
46888864
34666643
23444432

Using this matrix, the probability (p) of a knight landing on any square can be calculated.

The mean number of moves for the drunken knight is 1/p

The sum of all the possible landings is 342

There are 2 ways to land on a particular corner square

The probability of the knight landing on a particular corner is 2/342 = 1/171.

So the mean number of moves is 171.