{"id":1587,"date":"2023-07-05T18:45:31","date_gmt":"2023-07-05T18:45:31","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1587"},"modified":"2023-07-05T18:45:32","modified_gmt":"2023-07-05T18:45:32","slug":"markov-musings-2-couplings","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/07\/05\/markov-musings-2-couplings\/","title":{"rendered":"Markov Musings 2: Couplings"},"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 last post<\/a>, we saw a proof of the fundamental theorem of Markov chains using the method of couplings<\/a><\/em>. In this post, we will use couplings to provide quantitative bounds on the rate of Markov chain convergence.<\/p>\n\n\n\n

Mixing Time<\/h2>\n\n\n\n

Let us begin where the last post<\/a> ended by recalling some facts about the mixing time<\/em> of a Markov chain. Consider a Markov chain<\/a> \"x_0,x_1,x_2,\ldots\" with stationary distribution<\/a> \"\pi\". Recall that the mixing time is

  <\/span>   <\/span>\"\[\tau_{\rm mix} \coloneqq \min \left\{ n \ge 1 : \max_{\rho^{(0)}} \norm{\rho^{(n)} - \pi}_{\rm TV} \le \frac{1}{2e} \right\}.\]\"<\/p>
Here, \"\rho^{(n)}\" denotes the distribution of the state \"x_n\" of the chain at time \"n\" and \"\norm{\cdot}_{\rm TV}\" is the total variation distance<\/a>. For more on the total variation distance, see the previous post<\/a>.<\/p>\n\n\n\n

At the end of last post<\/a>, we saw the following theorem, showing that the mixing time controls the rate of Markov chain convergence.<\/p>\n\n\n\n

Theorem (mixing time as convergence rate).<\/strong> For any starting distribution \"\rho^{(0)}\",

  <\/span>   <\/span>\"\[\norm{\rho^{(n)} - \pi}_{\rm TV} \le e^{-\lfloor n / \tau_{\rm mix}\rfloor}.\]\"<\/p>Consequently, if \"n\ge \tau_{\rm mix}\cdot \lceil \log(1/\epsilon)\rceil\", then \"\norm{\rho^{(n)} - \pi}_{\rm TV} \le \varepsilon\".<\/p><\/blockquote>\n\n\n\n

This result motivates us to develop techniques to bound the mixing time \"\tau_{\rm mix}\".<\/p>\n\n\n\n

Couplings and Convergence<\/h2>\n\n\n\n

In the previous post, we made essential use of couplings of probability distributions<\/a><\/em>. In this post, we will extend this notion by using couplings of entire Markov chains<\/em>.<\/p>\n\n\n\n

Definition (coupling of Markov chains).<\/strong> A coupling of Markov chains<\/em> with transition matrix<\/a> \"P\" are two processes \"x_0,x_1,x_2,\ldots\" and \"y_0,y_1,y_2,\ldots\" such that (A) each process is individually a Markov chain with transition matrix \"P\": In particular,

  <\/span>   <\/span>\"\[\prob\{x_{n+1} = j \mid x_n = i \} = \prob\{y_{n+1} = j \mid y_n = i \} = P_{ij}\]\"<\/p>and (B) if \"x_n = y_n\", then \"x_{n+1} = y_{n+1}\".<\/p><\/blockquote>\n\n\n\n

A coupling of Markov chains thus consists of a pair of Markov chains which become glued together should they ever touch.<\/p>\n\n\n\n

There are several ways we can use couplings to bound the mixing time of Markov chains. Here is one way. Let \"x_0,x_1,x_2,\ldots\" and \"y_0,y_1,y_2,\ldots\" be a coupling of Markov chains for which \"x_0\" is initialized in some initial distribution \"x_0 \sim \rho^{(0)}\" and \"y_0\" is initialized in the stationary distribution \"y_0 \sim \pi\". Let \"\tau_{\rho^{(0)}}\" be the time at which \"x\" and \"y\" meet:

  <\/span>   <\/span>\"\[\tau_{\rho^{(0)}} \coloneqq \min\{ n \ge 0 : x_n = y_n\}.\]\"<\/p>The following theorem shows that the tails of the random variable \"\tau\" control the convergence of the Markov chain \"x_0,x_1,x_2,\ldots\" to stationarity.<\/p>\n\n\n\n

Theorem (convergence from couplings).<\/strong> Then \"\norm{\rho^{(n)} - \pi}_{\rm TV} \le \prob\{\tau_{\rho^{(0)}} > n\}\".<\/p><\/blockquote>\n\n\n\n

This result is an immediate application of the coupling lemma from last post<\/a>. Using this bound, we can bound the mixing time<\/p>\n\n\n\n

Corollary (mixing time from couplings).<\/strong> \"\tau_{\rm mix} \le 2e \max_{\rho^{(0)}} \expect[\tau_{\rho^{(0)}}]\".<\/p><\/blockquote>\n\n\n\n

The maximum is taken over all initial distributions \"\rho^{(0)}\".<\/p>\n\n\n\n

Indeed, by the above theorem and Markov’s inequality<\/a>,1<\/a><\/sup>For more on concentration inequalities such as Markov’s inequality, see my post on the subject<\/a>.<\/span>

  <\/span>   <\/span>\"\[\norm{\rho^{(n)} - \pi}_{\rm TV} \le \prob\{\tau_{\rho^{(0)}} > n\}\le \frac{\expect[\tau_{\rho^{(0)}}]}{n}.\]\"<\/p>Take a maximum over initial distribution \"\rho^{(0)}\" and set \"n \coloneqq \tau_{\rm mix}\". Then the left-hand side is at most \"1/2e\", so

  <\/span>   <\/span>\"\[\frac{1}{2e} \le \max_{\rho^{(0)}}\norm{\rho^{(\tau_{\rm mix})} - \pi}_{\rm TV} = \prob\{\tau_{\rho^{(0)}} > n\} \le \frac{\max_{\rho^{(0)}}\expect[\tau_{\rho^{(0)}}]}{\tau_{\rm mix}}.\]\"<\/p>Rearranging gives the corollary.<\/p>\n\n\n\n

Example: Bit Strings<\/a><\/h2>\n\n\n\n

There are a number of examples2<\/a><\/sup>See, for instance, section 5.3 of Markov Chains and Mixing Times<\/a><\/em>.<\/span> to prove bounds on mixing times using the method of couplings, but we will focus on a simple but illustrative example: a lazy random walk on the set of bit strings<\/a><\/em>.<\/p>\n\n\n\n

A bit string<\/em> is a sequence of 0’s and 1’s. Bit strings are used to store and represent information on digital computers. For instance, the character “a” is stored as “1100001” using the ASCII encoding<\/a>.<\/p>\n\n\n\n

The Chain<\/h3>\n\n\n\n

Our example is a Markov chain whose states consist of all bit strings of length \"N\". For each step of the chain,<\/p>\n\n\n\n