2
$\begingroup$

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$.
$\endgroup$
1
  • 1
    $\begingroup$ The matrix $M$ is invariant under horizontal reflection $A \leftrightarrow B, C \leftrightarrow D$ and vertical reflection $A \leftrightarrow C, B \leftrightarrow D$. Since this two reflections commutes between themselves, one can choose a basis which are eigenvectors for these three operations simultaneously. The eigenvectors of $M$ will be vectors which have definite parity under the two reflections. i.e. $$e_A + e_B + e_C + e_D,\quad e_A - e_B + e_C-e_D,\quad e_A-e_C + e_B-e_D \quad\text{ and }\quad e_A-e_B-e_C+e_D$$ where $e_X$ is the vector $= 1$ at vertex $X$ and $0$ at other vertices. $\endgroup$
    – achille hui
    Jan 14, 2016 at 14:24

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
1
  • 1
    $\begingroup$ How did you find this out ? $\endgroup$
    – Colas
    Jan 14, 2016 at 16:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .