# Random walking on a board

There’s a pawn starting in the center of this game board. At each move, it can advance randomly towards any of the adjacent squares sharing a common side with equal chance. What’s the probability of landing on the crossed spot on the ninth move?

This question is from a Swiss math contest, the FSJM, in 2008. The original questions are only available in French

• Can you please put your source in? It's actually required on this forum. – Dr Xorile Jun 1 '20 at 23:01
• The source is in French though. fsjm.ethz.ch/static/oldwebsite/documents/22_demi_enonces_F.pdf – Display maths Jun 1 '20 at 23:10
• It doesn't matter if it's in a different language. We just want to know where it comes from! Thanks – Dr Xorile Jun 1 '20 at 23:12
• Your welcome Dr Xorile. – Display maths Jun 1 '20 at 23:32
• Edited to add links to the question itself. – Stig Hemmer Jun 2 '20 at 8:31

$$\frac{935}{13122}$$

Proof

After an even number of moves the pawn must be on one of the shaded squares

Due to the symmetry of the problem the probability of being on any of the four surrounding squares is equal so this simplifies the calculation a bit.
If the pawn is on the centre square at move $$n$$ then it has probability $$\frac{1}{6}$$ of being on each surrounding square at move $$n+2$$ and probability of $$\frac{1}{3}$$ of being back in the centre.
If the pawn is on a surrounding square at move $$n$$ it has probability of $$\frac{1}{9}$$ of being at the centre at move $$n+2$$. This means we generate the following probabilities after $$2n$$ moves:

2 moves: $$p(centre) = \frac{1}{3}$$, $$p(surround) = \frac{1}{6}$$ each
4 moves: $$p(centre) = \frac{1}{9} + \frac{4}{54} = \frac{10}{54}$$, $$p(surround) = \frac{11}{54}$$ each
6 moves: $$p(centre) = \frac{10}{162} + \frac{44}{486} = \frac{74}{486}$$, $$p(surround) = \frac{103}{486}$$ each
8 moves: $$p(centre) = \frac{74}{1458} + \frac{412}{4374} = \frac{634}{4374}$$, $$p(surround) = \frac{935}{4374}$$
which means it has probability of $$\frac{935}{4374}$$ for being in the top-left shaded square after 8 moves so $$p=\frac{935}{13122}$$ of being on the X after 9 moves

• The value lines up with what I found running my script from working backwards, and overall this is a much more elegant solution. – Michael Moschella Jun 1 '20 at 20:51
• The answer is correct! – Display maths Jun 1 '20 at 20:52
• @MichaelMoschella Thanks I'm glad your percentage lined up with my reasoning. – hexomino Jun 1 '20 at 20:53
• What? No Markov chain matrix multiplication?! A little part of me dies when Markov chains aren't used for problems like this. (+1 Nice answer!) – Dr Xorile Jun 1 '20 at 23:02
• @justhalf, that's true. But with the formalism you can work it out even by hand quite quickly. Because $M^8=((M^2)^2)^2$. So you can easily skip the step 6 bit. – Dr Xorile Jun 2 '20 at 4:17

For simplification, I will represent squares with numbers 1-25 (With 1, 3, 5, 8, 11, 15, 18, 21, 23, and 25 unused) 2 is the goal square, and 13 is the starting point.

We can do this by working backwards, using the pretense that on each consecutive turn the pawn will end up on a "checkerboard" alternating from the previous turn:

Starting from 1 move to go,

On square 7 there is a 1/3 chance to reach the goal, on all other squares there is a 0% chance

From 2 moves to go,

On squares 2 and 6 there is a 100% chance to reach square 7, and on square 12 there is a 1/3 chance to reach square 7, (so effectively 1/9 total), on all else 0% chance

From 3 moves to go,

On square 7, there is a 2/3 chance of landing on a 1/3 square, and a 1/3 chance of landing on a 1/9 square. This averages out to a chance of 7/27. On Square 17 there is a 1/3 chance to land on a 1/9 square, so there is a chance of 1/27, and on square 13 there is a 1/2 chance to land on a 1/9 square, so there is a chance of 1/18.

From 4 moves to go,

On squares 2 and 6, you will always end on the 7/9 square. On squares 16 and 22, you will always end on the 1/27 square, on square 12, you will have an equal chance to land on the 7/9, 1/18, and 1/27 squares, so this averages to 47/162, lastly on square 14 you have a 1/3 chance to land on a 1/18 square, giving you a 1/54 chance.

