{"id":1562,"date":"2023-06-29T18:29:59","date_gmt":"2023-06-29T18:29:59","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1562"},"modified":"2023-06-29T18:29:59","modified_gmt":"2023-06-29T18:29:59","slug":"markov-musings-1-the-fundamental-theorem","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/06\/29\/markov-musings-1-the-fundamental-theorem\/","title":{"rendered":"Markov Musings 1: The Fundamental Theorem"},"content":{"rendered":"\n

For this summer, I’ve decided to open up another little mini-series on this blog called Markov Musings<\/strong> about the mathematical analysis of Markov chains, jumping off from my previous post on the subject<\/a>. My main goal in writing this is to learn the material for myself, and I hope that what I produce is useful to others. My main resources are:<\/em><\/p>\n\n\n\n

  1. The book Markov Chains and Mixing Times<\/a><\/strong> by Levin<\/a>, Peres<\/a>, and Wilmer<\/a>;<\/em><\/li>
  2. Lecture notes and videos by theoretical computer scientists Sinclair<\/a>, Oveis Gharan<\/a>, O’Donnell<\/a>, and Schulman; and<\/em><\/li>
  3. These notes<\/a> by Rob Webber<\/a>, for a complementary perspective from a scientific computing point of view.<\/em><\/li><\/ol>\n\n\n\n

    Be warned, these posts will be more mathematical in nature than most of the material on my blog.<\/em><\/p>\n\n\n\n

    \n\n\n\n

    In my previous post on Markov chains<\/a>, we discussed the fundamental theorem of Markov chains. Here is a slightly stronger version:<\/p>\n\n\n\n

    Theorem (fundamental Theorem of Markov chains).<\/strong> A primitive<\/a> Markov chain on a finite state space has a stationary distribution \"\pi > 0\". When initialized from any starting distribution \"\rho^{(0)}\", the distributions \"\rho^{(0)},\rho^{(1)},\rho^{(2)},\ldots\" of the chain at times \"0,1,2,\ldots\" converge at an exponential rate to \"\pi\".<\/p><\/blockquote>\n\n\n\n

    My goal in this post will be to provide a proof of this fact using the method of couplings<\/em>, adapted from the notes of Sinclair<\/a> and Oveis Gharan<\/a>. I like this proof because it feels very probabilistic<\/em> (as opposed to more linear algebraic<\/em> proofs of the fundamental theorem<\/a>).<\/p>\n\n\n\n

    Here, and throughout, we say a matrix or vector is \"> 0\" if all of its entries are strictly positive. Recall that a Markov chain with transition matrix \"P\" is primitive<\/a><\/em> if there exists \"n\" for which \"P^n > 0\". For this post, all Markov chains will have state space \"\{1,\ldots,m\}\".<\/p>\n\n\n\n

    Total Variation Distance<\/a><\/h2>\n\n\n\n

    In order to quantify the rate of Markov chain convergence, we need a way of quantifying the closeness of two probability distributions. This motivates the following definition:<\/p>\n\n\n\n

    Definition (total variation distance).<\/strong> The total variation distance<\/a><\/em> between probability distributions \"\rho\" and \"\sigma\" on \"\{1,\ldots,m\}\" is the maximum difference between the probability of an event \"S\" under \"\rho\" and under \"\sigma\":

      <\/span>   <\/span>\"\[\norm{\rho - \sigma}_{\rm TV} = \max_{S \subseteq \{1,\ldots,m\}} |\rho(S) - \sigma(S)| = \frac{1}{2} \sum_{i=1}^m \left| \rho_i - \sigma_i \right|.\]\"<\/p><\/p><\/blockquote>\n\n\n\n

    The total variation distance is always between \"0\" and \"1\". It is zero only when \"\rho\" and \"\sigma\" are the same distribution. It is one only when \"\rho\" and \"\sigma\" have disjoint supports<\/a>\u2014that is, there is no \"i \in \{1,\ldots,m\}\" for which \"\rho_i, \sigma_i > 0\".<\/p>\n\n\n\n

    The total variation distance is a very strict way of comparing two probability distributions. Sinclair’s notes provide a vivid example. Suppose that \"\rho\" denotes the uniform distribution on all possible ways of shuffling a deck of \"N\" cards, and \"\sigma\" denotes the uniform distribution on all ways of shuffling \"N\" cards with the ace of spades at the top. Then the total variation distance between \"\rho\" and \"\sigma\" is \"1 - 1/N\". Thus, despite these distributions seeming quite similar to us, the total variation distance between \"\rho\" and \"\sigma\" is almost as far apart as possible. There are a number<\/a> of<\/a> alternative<\/a> ways<\/a> of measuring the closeness of probability distributions, some of which are less severe.<\/p>\n\n\n\n

    Couplings<\/a><\/h2>\n\n\n\n

    Given a probability distribution \"\rho\", it can be helpful to work with random variables<\/a><\/em> drawn from \"\rho\". Say a random variable \"x\" is drawn from the distribution \"\rho\", written \"x \sim \rho\", if<\/p>\n\n\n\n

      <\/span>   <\/span>\"\[\prob \{x = i\} = \rho_i \quad \text{for $i=1,2,\ldots,m$}.\]\"<\/p><\/p>\n\n\n\n

    To understand the total variation distance more, we shall need the following definition:<\/p>\n\n\n\n

    Definition (coupling).<\/strong> Given probability distributions \"\rho,\sigma\" on \"\{1,\ldots,m\}\", a coupling<\/a><\/em> \"\gamma\" is a distribution on \"\{1,\ldots,m\}^2\" such that if a pair of random variables \"(x,y)\sim\gamma\" is drawn from \"\gamma\", then \"x \sim \rho\" and \"y \sim \sigma\". Denote the set of all couplings of \"\rho\" and \"\sigma\" as \"\operatorname{Couplings}(\rho,\sigma)\".<\/p><\/blockquote>\n\n\n\n

    More succinctly, a coupling of \"\rho\" and \"\sigma\" is a joint distribution<\/a> with marginals<\/a> \"\rho\" and \"\sigma\".<\/p>\n\n\n\n

    Couplings are related to total variation distance by the following lemma:1<\/a><\/sup>A proof is provided in Lemma 4.2 of Oveis Gharan’s notes<\/a>. The coupling lemma holds in the full generality of probability measures<\/a> on general spaces, and can be viewed as a special case of the Monge\u2013Kantorovich duality principle<\/a> of optimal transport<\/a>. See Theorem 4.13 and Example 4.14 in van Handel’s notes<\/a> for details.<\/span>\n\n\n\n

    Lemma (coupling lemma).<\/strong> Let \"\rho\" and \"\sigma\" be distributions on \"\{1,\ldots,m\}\". Then

      <\/span>   <\/span>\"\[\norm{\rho - \sigma}_{\rm TV} = \min_{\gamma \in \operatorname{Couplings}(\rho,\sigma)} \prob_{(x,y) \sim \gamma} \{ x \ne y \}.\]\"<\/p>Here, \"\prob_{(x,y) \sim \gamma}\" represents the probability for variables \"x,y\" drawn from joint distribution \"\gamma\".<\/p><\/blockquote>\n\n\n\n

    To see a simple example, suppose \"\rho = \sigma\". Then the coupling lemma tells us that there is a coupling \"\gamma\" of \"\rho\" and itself such that \"\prob \{ x \ne y \} = 0\". Indeed, such a coupling can be obtained by drawing \"x \sim \rho\" and setting \"y \coloneqq x\". This defines a joint distribution \"\gamma\" under which \"x = y\" with 100% probability.<\/p>\n\n\n\n

    To unpack the coupling lemma a little more, it really contains two statements:<\/p>\n\n\n\n