Results 1 to 2 of 2

Math Help - 2d random walk on Z^2

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    17

    2d random walk on Z^2

    Hi,
    I'm stuck with this question about 2d random walks on Z^2

    Let S_n = (X_n, Y_n) be a simple symmetric random walk in Z^2, starting from (0, 0), and set T = inf {n >= 0: max{|X_n|, |Y_n|} = 2}. Calculate E(T) (Expectation of T).

    How would I proceed? would i just use the standard definition of expectation? if so, i would need to work out P[T=n] for natural numbers n yes? but how would i work this out, there are too many possibilities!!!! Is there a formula for this?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by ramdayal9 View Post
    if so, i would need to work out P[T=n] for natural numbers n yes? but how would i work this out, there are too many possibilities!!!!
    Hi,

    this is a nice problem; at first, there indeed seems to be extremely many possibilities, but symmetry simplifies the situation a lot.

    So you want the expected time needed to exit the 3x3 square centered at 0. There are in fact only 3 kinds of vertices: A) the middle vertex 0, B) the four "medians" (1 step away from 0) and C) the 4 corners (2 steps away from 0). Plus D) the outside vertices.

    You can sketch a much simpler equivalent Markov chain with the only states A,B,C,D; for instance p_{A,B}=1, p_{B,A}=\frac{1}{4}=p_{B,D}, p_{B,C}=\frac{1}{2}, etc.

    Starting from 0, i.e. from A, you see that the walk can only be at B (or D) at odd times. Using induction, prove that the probability of being at B at time 2k+1 is \frac{1}{2^k}. Then deduce the probability of being at A at time 2k (hint: the walk is at B right before) and similarly for C.

    From there, you have several possibilities to conclude. Either you compute the probability to be at D at time n (this means being at B at time n-1 if n is even, or at C at time n-1 if n is odd) and sum E[T]=\sum_n n P(T=n). Or (this may be easier) you use E[T]=\sum_{n=0}^\infty P(T> n) and note that P(T> n) is the probability that the walk at time n is either at A, B or C (thus at B if n is odd, or at A or C if n is even) and you just have to sum the probabilities to get P(T>n). (Note that P(T>0)=P(T>1)=1)

    You should get
    Spoiler:
    E[T]=4.5
    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
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: May 3rd 2010, 09:14 AM
  5. Random walk
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 19th 2009, 05:22 AM

Search Tags


/mathhelpforum @mathhelpforum