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
    $\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 '16 at 14:24
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
    $\begingroup$ How did you find this out ? $\endgroup$ – Colas Jan 14 '16 at 16:13

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.