I have a standard 8*8 chess board. And I am analyzing the different possible moves that can be taken by various pieces. I take that there is no other piece on the board except for the Knight, who starts at any one of the 4 corners of the chess board. Now, I am trying to find the stationary distribution value at the starting square. This would give me the long run proportion of time spent at the starting square.
We have 64 states (squares) in total. When worked out, it involves complicated matrix multiplication for several states (squares). Is there any result that I have to use here that I am missing? Any insight will be very helpful. Thank you...
In general, let $G=(V,E)$ be a simple, connected graph which is not bipartite. Consider a random walk on $V$, where if you are currently at vertex $v\in V$, your next step is to one of $v$'s neighbors, chosen uniformly at random. Your knight problem is a special case of this general setup.
These random walks are well-studied. It is well-known that the stationary probability of each vertex is proportional to its degree (see these notes from a course taught by Fan Chung, specifically #2: Stable distributions). That is, the stationary probability of a vertex $v$ is $$ {\deg v \over 2|E|}. $$ For your graph, there are $64$ vertices. It turns out there are $168$ edges, which can be shown as follows. Each edge corresponds to two squares which are a knight's move apart. There are four possible slopes for the line connecting two squares which are a knight's move apart; either $\pm 2$, or $\pm 1/2$. By symmetry, there are the same number of edges of each slope, so we can count the edges with a slope of $2$ alone, then multiply by four to get the total. Suppose that $(x,y)$ is the coordinate of the lower left square of an edge of slope $2$, so the square it is joined to is $(x+1,y+2)$. There are $7$ choices for the $x$ coordinate, as you need $1\le x\le 7$. There are $6$ choices for the $y$-coordinate, as you need $1\le y\le 6$. Therefore, there are $7\times 6=42$ edges of slope $2$, which means there are $4\times 42=168$ edges total.
Furthermore, the degree of the corner vertex is $2$. Therefore, the stationary probability of the corner vertex is $$\frac2{2\cdot 168}=\frac1{168}.$$