Distribution on a grid

Instead of considering squares, we will consider possible moves that the token can take. It turns out that there are $1192$ possible combinations of starting square and ending square ( $120$ starting squares with $8$ , $44$ with $5$ and $4$ with $3$ ). The conditions of the problem can now be considered like this:

1) The sum of the probabilities of each out-move is the same as the sum of the probabilities of each in-move for each square (equivalent to the same distribution property);

2) The probabilities of each out-move for a given square are the same (uniform movement direction probability).

Suppose there exists an edge on which the probabilities of moving one way and the other way are different. Consider all such edges, and select the edge where the larger of the two probabilities is greatest. That move came from a square where each in-probability must be no larger than the out-probability by the assumption and rule 2, and since one of the edges is imbalanced, property 1 is violated. Hence, on each edge, the out and in probabilities are the same. It is easy to see that this means that all probabilities will be the same (effectively since the board is connected), and thus the probability of making each move is $\lambda = \frac{1}{1192}$ .

Now, we must compute the probability of the third and first square being the same. We will do this by considering each of the $1192$ possible first moves:

$12\lambda$ of moving to a corner square $\times$ $\frac{1}{3}$ of returning $= 4\lambda$ ;

$220\lambda$ of moving to an edge square $\times$ $\frac{1}{5}$ of returning $=44\lambda$ ;

$960\lambda$ of moving to a middle square $\times$ $\frac{1}{8}$ of returning $=120\lambda$ ;

This gives a total of $\frac{168}{1192} = \frac{21}{149}$ , giving a final answer of $\boxed{170}$ .

As a finite irreducible Markov chain, there is only one stationary distribution. Since the chain is time-reversible, it is easy to calculate. The probabilities of $P$ depend on whether the square is one of the $4$ corner squares, one of the $44$ edge squares, or one of the $120$ internal squares. The probabilities of being on a corner, edge and internal square are then $p_c \; = \; \frac{3}{1192} \qquad p_e \; = \; \frac{5}{1192} \qquad p_i \; = \; \frac{8}{1192}$

1. If the starting square is one of the four corner squares, then the probability of returning to the starting square after two moves is $\frac23\times\frac15 + \frac13\times\frac18 \; = \; \frac{7}{40}$

2. If the starting square is one of the $8$ edge squares which are adjacent to a corner, then the probability of returning to the starting square after two moves is $\frac{1}{5}\times\frac{1}{3} + \frac{2}{5}\times\frac{1}{5} + \frac{2}{5}\times\frac{1}{8} \; = \; \frac{59}{300}$

3. If the starting square is one of the other $36$ edge squares, then the probability of returning to the starting square after two moves is $\frac{2}{5}\times\frac{1}{5} + \frac{3}{5}\times\frac{1}{8} \; = \; \frac{31}{200}$

4. If the starting square is one of the $4$ internal squares which are adjacent to a corner square, then the probability of returning to the starting square after two moves is $\frac{1}{8}\times\frac{1}{3} + \frac{4}{8}\times\frac{1}{5} + \frac{3}{8}\times\frac{1}{8} \; = \; \frac{181}{960}$

5. If the starting square is one of the $36$ interior square which are adjacent to an edge, but not adjacent to a corner, then the probability of returning to the starting square after two moves is $\frac{3}{8}\times\frac{1}{5} + \frac{5}{8}\times\frac{1}{8} \; =\; \frac{49}{320}$

6. If the starting square is one of the $80$ fully internal squares, then the probability of returning to the starting square after two moves is $\frac{8}{8}\times\frac{1}{8} \; = \; \frac{1}{8}$

Thus we deduce that $q_P \; = \; \frac{7}{40}\times4p_c + \frac{59}{300}\times8p_e + \frac{31}{200}\times36p_e \\ + \frac{181}{960}\times4p_i + \frac{49}{320}\times36p_i + \frac{1}{8}\times80p_i \; = \; \frac{21}{149}$ and hence $a+b=170$ .

