{"id":1599,"date":"2023-07-13T15:48:59","date_gmt":"2023-07-13T15:48:59","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1599"},"modified":"2023-10-02T22:17:36","modified_gmt":"2023-10-02T22:17:36","slug":"markov-musings-3-spectral-theory","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/07\/13\/markov-musings-3-spectral-theory\/","title":{"rendered":"Markov Musings 3: Spectral Theory"},"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 two<\/a> posts, we proved the fundamental theorem of Markov chains using couplings<\/a><\/em> and discussed the use of couplings to bound the mixing time<\/em>, the time required for the chain to mix to near-stationarity<\/a>.<\/p>\n\n\n\n

In this post, we will continue this discussion by discussing spectral<\/a><\/em> methods for understanding the convergence of Markov chains.<\/p>\n\n\n\n

Mathematical Setting<\/h2>\n\n\n\n

In this post, we will study a reversible<\/a><\/em> Markov chain on \"\{1,\ldots,m\}\" with transition probability matrix \"P \in \real^{m\times m}\" and stationary distribution<\/a> \"\pi\". Our goal will be to use the eigenvalues and eigenvectors of the matrix \"P\" to understand the properties of the Markov chain.<\/p>\n\n\n\n

Throughout our discussion, it will be helpful to treat vectors<\/em> \"f\in\real^m\" and functions<\/em> \"f:\{1,\ldots,m\}\to \real\" as being one and the same, and we will use both \"f_i\" and \"f(i)\" to denote the \"i\"th entry of the vector \"f\" (aka the evaluation of the function \"f\" at \"i\"). By adopting this perspective, a vector is not merely a list of \"m\" numbers, but instead labels each state \"i=1,2,\ldots,m\" with a numeric value.<\/p>\n\n\n\n

Given a function\/vector \"f\", we let \"\expect[f]\" denote the expected value<\/a> of \"f(X)\" where \"X\" is drawn from \"\pi\":

  <\/span>   <\/span>\"\[\expect[f] \coloneqq \expect_{X \sim \pi} [f(X)] = \sum_{i=1}^m \pi_i f(i).\]\"<\/p>The variance<\/a> is defined similarly:

  <\/span>   <\/span>\"\[\Var(f) \coloneqq \expect [(f - \expect[f])^2] = \sum_{i=1}^m (f(i) - \expect[f])^2 \pi_i.\]\"<\/p><\/p>\n\n\n\n

As a final piece of notation, we let \"\delta_i\" denote a probability distribution which assigns 100% probability to outcome \"i\".<\/p>\n\n\n\n

Spectral Theory<\/h2>\n\n\n\n

The eigenvalues and eigenvectors of general square matrices are ill-behaved creatures<\/a>. Indeed, a general \"m\times m\" matrix with real entries can have complex-valued eigenvalues<\/a> and fail to possess<\/a> a full suite of \"m\" linearly independent<\/a> eigenvectors. The situation is dramatically better for symmetric matrices<\/a><\/em> which obey the spectral theorem<\/a><\/em>:<\/p>\n\n\n\n

Theorem (spectral theorem for real symmetric matrices).<\/strong> An \"m\times m\" real symmetric matrix \"A\" (i.e., one satisfying \"A^\top=A\") has \"m\" real eigenvalues \"\lambda_1,\ldots,\lambda_m\" and \"m\" orthonormal<\/a> eigenvectors \"u_1,\ldots,u_m\".<\/p><\/blockquote>\n\n\n\n

Unfortunately for us, the transition matrix \"P\" for a reversible Markov chain is not always symmetric. But despite this, there\u2019s a surprise: \"P\" always has real eigenvalues. This leads us to ask:<\/p>\n\n\n\n

Why does are the eigenvalues of the transition matrix \"P\" real?<\/p><\/blockquote>\n\n\n\n

To answer this question, we will need to develop and a more general version of the spectral theorem and use our standing assumption that the Markov chain is reversible<\/em>.<\/p>\n\n\n\n

The Transpose<\/a><\/h3>\n\n\n\n

In our quest to develop a general version of the spectral theorem, we look more deeply into the hypothesis of the theorem, namely that \"A\" is equal to its transpose \"A^\top\". Let\u2019s first ask: What does the transpose \"A^\top\" mean<\/em>?<\/p>\n\n\n\n

Recall that \"\real^m\" is equipped with the standard inner product<\/a><\/em>, sometimes called the Euclidean or dot product. We denote this product by \"(\cdot,\cdot)\" and it is defined as

  <\/span>   <\/span>\"\[(f,g) \coloneqq f^\top g = \sum_{i=1}^m f(i) g(i).\]\"<\/p>We can think of the standard inner product as defining the amount of the vector \"f\" that points in the direction of \"g\".<\/p>\n\n\n\n

The transpose of a matrix \"A\" is closely related to the standard inner product. Specifically, \"A^\top\" is the (unique) matrix satisfying the adjoint property<\/a><\/em>:

  <\/span>   <\/span>\"\[(f,Ag) = (A^\top f, g)\quad \text{for every }f,g\in\real^m.\]\"<\/p>So the amount of \"f\" in the direction of \"Ag\" is the same as the amount of \"A^\top f\" in the direction of \"g\".<\/p>\n\n\n\n

