As mentioned in the title, we have a chessboard $2\times2$, the king moves with equal probability to each square on the chessboard. King begins from the left upper corner. What is the approximate probability that the king will be standing in the bottom right corner after a thousand moves? I know how to solve it when the number of steps goes to infinity, which would make the probability $1/4$. But is there any trick to do it for a $1000$ moves or is it just "relatively" large number so that I would use my method to solve it as $n$ goes to infinity?
King on reduced chessboard $2\times 2$ moving randomly, what is the probability that it ends up in one of the corners after $1000$ moves
markov chainsprobability
Related Solutions
Details of the method mentioned in @Batman's comment:
We can view each square on the chessboard as a vertex on a graph consisting of $64$ vertices, and two vertices are connected by an edge if and only if a knight can move from one square to another by a single legal move.
Since knight can move to any other squares starting from a random square, then the graph is connected (i.e. every pair of vertices is connected by a path).
Now given a vertex $i$ of the graph, let $d_i$ denote the degree of the vertex, which is number of edges connected to the vertex. This is equivalent to number of possible moves that a knight can make at that vertex (square on chessboard). Since the knight moves randomly, transition probabilities from $i$ to its neighbors is $1/d_i$.
Now since the chain is irreducible (since the graph is connected) the stationary distribution of the chain is unique. Let's call this distribution $\pi$. Now we claim the following:
Claim Let $\pi_j$ denote $j^\text{th}$ component of $\pi$. Then $\pi_j$ is proportional to $d_j$.
Proof Let $I$ be the fuction on vertices of the graph such that $I(i)=1$ if $i$ is a neighbor of $j$, and $I(i)=0$ otherwise. Then
$$ d_j=\sum_i I(i)=\sum_i d_i \cdot \frac{I(i)}{d_i} = \sum_i d_i p_{ij} $$ where $p_{ij}$ is the transition probability from $i$ to $j$. Hence we have $dP=d$ where $P$ is the transition matrix of the chain, and $d=(d_1,\cdots,d_j,\cdots,d_{64})$. Thus $\pi P=\pi \implies$ Claim
Therefore, it follows that after normalising we have
$$ \pi_j=d_j/\sum_i d_i $$
Finally we recall the following theorem
Theorem If the chain is irreducible and positive recurrent, then
$$ m_i=1/\pi_i $$ Where $m_i$ is the mean return time of state $i$, and $\pi$ is the unique stationary distribution.
Thus if we call the corner vertex $1$, we have
$$ m_1=1/\pi_1 $$
You can check that $\sum_i d_i = 336$, and we have $d_1=2$ (at corner knight can make at most $2$ legal moves. Therefore $\pi_1=1/168$ and
$$ m_1=168 $$
Let me solve a related but slightly different problem. Consider a discrete random walk in 2D with $1/4$ probability of moving in each of the four directions for each step. We are given a destination vector $\vec{D}=Xe_1+Ye_2$ and we start at the origin. The question is: Given $n$, what is the probability $P_n$ of ending up at $X$ after $n$ steps.
By an $n$-path, I mean a sequence $\vec{r}_1, \cdots, \vec{r}_n$ with each $\vec{r}=xe_1+ye_2$ being such that either $x=\pm 1$ and $y=0$ or $x=0$ and $y=\pm 1$. There are exactly $4^n$ different $n$-paths. Let $N_n(X,Y)$ be the number of $n$-paths that end at $\vec{D}$. Then $P_n=N_n(X,Y)/4^n$. So we need to find $N_n(X,Y)$.
Take an $n$-path. Let $N^x_{\pm}$ be the number of horizontal steps in $\pm$ directionrespectively. Similarly define $N_\pm^y$. Clearly, $$ N_+^x-N_-^x=X, \qquad N_+^y-N_-^y=Y, \qquad N_+^x+N_-^x+N_+^y+N_-^y=n $$ We furthermore say an $n$-path is $m$-horizontal if $N_+^x+N_-^y=m$. Forgetting for the moment that we only care about non-negative integer solutions, one can solve these four equations $$ \begin{pmatrix} N_+^x\\ N_-^x\\ N_+^y\\ N_-^y \end{pmatrix}=\frac{1}{2}\begin{pmatrix} m+X\\ m-X\\ n-m+Y\\ n-m-Y \end{pmatrix} $$ Which obiously requires $m\geq |X|$, $n-m\geq |Y|$ and that $X+m$ and $n-m+Y$ are even. We say $m$ is $(n,X,Y)$-admissible if given $n,X,Y$, the number $m$ is such that all these conditions are satisfied. Then the number of $m$-horizontal $n$-paths ending at $\vec{D}$ are $$ \nu_m=\binom{n}{m}\binom{m}{N_+^x}\binom{n-m}{N_+^y}= \binom{n}{m}\binom{m}{\frac{m+X}{2}}\binom{n-m}{\frac{n-m+Y}{2}} $$ and the total number of $n$-paths ending at $\vec{D}$ are $$ \boxed{ N_n(X,Y)=\sum_{m\text{ is }(n,X,Y)\text{-admissible}} \binom{n}{m}\binom{m}{\frac{m+X}{2}}\binom{n-m}{\frac{n-m+Y}{2}}} $$ Note that it is not hard at all to find all $m$ that are $(n,X,Y)$-admissible once you know specifically what $n,X,Y$ are. For example, say $X=-10, Y=30$ and $n=1000$. Since $X$ is even, $m$ has to be even. The condition $n-m+Y$ even is automatically satisfied then. So you need $m\geq 10$ and $1000-m\geq 30$. So the set of $(1000, -10, 30)$-admissible $m$'s are all even numbers satisfiying $10\leq m\leq 970$.
Best Answer
After $n$ moves, the probabilities of the three squares other than the starting square are equal by symmetry. Let $p_n$ be the probability of being in the lower right square after $n$ moves. Then the probability of being in the upper left after $n$ moves is $1-3p_n$.
We can find a simple recursion here. To reach the lower right square on the $(n+1)$th move, we must be in one of the other three squares (probability $1-p_n$) after the $n$th move, and then make the correct move from there (probability $\frac13$). Thus $p_{n+1}=\frac13(1-p_n)$.
If $e_n=p_n-\frac14$, we then get $e_{n+1}+\frac14=\frac13(\frac34-e_n)=\frac14-\frac13e_n$, so $e_{n+1}=-\frac13 e_n$. Since $p_0=0$ and $e_0=-\frac14$, we get $e_{1000}=-\frac14\cdot \left(-\frac13\right)^{1000}=\frac{-1}{4\cdot 3^{1000}}$ and $p_{1000}=\frac14-\frac{1}{4\cdot 3^{1000}}=\frac{3^{1000}-1}{3^{1000}\cdot 4}$.
There it is. Exact, even.