Results 1 to 3 of 3

Thread: Random walk

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    103

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2009
    Posts
    94
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Amanda1990 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: Mar 26th 2011, 09:43 PM
  2. Random Walk
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Oct 18th 2010, 04:29 PM
  3. an almost random walk SP
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: Jul 15th 2010, 10:58 AM
  4. Random Walk in 1-D (Q2)
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: May 10th 2010, 12:45 AM
  5. Random Walk in 1-D
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: May 3rd 2010, 09:14 AM

Search Tags


/mathhelpforum @mathhelpforum