• Support PF! Buy your school textbooks, materials and every day products Here!

Build a Markov Matrix

  • Thread starter Aleoa
  • Start date
  • #1
128
5
Mentor note: Thread moved from Mathematics section, so is missing the HW template
John and Eli are playing a game with a hall that can roll into one of two
pockets labelled H and Y. John wants to keep the hall in H and Eli wants
to keep it in Y. When it is John's turn to play, ifhe finds the hall in H that is
fine with him and he does nothing; but if he finds it il). Y he attempts to roll
it into pocket H. This takes some skill; the probability that he succeeds is 2/3 ,
there being a 1/3 chance that the hall will roll back into Y. When Eli's turn
comes, he does nothing if the hall is in Y, but tries to get it there ifhe finds it
in H. Eli is less skillful than John and his probability of succeeding in bis
effort is only 1/2.

I built this 2x2 matrix:

[tex]
A=\begin{bmatrix}
\frac{1}{3} & \frac{1}{2}\\

\frac{2}{3} & \frac{1}{2}
\end{bmatrix}[/tex]
The first colum is for state Y and the second for the state H.

But, when i read the first exercise to do with this matrix, it seems not properly built:

(a)Starting with the hall in Y and John to play, what is the probability
that the hall will be in H after John's second play?


What is the correct Markov Matrix that represent this scenario ?
 
Last edited by a moderator:

Answers and Replies

  • #2
FactChecker
Science Advisor
Gold Member
5,398
1,962
Have you taken into account that John and Eli take turns? Who's turn it is is an essential part of the definition of the current state. So you have a situation where the state (John's turn and ball in H) goes to the state (Eli's turn and ball in H). Similarly for other states. I think this must be a 4x4 state transition matrix.

PS. There may be some way that I don't see that allows you to make this a 2x2, but I recommend that you keep it simple and 4x4 for now.
 
Last edited:
  • #3
33,314
5,006
@Aleoa, please post questions like this in the Homework sections, not in the technical Math sections.

Also, John and Eli are playing with a ball, not a hall. You can't normally roll a hall into a pocket.
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
Mentor note: Thread moved from Mathematics section, so is missing the HW template
John and Eli are playing a game with a hall that can roll into one of two
pockets labelled H and Y. John wants to keep the hall in H and Eli wants
to keep it in Y. When it is John's turn to play, ifhe finds the hall in H that is
fine with him and he does nothing; but if he finds it il). Y he attempts to roll
it into pocket H. This takes some skill; the probability that he succeeds is 2/3 ,
there being a 1/3 chance that the hall will roll back into Y. When Eli's turn
comes, he does nothing if the hall is in Y, but tries to get it there ifhe finds it
in H. Eli is less skillful than John and his probability of succeeding in bis
effort is only 1/2.

I built this 2x2 matrix:

[tex]
A=\begin{bmatrix}
\frac{1}{3} & \frac{1}{2}\\

\frac{2}{3} & \frac{1}{2}
\end{bmatrix}[/tex]
The first colum is for state Y and the second for the state H.

But, when i read the first exercise to do with this matrix, it seems not properly built:

(a)Starting with the hall in Y and John to play, what is the probability
that the hall will be in H after John's second play?


What is the correct Markov Matrix that represent this scenario ?
The vast majority of Markov chain presentations--in applied areas, at least, not necessarily in pure "math"--use the convention that the rows of a transition matrix sum to 1. You have columns summing to 1. Is that intentional on your part (for example, because your course notes do it that way), or is it an error you have made?

Note: having the columns sum to 1 is not, in itself, an error. However, if you do it that way you must very carefully and laboriously check each and every formula you are using, to make sure you are using the correct version.
 
  • #5
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,693
6,467
PS. There may be some way that I don't see that allows you to make this a 2x2, but I recommend that you keep it simple and 4x4 for now.
Since the turn always alternates, you could look at the transition from Eli's current turn to Eli's next turn (states H and Eli's turn + Y and Eli's turn), or the transition between John's turns (H and John's turn + Y and John's turn). Of course, those transition matrices will not be the same and they will be the two blocks of the block diagonal matrix which is the square of the 4x4 matrix that considers all four states (which is block off-diagonal).
 
  • #6