There is only one probability distribution $P$ on a $12 X 14$ chessboard that has the property that after the token is moved at random the distribution still satisfies $P$ . This is when the probability of landing on a corner is $3x$ , of landing on a edge is $5x$ , and of landing anywhere else ("middle" squares) is $8x$ . There are $4$ corners, $44$ edge squares, and $120$ middle squares. Thus $12x + 220x + 960x = 1$ , and $x = \frac {1}{1192}$ . Thus the probability that the token lands on a corner, edge, or middle square is $\frac {3}{1192}, \frac {5}{1192}, \frac {1}{149}$ , respectively.

Looking at the squares, we have $6$ unique probabilities for a token having the same first and last position. The squares with the same probabilities can be split into the following $6$ groups: when it starts in a corner $(4$ squares), when it starts on an edge adjacent to a corner $(8$ squares), when it starts on a middle square diagonally adjacent with a corner $(4$ squares), when it starts on an edge that is not adjacent with a corner $(36$ squares), when it starts on a middle piece that is adjacent to an edge but not a corner $(36$ squares), and when it starts on a middle square only adjacent to middle squares $(80$ squares).

Case 1: The probability that it moves to an edge square is $\frac {2}{3}$ , and the probability that it then moves back to the corner is $\frac{1}{5}$ . The probability that it moves to a middle square is $\frac {1}{3}$ , and the probability that it moves back to the corner is $\frac {1}{8}$ . So we have $\frac {2}{15} + \frac {1}{24}$ . Then, we must multiply this by the probability that it starts on a corner piece (which is $\frac {3}{1192}$ according to $P$ ) and the number of squares in this case, which is $4$ . So for this case we have $p = \frac {21}{11920}$ .

Using the same principles as stated in the first case, we can find the probabilities of the other six cases. Adding together the probabilities found in the six cases we get our final answer of $\frac {21}{149}$ , thus $a + b = 170$ .

For $x$ a cell, let $p(x)$ be the probability of $x$ under a given distribution $p$ and $n(x)$ the number of neighbors of that cell. We show that, in fact, only one probability distribution satisfies the first relation. This probability distribution has $p(x) = c n(x)$ for $c = (\sum_x n(x))^{-1}$ .

We define $q(x)=p(x)/n(x)$ . The first relation, that $p$ is invariant under uniformly distributed "king's moves," means that the probability of being on $x$ is the sum over each neighbor $y$ of $x$ of $p(y)/n(y)$ . That is, the probability of starting on $y$ times the probability of ending up on $x$ given that you started on $y$ . In terms of $q$ , this is $q(x) = \frac{1}{n(x)}\sum_y q(y)$ where the sum is over neighbors. So $q(x)$ takes the value of the average of its neighbors.

Consider the largest value that $q$ takes. That cell must be surrounded by cells of the same value, otherwise the average of its neighbors will be strictly less. As a grid of squares is clearly path-connected, this implies that $q$ must be constant on the entire grid. This determines $p$ up to a constant, which is determined by the fact that probabilities must sum to 1.

Now we find the probability of winding up on the starting square after two moves. Given that we start on a given square $x$ , the probability is the sum, for each neighbor $y$ , of the probability that we move to $y$ times the probability we move back. Thus the desired number is $\sum_x \frac{p(x)}{n(x)} \sum_y \frac{1}{n(y)}$ , where the inner sum is taken over neighbors. Recalling that $q$ is constant, we move it out of the sum. For the remaining part, for each cell $y$ , the term $\frac{1}{n(y)}$ is included once per neighbor of $y$ , ie, $n(y)$ times. Then this sum is the constant value of $q$ times 1 for each cell.

We note that $q(x) = c$ for all $x$ . To compute $c$ we note that each interior edge is involved in one pair of neighbors and each interior vertex is involved in two pairs of neighbors. The number of edges parallel to the long side is $11\cdot14$ . The number parallel to the short side is $12\cdot13$ . The number of interior vertices is $13\cdot11$ . Counting each the appropriate number of times gives $c = (11\cdot14\cdot2+12\cdot13\cdot2+13\cdot11\cdot4)^{-1}$ . Then the desired probability is $12\cdot 14\cdot c = \frac{21}{149}$ , from which we easily obtain 170.