A bug is sitting on vertex A of a regular tetrahedron. At the start of each minute, he randomly chooses one of the edges at the vertex he is currently sitting on and crawls along that edge to the adjacent vertex. It takes him one minute to crawl to the next vertex, at which point he chooses another edge (at random) and starts crawling again. What is the probability that, after 6 minutes, he is back at vertex A?
This problem can be solved with a simple state diagram with 2 states (on A, not on A).
Pn = (1/3) * (1-Pn-1). Basically, the probability that the bug is on A is the probability that it wasn't on A on the previous timestep, times 1/3 (it chooses to go to A). Using this recurrence relation, we get the answer of 61/243.
Now this is my question. If we do the same problem, but now the bug is crawling on a cube, why is the answer the same? On a cube, if we drew the state diagram, there would be 4 states: on A, 1 away from A, 2 away from A, and then 3 away from A. How come the answer comes out to be the same, 61/243?
Best Answer
Let $X_n\in\{T_0,T_1\}$ denote the position of the ant on the tetrahedron and let $Y_n\in\{C_0,C_1,C_2,C_3\}$ denote the position of the ant on the cube, where $n=0,1,2,\dots$ is the time step, and the state index represents distance from initial position. Both $X_n$ and $Y_n$ are Markov processes.
Observe that if the cube ant starts in position $C_0$, then for even $n$ we must have $P(Y_n=C_1)=P(Y_n=C_3)=0$, this is because on the cube the ant is forced to move to an adjacent state each step. Thus, if we only consider even $n$, we can form a reduced system consisting only of the states $\{C_0,C_2\}$. It is not hard to check that this system is equivalent to the tetrahedron system since the transition probability are the same.