FactChecker
Science Advisor
Gold Member
5,398
1,962
Since the turn always alternates, you could look at the transition from Eli's current turn to Eli's next turn (states H and Eli's turn + Y and Eli's turn), or the transition between John's turns (H and John's turn + Y and John's turn).
Good point. I guess a problem with that approach would be that it would be difficult to answer questions about state transition probabilities from John's turn to any of Eli's turns. In general, I think it is a messy way to address the process. It's probably a "simplification" to two separate 2x2 matrices that makes some things more complicated.
Of course, those transition matrices will not be the same and they will be the two blocks of the block diagonal matrix which is the square of the 4x4 matrix that considers all four states (which is block off-diagonal).
They would be related, but I don't think that any of the entries of the 4x4 would match any of the 2x2 entries. The 2x2 entries are for a John-Eli (or Eli-John) sequence of two state transitions. (CORRECTION: @Orodruin did specify that the 2x2 entries would match entries in the square of the 4x4 matrix.)
 
Last edited:
  • #7
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,146
550
A few thoughts:

1.)
The states are ##\text{\{(1) Eli's turn, ball in H, (2) Eli's turn, ball in Y, (3) John's turn, ball in H, (4) John's turn, ball in Y\}}##

This seems to be a bipartite graph.

From a past post of mine, here's the blocked multiplication:
##
\mathbf Y =
\begin{bmatrix}\mathbf 0 &\mathbf{A} \\ \mathbf{B} &\mathbf 0\end{bmatrix}
##

##\mathbf Y^2 =
\begin{bmatrix}\mathbf{AB} & \mathbf 0 \\ \mathbf 0 & \mathbf{BA}\end{bmatrix}
##

so for odd powers, say to the seventh power:
##\mathbf Y^7 = \mathbf Y^2\mathbf Y^2\mathbf Y^2\mathbf Y = \big(\mathbf Y^2\big)^3 \mathbf Y##

and for even powers, like the sixth power:
##\mathbf Y^6 = \mathbf Y^2 \mathbf Y^2 \mathbf Y^2= \big(\mathbf Y^2\big)^3##

which should make the multiplications a lot easier.

2.) Ray's right that the standard approach is for the matrix to be row stochastic, not column stochastic. Pretty much everyone --including Feller-- does this-- except me (most of the time). For some reason I've developed a distaste for vector matrix products and have a strong preference for matrix vector products. That said, if you leave it in matrix vector form, it's very easy to transpose between the two different approaches.
 
Last edited:
  • #8
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,693
6,467
They would be related, but I don't think that any of the entries of the 4x4 would match any of the 2x2 entries. The 2x2 entries are for a John-Eli (or Eli-John) sequence of two state transitions.
That is not what I said. I said the entries of the 2x2 matrices would match the diagonal blocks of the square of the 4x4.

Pretty much everyone --including Feller-- does this-- except me (most of the time). For some reason I've developed a distaste for vector matrix products and have a strong preference for matrix vector products.
This may be another mathematician-physicist discrepancy. I would also prefer to be column stochastic.
 
  • #9
128
5
A few thoughts:

The states are ##\text{\{(1) Eli's turn, ball in H, (2) Eli's turn, ball in Y, (3) John's turn, ball in H, (4) John's turn, ball in Y\}}##
Considering this states order i built this 4x4 markov matrix:

[tex]
M=\begin{bmatrix}
0 &0 & 1 & \frac{2}{3}\\
0 & 0 & 0 & \frac{1}{3}\\
\frac{1}{2} & 0 &0 &0 \\
\frac{1}{2} &1 &0 &0
\end{bmatrix}[/tex]

It seems correct to me . Is that it?
 
  • #10
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,693
6,467
Considering this states order i built this 4x4 markov matrix:

