{"id":1610,"date":"2023-08-16T03:49:04","date_gmt":"2023-08-16T03:49:04","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1610"},"modified":"2023-11-24T02:53:52","modified_gmt":"2023-11-24T02:53:52","slug":"markov-musings-4-should-you-be-lazy","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/08\/16\/markov-musings-4-should-you-be-lazy\/","title":{"rendered":"Markov Musings 4: Should You Be Lazy?"},"content":{"rendered":"\n

This post is part of a series, Markov Musings<\/a><\/strong>, about the mathematical analysis of Markov chains. See here for the first post<\/a> in the series.<\/em><\/p>\n\n\n\n

\n\n\n\n

In the previous post<\/a>, we proved the following convergence results for a reversible<\/a> Markov chain<\/a>

  <\/span>   <\/span>\"\[\chi^2\left(\rho^{(n)} \, \middle|\middle| \, \pi\right) \le \left( \max \{ \lambda_2, -\lambda_n \} \right)^{2n} \chi^2\left(\rho^{(0)} \, \middle|\middle| \, \pi\right).\]\"<\/p>Here, \"\rho^{(n)}\" denotes the distribution of the chain at time \"n\", \"\pi\" denotes the stationary distribution<\/a>, \"\chi^2(\cdot \mid\mid \cdot)\" denotes the \"\chi^2\" divergence<\/a>, and \"1 = \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_m \ge -1\" denote the decreasingly ordered eigenvalues<\/a> of the Markov transition matrix \"P\". To bound the rate of convergence to stationarity, we therefore must upper bound<\/em> \"\lambda_2\" and lower bound<\/em> \"\lambda_m\".<\/p>\n\n\n\n

Having to prove separate bounds for two eigenvalues is inconvenient. In the next post, we will develop tools to bound \"\lambda_2\". But what should we do about \"\lambda_m?\" Fortunately, there is a trick.<\/p>\n\n\n\n

It Pays to be Lazy<\/h2>\n\n\n\n

Call a Markov chain lazy<\/em> if, at every step, the chain has at least a 50% chance of staying put. That is, \"P_{ii} \ge 1/2\" for every \"i\".<\/p>\n\n\n\n

Any Markov chain can be made into a lazy chain. At every step of the chain, flip a coin. If the coin is heads, perform a step of the Markov chain as normal, drawing the next step randomly according to the transition matrix \"P\". If the coin comes up tails, do nothing and stay put.<\/p>\n\n\n\n

Algebraically, the lazy chain described in the previous paragraph corresponds to replacing the original transition matrix \"P\" with the lazy transition matrix \"P^{\rm lazy} \coloneqq (I+P)/2\", where \"I\" denotes the identity matrix. It is easy to see that the stationary distribution \"\pi\" for \"P\" is also a stationary distribution for \"P^{\rm lazy}\":

  <\/span>   <\/span>\"\[\pi^\top P^{\rm lazy} = \frac{1}{2} \pi^\top P + \frac{1}{2} \pi^\top I = \frac{1}{2} \pi^\top + \frac{1}{2} \pi^\top = \pi^\top.\]\"<\/p>The eigenvalues of the lazy transition matrix are

  <\/span>   <\/span>\"\[\lambda_i^{\rm lazy} = \frac{1+\lambda_i}{2}.\]\"<\/p>In particular, since all of the original eigenvalues \"\lambda_i\" are \"\ge -1\", all of the eigenvalues of the lazy chain are \"\ge 0\". Thus, the smallest eigenvalue of \"P^{\rm lazy}\" is always \"\ge 0\" and thus, for the lazy chain, the convergence is controlled only by \"\lambda_2^{\rm lazy}\":

  <\/span>   <\/span>\"\[\chi^2\left(\rho^{(n)} \, \middle|\middle| \, \pi\right) \le \left( \lambda_2^{\rm lazy} \right)^{2n} \chi^2\left(\rho^{(0)} \, \middle|\middle| \, \pi\right).\]\"<\/p>Since it can be easier to establish bounds on the second eigenvalue than on both the second and last, it can be convenient\u2014for theoretical purposes especially\u2014to work with lazy chains, using the construction above to enforce laziness if necessary.<\/p>\n\n\n\n

Should You be Lazy?<\/h2>\n\n\n\n

We\u2019ve seen one theoretical<\/em> argument for why it pays to use lazy Markov chains. But should we use lazy Markov chains in practice<\/em>? The answer ultimately depends on how we want to use<\/em> the Markov chain.<\/p>\n\n\n\n

Here are two very different ways we could use a Markov chain:<\/p>\n\n\n\n