Random walk on a square

Question

Problem:

Given a square $ABCD$, $AB$ being an horizontal vertex, we start at $A$. With each step, we move to another corner:

• horizontally with a probability $p$
• vertically with a probability $q$
• to the opposite corner (along the diagonal) with a probability $r$.

What is the probability, after $n$ steps, to be in $A$, $B$, $C$ or $D$?

Attempt to find solution:

If $A_n$, etc. denotes the probability to be in $A$, etc. before the $n$-th step, and if $$ X_n = (A_n, B_n, C_n, D_n) $$ we find a relation $X_{n+1} = X_n \cdot M$, with $$ M = \left (\begin{array}{cccc} 0&p&r&q\\ p&0&q&r\\ r&q&0&p\\ q&r&p&0 \end{array} \right ). $$ This matrix is symmetrical hence can be diagonalized. But, it seems that it may be too complicated to do.

Questions:

• Am I missing another argument? We know that $p+q+r=1$, of course. And we know that $A_n+B_n+C_n+D_n=1$ but I don't feel that it will simplify the difficulty of the diagonalization.
• Is $M$ easily diagonalizable? $1$ is a eigen vector for the eigen value $1$.

Answer 1

Abusing technology (Mathematica) I got $$P=\left (\begin{array}{cccc} a&b&c&d\\ a&b&-c&-d\\ a&-b&c&-d\\ a&-b&-c&d \end{array} \right )$$

Such that $P^{-1}\cdot M\cdot P$ was diagonal.

Not sure how much fun that would be to try by hand.

Answer 2

Given the present symmetries I'd call this a random walk on a tetrahedron.

Your matrix has the eigenvalues $$1, \quad 2p-1, \quad 2q-1, \quad 2r-1\tag{1}$$ with corresponding eigenvectors $$(1,1,1,1),\quad(1,1,-1,-1),\quad(1,-1,-1,1),\quad(1,-1,1,-1)\ .\tag{2}$$ Don't ask me how I found this out. It seems that @IanMiller in his answer hints at $(2)$, and that @achillehui (see his comment) might be able to explain a direct route to this result.

Anyway, starting with $(1)$ and $(2)$, and going through the motions one finds $$\eqalign{ A_n&={1\over4}\bigl(1+(2p-1)^n+(2q-1)^n+(2r-1)^n\bigr)\cr B_n&={1\over4}\bigl(1+(2p-1)^n-(2q-1)^n-(2r-1)^n\bigr)\cr C_n&={1\over4}\bigl(1-(2p-1)^n-(2q-1)^n+(2r-1)^n\bigr)\cr D_n&={1\over4}\bigl(1-(2p-1)^n+(2q-1)^n-(2r-1)^n\bigr)\cr}$$