Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A little change in that problem:

Logic question: Ant walking a cube

There is a cube and an ant is performing a random walk on the edges where it can select any of the 3 adjoining vertices with equal probability. What is the expected number of steps it needs till it reaches the diagonally opposite vertex?

Taking the cube image there, and starting in 1 and ending in 8,

What would be the expected number of steps without passing by vertex 5?

Thanks!

share|improve this question
1  
If by "without passing by vertex 5" you mean that the random walk is performed on the cube without vertex 5 (or, equivalently, you want the conditional expectation value given the condition that the walk doesn't pass by vertex 5), then you can use the same kind of analysis that Sivaram applied in the other question (except for the symmetry) to get the result for this one. –  joriki Mar 25 '11 at 11:37
    
Please clarify what you mean by "without passing by vertex 5" since it appears there are different interpretations and you probably mean only one of them. –  Douglas Zare Mar 25 '11 at 15:42
add comment

1 Answer

Conditioning the ant to never pass by vertex $5$ is equivalent to cancelling edges $\{4,5\}$, $\{6,5\}$ and $\{8,6\}$. This leaves $7$ vertices and $9$ edges. The symmetry with respect to the plane containing $1$, $2$, $5$ and $8$ shows that $3$ and $7$ play the same role for a path starting from $1$ and ending at $8$. Likewise, $4$ and $6$ play the same role. So one can consider $3$ and $7$ as a single vertex, and $4$ and $6$ as a single vertex, only with more edges leading to them and leaving them than the others.

Thus the setting is equivalent to a random walk on a weighted graph with $5$ vertices and $5$ edges, drawn like a square plus an additional edge added to a vertex of the square. The square has vertices $1$, $2$, $3$ (which represents $3$ and $7$) and $4$ (which represents $4$ and $6$), the fifth vertex is $8$, and the edges are those of the square $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{4,1\}$, plus the additional edge $\{3,8\}$. Every edge has weight $2$ except the edge $\{1,2\}$ which has weight $1$. Weights on edges mean for instance that starting from $1$, one has $1/(1+2)$ chances to go to $2$ and $2/(1+2)$ chances to go to $4$.

Writing $t_i$ for the mean hitting time of $8$ starting from $i$ on the reduced graph, one looks for $t_1$. The vector $(t_1,t_2,t_3,t_4)$ solves the system $t_1=1+(t_2+2t_4)/3$, $t_2=1+(t_1+2t_3)/3$, $t_3=1+(t_1+t_2+0)/3$ and $t_4=1+(t_1+t_3)/2$. Hence $t_1=62/5$ or something like that.

Alternatively, one can solve an analogous system on the original graph with $7$ vertices and $9$ edges. This system has size $6$ since $t_8=0$ and if one solves it one will note that some coordinates of the solution are equal, namely $t_3=t_7$ and $t_4=t_6$. The reduction explained above uses this fact to lower a priori the size of the linear system down to $4$ but it is not essential.

All this, and much more, in the must-read short book Random walks and electric networks by Peter G. Doyle and J. Laurie Snell.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.