The Adjoint and the General Spectral Theorem<\/h3>\n\n\n\n

Since the transpose is intimately related to the standard inner product on \"\real^m\", it is natural to wonder if non-standard inner products<\/a><\/em> on \"\real^m\" give rise to non-standard versions of the transpose<\/a><\/em>. This idea proves to be true.<\/p>\n\n\n\n

Definition (adjoint).<\/strong> Let \"[\cdot,\cdot]\" be any inner product on \"\real^m\" and let \"A\" be an \"m\times m\" matrix. The adjoint<\/a><\/em> of \"A\" with respect to the inner product \"[\cdot,\cdot]\" is the (unique) matrix \"A^*\" such that

  <\/span>   <\/span>\"\[[f,Ag]=[A^*f,g]\quad\text{for every }f,g\in\real^m.\]\"<\/p>A matrix \"A\" is self-adjoint<\/a><\/em> if it equals its own adjoint, \"A=A^*\".<\/p><\/blockquote>\n\n\n\n

The spectral theorem naturally extends to the more abstract setting of adjoints with respect to non-standard inner products:<\/p>\n\n\n\n

Theorem (general spectral theorem).<\/strong> Let \"A\" be an \"m\times m\" matrix which is set-adjoint with respect to an inner product \"[\cdot,\cdot]\". Then \"A\" has \"m\" real eigenvalues \"\lambda_1,\ldots,\lambda_m\" and \"m\" eigenvectors \"u_1,\ldots,u_m\" which are \"[\cdot,\cdot]\"–orthonormal<\/a>:

  <\/span>   <\/span>\"\[[u_i,u_j]=\begin{cases}1, & i=j, \\0,& i\ne j.\end{cases}\]\"<\/p><\/p><\/blockquote>\n\n\n\n

Reversibility and Self-Adjointness<\/h3>\n\n\n\n

The general spectral theorem offers us a path to understand our observation from above that the eigenvalues of \"P\" are always real. Namely, we ask:<\/p>\n\n\n\n

Is there an inner product under which \"P\" is self-adjoint?<\/p><\/blockquote>\n\n\n\n

Fortunately, the answer is yes. Define the \"\pi\"-inner product

  <\/span>   <\/span>\"\[\langle f, g \rangle \coloneqq \expect[f\cdot g] = \sum_{i=1}^m f(i)g(i) \pi_i.\]\"<\/p>This inner product is very natural. If \"f\" and \"g\" are mean-zero (\"\expect[f] = \expect[g] = 0\"), it reports the covariance<\/a> of \"f(x)\" and \"g(x)\" where \"x \sim \pi\" is drawn from \"\pi\".<\/p>\n\n\n\n

Let us compute the adjoint of the transition matrix \"P\" in the \"\pi\"-inner product \"\langle \cdot,\cdot \rangle\":

  <\/span>   <\/span>\"\begin{align*}\langle f, Pg \rangle&= \sum_{i=1}^m f(i) \left(\sum_{j=1}^m P_{ij} g(i) \right)\pi_i= \sum_{i,j=1}^m f(i) g(j) \pi_iP_{ij} .\end{align*}\"<\/p>Recall that we have assumed our Markov chain is reversible. Thus, the detailed balance condition

  <\/span>   <\/span>\"\[\pi_i P_{ij} = \pi_j P_{ji} \quad \text{for } i,j=1,2,\ldots,m\]\"<\/p>implies that

  <\/span>   <\/span>\"\[\langle f, Pg \rangle= \sum_{i,j=1}^m f(i) g(j) \pi_jP_{ji} = \sum_{j=1}^m \left( \sum_{i=1}^m f(i) P_{ij} \right) g(j) \pi_j = \langle Pf, g\rangle.\]\"<\/p>Thus, we conclude that \"P\" is self-adjoint.<\/p>\n\n\n\n

We cannot emphasize enough that the reversibility assumption is crucial to ensure that \"P\" is self-adjoint. In fact,<\/p>\n\n\n\n

Theorem (reversibility and self-adjointness).<\/strong> The transition matrix of a general Markov chain with stationary distribution \"\pi\" is self-adjoint in the \"\pi\"-inner product if and only if the chain is reversible.<\/p><\/blockquote>\n\n\n\n

Spectral Theorem for Markov Chains<\/h3>\n\n\n\n

Since \"P\" is self-adjoint in the \"\pi\"-inner product, the general spectral theorem implies the following<\/p>\n\n\n\n

Corollary (spectral theorem for reversible Markov chain).<\/strong> The reversible Markov transition matrix \"P\" has \"m\" real eigenvalues \"\lambda_1 \ge \cdots \ge \lambda_m\" associated with eigenvectors \"\varphi_1,\ldots,\varphi_m\" which are orthonormal in the \"\pi\"-inner product:

  <\/span>   <\/span>\"\[\langle\varphi_i,\varphi_j\rangle=\begin{cases}1, &i=j\\0,& i\ne j.\end{cases}\]\"<\/p><\/p><\/blockquote>\n\n\n\n

Since \"P\" is a reversible Markov transition matrix\u2014not just any self-adjoint matrix\u2014the eigenvalues of \"P\" satisfy additional properties:<\/p>\n\n\n\n