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?

Question

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?

Answer 1

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.

Answer 2

The following is a Markov chain approach, since OP tagged it:

There are two states: 1) Not being in the bottom right corner, and 2) being in brc. The transition matrix is $$A=\begin{pmatrix}2/3&1\\1/3&0\end{pmatrix}$$ What is being asked is the value of $$p=\begin{pmatrix}0&1\end{pmatrix}\cdot A^{1000}\begin{pmatrix}1\\0\end{pmatrix}=\frac{1}{4}\begin{pmatrix}0&1\end{pmatrix}\begin{pmatrix}1&-1\\1&3\end{pmatrix}\begin{pmatrix}1&0\\0&(-\frac{1}{3})^{1000}\end{pmatrix}\begin{pmatrix}3&1\\-1&1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\frac{1}{4}\left(1-\frac{1}{3^{1000}}\right)$$ The column $(1,0)$ refers to the starting state of 1) and the left-most $(0,1)$ refers to the end-state 2), with a thousand transitions in between.