# Markov Processes and Random Walks

• Oct 5th 2008, 11:29 AM
n3mo
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:
http://tech.metatake.com/images/3/3f/Intersection.jpg
(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
• Oct 5th 2008, 12:46 PM
galactus
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.
• Oct 5th 2008, 01:18 PM
Plato
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.
• Oct 5th 2008, 06:48 PM
n3mo
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:

$
\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}
$

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!
• Oct 6th 2008, 08:18 AM
n3mo
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
• Oct 6th 2008, 09:31 AM
Laurent
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.
• Oct 6th 2008, 10:39 AM
n3mo
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!