A particle performs a random walk on the vertices of a cube. At each step it remains where it is with probability 1/4, and moves to each of its neighbouring vertices with probability 1/4. Let v and w be diametrically opposite vertices. If the walk starts at v, find:
1) the mean number of steps until its first return to v.
2) the mean number of steps until its first visit to w.
The only way I can think of doing this would be to solve some system of 8 simultaneous equations. This seems pretty nasty. How could you do this?
Nice question! Do you have a source? Where did you see it?
Here is my approach:
A cube has 8 vertices.
1 is already taken (original vertex)
6 are neighbors.
1 is the most distant.
Here I can claim that long-run probability of being in 6-neighbor vertices are equal. (Why?)
This should reduce you equations to only 3 (I think) and it should be solvable. Mine is just a guess. Hope this helps.
I don't understand oswaldo's answer, so here's mine.
Originally Posted by Amanda1990
Note: If you don't understand my answer to 1), the answer to 2) gives another method.
I will denote the random walk by .
1) The mean number of steps before the random walk comes back to can be obtained using the invariant measure. You may know that if the random walk is irreducible and is the invariant probability, then for any state ,
where is the hitting time of vertex .
In the present case, it is easily seen that the uniform probability ( for any vertex ) is invariant. This is even a reversible measure. By the above mentioned result, we deduce that the answer is:
Note: this result would remain unchanged if the probability to remain at a vertex is any and the probability to go to a neighbour is .
2) Here you need to find (starting at , time to hit ). You can indeed get this by solving a linear system. Using the symmetries, it is a simple one.
Consider for any initial vertex : the mean time to hit starting from .
- We need .
- Due to the symmetry (think at the cube), the mean hitting time of is the same from the three neighbours of ; we will denote by the value taken by on any of these three vertices. Thus is the mean number of steps to reach from a neighbour of .
- Due to the symmetry again, the hitting time of is the same from the three neighbours of . We will denote it by .
Finaly, there are relations between . For instance, we have:
Indeed, the mean number of steps to hit from is 1 (for the first step) + the mean number of steps to hit from the point where the random walk is located after the first step; And may be with probability or a neighbour of with probability .
The same kind of argument (decomposing into the first step + the remainder), we get also:
(the 0 refers to the case when the first step is : then the hitting time is 0)
These equations are easily solved. You should get .
Note: the equations give and as well, so that you know for any vertex of the cube. For instance, we can verify the value found in question 1. Indeed, (one step + the mean number of remaining steps, which is 0 if the first step goes back to or if a neighbour was chosen). You can check that you get , like in the first proof. It was for , but obviously this is the same for any vertex.