  Lifted Markov chains are Markov chains on graphs with added local "memory"
and can be used to mix towards a target distribution faster than their
memoryless counterparts. Upper and lower bounds on the achievable performance
have been provided under specific assumptions. In this paper, we analyze which
assumptions and constraints are relevant for mixing, and how changing these
assumptions affects those bounds. Explicitly, we find that requesting mixing on
either the original or the full lifted graph, and allowing for reducible lifted
chains or not, have no essential influence on mixing time bounds. On the other
hand, allowing for suitable initialization of the lifted dynamics and/or
imposing invariance of the target distribution for any initialization do
significantly affect the convergence performance. The achievable convergence
speed for a lifted chain goes from diameter-time to no acceleration over a
standard Markov chain, with conductance bounds limiting the effectiveness of
the intermediate cases. In addition, we show that the relevance of imposing
ergodic flows depends on the other criteria. The presented analysis allows us
to clarify in which scenarios designing lifted dynamics can lead to better
mixing, and provide a flexible framework to compare lifted walks with other
acceleration methods.