[tex]
M=\begin{bmatrix}
0 &0 & 1 & \frac{2}{3}\\
0 & 0 & 0 & \frac{1}{3}\\
\frac{1}{2} & 0 &0 &0 \\
\frac{1}{2} &1 &0 &0
\end{bmatrix}[/tex]

It seems correct to me . Is that it?
Yes.
 
  • #11
128
5
Thanks so much to all you guys :)
 
  • #12
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,146
550
Considering this states order i built this 4x4 markov matrix:

[tex]
M=\begin{bmatrix}
0 &0 & 1 & \frac{2}{3}\\
0 & 0 & 0 & \frac{1}{3}\\
\frac{1}{2} & 0 &0 &0 \\
\frac{1}{2} &1 &0 &0
\end{bmatrix}[/tex]

It seems correct to me . Is that it?
Sometimes drawing the state diagram helps...

upload_2018-5-21_23-3-48.png


edit: I just dropped my state diagram labels in with your matrix. Maybe some labeling nits remain (graph isomorphism, I know...)
- - - -
it seems to be ok afterall.
 

Attachments

  • #13
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
That is not what I said. I said the entries of the 2x2 matrices would match the diagonal blocks of the square of the 4x4.


This may be another mathematician-physicist discrepancy. I would also prefer to be column stochastic.
All the mathematician-authored books I have seen/own that treat Markov chains use row stochasticity. More to the point, while I got my PhD in Physics I spent all my after-post-doc working life doing Operations Research, and every single book and almost all papers in that field use row stochasticity. The column-stochasticity convention is used, but rarely, at least outside physics.
 
  • #14
128
5
All the mathematician-authored books I have seen/own that treat Markov chains use row stochasticity. More to the point, while I got my PhD in Physics I spent all my after-post-doc working life doing Operations Research, and every single book and almost all papers in that field use row stochasticity. The column-stochasticity convention is used, but rarely, at least outside physics.
The book i'm using is :https://www.amazon.com/dp/0521406498/?tag=pfamazon01-20 , and the author uses column stochasticity
 
  • #15
FactChecker
Science Advisor
Gold Member
5,398
1,962
That is not what I said. I said the entries of the 2x2 matrices would match the diagonal blocks of the square of the 4x4.
Sorry Orodruin, I missed that you specified square. I have corrected that post.
 
  • #16
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
The book i'm using is :https://www.amazon.com/dp/0521406498/?tag=pfamazon01-20 , and the author uses column stochasticity
Well, I did specify that the row method is used extensively in applied areas outside of physics.

Anyway, the main point is that you were, indeed, doing it that way on purpose (following your textbook) and are presumably perfectly aware of the issue and know the correct formulas to use. In other words, you did not make a mistake of the kind I have seen many people make in the past.
 
  • #17
128
5
This is the third point of the exercise:
(c) Suppose the game has been going on fora 'long time' and you look in
just after Eli has played. What is the probability that the ball is now in
H? How many turns constitutes a 'long time' if we want to be certain
that this probability is correct within 0.001?


Is there a way to reduce the matrix i built , or i have to calculate the eigenvectors/eigenvalues of a 4x4 matrix ?
 
  • #18
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,146
550
This is the third point of the exercise:
(c) Suppose the game has been going on fora 'long time' and you look in
just after Eli has played. What is the probability that the ball is now in
H? How many turns constitutes a 'long time' if we want to be certain
that this probability is correct within 0.001?


Is there a way to reduce the matrix i built , or i have to calculate the eigenvectors/eigenvalues of a 4x4 matrix ?
You may enjoy this post: https://www.physicsforums.com/threads/eigenvalues-of-block-matrices.925046/#post-5840702

And you may want to consider that

##
\big(\mathbf Y^2\big)^k =
\begin{bmatrix}\big(\mathbf{AB}\big)^k & \mathbf 0 \\ \mathbf 0 & \big(\mathbf{BA}\big)^k\end{bmatrix}
##

so

