0
$\begingroup$

In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1]$ as our closeness parameter.

Now suppose that we have a Markov Chain M with mixing time T, and suppose that we want to draw 10 independent samples from the stationary distribution of M. What is the correct way to do that?

  1. Do we have to apply the Markov chain for $10\cdot T$ steps, and pick the resulting states at time $T, 2T, ...,10T$ as my samples, or...
  2. is it enough to apply the Markov chain for T+10 steps, and pick the resulting states at time $T+1,T+2,...,T+10$ as my samples?

The justification for the first alternative is that once we have drawn a sample state $s$ at time $T$, then the immediate samples following $s$ will be correlated with $s$ according to the transition matrix of the chain.

On the other hand, maybe it is possible to use some property about Markov chains to show that alternative 2 is enough? For instance, by arguing that the distribution at time T+i is close to uniform with respect to the initial state anyways. This leads to question 3 below...

3) Is there some class of Markov chains for which alternative 2 is enough?

$\endgroup$
  • $\begingroup$ I suspect that 2 is only enough if your chain has mixing time 1, i.e., the state at time $t+1$ is independent of the state at time $t$. In other words, your "chain" is really just a sequence of independent samples from the stationary distribution. $\endgroup$ – David Richerby Feb 6 '18 at 14:09
1
$\begingroup$

One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps.

I don't know whether your first proposal gives the correct distribution in all cases. You can consider the Markov chain $A \leftarrow B \rightarrow C$ with self-loops $A \to A$ and $C \to C$ and more complicated examples in that vein.

Your second proposal doesn't give the correct distribution. The $T$th and $T+1$th state are highly correlated: for instance, they will always be adjacent -- something that wouldn't be true of 10 independent samples from the steady state distribution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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