Results 1 to 7 of 7

Math Help - Markov Processes and Random Walks

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    10

    Markov Processes and Random Walks

    Hello all! I'm currently facing this problem that is giving me all kinds of fits. I'm relatively new to Markov processes, but I feel like I understand how they work. Unfortunately, figuring out the probabilities for this problem is beyond me. Can anyone lend a hand in explaining this problem? The problem: Imagine this intersection:

    (e.g./ Intersection #8 is only adjacent to #5 and #7) There is a policeman who moves from intersection to an ADJACENT intersection with equal probability each hour. He thinks he'll spend 1/8 of his time in each intersection. But he's wrong. Using Markov processes, explain why explicitly. * Compute T, the transition matrix * Pick a large value of n and compute T^n * Explain why he is wrong for a) Intersection #1 and #3 are considered adjacent b) Intersection #1 and #3 are not considered adjacent
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    The transition matrix:

    Label 1 - 8 along the top and down the side to label the grid.

    \begin{bmatrix}1/3&1/3&0&1/5&0&0&0&0\\1/3&1/3&0&0&1/4&0&0&0\\0&0&1/3&1/5&0&1/3&0&0\\1/3&0&1/3&1/5&1/4&0&1/4&0\\0&1/3&0&1/5&1/4&0&0&1/3\\0&0&1/3&0&0&1/3&1/4&0\\0&0&0&1/5&0&1/3&1/4&1/3\\0&0&0&0&1/4&0&1/4&1/3\end{bmatrix}

    For all values of n > 22, all state vectors equal to x^{(22)}.

    The state vectors approach a fixed vector as n increases.

    I am not going to compute the probabilities for the state vectors. You can do that and see the limiting value.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    Surely the diagonal elements must be zero. Can the policeman stay put at an intersection?
    It seems to me that row 1 has two non-zero entries: in the 2nd and 4th columns.
    Maybe I have misread the question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    10
    Thanks be to Galactus! Everything is so clear once it gets explained to you. I do believe, however, that Plato may be on to something. Now that I understand the system for creating the transitional matrix (along with the appropriate probabilities) I have to agree with Plato's comments. Perhaps the wording of the question was ambiguous, but I believe that the policeman must move to a *new* intersection every hour (i.e., his location at time 1 cannot be the same as time 2). This does produce zeros down the main diagonal, along with a change in the probabilities. Every fraction that reads 1/3 should be 1/2, every 1/4 should be 1/3, and every 1/5 should be 1/4 (because you cannot count the current location as one of the possibilities). This gives me this matrix:

    <br />
\begin{bmatrix}0&1/2&0&1/4&0&0&0&0\\1/2&0&0&0&1/3&0&0&0\\0&0&0&1/4&0&1/2&0&0\\1/2&0&1/2&0&1/3&0&1/3&0\\0&1/2&0&1/4&0&0&0&1/2\\0&0&1/2&0&0&0&1/3&0\\0&0&0&1/4&0&1/2&0&1/2\\0&0&0&0&1/3&0&1/3&0\end{bmatrix}<br />

    Am I mistaken? If I am correct, though, I still owe some serious gratitude to Galactus-- I wouldn't have been able to make this leap without your explanation. Thanks!
    Last edited by n3mo; October 5th 2008 at 07:27 PM. Reason: Added LaTeX code for matrix
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    10
    Now I'm confused further... Based on the wording of the question, and in relation to what we're learning currently in class, I believe that this transition matrix should enter a steady state at some point (in accord with what Galactus was saying). My changes to the probability matrix result in an oscillation in values when the value of n is high. For example, for the values where n=500, 501, 502, 503, the results of T^n reveal that: an identical matrix is produced when n equals 500 or 502, and a different identical matrix is produced when n equals 501 and 503. This pattern continues, forever generating one of two possible matrices.

    Is this oscillation considered a steady state, or does this indicate that my transitional matrix is incorrect? Any ideas?

    -thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    There is a periodicity problem you must notice: if 1 and 3 are not connected to each other, then the policeman always lies on an intersection with same parity as the number n of steps (or the contrary if the starting point is odd). In this case, the probability for the policeman to be at a given intersection does not converge (there are two different limits if we consider the limit along odd or even numbers n).

    If 1 and 3 are connected to each other, then the period is 1: the chain is "aperiodic" and the theorem about the convergence to a steady state holds.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2008
    Posts
    10
    I see. I think I was looking for a particular answer before actually doing the calculations, thus I was disappointed by the results. In both scenarios (a & b) the time spent in each intersection will not be 1/8 across the board-- only for different reasons in each case.

    Thanks for clarifying this!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof that summation of N Markov processes is a Markov process
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 28th 2011, 07:44 AM
  2. Markov Processes
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 24th 2010, 06:16 PM
  3. Markov Processes
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 22nd 2010, 05:19 AM
  4. Markov Processes
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 20th 2010, 02:08 PM
  5. Markov Processes
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 25th 2009, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum