I've been wondering about how can I calculate the limit of this matrix: 
These states the different movements of the knight within a $4\times3$ chessboard, and what I'm trying to do with the limit is to get an insight of the long-term probability of being on each and every square, in order to analyze which squares are the most difficult to get to or the once less likely to be visited on a random knight's tour attempt. I really appreciate the help.
Asked
Active
Viewed 132 times
0
Anton Vrdoljak
- 2,717
-
Have you tried jordan normal form? It is easier to calculate an arbitrary power of the matrix when it's decomposed in JNF – dnes Oct 01 '23 at 10:37
-
See here for a related problem, in particular check the link in the question for an analytic solution of that problem. I think it should apply here in essentially the same way. – jd27 Oct 01 '23 at 11:10
-
@dnes is there any less complicated way of getting to the limit? I've tried reading it and it seems really complex. Can you recommend any other method? – Daniel Alonso Paz Oct 02 '23 at 11:33
-
@DanielAlonsoPaz in case of a completely arbitrary matrix $A$ -- not that I know of any other methods. But there is a great idea in an answer below. – dnes Oct 02 '23 at 18:30
1 Answers
1
Given that the markov chain is irreducible and aperiodic, which it is, the limiting distribution coincides with the unique stationary distribution, which can be found as the solution $\pi$ to the equations: \begin{equation} \pi X = \pi \quad \text{ and } \quad \sum_i \pi_i = 1 \tag{1}\end{equation} where $X$ is the transition matrix. You are asking specifically for the limit of the transition matrix $X^n$, but since the limiting behaviour cannot depend on the initial distribution, we must have that all rows are equal in the limit. In fact all rows of the limiting matrix will be equal to the limiting distribution $\pi$, which can be found as the solution to $(1).$
