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?

  • $\begingroup$ I don't see why $1000$ should be special in any way. $\endgroup$ – Arthur Feb 13 '19 at 9:23
  • $\begingroup$ Since the king is standing on one of the four fields, there are only three options for him to go. So I would say probability is 1/3. Why you think it is 1/4? $\endgroup$ – user526015 Feb 13 '19 at 9:24
  • $\begingroup$ Just getting to know them, I solved the first part using it. $\endgroup$ – ryszard eggink Feb 13 '19 at 9:24
  • $\begingroup$ @James That's if he only makes one move. We are making 1000 random moves one after the other. It's quite easy to make a sequence ending up in any of the four squares. $\endgroup$ – Arthur Feb 13 '19 at 9:24
  • $\begingroup$ It cannot be exactly $\frac{1}{4}$ after any finite number of moves since at any point, the number of possible moves is $3$ and so there are $3^n$ possible sequences of $n$ moves. If $m$ of these end in the desired location then the probability will be $\frac{m}{3^n}$ which cannot be $\frac{1}{4}$ though it could be very close. $\endgroup$ – badjohn Feb 13 '19 at 9:30

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.