Mixing time of a lifted Markov Chain.

Question

Let $(X_t)$ be a Markov chain and $(Y_t)$ a lifted chain of $(X_t)$, that is, the lifted chain splits each state in several states.
$t_O$ denotes the mixing time of the original chain;
$t_L$ denotes the mixing time of the lifted chain;

How can we related the mixing times of both chains? Intuitively it makes sense that by considering a larger state space, the lifted chain will mix faster, but I don't find a result saying that that is always true.

Is it always the case that $t_L \leq t_O$?

Edit: In fact what is always true is that $$t_O \leq t_L.$$

Answer 1

If you go by the total variation distance from a stationary distribution, as defined for instance on Wikipedia, then the lifted chain will never mix faster.

That's because for every subset $A$ of the state space of $(X_t)$, we have a corresponding subset $B$ of the state space of $(Y_t)$ consisting of all sub-states of every state in $A$. The events $\Pr[X_t \in A]$ and $\Pr[Y_t \in B]$ coincide, and so do the stationary measures $\pi(A)$ and $\pi(B)$, so we have $$|\Pr[X_t \in A] - \pi(A)| < \frac14 \iff |\Pr[Y_t \in B] - \pi(B)| < \frac14.$$ The condition is satisfied for all subsets $A$ at the same time it's satisfied for all "lifted subsets" $B$ of this form.

In particular, at time $t_L$, the second inequality holds for all $B$, in particular for all "lifted subsets" $B$, so the first inequality holds for all $A$; we conclude that $t_O \le t_L$. However, the reverse inequality does not hold: if the first inequality holds for all $A$, we can only conclude the second inequality for sets $B$ of the right form.

For an example where the lifted chain has a much worse mixing time, imagine the following two cases:

• The lifted chain has two copies of the original chain, with no transitions between them. In that case, $(Y_t)$ will never mix, because it can never leave the copy it started in to go to the other copy.
• The lifted chain has two copies of the original chain, with one very rare transition between them in each direction. In that case, $(Y_t)$'s mixing time will be dominated by the time it takes to see that transition sufficiently many times, rather than the mixing time within each copy.