8
$\begingroup$

I have a question about the random walk of two kings in a 3×3 chessboard.

Each king is moving randomly with equal probability on this chessboard - vertically, horizontally and diagonally. Τhe two kings are moving independently from each other in the same chessboard. Both of them start in the same square, and then they move independently.

How could we find the probability in time $n$ both of them are in the same square, as $n$ goes to infinity?

$\endgroup$
  • $\begingroup$ What is "the same area"? Do you mean "the same square?" $\endgroup$ – Peter Flom Jan 8 '14 at 17:19
  • $\begingroup$ Oh yes,sorry!!! $\endgroup$ – cube Jan 8 '14 at 17:22
  • $\begingroup$ Use transition probability matrix approach $\endgroup$ – vinux Jan 8 '14 at 17:59
  • $\begingroup$ if i do it with transition probability matrix,at first i have to find the transition probability matrix of the first king's random walk and then rise it in the 2? $\endgroup$ – cube Jan 8 '14 at 18:09
  • $\begingroup$ it is an exercise i have and i am trying to solve it for a lot of days now,that was my last idea to get a good idea how to deal with it.. $\endgroup$ – cube Jan 8 '14 at 18:14
12
$\begingroup$

Let's exploit the symmetry to simplify the calculations.

The chessboard and its moves remain the same when the board is reflected vertically, horizontally, or diagonally. This decomposes its nine squares into three types, their orbits under this symmetry group. Correspondingly, each king can be in one of three "states": a corner square ($C$), an edge square ($E$), or the central ("middle") square ($M$). (A state ignores which particular square a king is on and tracks only its equivalence class under the group of symmetries.)

The following results are immediate:

  • From a corner square, there are two transitions to edge squares and one transition to a middle square. Because the three transitions are equiprobable,

    $$\Pr(C \to E) = 2/3,\quad \Pr(C \to M) = 1/3.$$

    This gives a row $(0, 2/3, 1/3)$ in a transition matrix for the states $(C, E, M)$.

  • From an edge square there are two transitions to corner squares, two to other edge squares, and one to the middle square. This gives a second row $(2/5, 2/5, 1/5)$ in a transition matrix.

  • From the middle square there are four transitions to corner squares and four to middle squares. The third row of a transition matrix therefore is $(4/8, 4/8, 0) = (1/2, 1/2, 0)$.

In this graph representing this Markov chain, transition probabilities are represented both by edge thickness and color:

Figure

By inspection or otherwise, we find that a left eigenvector of its transition matrix

$$\mathbb{P} = \left( \begin{array}{ccc} 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{2}{5} & \frac{2}{5} & \frac{1}{5} \\ \frac{1}{2} & \frac{1}{2} & 0 \\ \end{array} \right)$$

is $\omega = (3, 5, 2)^\prime$. This claim is easily checked by performing the multiplication: $\omega \mathbb{P} = 1 \omega.$ The eigenvalue manifestly is $1$. Because all states are connected, $\omega$ gives the limiting probabilities of each king being in each state; we only need to rescale its components to sum to unity:

$$\omega = (\omega_C, \omega_E, \omega_M) = (3/10, 5/10, 2/10).$$

(This is where we reap the benefits of exploiting the symmetry: instead of working with a nine by nine matrix of $81$ elements we only have to compute with a three by three matrix of $9$ elements. The reduction of the problem from nine states to three paid off quadratically by reducing the computational effort by a factor of $(9/3)^2 = 9$.)

The (limiting) chance that both kings are in a state $s$ of (limiting) probability $\omega_s$ is $\omega_s^2$ because the kings move independently. The chance that both kings are in the same cell is found by conditioning on the state: by symmetry, each cell in a given state has the same limiting probability, so if both kings are found in a state $s$ having $k_s$ cells, the chance they are both in the same cell is $1/k_s$. Whence the solution is

$$\sum_{s\in \{C,E,M\}}\frac{ \omega_s^2 }{k_s} = \left(\frac{3}{10}\right)^2\frac{1}{4} + \left(\frac{5}{10}\right)^2\frac{1}{4} + \left(\frac{2}{10}\right)^2\frac{1}{1} = \frac{9}{400} + \frac{25}{400} + \frac{16}{400} = \frac{1}{8}.$$

