# Random walk

• Feb 17th 2009, 12:25 PM
Amanda1990
Random walk
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?
• Feb 17th 2009, 01:18 PM
oswaldo
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.

-O
• Feb 19th 2009, 05:22 AM
Laurent
Quote:

Originally Posted by Amanda1990
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?

I don't understand oswaldo's answer, so here's mine.

Note: If you don't understand my answer to 1), the answer to 2) gives another method.

I will denote the random walk by $(X_n)_{n\geq 0}$.

1) The mean number of steps before the random walk comes back to $u$ can be obtained using the invariant measure. You may know that if the random walk $(X_n)_n$ is irreducible and $\pi$ is the invariant probability, then for any state $x$,

$E_x[\tau(x)]=\frac{1}{\pi(x)}$,

where $\tau(x)=\inf\{n\geq 1|X_n=x\}$ is the hitting time of vertex $x$.

In the present case, it is easily seen that the uniform probability ( $\pi(x)=\frac{1}{8}$ for any vertex $x$) is invariant. This is even a reversible measure. By the above mentioned result, we deduce that the answer is:

$E_u[\tau(u)]=\frac{1}{\pi(u)}=8$.

Note: this result would remain unchanged if the probability to remain at a vertex is any $p\in[0,1)$ and the probability to go to a neighbour is $\frac{1-p}{3}$.

2) Here you need to find $E_u[\tau(v)]$ (starting at $u$, time to hit $v$). You can indeed get this by solving a linear system. Using the symmetries, it is a simple one.

Consider $h(x)=E_x[\tau(v)]$ for any initial vertex $x$: the mean time to hit $v$ starting from $x$.

- We need $h_1=h(u)$.

- Due to the symmetry (think at the cube), the mean hitting time of $v$ is the same from the three neighbours of $u$; we will denote by $h_2$ the value taken by $h$ on any of these three vertices. Thus $h_2$ is the mean number of steps to reach $v$ from a neighbour of $u$.

- Due to the symmetry again, the hitting time of $v$ is the same from the three neighbours of $v$. We will denote it by $h_3$.

Finaly, there are relations between $h_1,h_2,h_3$. For instance, we have:

$h_1=1+\frac{1}{4}h_1+\frac{3}{4}h_2$.

Indeed, the mean number of steps to hit $v$ from $u$ is 1 (for the first step) + the mean number of steps to hit $v$ from the point $X_1$ where the random walk is located after the first step; And $X_1$ may be $u$ with probability $1/4$ or a neighbour of $u$ with probability $3/4$.
The same kind of argument (decomposing into the first step + the remainder), we get also:

$h_2=1+\frac{1}{4}h_2+\frac{1}{4}h_1+\frac{2}{4}h_4$
and
$h_3=1+\frac{1}{4}h_4+\frac{1}{4} 0+\frac{2}{4}h_2$.

(the 0 refers to the case when the first step is $v$: then the hitting time is 0)

These equations are easily solved. You should get $h_1=\frac{40}{3}$.

Note: the equations give $h_2$ and $h_3$ as well, so that you know $E_x[\tau(v)]$ for any vertex $x$ of the cube. For instance, we can verify the value found in question 1. Indeed, $E_v[\tau(v)]=h(v)=1+\frac{1}{4}0+\frac{3}{4}h_3$ (one step + the mean number of remaining steps, which is 0 if the first step goes back to $v$ or $h_3$ if a neighbour was chosen). You can check that you get $E_v[\tau(v)]=8$, like in the first proof. It was for $u$, but obviously this is the same for any vertex.