Thread: 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

The transition matrix:

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



For all values of n > 22, all state vectors equal to .

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.

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.

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:



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!

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

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 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 ).

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.

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!