If a particle performs a random walk on the vertices of a cube, what is the mean number of steps before it returns to the starting vertex S? What is the mean number of visits to the opposite vertex T to S before its first return to S and what is the mean number of steps before its first visit to T?
Nobody ever explained random walks to me, so I find it all very odd right now. Maybe someone can explain how to handle these problems or you can link me to a site where these kinds of problems are explained well? Thanks a lot!
Best Answer
The vertices of a cube(oid) can be labelled with 3-digit binary numbers since there are $8$ corners and $2^3=8$. To keep things simple lets say that we are considering the unit cube and the binary number correspond directly to the coordinates, so that vertce $000$ is at $(0,0,0)$, vertex $010$ is at $(0,1,0)$ and so forth. Taking one step on the random walk is equivalent to picking one digit with uniform probability of $1/3$ from our binary number and flipping it.
W.l.o.g. let us consider starting at $000$, let us say that the expected time to return to $000$ is $x$. Now consider the three vertices $001$,$010$ and $100$, they are all one step away from the start. Let's say the expected time to return to the start from here is $y$. Similarly consider the vertices with two ones $110$, $101$ and $011$. These are all two steps away from the start. Let us say that the expected time to get back to $000$ from here is $z$.
How can we link all of these together? Well, if we are at one of the vertices $001$, $010$ or $100$ we have a $1/3$ probability of returning to the start and a $2/3$ probability to go to one that is two steps away. This gives us $$y = \frac{1}{3} + \frac{2}{3}(z+2)$$ To make sense of this, see that we have a 1/3 probability to be finished, otherwise we are at a vertex two steps away (whose expected time is $z$) but we took two steps to get there (hence $z+2$). We can perform a similar process for the vertices $011$, $101$ and $110$. Here we have a $2/3$ probability to return to a vertex one step from the start and a $1/3$ prob. to go to $111$, but at $111$ our only option is to back to one of the vertices two steps away and so the corresponding equation reads $$z = \frac{2}{3}(y+1) + \frac{1}{3}(z+2)$$ Using these we can solve to get $y=7$. Now clearly from $000$ we can only reach vertices one step away, for which we already know the expected time to return to $000$ is 7. Thus our expected time to return to $000$ is $x=y+1=8$.
Although our discussion focused on starting from $000$ there was nothing special about this choice other than to keep the number of ones equal to the steps away from the start and thus it holds for any starting vertex the expected number of steps to return is $8$.
I decided to check whether this answer is correct using Monte-Carlo. With 1,000,000 trials the answer came out as 7.99 (3 s.f.).