Construct transition probability matrix for markov chain
$begingroup$
Three fair coins are tossed, and we let $X_1$, denote the number of
heads that appear. Those coins that were heads on the first trial (there were
$X_1$, of them) we pick up and toss again, and now we let $X_2$, be the total number of tails, including those left from the first toss. We toss again all coins
showing tails, and let $X_3$ be the resulting total number of heads, including
those left from the previous toss. We continue the process. The pattern is,
Count heads, toss heads, count tails, toss tails, count heads, toss heads,
etc., and $X_0 = 3$. Then ${X_n}$ is a Markov chain. What is the transition probability matrix?
I have read the answer from
Transition Probability Matrix of Tossing Three coins
But I don't know yet why the states are 8, and how to construct the transition probability matrix. Can anyone help me?
probability stochastic-processes markov-chains
New contributor
$endgroup$
add a comment |
$begingroup$
Three fair coins are tossed, and we let $X_1$, denote the number of
heads that appear. Those coins that were heads on the first trial (there were
$X_1$, of them) we pick up and toss again, and now we let $X_2$, be the total number of tails, including those left from the first toss. We toss again all coins
showing tails, and let $X_3$ be the resulting total number of heads, including
those left from the previous toss. We continue the process. The pattern is,
Count heads, toss heads, count tails, toss tails, count heads, toss heads,
etc., and $X_0 = 3$. Then ${X_n}$ is a Markov chain. What is the transition probability matrix?
I have read the answer from
Transition Probability Matrix of Tossing Three coins
But I don't know yet why the states are 8, and how to construct the transition probability matrix. Can anyone help me?
probability stochastic-processes markov-chains
New contributor
$endgroup$
1
$begingroup$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago
add a comment |
$begingroup$
Three fair coins are tossed, and we let $X_1$, denote the number of
heads that appear. Those coins that were heads on the first trial (there were
$X_1$, of them) we pick up and toss again, and now we let $X_2$, be the total number of tails, including those left from the first toss. We toss again all coins
showing tails, and let $X_3$ be the resulting total number of heads, including
those left from the previous toss. We continue the process. The pattern is,
Count heads, toss heads, count tails, toss tails, count heads, toss heads,
etc., and $X_0 = 3$. Then ${X_n}$ is a Markov chain. What is the transition probability matrix?
I have read the answer from
Transition Probability Matrix of Tossing Three coins
But I don't know yet why the states are 8, and how to construct the transition probability matrix. Can anyone help me?
probability stochastic-processes markov-chains
New contributor
$endgroup$
Three fair coins are tossed, and we let $X_1$, denote the number of
heads that appear. Those coins that were heads on the first trial (there were
$X_1$, of them) we pick up and toss again, and now we let $X_2$, be the total number of tails, including those left from the first toss. We toss again all coins
showing tails, and let $X_3$ be the resulting total number of heads, including
those left from the previous toss. We continue the process. The pattern is,
Count heads, toss heads, count tails, toss tails, count heads, toss heads,
etc., and $X_0 = 3$. Then ${X_n}$ is a Markov chain. What is the transition probability matrix?
I have read the answer from
Transition Probability Matrix of Tossing Three coins
But I don't know yet why the states are 8, and how to construct the transition probability matrix. Can anyone help me?
probability stochastic-processes markov-chains
probability stochastic-processes markov-chains
New contributor
New contributor
edited 5 hours ago
stressed out
5,8891838
5,8891838
New contributor
asked 5 hours ago
liswyhyliswyhy
183
183
New contributor
New contributor
1
$begingroup$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago
add a comment |
1
$begingroup$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago
1
1
$begingroup$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago
$begingroup$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of ${0,1,2,3}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j in {0,1,2,3}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $frac 12$. So the transition probability is just $frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $frac 12$. So the transition probability is just $frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.
$endgroup$
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
add a comment |
$begingroup$
As for why there are $8$ states, there are two things we have to know: how many heads are showing, and whether we're going to re-toss the heads or the tails. Since there are $3$ coins, once we know the number of heads, we also know the numbers of tails, so we don't have to worry about that yet. Now there are $4$ possible values for the number of heads: $0,1,2,3$ and there are two possibilities for which coins we will re-toss: heads and tails. All combinations are possible, so we have $4cdot2=8$ states.
As for constructing the transition matrix, you just have to figure out what might happen. Suppose we have $2$ heads, and we are re-tossing the heads. We know that at the next stage, we'll be re-tossing tails, so we just have to worry about how many heads we'll have. We're keep one tails, so we can have anywhere form $0$ to $2$ heads. We'll have $0$ heads, if both coins come up tails (probability $frac14,$) $1$ heads if one coin comes up heads and the other tails, (probability $frac12,$) and $2$ heads if both coins show heads (probability $frac14.$) The transition probabilities to all other states are $0.$
Just go through this procedure for all the states.
$endgroup$
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
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
});
}
});
liswyhy is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3129620%2fconstruct-transition-probability-matrix-for-markov-chain%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of ${0,1,2,3}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j in {0,1,2,3}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $frac 12$. So the transition probability is just $frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $frac 12$. So the transition probability is just $frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.
$endgroup$
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
add a comment |
$begingroup$
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of ${0,1,2,3}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j in {0,1,2,3}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $frac 12$. So the transition probability is just $frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $frac 12$. So the transition probability is just $frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.
$endgroup$
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
add a comment |
$begingroup$
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of ${0,1,2,3}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j in {0,1,2,3}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $frac 12$. So the transition probability is just $frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $frac 12$. So the transition probability is just $frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.
$endgroup$
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of ${0,1,2,3}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j in {0,1,2,3}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $frac 12$. So the transition probability is just $frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $frac 12$. So the transition probability is just $frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.
edited 1 hour ago
answered 4 hours ago
астон вілла олоф мэллбэргастон вілла олоф мэллбэрг
38.9k33477
38.9k33477
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
add a comment |
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
1
1
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
Your answer is so detail, thank you so much. I'll try to understand it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
You are welcome! You may get back with the answers, I will verify them when I get the time!
$endgroup$
– астон вілла олоф мэллбэрг
1 hour ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@астонвіллаолофмэллбэрг You write "Here are examples of states :" (3, "count heads next round") (1, "count tails next round")(2, "count heads next round")" . Isn't that supposed to be " (3, "count heads next round") (1, "count heads next round")(2, "count tails next round")" , because $X_n$ if $n$ is odd then count head, if $n$ even then count tails.
$endgroup$
– Ongky Denny Wijaya
47 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
$begingroup$
@OngkyDennyWijaya The value of $X_n$ doesn't have anything to do with what is to happen next round,right? It only depends on the value of $n$. The point is, note that our Markov chain always starts at the same point i.e. we always start at the state $X_0 = (3,mathrm{"count heads next round"})$ as per the experiment, so that in $X_1$ we are tossing all the three coins and counting the heads. However, I can start anywhere, so the parity of $X_n$ and the parity of $n$ actually have nothing to do with the state I am at.
$endgroup$
– астон вілла олоф мэллбэрг
39 mins ago
add a comment |
$begingroup$
As for why there are $8$ states, there are two things we have to know: how many heads are showing, and whether we're going to re-toss the heads or the tails. Since there are $3$ coins, once we know the number of heads, we also know the numbers of tails, so we don't have to worry about that yet. Now there are $4$ possible values for the number of heads: $0,1,2,3$ and there are two possibilities for which coins we will re-toss: heads and tails. All combinations are possible, so we have $4cdot2=8$ states.
As for constructing the transition matrix, you just have to figure out what might happen. Suppose we have $2$ heads, and we are re-tossing the heads. We know that at the next stage, we'll be re-tossing tails, so we just have to worry about how many heads we'll have. We're keep one tails, so we can have anywhere form $0$ to $2$ heads. We'll have $0$ heads, if both coins come up tails (probability $frac14,$) $1$ heads if one coin comes up heads and the other tails, (probability $frac12,$) and $2$ heads if both coins show heads (probability $frac14.$) The transition probabilities to all other states are $0.$
Just go through this procedure for all the states.
$endgroup$
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
add a comment |
$begingroup$
As for why there are $8$ states, there are two things we have to know: how many heads are showing, and whether we're going to re-toss the heads or the tails. Since there are $3$ coins, once we know the number of heads, we also know the numbers of tails, so we don't have to worry about that yet. Now there are $4$ possible values for the number of heads: $0,1,2,3$ and there are two possibilities for which coins we will re-toss: heads and tails. All combinations are possible, so we have $4cdot2=8$ states.
As for constructing the transition matrix, you just have to figure out what might happen. Suppose we have $2$ heads, and we are re-tossing the heads. We know that at the next stage, we'll be re-tossing tails, so we just have to worry about how many heads we'll have. We're keep one tails, so we can have anywhere form $0$ to $2$ heads. We'll have $0$ heads, if both coins come up tails (probability $frac14,$) $1$ heads if one coin comes up heads and the other tails, (probability $frac12,$) and $2$ heads if both coins show heads (probability $frac14.$) The transition probabilities to all other states are $0.$
Just go through this procedure for all the states.
$endgroup$
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
add a comment |
$begingroup$
As for why there are $8$ states, there are two things we have to know: how many heads are showing, and whether we're going to re-toss the heads or the tails. Since there are $3$ coins, once we know the number of heads, we also know the numbers of tails, so we don't have to worry about that yet. Now there are $4$ possible values for the number of heads: $0,1,2,3$ and there are two possibilities for which coins we will re-toss: heads and tails. All combinations are possible, so we have $4cdot2=8$ states.
As for constructing the transition matrix, you just have to figure out what might happen. Suppose we have $2$ heads, and we are re-tossing the heads. We know that at the next stage, we'll be re-tossing tails, so we just have to worry about how many heads we'll have. We're keep one tails, so we can have anywhere form $0$ to $2$ heads. We'll have $0$ heads, if both coins come up tails (probability $frac14,$) $1$ heads if one coin comes up heads and the other tails, (probability $frac12,$) and $2$ heads if both coins show heads (probability $frac14.$) The transition probabilities to all other states are $0.$
Just go through this procedure for all the states.
$endgroup$
As for why there are $8$ states, there are two things we have to know: how many heads are showing, and whether we're going to re-toss the heads or the tails. Since there are $3$ coins, once we know the number of heads, we also know the numbers of tails, so we don't have to worry about that yet. Now there are $4$ possible values for the number of heads: $0,1,2,3$ and there are two possibilities for which coins we will re-toss: heads and tails. All combinations are possible, so we have $4cdot2=8$ states.
As for constructing the transition matrix, you just have to figure out what might happen. Suppose we have $2$ heads, and we are re-tossing the heads. We know that at the next stage, we'll be re-tossing tails, so we just have to worry about how many heads we'll have. We're keep one tails, so we can have anywhere form $0$ to $2$ heads. We'll have $0$ heads, if both coins come up tails (probability $frac14,$) $1$ heads if one coin comes up heads and the other tails, (probability $frac12,$) and $2$ heads if both coins show heads (probability $frac14.$) The transition probabilities to all other states are $0.$
Just go through this procedure for all the states.
answered 5 hours ago
saulspatzsaulspatz
15.9k31331
15.9k31331
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
add a comment |
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
$begingroup$
Thank you for your answer. I'll try it.
$endgroup$
– liswyhy
1 hour ago
add a comment |
liswyhy is a new contributor. Be nice, and check out our Code of Conduct.
liswyhy is a new contributor. Be nice, and check out our Code of Conduct.
liswyhy is a new contributor. Be nice, and check out our Code of Conduct.
liswyhy is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3129620%2fconstruct-transition-probability-matrix-for-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$
I am writing an answer. I request you to wait.
$endgroup$
– астон вілла олоф мэллбэрг
5 hours ago