Results 1 to 4 of 4

Math Help - Discrete Time Markov Chain

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    184

    Discrete Time Markov Chain

    Let X_{0},X_{1},..... be a discrete time Markov chain on state space S.
    Charikaar tosses a fair coin. If it shows heads he takes one step North. If it shows tails he takes one step South. This process is performed repeatedly.
    Show that the probability that after 2k coin tosses Charikaar is back where he started is 2^{-2k}\binom {2k} {k}
    I think this is Random walk on integers but I am not sure what is the state space in this example ... can the state space be S={.....,-3,-2,-1,0,1,2,3,.....}? he starts at zero and moves left and right? Can you please help me get started with the answer. Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Anonymous1's Avatar
    Joined
    Nov 2009
    From
    Big Red, NY
    Posts
    517
    Thanks
    1
    This looks like one of those problems where you can use a combinatorial argument. Even if your instructor does not accept it, this it will give intuition on how to solve.

    Try to describe the sample space and event space.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2008
    Posts
    184
    I don't know what is State space equal to in this case so can't really get started!

    thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Anonymous1's Avatar
    Joined
    Nov 2009
    From
    Big Red, NY
    Posts
    517
    Thanks
    1
    Do it like this:

    At time t_0 he is where he started with p=1.

    On the next step he moves in one of the two directions, so he is back with p=0

    N
    |
    x_0
    |
    S

    At time 3 he is :
    P(gets back at time 3)= p(Goes back|Went North)P(Went North) + p(Goes back|Went South)P(Went South) = (1/2)^2 + (1/2)^2 = 1/2

    At time 4 he can be in on of the following places

    N (here) p(Gets back|here)=0
    |
    here p(Gets back|here)= 1/2
    |
    X_0 (here) p(gets back)=0
    |
    here p(Gets back|here)= 1/2
    |
    S (here) p(Gets back|here)=0

    You tell me the p(Gets back) for this one. Note that you can use symmetry and the fact that if he can not get back from a certain position, being at that position is not included in the desired probability.

    If you must prove this, use induction. Here is your base case. Although you probably don't and can just say the result follows.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Time Markov Chain
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: March 22nd 2011, 07:56 AM
  2. Time reversible Markov Chain
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 1st 2011, 11:49 PM
  3. Discrete Time Markov Chain
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: September 29th 2009, 01:44 PM
  4. Replies: 0
    Last Post: March 10th 2009, 11:29 AM
  5. Discrete Time Markov Chain
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: March 10th 2008, 10:54 PM

Search Tags


/mathhelpforum @mathhelpforum