Results 1 to 3 of 3

Math Help - 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 (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.
    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: March 26th 2011, 09:43 PM
  2. Random Walk
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 18th 2010, 04:29 PM
  3. an almost random walk SP
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: July 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