Probability and expected number of steps of/from a transient to an absorbing state in a Markov Chain
$begingroup$
Given an arbitrary but relatively large (more than 50 states) transition matrix, the goal is to find the answer to the following problem:
Assuming we start at state A and ultimately end up in (the only)
absorbing state Z we are looking for a state S that follows:
A → [m steps] → S → [n steps] → Z
How can I calculate the probability of reaching S before reaching Z and the corresponding expected number of steps (n) from S to Z?
Update 24-12:
So I guess the first part is mosre doable than i thought (if my reasoning is correct). My approach:
Rearrange the matrix in canonical form:
$P = left[begin{matrix}
Q & R \ mathbf{0} & I
end{matrix}right]$
Find the fundamental matrix:
$ N = (I - Q)^{-1} $
Find the transient probabilities:
$ H = (N - I)N_{dg} $
And the row of H which corresponds to starting state A. The entries in this row vector should correspond to the probabilities of reaching A before reaching Z.
** Is my thinking here correct? And how can I condition the original transition matrix P to estimate the steps (n) between A and Z? **
markov-chains conditional-probability
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
$endgroup$
add a comment |
$begingroup$
Given an arbitrary but relatively large (more than 50 states) transition matrix, the goal is to find the answer to the following problem:
Assuming we start at state A and ultimately end up in (the only)
absorbing state Z we are looking for a state S that follows:
A → [m steps] → S → [n steps] → Z
How can I calculate the probability of reaching S before reaching Z and the corresponding expected number of steps (n) from S to Z?
Update 24-12:
So I guess the first part is mosre doable than i thought (if my reasoning is correct). My approach:
Rearrange the matrix in canonical form:
$P = left[begin{matrix}
Q & R \ mathbf{0} & I
end{matrix}right]$
Find the fundamental matrix:
$ N = (I - Q)^{-1} $
Find the transient probabilities:
$ H = (N - I)N_{dg} $
And the row of H which corresponds to starting state A. The entries in this row vector should correspond to the probabilities of reaching A before reaching Z.
** Is my thinking here correct? And how can I condition the original transition matrix P to estimate the steps (n) between A and Z? **
markov-chains conditional-probability
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
$endgroup$
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31
add a comment |
$begingroup$
Given an arbitrary but relatively large (more than 50 states) transition matrix, the goal is to find the answer to the following problem:
Assuming we start at state A and ultimately end up in (the only)
absorbing state Z we are looking for a state S that follows:
A → [m steps] → S → [n steps] → Z
How can I calculate the probability of reaching S before reaching Z and the corresponding expected number of steps (n) from S to Z?
Update 24-12:
So I guess the first part is mosre doable than i thought (if my reasoning is correct). My approach:
Rearrange the matrix in canonical form:
$P = left[begin{matrix}
Q & R \ mathbf{0} & I
end{matrix}right]$
Find the fundamental matrix:
$ N = (I - Q)^{-1} $
Find the transient probabilities:
$ H = (N - I)N_{dg} $
And the row of H which corresponds to starting state A. The entries in this row vector should correspond to the probabilities of reaching A before reaching Z.
** Is my thinking here correct? And how can I condition the original transition matrix P to estimate the steps (n) between A and Z? **
markov-chains conditional-probability
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
$endgroup$
Given an arbitrary but relatively large (more than 50 states) transition matrix, the goal is to find the answer to the following problem:
Assuming we start at state A and ultimately end up in (the only)
absorbing state Z we are looking for a state S that follows:
A → [m steps] → S → [n steps] → Z
How can I calculate the probability of reaching S before reaching Z and the corresponding expected number of steps (n) from S to Z?
Update 24-12:
So I guess the first part is mosre doable than i thought (if my reasoning is correct). My approach:
Rearrange the matrix in canonical form:
$P = left[begin{matrix}
Q & R \ mathbf{0} & I
end{matrix}right]$
Find the fundamental matrix:
$ N = (I - Q)^{-1} $
Find the transient probabilities:
$ H = (N - I)N_{dg} $
And the row of H which corresponds to starting state A. The entries in this row vector should correspond to the probabilities of reaching A before reaching Z.
** Is my thinking here correct? And how can I condition the original transition matrix P to estimate the steps (n) between A and Z? **
markov-chains conditional-probability
markov-chains conditional-probability
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
edited Dec 24 '18 at 22:19
Remy Kabel
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
asked Dec 19 '18 at 8:45
Remy KabelRemy Kabel
735
735
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31
add a comment |
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31
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%2f3046175%2fprobability-and-expected-number-of-steps-of-from-a-transient-to-an-absorbing-sta%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%2f3046175%2fprobability-and-expected-number-of-steps-of-from-a-transient-to-an-absorbing-sta%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
$begingroup$
To clarify, we have a starting state A, ending state Z, and want to find a state S such that, conditioned on passing through S, the expected value of the number of steps to get to S is m, the the number of steps to get to Z is n?
$endgroup$
– Alex
Dec 23 '18 at 3:10
$begingroup$
Yes, exactly! I just don't exactly how to approach such calculation.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:00
$begingroup$
My idea would be that this problem is two-fold: 1. Find the probability of reaching S before absorption, and then 2. Transforming the matrix to the conditional probability as you say. But honestly I don't know exactly how to approach either.
$endgroup$
– Remy Kabel
Dec 23 '18 at 11:06
$begingroup$
Are you looking for the probability distribution of the time to absorption for finite discrete or continuous time Markov chain?
$endgroup$
– Waqas
Dec 28 '18 at 12:31