Fundamental Matrix of a Reducible Recurrent Markov Chain
$begingroup$
I have a Markov chain with states ${A,B,C,D,E}$ and the following transition matrix $P$:
$$
begin{bmatrix}
0 & 0 & 0 & 0 & 1 \
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 \
0.2404 & 0 & 0.7596 & 0 & 0
end{bmatrix}
$$
Which, as far as I can say, is aperiodic and reducible. Its communicating classes are ${{1,3,5},2,4}$, all of which are recurrent.
The following pseudo-code represents the approach I'm using in order to compute the fundamental matrix of a given chain:
function get_fundamental_matrix(chain)
{
if (chain.is_irreducible)
{
// the transition matrix is converted into its canonical form
// with all the transient states coming first
p = chain.to_canonical_form().p
// only one stationary distribution row vector should exist,
// so it's converted into a squared matrix by tiling it
// vertically for states_count times
a = repeat(chain.stationary_distributions[0], chain.states_count)
// the fundamental matrix is computed using the Kemeny and Snell
// approach; sometimes Z contains negative values but as far as
// I can say this is correct and rows always sum to 1
i = eye(chain.size)
result = inv(i - p + a) // Z
}
else
{
// the standard approach is used otherwise; q is a squared matrix
// containing all the transient states probabilities
q = chain.p[transient_indices,transient_indices]
i = np.eye(len(transient_indices))
result = npl.inv(i - q) // N
}
return result
}
I run this function with a lot of test cases and it always managed to produce a coherent result. But with this matrix it's failing because:
- the matrix it's not irreducible, so the if statements goes into the else case;
- the matrix contains no transient states, hence $Q$ is empty and $N$ is returned as an empty matrix.
Can someone explain me how I should proceed in order to obtain the fundamental matrix? Maybe it's simply not possible?
matrices markov-chains
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
$endgroup$
add a comment |
$begingroup$
I have a Markov chain with states ${A,B,C,D,E}$ and the following transition matrix $P$:
$$
begin{bmatrix}
0 & 0 & 0 & 0 & 1 \
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 \
0.2404 & 0 & 0.7596 & 0 & 0
end{bmatrix}
$$
Which, as far as I can say, is aperiodic and reducible. Its communicating classes are ${{1,3,5},2,4}$, all of which are recurrent.
The following pseudo-code represents the approach I'm using in order to compute the fundamental matrix of a given chain:
function get_fundamental_matrix(chain)
{
if (chain.is_irreducible)
{
// the transition matrix is converted into its canonical form
// with all the transient states coming first
p = chain.to_canonical_form().p
// only one stationary distribution row vector should exist,
// so it's converted into a squared matrix by tiling it
// vertically for states_count times
a = repeat(chain.stationary_distributions[0], chain.states_count)
// the fundamental matrix is computed using the Kemeny and Snell
// approach; sometimes Z contains negative values but as far as
// I can say this is correct and rows always sum to 1
i = eye(chain.size)
result = inv(i - p + a) // Z
}
else
{
// the standard approach is used otherwise; q is a squared matrix
// containing all the transient states probabilities
q = chain.p[transient_indices,transient_indices]
i = np.eye(len(transient_indices))
result = npl.inv(i - q) // N
}
return result
}
I run this function with a lot of test cases and it always managed to produce a coherent result. But with this matrix it's failing because:
- the matrix it's not irreducible, so the if statements goes into the else case;
- the matrix contains no transient states, hence $Q$ is empty and $N$ is returned as an empty matrix.
Can someone explain me how I should proceed in order to obtain the fundamental matrix? Maybe it's simply not possible?
matrices markov-chains
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
$endgroup$
1
$begingroup$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07
add a comment |
$begingroup$
I have a Markov chain with states ${A,B,C,D,E}$ and the following transition matrix $P$:
$$
begin{bmatrix}
0 & 0 & 0 & 0 & 1 \
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 \
0.2404 & 0 & 0.7596 & 0 & 0
end{bmatrix}
$$
Which, as far as I can say, is aperiodic and reducible. Its communicating classes are ${{1,3,5},2,4}$, all of which are recurrent.
The following pseudo-code represents the approach I'm using in order to compute the fundamental matrix of a given chain:
function get_fundamental_matrix(chain)
{
if (chain.is_irreducible)
{
// the transition matrix is converted into its canonical form
// with all the transient states coming first
p = chain.to_canonical_form().p
// only one stationary distribution row vector should exist,
// so it's converted into a squared matrix by tiling it
// vertically for states_count times
a = repeat(chain.stationary_distributions[0], chain.states_count)
// the fundamental matrix is computed using the Kemeny and Snell
// approach; sometimes Z contains negative values but as far as
// I can say this is correct and rows always sum to 1
i = eye(chain.size)
result = inv(i - p + a) // Z
}
else
{
// the standard approach is used otherwise; q is a squared matrix
// containing all the transient states probabilities
q = chain.p[transient_indices,transient_indices]
i = np.eye(len(transient_indices))
result = npl.inv(i - q) // N
}
return result
}
I run this function with a lot of test cases and it always managed to produce a coherent result. But with this matrix it's failing because:
- the matrix it's not irreducible, so the if statements goes into the else case;
- the matrix contains no transient states, hence $Q$ is empty and $N$ is returned as an empty matrix.
Can someone explain me how I should proceed in order to obtain the fundamental matrix? Maybe it's simply not possible?
matrices markov-chains
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
$endgroup$
I have a Markov chain with states ${A,B,C,D,E}$ and the following transition matrix $P$:
$$
begin{bmatrix}
0 & 0 & 0 & 0 & 1 \
0 & 1 & 0 & 0 & 0 \
1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 \
0.2404 & 0 & 0.7596 & 0 & 0
end{bmatrix}
$$
Which, as far as I can say, is aperiodic and reducible. Its communicating classes are ${{1,3,5},2,4}$, all of which are recurrent.
The following pseudo-code represents the approach I'm using in order to compute the fundamental matrix of a given chain:
function get_fundamental_matrix(chain)
{
if (chain.is_irreducible)
{
// the transition matrix is converted into its canonical form
// with all the transient states coming first
p = chain.to_canonical_form().p
// only one stationary distribution row vector should exist,
// so it's converted into a squared matrix by tiling it
// vertically for states_count times
a = repeat(chain.stationary_distributions[0], chain.states_count)
// the fundamental matrix is computed using the Kemeny and Snell
// approach; sometimes Z contains negative values but as far as
// I can say this is correct and rows always sum to 1
i = eye(chain.size)
result = inv(i - p + a) // Z
}
else
{
// the standard approach is used otherwise; q is a squared matrix
// containing all the transient states probabilities
q = chain.p[transient_indices,transient_indices]
i = np.eye(len(transient_indices))
result = npl.inv(i - q) // N
}
return result
}
I run this function with a lot of test cases and it always managed to produce a coherent result. But with this matrix it's failing because:
- the matrix it's not irreducible, so the if statements goes into the else case;
- the matrix contains no transient states, hence $Q$ is empty and $N$ is returned as an empty matrix.
Can someone explain me how I should proceed in order to obtain the fundamental matrix? Maybe it's simply not possible?
matrices markov-chains
matrices markov-chains
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
edited Dec 7 '18 at 9:54
Zarathos
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
asked Dec 7 '18 at 9:30
ZarathosZarathos
1087
1087
1
$begingroup$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07
add a comment |
1
$begingroup$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07
1
1
$begingroup$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07
add a comment |
0
active
oldest
votes
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%2f3029693%2ffundamental-matrix-of-a-reducible-recurrent-markov-chain%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3029693%2ffundamental-matrix-of-a-reducible-recurrent-markov-chain%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$
Isn’t the fundamental matrix only defined for an absorbing Markov chain—one in which every state communicates with some absorbing state? (Alternatively, one that has only absorbing and transient states?)
$endgroup$
– amd
Dec 7 '18 at 10:21
$begingroup$
If being absorbing is a necessary condition for the chain, then solving this issue would be easier than expected. Although I read a lot of papers, and most of them were referring to absorbing chains, but none of them stated this condition explicitly.
$endgroup$
– Zarathos
Dec 7 '18 at 12:06
$begingroup$
You could convert the example into an absorbing chain by collapsing the nontrivial recurrent class into a single absorbing state. In that case, the fundamental matrix would indeed be empty since the “quotient” system simply remains in whatever state it started in.
$endgroup$
– amd
Dec 7 '18 at 19:07