17
$\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$.

|cite|improve this question
$\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
28
$\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.

|cite|improve this answer
$\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
15
$\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.

|cite|improve this answer
$\endgroup$
5
$\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.

|cite|improve this answer
$\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.