4
$\begingroup$

Recently, I came across a very nice question from the 1985 AIME:

Let $A$, $B$, $C$ and $D$ be the vertices of a regular tetrahedron, each of whose edges measures $1$ meter. A bug, starting from vertex $A$, observes the following rule: at each vertex it chooses one of the three edges meeting at that vertex, each edge being equally likely to be chosen, and crawls along that edge to the vertex at its opposite end. Let $p = \frac{n}{729}$ be the probability that the bug is at vertex $A$ when it has crawled exactly $7$ meters. Find the value of $n$.

It immediately clicked to me that this is a Markov process and I just need to form the transition matrix, which I did, and it is

$$ T = \begin{bmatrix} 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{bmatrix} $$

Now the only problem remains in finding $[a_{11}]T^7$ which I right now did by calculator, but is there a way to do it smartly without using calculator and completely manually?

$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

You can write $T = \frac{1}{n-1}(v \, v^T -1)$ with $n=4$, $v = (1,...,1)^T$ and expand $(v \, v^T -1)^k$ to a sum of powers of $v \, v^T$. Using that for any $i \geq 1$ one has $(v \, v^T)^i = n^{i-1} \, v \, v^T$ you then find that for any $k \geq 0$

$$ T^k \, = \, \frac{1}{(n-1)^k} \left((-1)^k + \frac{1}{n} ((n-1)^k - (-1)^k) \, v \, v^T\right) \, . $$

$\endgroup$
2
  • $\begingroup$ Did you use the binomial theorem? $\endgroup$ Commented Feb 22 at 10:05
  • 1
    $\begingroup$ Yes, twice. First to express $(v \, v^T-1)^k$ as a sum of powers of $v \, v^T$ and then also to get the $(n-1)^k$ in the end. $\endgroup$ Commented Feb 22 at 10:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.