##\text{trace}\Big(\big(\mathbf Y^2\big)^k\Big) = \text{trace}\Big(\big(\mathbf{AB}\big)^k+ \big(\mathbf{BA}\big)^k\Big) = 2\text{trace}\Big(\big(\mathbf{AB}\big)^k\Big)##

i.e. the above is true for an even number of iterations.

For odd number of iterations, the trace is always zero --e.g. like ##\text{trace}\Big(\mathbf Y^7\Big)##.

This is some special bipartite graph stuff, which gives strong information on the eigenvalues.

But it comes down to how comfortable you are with linear algebra.

- - - -
edit:
Clever use of ##\text{trace}\Big(\big(\mathbf Y^2\big)\Big)## can give you all the eigenvalues with no real work. But I'm not supposed to give this all way. Happy to show the way after you're done if you don't uncover the secret.


- - - -
If the above makes you uncomfortable, you can take a simpler, longer approach and just calculate the characteristic polynomial and solve for the eigenvalues and eigenvectors. You know at least one eigenvalue is 1 because it is (column) stochastic, so ##\mathbf 1^* \mathbf Y = \lambda_1 \mathbf 1^* = 1 \mathbf 1^* = \mathbf 1^*##

as another hint, you may consider that there are basically two separate (i.e. bi partitions) of the graph, so maybe you can do something interesting with the ones vector here...
 
  • #19
128
5
What i thought is to calculate the eigenvalues and eigenvector of the 2x2 top right matrix, and the eigenvalues and eigenvector of the 2x2 lower left matrix, and then use the initial state vector
[tex]V=\begin{bmatrix}
a\\ b
\\ 0
\\ 0

\end{bmatrix}[/tex] Multiplying the sub-vector [a,b] with the top right 2x2 matrix , and then multiply the result of this calculation with the lower left 2x2 matrix and watch what happens.
Is this correct ?
 
  • #20
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,146
550
What i thought is to calculate the eigenvalues and eigenvector of the 2x2 top right matrix, and the eigenvalues and eigenvector of the 2x2 lower left matrix, and then use the initial vector
[tex]V=\begin{bmatrix}
a\\ b
\\ 0
\\ 0

\end{bmatrix}[/tex] Multiplying the sub-vecto [a,b] with the top right 2x2 matrix , and then multiply the result of this calculation with the lower left 2x2 matrix and watch what happens.
Is this correct ?
It's a decent idea, kinda close but...

Look your matrices in the corner are triangular so it would be ideal, right? I mean, I can see the eigenvalues on the diagonals of triangular matrices.

Your approach would tell you that ##\mathbf Y## has eigenvalues of ##\{1, \frac{1}{3}, \frac{1}{2}, 1\}## but

##1 + \frac{1}{3} + \frac{1}{2} + 1 = 2 \frac{5}{6} \gt 0 = \text{trace}\Big(\mathbf Y\Big) = \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4##

which is a contradiction.
 
Last edited:
  • #21
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
16,693
6,467
Hint: Look at the transition matrix from just before John’s turn n to just before John’s turn n+1. The state space is then two-dimensional as discussed earlier.
 
  • #22
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
What i thought is to calculate the eigenvalues and eigenvector of the 2x2 top right matrix, and the eigenvalues and eigenvector of the 2x2 lower left matrix, and then use the initial state vector
[tex]V=\begin{bmatrix}
a\\ b
\\ 0
\\ 0

\end{bmatrix}[/tex] Multiplying the sub-vector [a,b] with the top right 2x2 matrix , and then multiply the result of this calculation with the lower left 2x2 matrix and watch what happens.
Is this correct ?
Your transition matrix has the form
$$P = \begin{bmatrix} 0 & Q \\ R & 0 \end{bmatrix} ,$$
where the ##2 \times 2##matrices ##Q## and ##R## are stochastic.
Thus,
$$P^2= \begin{bmatrix} A & 0 \\ 0 & B \end{bmatrix} .$$
Here, the ##2 \times 2## matrices ##A## and ##B## are the 2-step E-E and J-J transition matrices, respectively. So, ##A^n## is the ##2n##-step transition matrix for player E, and similarly for ##B^n##.