$\endgroup$
  • 3
    $\begingroup$ Reader @xan makes some very interesting comments after the (beautiful) answer by Accidental Statistician in this thread. Those comments point to a logical gap in my argument: it is necessary also to show that the two kings can (in some intuitive sense) truly move independently of each other. Xan's example concerns kings that cannot make diagonal moves: if one king starts in state $E$ and the other in $C$ or $M$, then they never can occupy the same square! This gap can be fixed by considering a transition matrix for ordered pairs of states. $\endgroup$ – whuber Jan 9 '14 at 22:12
  • $\begingroup$ Thank you for this answer,very intresting and enlightening! $\endgroup$ – cube Jan 10 '14 at 16:32
  • $\begingroup$ @user929304 That's correct. If you imagine a different situation in which those probabilities were each (say) $1/3$, which is quite possible--their total is only $2/3$ for each king--then your formula would give a probability of $2(1/3+1/3)=4/3$ which is obviously wrong. $\endgroup$ – whuber Aug 25 '16 at 14:57
  • $\begingroup$ @user929304 The probability of the union is the sum of the probabilities only when the events are disjoint (aka "mutually exclusive"). Being disjoint is not the same as being independent--in fact, it's a rather extreme violation of independence. $\endgroup$ – whuber Aug 25 '16 at 15:15
  • $\begingroup$ @user929304 Cox and Miller is accessible and covers a lot of ground. $\endgroup$ – whuber Sep 13 '16 at 16:05
10
$\begingroup$

Since the two kings are moving independently, you can consider them separately. If the board is of finite size, and doesn't have any closed subsections, this is one of those cases where the stationary distribution can be found by solving the detailed balance equation.

In this case, as $n$ goes to infinity, the probability of a king being in a square becomes proportional to the number of squares adjacent to it, i.e. three for each corner square, five for each edge square, and eight for the middle square. This sums to $40$, so the chance of being in the middle square is $8/40$, in any corner square is $3/40$, and in any edge square is $5/40$.

Since this is true for both kings independently, the chance of them both being in the middle square is $(8/40)^2 = 64/1600$, of both being in any corner square is $(3/40)^2=9/1600$, and in any edge square is $(5/40)^2=25/1600$. So the chance of them being in the same square approaches $\frac{64+4\times9+4\times25}{1600} = \frac{200}{1600} = \frac{1}{8}$ as $n$ approaches infinity.

$\endgroup$
  • $\begingroup$ Oh,your explanation is really good and i totally understand it!! $\endgroup$ – cube Jan 8 '14 at 17:34
  • $\begingroup$ Can i ask you one more think?In the last equality 1/16+8(9/1024) the numbre 8 is as result from the chessboard's dimensions?It doesn't matter that we have a 3x3 chessboard? $\endgroup$ – cube Jan 8 '14 at 17:45
  • 2
    $\begingroup$ Edge squares are squares that are on the outside, but not in a corner. Each edge square has five neighbours: the middle square, two other edge squares, and two corner squares. $\endgroup$ – Accidental Statistician Jan 8 '14 at 18:41
  • 1
    $\begingroup$ It's sufficient for the graph to be undirected (if you can move from A to B, you can move from B to A), finite (finite number of squares), and complete (no subgroup of squares from which there's no escape), and for the probability of moving in a certain direction from a square being the same for every direction. In this case, the probability of being in a square converges over time to being proportional to the number of adjacent squares. You can check this by solving either for $\pi P=\pi$ as in vinux's answer, or by solving the detailed balance equation, which is easier. $\endgroup$ – Accidental Statistician Jan 9 '14 at 14:50
  • 1
    $\begingroup$ +1 This is a pretty answer. A simple way to justify the assertion quoted by @xan is just apply the transition matrix to that vector of proportions: you will obtain the vector itself (from its very definition!), showing it is an eigenvector of eigenvalue $1$. Because all states are connected, that's the limiting distribution. (In other words, you don't actually have to solve $\pi P = \pi$; you only have to check the solution you have proposed.) $\endgroup$ – whuber Jan 9 '14 at 16:08
6
$\begingroup$

You can solve using transition probability matrix.

$\begin{bmatrix} C_1 & C_2 & C_3 \\ C_4 & C_5 & C_6 \\ C_7 & C_8 & C_9 \\\end{bmatrix}$

Construct Transition probability matrix, using the probability of one cell to another. Eg: $P[C_1, C_2] = P[C_1, C_4]= P[C_1, C_5] = \frac{1}{3}$. P will be a $9 \times 9$ matrix.

Now you can calculate stationary probabilities (Since all states are recurrent).

Solve $\pi P = \pi $ such that $\sum \pi =1$.

This gives the probability of one king in particular square as n large. Use the independence property you can arrive at the required probability.

$\endgroup$

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.