Are MCMC without memory?
$begingroup$
I'm trying to understand what Markov chain Monte Carlo (MCMC) are from the French Wikipedia page. They say "that the Markov chain Monte Carlo methods consist of generating a vector $x_ {i}$ only from the vector data $x_ {i-1}$ it is therefore a process "without memory""
Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer
un vecteur $x_{i}$ uniquement à partir de la
donnée du vecteur $x_{{i-1}}$ ; c'est donc un
processus « sans mémoire »,
I don't understand why they say MCMC are "without memory" as far as we use information from the vector data $x_ {i-1}$ to generate $x_i$.
mcmc
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
$endgroup$
add a comment |
$begingroup$
I'm trying to understand what Markov chain Monte Carlo (MCMC) are from the French Wikipedia page. They say "that the Markov chain Monte Carlo methods consist of generating a vector $x_ {i}$ only from the vector data $x_ {i-1}$ it is therefore a process "without memory""
Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer
un vecteur $x_{i}$ uniquement à partir de la
donnée du vecteur $x_{{i-1}}$ ; c'est donc un
processus « sans mémoire »,
I don't understand why they say MCMC are "without memory" as far as we use information from the vector data $x_ {i-1}$ to generate $x_i$.
mcmc
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
$endgroup$
3
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56
add a comment |
$begingroup$
I'm trying to understand what Markov chain Monte Carlo (MCMC) are from the French Wikipedia page. They say "that the Markov chain Monte Carlo methods consist of generating a vector $x_ {i}$ only from the vector data $x_ {i-1}$ it is therefore a process "without memory""
Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer
un vecteur $x_{i}$ uniquement à partir de la
donnée du vecteur $x_{{i-1}}$ ; c'est donc un
processus « sans mémoire »,
I don't understand why they say MCMC are "without memory" as far as we use information from the vector data $x_ {i-1}$ to generate $x_i$.
mcmc
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
$endgroup$
I'm trying to understand what Markov chain Monte Carlo (MCMC) are from the French Wikipedia page. They say "that the Markov chain Monte Carlo methods consist of generating a vector $x_ {i}$ only from the vector data $x_ {i-1}$ it is therefore a process "without memory""
Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer
un vecteur $x_{i}$ uniquement à partir de la
donnée du vecteur $x_{{i-1}}$ ; c'est donc un
processus « sans mémoire »,
I don't understand why they say MCMC are "without memory" as far as we use information from the vector data $x_ {i-1}$ to generate $x_i$.
mcmc
mcmc
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
asked Feb 4 at 12:25
ThePassengerThePassenger
263113
263113
3
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56
add a comment |
3
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56
3
3
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The defining characteristic of a Markov chain is that the conditional distribution of its present value conditional on past values depends only on the previous value. So every Markov chain is "without memory" to the extent that only the previous value affects the present conditional probability, and all previous states are "forgotten". (You are right that it is not completely without memory - after all, the conditional distribution of the present value depends on the previous value.) That is true for MCMC and also for any other Markov chain.
answered Feb 4 at 13:05
BenBen
24.7k226117
$endgroup$
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
add a comment |
$begingroup$
While we have the correct answer, I would like to expand just a little bit on the intuitive semantics of the statement. Imagine that we redefine our indices such that you generate vector $x_{i+1}$ from vector $x_{i}$. Now, moment $i$ is metaphorically seen as "the present", and all vectors coming "earlier than" $x_{i}$ are irrelevant for calculating the next one in the future.
Through this simple renumbering, it becomes "completely without memory" in the intuitive sense - that is, it doesn't matter at all how the Markov system came to be in its present state. The present state alone determines future states, without using any information from past ($x_{i-n}$) states.
A maybe subtler point: the word "memory" is also being used because this also means that you can't infer past states from the present state. Once you are at $x_{i}$, you don't know what happened "before" during $x_{i-n}$. This is the opposite of systems which encode knowledge of past states in the present state.
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
$endgroup$
add a comment |
$begingroup$
You wake up. You have no idea how you got where you are. You look around at your surroundings and make a decision on what to do next based solely on the information you have available at that point in time. That is essentially the same situation as what is happening in MCMC.
It is using the current information that it can currently see to make a decision about what to do next. Instead of thinking of it as figuring out $x_{i}$ from $x_{i-1}$ (which might be what is causing you trouble because you're thinking "hey we're looking into the past when we look at $x_{i-1}$) think of it as figuring out what $x_{i+1}$ should be based on the current information $x_i$ for which you don't need any 'memory'. Those two formulations are equivalent but it might help you think about the semantics a bit better.
answered Feb 4 at 16:05
DasonDason
1,5641416
$endgroup$
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
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: "65"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
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%2fstats.stackexchange.com%2fquestions%2f390712%2fare-mcmc-without-memory%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The defining characteristic of a Markov chain is that the conditional distribution of its present value conditional on past values depends only on the previous value. So every Markov chain is "without memory" to the extent that only the previous value affects the present conditional probability, and all previous states are "forgotten". (You are right that it is not completely without memory - after all, the conditional distribution of the present value depends on the previous value.) That is true for MCMC and also for any other Markov chain.
answered Feb 4 at 13:05
BenBen
24.7k226117
$endgroup$
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
add a comment |
$begingroup$
The defining characteristic of a Markov chain is that the conditional distribution of its present value conditional on past values depends only on the previous value. So every Markov chain is "without memory" to the extent that only the previous value affects the present conditional probability, and all previous states are "forgotten". (You are right that it is not completely without memory - after all, the conditional distribution of the present value depends on the previous value.) That is true for MCMC and also for any other Markov chain.
answered Feb 4 at 13:05
BenBen
24.7k226117
$endgroup$
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
add a comment |
$begingroup$
The defining characteristic of a Markov chain is that the conditional distribution of its present value conditional on past values depends only on the previous value. So every Markov chain is "without memory" to the extent that only the previous value affects the present conditional probability, and all previous states are "forgotten". (You are right that it is not completely without memory - after all, the conditional distribution of the present value depends on the previous value.) That is true for MCMC and also for any other Markov chain.
answered Feb 4 at 13:05
BenBen
24.7k226117
$endgroup$
The defining characteristic of a Markov chain is that the conditional distribution of its present value conditional on past values depends only on the previous value. So every Markov chain is "without memory" to the extent that only the previous value affects the present conditional probability, and all previous states are "forgotten". (You are right that it is not completely without memory - after all, the conditional distribution of the present value depends on the previous value.) That is true for MCMC and also for any other Markov chain.
answered Feb 4 at 13:05
BenBen
24.7k226117
answered Feb 4 at 13:05
BenBen
24.7k226117
answered Feb 4 at 13:05
BenBen
24.7k226117
answered Feb 4 at 13:05
BenBen
24.7k226117
24.7k226117
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
add a comment |
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
9
9
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
If you take this a step forward, you can say the conditional distribution of its future values conditional on past and present values depends only on the present value and in that sense memory of the past is not needed so long as the current position is known
$endgroup$
– Henry
Feb 4 at 19:14
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
$begingroup$
Except you can always adjust the state space to store any finite amount of information about the past. It's still Markovian to, for example, depend on your last ten states, since you can just expand the state space to include that information in "the previous state".
$endgroup$
– David Richerby
Feb 5 at 13:09
add a comment |
$begingroup$
While we have the correct answer, I would like to expand just a little bit on the intuitive semantics of the statement. Imagine that we redefine our indices such that you generate vector $x_{i+1}$ from vector $x_{i}$. Now, moment $i$ is metaphorically seen as "the present", and all vectors coming "earlier than" $x_{i}$ are irrelevant for calculating the next one in the future.
Through this simple renumbering, it becomes "completely without memory" in the intuitive sense - that is, it doesn't matter at all how the Markov system came to be in its present state. The present state alone determines future states, without using any information from past ($x_{i-n}$) states.
A maybe subtler point: the word "memory" is also being used because this also means that you can't infer past states from the present state. Once you are at $x_{i}$, you don't know what happened "before" during $x_{i-n}$. This is the opposite of systems which encode knowledge of past states in the present state.
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
$endgroup$
add a comment |
$begingroup$
While we have the correct answer, I would like to expand just a little bit on the intuitive semantics of the statement. Imagine that we redefine our indices such that you generate vector $x_{i+1}$ from vector $x_{i}$. Now, moment $i$ is metaphorically seen as "the present", and all vectors coming "earlier than" $x_{i}$ are irrelevant for calculating the next one in the future.
Through this simple renumbering, it becomes "completely without memory" in the intuitive sense - that is, it doesn't matter at all how the Markov system came to be in its present state. The present state alone determines future states, without using any information from past ($x_{i-n}$) states.
A maybe subtler point: the word "memory" is also being used because this also means that you can't infer past states from the present state. Once you are at $x_{i}$, you don't know what happened "before" during $x_{i-n}$. This is the opposite of systems which encode knowledge of past states in the present state.
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
$endgroup$
add a comment |
$begingroup$
While we have the correct answer, I would like to expand just a little bit on the intuitive semantics of the statement. Imagine that we redefine our indices such that you generate vector $x_{i+1}$ from vector $x_{i}$. Now, moment $i$ is metaphorically seen as "the present", and all vectors coming "earlier than" $x_{i}$ are irrelevant for calculating the next one in the future.
Through this simple renumbering, it becomes "completely without memory" in the intuitive sense - that is, it doesn't matter at all how the Markov system came to be in its present state. The present state alone determines future states, without using any information from past ($x_{i-n}$) states.
A maybe subtler point: the word "memory" is also being used because this also means that you can't infer past states from the present state. Once you are at $x_{i}$, you don't know what happened "before" during $x_{i-n}$. This is the opposite of systems which encode knowledge of past states in the present state.
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
$endgroup$
While we have the correct answer, I would like to expand just a little bit on the intuitive semantics of the statement. Imagine that we redefine our indices such that you generate vector $x_{i+1}$ from vector $x_{i}$. Now, moment $i$ is metaphorically seen as "the present", and all vectors coming "earlier than" $x_{i}$ are irrelevant for calculating the next one in the future.
Through this simple renumbering, it becomes "completely without memory" in the intuitive sense - that is, it doesn't matter at all how the Markov system came to be in its present state. The present state alone determines future states, without using any information from past ($x_{i-n}$) states.
A maybe subtler point: the word "memory" is also being used because this also means that you can't infer past states from the present state. Once you are at $x_{i}$, you don't know what happened "before" during $x_{i-n}$. This is the opposite of systems which encode knowledge of past states in the present state.
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
edited Feb 5 at 13:26
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
answered Feb 4 at 14:53
rumtschorumtscho
1,070819
1,070819
add a comment |
add a comment |
$begingroup$
You wake up. You have no idea how you got where you are. You look around at your surroundings and make a decision on what to do next based solely on the information you have available at that point in time. That is essentially the same situation as what is happening in MCMC.
It is using the current information that it can currently see to make a decision about what to do next. Instead of thinking of it as figuring out $x_{i}$ from $x_{i-1}$ (which might be what is causing you trouble because you're thinking "hey we're looking into the past when we look at $x_{i-1}$) think of it as figuring out what $x_{i+1}$ should be based on the current information $x_i$ for which you don't need any 'memory'. Those two formulations are equivalent but it might help you think about the semantics a bit better.
answered Feb 4 at 16:05
DasonDason
1,5641416
$endgroup$
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
add a comment |
$begingroup$
You wake up. You have no idea how you got where you are. You look around at your surroundings and make a decision on what to do next based solely on the information you have available at that point in time. That is essentially the same situation as what is happening in MCMC.
It is using the current information that it can currently see to make a decision about what to do next. Instead of thinking of it as figuring out $x_{i}$ from $x_{i-1}$ (which might be what is causing you trouble because you're thinking "hey we're looking into the past when we look at $x_{i-1}$) think of it as figuring out what $x_{i+1}$ should be based on the current information $x_i$ for which you don't need any 'memory'. Those two formulations are equivalent but it might help you think about the semantics a bit better.
answered Feb 4 at 16:05
DasonDason
1,5641416
$endgroup$
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
add a comment |
$begingroup$
You wake up. You have no idea how you got where you are. You look around at your surroundings and make a decision on what to do next based solely on the information you have available at that point in time. That is essentially the same situation as what is happening in MCMC.
It is using the current information that it can currently see to make a decision about what to do next. Instead of thinking of it as figuring out $x_{i}$ from $x_{i-1}$ (which might be what is causing you trouble because you're thinking "hey we're looking into the past when we look at $x_{i-1}$) think of it as figuring out what $x_{i+1}$ should be based on the current information $x_i$ for which you don't need any 'memory'. Those two formulations are equivalent but it might help you think about the semantics a bit better.
answered Feb 4 at 16:05
DasonDason
1,5641416
$endgroup$
You wake up. You have no idea how you got where you are. You look around at your surroundings and make a decision on what to do next based solely on the information you have available at that point in time. That is essentially the same situation as what is happening in MCMC.
It is using the current information that it can currently see to make a decision about what to do next. Instead of thinking of it as figuring out $x_{i}$ from $x_{i-1}$ (which might be what is causing you trouble because you're thinking "hey we're looking into the past when we look at $x_{i-1}$) think of it as figuring out what $x_{i+1}$ should be based on the current information $x_i$ for which you don't need any 'memory'. Those two formulations are equivalent but it might help you think about the semantics a bit better.
answered Feb 4 at 16:05
DasonDason
1,5641416
answered Feb 4 at 16:05
DasonDason
1,5641416
answered Feb 4 at 16:05
DasonDason
1,5641416
answered Feb 4 at 16:05
DasonDason
1,5641416
1,5641416
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
add a comment |
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
2
2
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
Let's call it the Hangover method
$endgroup$
– ThePassenger
Feb 5 at 16:21
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
$begingroup$
@ThePassenger Call it whatever you want. Just please pass the aspirin.
$endgroup$
– Dason
Feb 5 at 17:29
add a comment |
Thanks for contributing an answer to Cross Validated!
- 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%2fstats.stackexchange.com%2fquestions%2f390712%2fare-mcmc-without-memory%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
3
$begingroup$
Because you do not have to "remember" anything about the process except for the last state of the chain. I guess you still need some memory but it is just one piece of information.
$endgroup$
– user2974951
Feb 4 at 12:28
$begingroup$
$x_{i-1}$ isn't "remembered"; it's the explicit input.
$endgroup$
– chepner
Feb 5 at 18:56