From 5 moves to go,

On squares 9 and 19, there is a 1/3 chance to land on the 1/54 square, giving a 1/162 chance, on square 13 you take the average of squares 12 and 14 to get a 25/162 chance...

The more I'm doing this the more I'm realizing the ugly math here, and I'm realizing instead:

I can run a script starting with all squares occupied with 0 except the goal square occupied by 1, and run a procedure to change each square to the average of each adjacent square, run this 9 times, and return the value in the start square. I will get back with a solution after running this

Update, using my script I got a solution of:

7.125438195397042%

• The answer is correct! However, I highly suggest others to solve it without computers because this question was asked during a maths contest. – Display maths Jun 1 '20 at 20:51

This can be solved with linear algebra as follows:

2. For each row in the matrix, scale all of the values so that the row sums to 1.
3. At this point, the value at row i, column j will be the probability that a single random step starting in cell i will land you in cell j.
4. Raise the matrix to the 9th power. If you're doing this by hand, you can do it in only 4 matrix multiplications if you're clever enough.
5. At this point, the value at row i, column j will be the probability that exactly 9 random steps starting in cell i will land you in cell j.
6. The row and column corresponding to the puzzle's specified starting and ending square will now contain the desired probability.

Here's a demonstration of this approach in Haskell (it requires the matrix package):


import Data.Matrix

[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],
[1,0,1,0,0,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,0,1,0,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,1,0,0,1,0,0,0,0],
[0,0,0,0,0,0,1,0,1,0,0,0,0,0,0],
[0,0,0,0,1,0,0,1,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,1,0,0,1,0,0,0,1,0],
[0,0,0,0,0,0,0,0,1,0,0,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]]

normalize :: [Rational] -> [Rational]
normalize xs = map (\x -> x / s) xs
where s = sum xs

stepProbabilities = fromLists (map normalize adjacencies)

walkProbabilities = stepProbabilities ^ 9

-- Result: 935 % 13122
main = print \$ getElem 8 1 walkProbabilities


One thing to know about FSJM problems is that they are to be solved with just pencil and paper, without a calculator.

I concur with hexomino in his answer and his method. I used a different method to compute the result. It is the "Markov chain matrix multiplication" method others mentioned. I initially thought it would be much simpler or faster to compute, but it the end it is not significantly different. I leave it here, it might be of interest to some.

Like in hexomino's answer I consider the probability of being in the center versus being in one of the 4 surrounding "even" squares after 2, 4 and 8 moves.

When you start in the center and do 2 moves, you end up in the center 1 out of 3 times. Or 3 in 9. And when you start in a surrounding square and do 2 moves, you end up in the center only 1 out of 9 times.

You can write the transition matrix for 2 moves between these 2 positions. The first row/column is the center, the 2nd row/column is any of the four surrounding squares. $$\frac{1}{9}\begin{pmatrix} 3 & 1 \\ 6 & 8 \\ \end{pmatrix}$$ If you square this matrix 2 times, you get the transition matrix for 8 moves.
$$(\frac{1}{9}\begin{pmatrix} 3 & 1 \\ 6 & 8 \\ \end{pmatrix})^2 = \frac{1}{81}\begin{pmatrix} 15 & 11 \\ 66 & 70 \\ \end{pmatrix}$$ $$(\frac{1}{81}\begin{pmatrix} 15 & 11 \\ 66 & 70 \\ \end{pmatrix})^2 = \frac{1}{81^2}\begin{pmatrix} 225+726 & 165+770 \\ 990+4620 & 726+4900 \\ \end{pmatrix} = \frac{1}{6561}\begin{pmatrix} 951 & 935 \\ 5610 & 5626 \\ \end{pmatrix}$$
(the matrix is complete here, but you actually need to compute only the bottom left term).

This matrix tells you that if you start from the center (1st column), the probability to end in a "corner" (bottom row) after 8 moves is $$\frac{5610}{6561} = \frac{1870}{2187}$$
To end up on the big cross after one more move, you have to actually be in the top-left corner, which happens 1 out of 4 times, and then move up, which happens 1 out of 3 times. Multiplying these probabilities you get the answer:

P(on X after 9 moves) $$= \frac{1870}{2187} \times \frac{1}{4} \times \frac{1}{3} = \frac{935}{13122}$$