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 $\displaystyle (X_n)_{n\geq 0}$.

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

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

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

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

$\displaystyle 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 $\displaystyle p\in[0,1)$ and the probability to go to a neighbour is $\displaystyle \frac{1-p}{3}$.

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

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

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

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

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

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

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

Indeed, the mean number of steps to hit $\displaystyle v$ from $\displaystyle u$ is 1 (for the first step) + the mean number of steps to hit $\displaystyle v$ from the point $\displaystyle X_1$ where the random walk is located after the first step; And $\displaystyle X_1$ may be $\displaystyle u$ with probability $\displaystyle 1/4$ or a neighbour of $\displaystyle u$ with probability $\displaystyle 3/4$.

The same kind of argument (decomposing into the first step + the remainder), we get also:

$\displaystyle h_2=1+\frac{1}{4}h_2+\frac{1}{4}h_1+\frac{2}{4}h_4$

and

$\displaystyle 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 $\displaystyle v$: then the hitting time is 0)

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

Note: the equations give $\displaystyle h_2$ and $\displaystyle h_3$ as well, so that you know $\displaystyle E_x[\tau(v)]$ for any vertex $\displaystyle x$ of the cube. For instance, we can verify the value found in question 1. Indeed, $\displaystyle 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 $\displaystyle v$ or $\displaystyle h_3$ if a neighbour was chosen). You can check that you get $\displaystyle E_v[\tau(v)]=8$, like in the first proof. It was for $\displaystyle u$, but obviously this is the same for any vertex.