Mixing
Markov Chain--starting states
$begingroup$
How do we define the starting states in a Markov Chain. For example if we are asked to calculate the transition matrix for different starting states, what does that mean?
I am ultimately asked to derive the matrix M^n as n tends to infinity?
probability-theory markov-chains
asked Apr 8 '15 at 2:35
BachelierBachelier
667
$endgroup$
add a comment |
$begingroup$
How do we define the starting states in a Markov Chain. For example if we are asked to calculate the transition matrix for different starting states, what does that mean?
I am ultimately asked to derive the matrix M^n as n tends to infinity?
probability-theory markov-chains
asked Apr 8 '15 at 2:35
BachelierBachelier
667
$endgroup$
1
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09
add a comment |
$begingroup$
How do we define the starting states in a Markov Chain. For example if we are asked to calculate the transition matrix for different starting states, what does that mean?
I am ultimately asked to derive the matrix M^n as n tends to infinity?
probability-theory markov-chains
asked Apr 8 '15 at 2:35
BachelierBachelier
667
$endgroup$
How do we define the starting states in a Markov Chain. For example if we are asked to calculate the transition matrix for different starting states, what does that mean?
I am ultimately asked to derive the matrix M^n as n tends to infinity?
probability-theory markov-chains
probability-theory markov-chains
asked Apr 8 '15 at 2:35
BachelierBachelier
667
asked Apr 8 '15 at 2:35
BachelierBachelier
667
asked Apr 8 '15 at 2:35
BachelierBachelier
667
asked Apr 8 '15 at 2:35
BachelierBachelier
667
asked Apr 8 '15 at 2:35
BachelierBachelier
667
667
1
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09
add a comment |
1
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09
1
1
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the transition matrix has columns adding to one and multiplying by distribution vectors on the right).
A regular Markov Chain is one in which for our transition matrix $T$, there exists some $n$ such that $T^{n}$ has all nonzero positive entries. Regular Markov chains have the very nice property that as $ntoinfty$ you will have some stable distribution, $y$, such that $T y = y$, and furthermore that $lim_{ntoinfty}T^n x = y$ regardless what $x$ is.
To solve, noting that $Ty = y$ and that $y$ is a distribution, meaning that the sum of the entries of $y$ will equal one, you are given the system of equations:
$begin{cases} y_1 + y_2 + dots + y_k = 1\ T_{1,1}y_1 + T_{1,2}y_2 + dots + T_{1,k}y_k = y_1 \ vdots \ T_{k,1}y_1 + T_{k,2}y_2 + dots + T_{k,k}y_k = y_kend{cases}$
This is a system of $k+1$ equations in $k$ unknowns, and as it so happens, one of the lines will be redundant (the rows are not linearly independent due to the stochastic property). Using your favorite method, solve the system to obtain the stable distribution $y$.
The long term matrix, $lim_{ntoinfty}T^n$, having the property that any initial distribution (in particular distributions with only one nonzero state) will eventually reach the stable distribution, it follows that it will appear as every column being a copy of $y$.
The other type of Markov Chain you are likely to see is an absorbing markov chain. An absorbing markov chain is one that has an absorbing state, a state that once entered cannot be left. I.e. when looking at the transition matrix, there will be a one along the main diagonal. The rows/columns with a one are the absorbing states. The final distribution in these cases will depend on what the initial distribution is, however there will be a longterm trend for the transition matrix itself.
Reorganizing the matrix into its standard form by swapping columns and rows (making sure that the order states appear in the columns is the same as the order they appear for the rows), you will have a matrix in the form
$$T=left[begin{array}{c|c}
I & S\ hline 0 & Rend{array}right]$$
and the long term matrix will be:
$$lim_{ntoinfty} T^n = left[begin{array}{c|c}
I & S(I-R)^{-1}\ hline 0 & 0end{array}right]$$
See examples of absorbing markov chains in action in some of my previous answers Chance of winning simple dice game and Sniper probability question
For an example of a regular markov chain, suppose we have a fleet of taxicabs and three major hubs in the city for them to go. We have midtown, downtown, and the airport. Each taxi will transition from one location to another or stay at the same spot once every 15 minutes.
Suppose our transition diagram is given as:
Our transition matrix is then:
$$begin{bmatrix} .4 & 0 & .2\ .3 & 0 & .7\ .3 & 1 & .1end{bmatrix}$$
This doesn't have nothing but nonzero numbers, so we might be hesitant to think it falls under the first case, but tedious arithmetic aside, you will see that $T^3$ has all strictly positive entries. (This is seen easier from the transition diagram from a graph theoretic sense by noting that there exists a length 3 path from any state to any other state).
Thus, we solve the system:
$$begin{cases} y_1+y_2+y_3 = 1\ .4y_1 + 0 + .2y_3 = y_1\ .3y_1 + 0 + .7y_3 = y_2\ .3y_1 + 1y_2 + .1y_3 = y_3end{cases}$$
Rearranging and setting up a matrix to rowreduce, we arrive at:
$$left[begin{array}{ccc|c}
1 & 1 & 1 & 1\
-.6 & 0 & .2 & 0\
.3 & -1 & .7 & 0\
.3 & 1 & -.9 & 0end{array}right]$$
which row reduces to
$$left[begin{array}{ccc|c}
1 & 0 & 0 & .15625\
0 & 1 & 0 & .375\
0 & 0 & 1 & .46875\
0 & 0 & 0 & 0end{array}right]$$
Indeed, checking $Ty$ it works out correctly.
Thus, after a "long time", about an eighth of the taxis will be at midtown, about one third of the taxis will be at the airport, and about half will be at downtown.
Our longterm matrix is thus three columns identical to $y$.
edited Apr 13 '17 at 12:21
Community♦
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
$endgroup$
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1224897%2fmarkov-chain-starting-states%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the transition matrix has columns adding to one and multiplying by distribution vectors on the right).
A regular Markov Chain is one in which for our transition matrix $T$, there exists some $n$ such that $T^{n}$ has all nonzero positive entries. Regular Markov chains have the very nice property that as $ntoinfty$ you will have some stable distribution, $y$, such that $T y = y$, and furthermore that $lim_{ntoinfty}T^n x = y$ regardless what $x$ is.
To solve, noting that $Ty = y$ and that $y$ is a distribution, meaning that the sum of the entries of $y$ will equal one, you are given the system of equations:
$begin{cases} y_1 + y_2 + dots + y_k = 1\ T_{1,1}y_1 + T_{1,2}y_2 + dots + T_{1,k}y_k = y_1 \ vdots \ T_{k,1}y_1 + T_{k,2}y_2 + dots + T_{k,k}y_k = y_kend{cases}$
This is a system of $k+1$ equations in $k$ unknowns, and as it so happens, one of the lines will be redundant (the rows are not linearly independent due to the stochastic property). Using your favorite method, solve the system to obtain the stable distribution $y$.
The long term matrix, $lim_{ntoinfty}T^n$, having the property that any initial distribution (in particular distributions with only one nonzero state) will eventually reach the stable distribution, it follows that it will appear as every column being a copy of $y$.
The other type of Markov Chain you are likely to see is an absorbing markov chain. An absorbing markov chain is one that has an absorbing state, a state that once entered cannot be left. I.e. when looking at the transition matrix, there will be a one along the main diagonal. The rows/columns with a one are the absorbing states. The final distribution in these cases will depend on what the initial distribution is, however there will be a longterm trend for the transition matrix itself.
Reorganizing the matrix into its standard form by swapping columns and rows (making sure that the order states appear in the columns is the same as the order they appear for the rows), you will have a matrix in the form
$$T=left[begin{array}{c|c}
I & S\ hline 0 & Rend{array}right]$$
and the long term matrix will be:
$$lim_{ntoinfty} T^n = left[begin{array}{c|c}
I & S(I-R)^{-1}\ hline 0 & 0end{array}right]$$
See examples of absorbing markov chains in action in some of my previous answers Chance of winning simple dice game and Sniper probability question
For an example of a regular markov chain, suppose we have a fleet of taxicabs and three major hubs in the city for them to go. We have midtown, downtown, and the airport. Each taxi will transition from one location to another or stay at the same spot once every 15 minutes.
Suppose our transition diagram is given as:
Our transition matrix is then:
$$begin{bmatrix} .4 & 0 & .2\ .3 & 0 & .7\ .3 & 1 & .1end{bmatrix}$$
This doesn't have nothing but nonzero numbers, so we might be hesitant to think it falls under the first case, but tedious arithmetic aside, you will see that $T^3$ has all strictly positive entries. (This is seen easier from the transition diagram from a graph theoretic sense by noting that there exists a length 3 path from any state to any other state).
Thus, we solve the system:
$$begin{cases} y_1+y_2+y_3 = 1\ .4y_1 + 0 + .2y_3 = y_1\ .3y_1 + 0 + .7y_3 = y_2\ .3y_1 + 1y_2 + .1y_3 = y_3end{cases}$$
Rearranging and setting up a matrix to rowreduce, we arrive at:
$$left[begin{array}{ccc|c}
1 & 1 & 1 & 1\
-.6 & 0 & .2 & 0\
.3 & -1 & .7 & 0\
.3 & 1 & -.9 & 0end{array}right]$$
which row reduces to
$$left[begin{array}{ccc|c}
1 & 0 & 0 & .15625\
0 & 1 & 0 & .375\
0 & 0 & 1 & .46875\
0 & 0 & 0 & 0end{array}right]$$
Indeed, checking $Ty$ it works out correctly.
Thus, after a "long time", about an eighth of the taxis will be at midtown, about one third of the taxis will be at the airport, and about half will be at downtown.
Our longterm matrix is thus three columns identical to $y$.
edited Apr 13 '17 at 12:21
Community♦
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
$endgroup$
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
add a comment |
$begingroup$
There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the transition matrix has columns adding to one and multiplying by distribution vectors on the right).
A regular Markov Chain is one in which for our transition matrix $T$, there exists some $n$ such that $T^{n}$ has all nonzero positive entries. Regular Markov chains have the very nice property that as $ntoinfty$ you will have some stable distribution, $y$, such that $T y = y$, and furthermore that $lim_{ntoinfty}T^n x = y$ regardless what $x$ is.
To solve, noting that $Ty = y$ and that $y$ is a distribution, meaning that the sum of the entries of $y$ will equal one, you are given the system of equations:
$begin{cases} y_1 + y_2 + dots + y_k = 1\ T_{1,1}y_1 + T_{1,2}y_2 + dots + T_{1,k}y_k = y_1 \ vdots \ T_{k,1}y_1 + T_{k,2}y_2 + dots + T_{k,k}y_k = y_kend{cases}$
This is a system of $k+1$ equations in $k$ unknowns, and as it so happens, one of the lines will be redundant (the rows are not linearly independent due to the stochastic property). Using your favorite method, solve the system to obtain the stable distribution $y$.
The long term matrix, $lim_{ntoinfty}T^n$, having the property that any initial distribution (in particular distributions with only one nonzero state) will eventually reach the stable distribution, it follows that it will appear as every column being a copy of $y$.
The other type of Markov Chain you are likely to see is an absorbing markov chain. An absorbing markov chain is one that has an absorbing state, a state that once entered cannot be left. I.e. when looking at the transition matrix, there will be a one along the main diagonal. The rows/columns with a one are the absorbing states. The final distribution in these cases will depend on what the initial distribution is, however there will be a longterm trend for the transition matrix itself.
Reorganizing the matrix into its standard form by swapping columns and rows (making sure that the order states appear in the columns is the same as the order they appear for the rows), you will have a matrix in the form
$$T=left[begin{array}{c|c}
I & S\ hline 0 & Rend{array}right]$$
and the long term matrix will be:
$$lim_{ntoinfty} T^n = left[begin{array}{c|c}
I & S(I-R)^{-1}\ hline 0 & 0end{array}right]$$
See examples of absorbing markov chains in action in some of my previous answers Chance of winning simple dice game and Sniper probability question
For an example of a regular markov chain, suppose we have a fleet of taxicabs and three major hubs in the city for them to go. We have midtown, downtown, and the airport. Each taxi will transition from one location to another or stay at the same spot once every 15 minutes.
Suppose our transition diagram is given as:
Our transition matrix is then:
$$begin{bmatrix} .4 & 0 & .2\ .3 & 0 & .7\ .3 & 1 & .1end{bmatrix}$$
This doesn't have nothing but nonzero numbers, so we might be hesitant to think it falls under the first case, but tedious arithmetic aside, you will see that $T^3$ has all strictly positive entries. (This is seen easier from the transition diagram from a graph theoretic sense by noting that there exists a length 3 path from any state to any other state).
Thus, we solve the system:
$$begin{cases} y_1+y_2+y_3 = 1\ .4y_1 + 0 + .2y_3 = y_1\ .3y_1 + 0 + .7y_3 = y_2\ .3y_1 + 1y_2 + .1y_3 = y_3end{cases}$$
Rearranging and setting up a matrix to rowreduce, we arrive at:
$$left[begin{array}{ccc|c}
1 & 1 & 1 & 1\
-.6 & 0 & .2 & 0\
.3 & -1 & .7 & 0\
.3 & 1 & -.9 & 0end{array}right]$$
which row reduces to
$$left[begin{array}{ccc|c}
1 & 0 & 0 & .15625\
0 & 1 & 0 & .375\
0 & 0 & 1 & .46875\
0 & 0 & 0 & 0end{array}right]$$
Indeed, checking $Ty$ it works out correctly.
Thus, after a "long time", about an eighth of the taxis will be at midtown, about one third of the taxis will be at the airport, and about half will be at downtown.
Our longterm matrix is thus three columns identical to $y$.
edited Apr 13 '17 at 12:21
Community♦
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
$endgroup$
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
add a comment |
$begingroup$
There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the transition matrix has columns adding to one and multiplying by distribution vectors on the right).
A regular Markov Chain is one in which for our transition matrix $T$, there exists some $n$ such that $T^{n}$ has all nonzero positive entries. Regular Markov chains have the very nice property that as $ntoinfty$ you will have some stable distribution, $y$, such that $T y = y$, and furthermore that $lim_{ntoinfty}T^n x = y$ regardless what $x$ is.
To solve, noting that $Ty = y$ and that $y$ is a distribution, meaning that the sum of the entries of $y$ will equal one, you are given the system of equations:
$begin{cases} y_1 + y_2 + dots + y_k = 1\ T_{1,1}y_1 + T_{1,2}y_2 + dots + T_{1,k}y_k = y_1 \ vdots \ T_{k,1}y_1 + T_{k,2}y_2 + dots + T_{k,k}y_k = y_kend{cases}$
This is a system of $k+1$ equations in $k$ unknowns, and as it so happens, one of the lines will be redundant (the rows are not linearly independent due to the stochastic property). Using your favorite method, solve the system to obtain the stable distribution $y$.
The long term matrix, $lim_{ntoinfty}T^n$, having the property that any initial distribution (in particular distributions with only one nonzero state) will eventually reach the stable distribution, it follows that it will appear as every column being a copy of $y$.
The other type of Markov Chain you are likely to see is an absorbing markov chain. An absorbing markov chain is one that has an absorbing state, a state that once entered cannot be left. I.e. when looking at the transition matrix, there will be a one along the main diagonal. The rows/columns with a one are the absorbing states. The final distribution in these cases will depend on what the initial distribution is, however there will be a longterm trend for the transition matrix itself.
Reorganizing the matrix into its standard form by swapping columns and rows (making sure that the order states appear in the columns is the same as the order they appear for the rows), you will have a matrix in the form
$$T=left[begin{array}{c|c}
I & S\ hline 0 & Rend{array}right]$$
and the long term matrix will be:
$$lim_{ntoinfty} T^n = left[begin{array}{c|c}
I & S(I-R)^{-1}\ hline 0 & 0end{array}right]$$
See examples of absorbing markov chains in action in some of my previous answers Chance of winning simple dice game and Sniper probability question
For an example of a regular markov chain, suppose we have a fleet of taxicabs and three major hubs in the city for them to go. We have midtown, downtown, and the airport. Each taxi will transition from one location to another or stay at the same spot once every 15 minutes.
Suppose our transition diagram is given as:
Our transition matrix is then:
$$begin{bmatrix} .4 & 0 & .2\ .3 & 0 & .7\ .3 & 1 & .1end{bmatrix}$$
This doesn't have nothing but nonzero numbers, so we might be hesitant to think it falls under the first case, but tedious arithmetic aside, you will see that $T^3$ has all strictly positive entries. (This is seen easier from the transition diagram from a graph theoretic sense by noting that there exists a length 3 path from any state to any other state).
Thus, we solve the system:
$$begin{cases} y_1+y_2+y_3 = 1\ .4y_1 + 0 + .2y_3 = y_1\ .3y_1 + 0 + .7y_3 = y_2\ .3y_1 + 1y_2 + .1y_3 = y_3end{cases}$$
Rearranging and setting up a matrix to rowreduce, we arrive at:
$$left[begin{array}{ccc|c}
1 & 1 & 1 & 1\
-.6 & 0 & .2 & 0\
.3 & -1 & .7 & 0\
.3 & 1 & -.9 & 0end{array}right]$$
which row reduces to
$$left[begin{array}{ccc|c}
1 & 0 & 0 & .15625\
0 & 1 & 0 & .375\
0 & 0 & 1 & .46875\
0 & 0 & 0 & 0end{array}right]$$
Indeed, checking $Ty$ it works out correctly.
Thus, after a "long time", about an eighth of the taxis will be at midtown, about one third of the taxis will be at the airport, and about half will be at downtown.
Our longterm matrix is thus three columns identical to $y$.
edited Apr 13 '17 at 12:21
Community♦
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
$endgroup$
There are different types of Markov chains, which you will be able to recognize by their transition matrix (and/or by their transition graph). These transition matrices have the property that their columns add up to one and all entries are between 0 and 1. I will discuss here two of the most common types. (Here I will use the convention that the transition matrix has columns adding to one and multiplying by distribution vectors on the right).
A regular Markov Chain is one in which for our transition matrix $T$, there exists some $n$ such that $T^{n}$ has all nonzero positive entries. Regular Markov chains have the very nice property that as $ntoinfty$ you will have some stable distribution, $y$, such that $T y = y$, and furthermore that $lim_{ntoinfty}T^n x = y$ regardless what $x$ is.
To solve, noting that $Ty = y$ and that $y$ is a distribution, meaning that the sum of the entries of $y$ will equal one, you are given the system of equations:
$begin{cases} y_1 + y_2 + dots + y_k = 1\ T_{1,1}y_1 + T_{1,2}y_2 + dots + T_{1,k}y_k = y_1 \ vdots \ T_{k,1}y_1 + T_{k,2}y_2 + dots + T_{k,k}y_k = y_kend{cases}$
This is a system of $k+1$ equations in $k$ unknowns, and as it so happens, one of the lines will be redundant (the rows are not linearly independent due to the stochastic property). Using your favorite method, solve the system to obtain the stable distribution $y$.
The long term matrix, $lim_{ntoinfty}T^n$, having the property that any initial distribution (in particular distributions with only one nonzero state) will eventually reach the stable distribution, it follows that it will appear as every column being a copy of $y$.
The other type of Markov Chain you are likely to see is an absorbing markov chain. An absorbing markov chain is one that has an absorbing state, a state that once entered cannot be left. I.e. when looking at the transition matrix, there will be a one along the main diagonal. The rows/columns with a one are the absorbing states. The final distribution in these cases will depend on what the initial distribution is, however there will be a longterm trend for the transition matrix itself.
Reorganizing the matrix into its standard form by swapping columns and rows (making sure that the order states appear in the columns is the same as the order they appear for the rows), you will have a matrix in the form
$$T=left[begin{array}{c|c}
I & S\ hline 0 & Rend{array}right]$$
and the long term matrix will be:
$$lim_{ntoinfty} T^n = left[begin{array}{c|c}
I & S(I-R)^{-1}\ hline 0 & 0end{array}right]$$
See examples of absorbing markov chains in action in some of my previous answers Chance of winning simple dice game and Sniper probability question
For an example of a regular markov chain, suppose we have a fleet of taxicabs and three major hubs in the city for them to go. We have midtown, downtown, and the airport. Each taxi will transition from one location to another or stay at the same spot once every 15 minutes.
Suppose our transition diagram is given as:
Our transition matrix is then:
$$begin{bmatrix} .4 & 0 & .2\ .3 & 0 & .7\ .3 & 1 & .1end{bmatrix}$$
This doesn't have nothing but nonzero numbers, so we might be hesitant to think it falls under the first case, but tedious arithmetic aside, you will see that $T^3$ has all strictly positive entries. (This is seen easier from the transition diagram from a graph theoretic sense by noting that there exists a length 3 path from any state to any other state).
Thus, we solve the system:
$$begin{cases} y_1+y_2+y_3 = 1\ .4y_1 + 0 + .2y_3 = y_1\ .3y_1 + 0 + .7y_3 = y_2\ .3y_1 + 1y_2 + .1y_3 = y_3end{cases}$$
Rearranging and setting up a matrix to rowreduce, we arrive at:
$$left[begin{array}{ccc|c}
1 & 1 & 1 & 1\
-.6 & 0 & .2 & 0\
.3 & -1 & .7 & 0\
.3 & 1 & -.9 & 0end{array}right]$$
which row reduces to
$$left[begin{array}{ccc|c}
1 & 0 & 0 & .15625\
0 & 1 & 0 & .375\
0 & 0 & 1 & .46875\
0 & 0 & 0 & 0end{array}right]$$
Indeed, checking $Ty$ it works out correctly.
Thus, after a "long time", about an eighth of the taxis will be at midtown, about one third of the taxis will be at the airport, and about half will be at downtown.
Our longterm matrix is thus three columns identical to $y$.
edited Apr 13 '17 at 12:21
Community♦
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
edited Apr 13 '17 at 12:21
Community♦
1
1
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
answered Apr 8 '15 at 3:12
JMoravitzJMoravitz
48.3k33987
48.3k33987
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
add a comment |
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
1
1
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
Note that you have said the column sums are $1$ and then wrote transition matrices whose row sums are $1$. Either way is fine but please be consistent.
$endgroup$
– Ian
Apr 8 '15 at 3:44
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
$begingroup$
@Ian fixed my example. The numbers didn't work out quite as nicely as before, but are much more believable now. It is always good to double check yourself that you are using things as you define them. When doing $Tx_n = x_{n+1}$ it should be columns adding to one and the $i^{th}$ row, $j^{th}$ column entry is the chance of going from state $j$ to state $i$. A good way to double check yourself is with a permutation matrix. There are those who prefer to use $lambda T$ instead, in which case everything is transposed. Instead of a column vector on the right it is row vector on left etc...
$endgroup$
– JMoravitz
Apr 8 '15 at 3:56
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1224897%2fmarkov-chain-starting-states%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
The transition matrix doesn't depend on the starting state with a Markov chain. That's part of the Markov property.
$endgroup$
– Ian
Apr 8 '15 at 2:37
$begingroup$
@Ian could you please give me an example of a starting state in the case of a 3x3 TM. would that be something like a 1x3 vector?
$endgroup$
– Bachelier
Apr 8 '15 at 2:46
$begingroup$
That depends what you mean by starting state. Do you mean a starting distribution? That would indeed be a 1x3 vector. Usually in discussing Markov chains we reserve the word "state" for elements of the set of possible values of the chain. This set is usually written $S$.
$endgroup$
– Ian
Apr 8 '15 at 2:50
$begingroup$
@Ian all good. But the following question is confusing me: I am trying to develop an r program to simulate a Markov chain with TM. Then the question asks: "for different starting states and arbitrary matrix (as it may be random matrix ), calculate M to the power of n?" and it asks what can we say about the M^n for large n.
$endgroup$
– Bachelier
Apr 8 '15 at 3:01
$begingroup$
I think they mean that you should consider $lambda M^n$ for different initial distributions $lambda$ and different transition matrices $M$.
$endgroup$
– Ian
Apr 8 '15 at 3:09