1

enter image description here

Assume we have the following chessboard and we have a knight that starts at the top left corner of the board. On every move the Knight chooses reachable square (i.e. a valid chess move a Knight can make to that square so moving in the shape of an L for the Knight.) Consider a Markov Chain that represents the random walk of the Knight. What kind of Markov Chain is this? Irreducible, reducible, aperiodic, periodic?

My educated guess is that'd it be irreducible since given at state the Knight has the guaranteed possibility to get back to a state it started at by reversing it's actions. Then it'd have to be aperiodic because it's irreducible. Is this correct?

Gooby
  • 149
  • 2
    Think about a two state Markov chain with $P(1 \rightarrow 2) = 1$ and $P(2 \rightarrow 1) = 1$. Irreducible? Aperiodic? – jbowman Apr 14 '22 at 19:28
  • @jbowman this should be irreducible and automatically aperiodic if it's irreducible. It's irreducible, because there exists K steps you can get from any state to any other state with a guaranteed probability > 0. That AFAIK is the formal definition of irreducible, written not so formally. – Gooby Apr 14 '22 at 19:31
  • 2
    See https://stats.stackexchange.com/a/143982/919. You might find it illuminating to consider a knight on a $3\times 3$ board. – whuber Apr 14 '22 at 21:00
  • 1
    Why do you believe irreducible implies aperiodic? Look at @whuber's link, it will clarify this issue for you. – jbowman Apr 14 '22 at 22:47
  • @jbowman does it not? Thought I read that somewhere. – Gooby Apr 14 '22 at 23:25

1 Answers1

1

A quick simulation suggests that the chain in periodic. The knight will never return to start after an odd number of iterations.

A knight starts at position (X, Y). After a significantly large number of iterations (N), the knight is guaranteed to be on one of 50 tiles. These 50 tiles depend on whether (X+Y+N) is even or odd.

This makes intuitive sense since the vector a knight moves always has an L1 norm equal to 3 (an odd number). On the other hand, the vector a bishop moves always has an even L1 norm. Likewise a bishop always stays on either white or black tiles since the color of any tile is a function of (X+Y)%2.

1

  • Red "X" shows the starting position.
  • Faint "0" shows a position with zero probability the knight may be there on the next iteration.
  • Look closely and you'll notice that the probability after 100 iterations depends on the starting position.
Jacob
  • 11
  • Are you using a $10\times 10$ board perhaps? – whuber Apr 14 '22 at 21:01
  • zero-index, 10x10, yes – Jacob Apr 14 '22 at 21:03
  • Why would you use a 10 by 10 board as an actual chess board is 8 by 8? Just curious. – num_39 Apr 14 '22 at 21:06
  • Because I've never played chess (: I updated the image. – Jacob Apr 14 '22 at 21:15
  • In case somebody is curious, the same conclusions are true for odd-sized square boards as well. – Jacob Apr 14 '22 at 21:18
  • Let's not dwell on board sizes or number of iterations. Because the standard checkerboard coloring obviously partitions the squares into two classes and the knight's move alternates between classes, the same conclusion (periodic) applies to moves on any subset of the infinite checkerboard that contains at least one white square and one black square attainable by the knight from its initial position. That includes rectangular and even oddly shaped boards. – whuber Apr 15 '22 at 13:18