Random walk

**Amanda1990** · February 17th 2009, 12:25 PM

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?

**oswaldo** · February 17th 2009, 01:18 PM

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

**Laurent** · February 19th 2009, 05:22 AM

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.

Thread: Random walk

LinkBack

Thread Tools

Display

Random walk

Similar Math Help Forum Discussions

Random walk

Random Walk

an almost random walk SP

Random Walk in 1-D (Q2)

Random Walk in 1-D

Search Tags