We want to know the rates of convergence of ##A^n## and ##B^n## to their limits. My favorite way of doing such problems is as follows.

If ##r_1## and ##r_2## are the eigenvalues of ##A##, and if ##r_1 \neq r_2## (true in this case) then from diagonalization arguments we know that
$$A = r_1 E_1 + r_2 E_2,$$
for some ##2 \times 2## matrices ##E_1## and ##E_2##. Again, because of diagonalization arguments, it is a fact that for any analytic function
$$f(x) = c_0 + c_1 x + c_2 x^2 + \cdots$$
the matrix function
$$f(A) = c_0 I + c_1 A + c_2 A^2 + \cdots $$
(with ##I## the identity matrix) obeys
$$f(A) = f(r_1) E_1+ f(r_2) E_2$$
That is, the function ##f## acts on the eigenvalues only, and leaves the ##E_i## unchanged.

We can get the ##E_i## from
$$\begin{array}{rcl}
f(x) = 1 = x^0 & \Rightarrow &I = r_1^0 E_1 + r_2^0 E_2 = E_1 + E_2\\
f(x) = x = x^1 & \Rightarrow & A = r_1^1 E_1 + r_2^1 E_2 = r_1 E_1 + r_2 E_2
\end{array}
$$
That is, ##I = E_1 + E_2## and ##A = r_1 E_1 + r_2 E_2##. You can solve these for ##E_1## and ##E_2##, and so can easily get ##A^n = r_1^n E_1 + r_2^n E_2.## From that you can assess convergence rates, etc.

You can just repeat all that for the matrix ##B##.

Things become a bit more complicated if you have repeated eigenvalues, but it is still possible to do such calculations without going into the laborious process of finding the Jordan canonical form. It is not relevant to this thread, so I will skip the details for now.
 
Last edited:
  • #23
128
5
I did some calculation using your advises, i get that the 2 states at [tex]N\rightarrow \infty[/tex] are [tex]
V1=\begin{bmatrix}
0\\0
\\\frac{2}{3}
\\ \frac{1}{3}

\end{bmatrix}[/tex] and [tex]
V2=\begin{bmatrix}
\frac{1}{3} \\\frac{2}{3}
\\0
\\ 0

\end{bmatrix}[/tex]

Is it correct ?
 
  • #24
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,146
550
I did some calculation using your advises, i get that the 2 states at [tex]N\rightarrow \infty[/tex] are [tex]
V1=\begin{bmatrix}
0\\0
\\\frac{2}{3}
\\ \frac{1}{3}

\end{bmatrix}[/tex] and [tex]
V2=\begin{bmatrix}
\frac{1}{3} \\\frac{2}{3}
\\0
\\ 0

\end{bmatrix}[/tex]

Is it correct ?
I'm not sure what you did here, but it doesn't seem correct to me. Help us understand what kinds of calculations you did.

I think we've all hinted at this... can you write out what ##\mathbf Y^2## looks like? This is a much easier problem to deal with as shown in the blocked multiplication.
 
  • #25
128
5
I simply get the eigenvalues and eigenvectors, and i deduced that whatever vectors i use at start, for [itex]N\rightarrow \infty[/itex] , we have only 2 states and they continuously alternate:

[itex]
V_{1}=\begin{bmatrix}
\frac{2}{3}\\\frac{1}{3}
\\ 0
\\ 0

\end{bmatrix}[/itex]

and

[itex]
V_{2}=\begin{bmatrix}
0\\0
\\ \frac{2}{3}
\\ \frac{1}{3}

\end{bmatrix}[/itex]
 

Related Threads on Build a Markov Matrix

  • Last Post
Replies
3
Views
4K
Replies
5
Views
5K
Replies
3
Views
5K
Replies
2
Views
4K
Replies
3
Views
2K
Replies
0
Views
2K
Replies
4
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
0
Views
962
Top