{"id":36,"date":"2010-05-09T11:05:16","date_gmt":"2010-05-09T09:05:16","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=36"},"modified":"2019-10-16T09:29:46","modified_gmt":"2019-10-16T07:29:46","slug":"spectrum-of-a-markov-matrix","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2010\/05\/09\/spectrum-of-a-markov-matrix\/","title":{"rendered":"Spectrum of a Markov matrix"},"content":{"rendered":"

Let $M$ be an $n\\times n$ Markov matrix (e.g. a stochastic matrix). This means that $M$ has entries in $[0,1]$ and each row sums up to $1$. Let $\\lambda_1,\\ldots,\\lambda_n$ be the roots in $\\mathbb{C}$ of its characteristic polynomial. Let us order them in such a way that $|\\lambda_1|\\geq\\cdots\\geq|\\lambda_n|$ with growing phases. It is not difficult to show that $\\{\\lambda_1,\\ldots,\\lambda_n\\}\\subset\\{z\\in\\mathbb{C}:|z|\\leq1\\}$, that $\\lambda_1=1$, and that the spectrum of $M$ is symmetric with respect to the real axis. A good reference for the spectrum of Markov matrices is the book of Seneta<\/a>.<\/p>\n

Suppose from now on that $M$ is irreducible. Then the eigenspace associated to $\\lambda_1$ has dimension $1$ and $M$ admits a unique invariant probability measure $\\mu$. One can show that the spectrum of $M$ is invariant by the rotation of angle $2\\pi\/d$ where $d\\in\\{1,2,\\ldots\\}$ is called the period of $M$. In particular, there are exactly $d$ eigenvalues of unit module, and if $M$ is reversible, then its spectrum is real and $-1$ belongs to the spectrum if and only if $d=2$.<\/p>\n

From now on, we suppose additionally that $M$ is aperiodic: $d=1$. Then $|\\lambda_2|<1$. In this case, the spectral gap $1-|\\lambda_2|$\u00a0 describes the worst exponential decay to the equilibrium $\\mu$ in $\\ell^2(\\mu)$ for a Markov chain of kernel $M$. This corresponds to the control of the decay of the powers of $M-I$ by using its spectral radius.<\/p>\n

Beyond the spectral gap, one may ask about some dynamical interpretation of the remaining eigenvalues. If $M$ is reversible, then\u00a0 $M$ is self-adjoint in $\\ell^2(\\mu)$ and $1-|\\lambda_k|$ for $\\lambda_k\\not\\in\\{0,1\\}$ describes the worst exponential decay to the equilibrium $\\mu$ in $\\ell^2(\\mu)$ when the initial law of the chain is orthogonal to the eigenspaces of $M^\\top$ associated to the eigenvalues of higher module. One may also think about the Chen and Saloff-Coste criterion<\/a> for the $\\ell^2$ cuttoff of reversible Markov chains. Beyond reversibility, this simple interpretation is still valid if $M$ is normal, i.e. if $MM^*=M^*M$ where $M^*$ is the adjoint of $M$ in $\\ell^2(\\mu)$.<\/p>\n

The empirical spectral distribution of $M$ is the discrete probability measure<\/p>\n

$\\displaystyle\\nu:=\\frac{1}{n}\\delta_{\\lambda_1}+\\cdots+\\frac{1}{n}\\delta_{\\lambda_n}.$<\/p>\n

For every $k\\in\\{0,1,2,\\ldots\\}$, we have the global spectral identity<\/p>\n

$\\displaystyle \\int\\!z^k\\,d\\nu(z)=\\frac{1}{n}\\sum_{i=1}^n\\lambda_i^k=\\frac{1}{n}\\mathrm{Tr}(M^k)=\\frac{1}{n}\\sum_{i=1}^nM^k_{i,i}=\\frac{1}{n}\\sum_{i=1}^np(i,k)$<\/p>\n

where $p(i,k):=M^k_{i,i}$ is the probability of a loop of lenght $k$ rooted at $i$ for a Markov chain of kernel $M$. This gives a global interpretation of the spectrum: the moments of the empirical spectral distribution of $M$ correspond to the mean loops probabilities for the chain.<\/p>\n

Let $f:\\{1,\\ldots,n\\}\\to\\mathbb{R}$ be some observable and $(X_n)_{n\\geq1}$ be a Markov chain on $\\{1,\\ldots,n\\}$ with kernel $M$. The ergodic theorem (strong law of large numbers for additive functionals) states that regardless of the initial law of the chain, we have<\/p>\n

$\\displaystyle \\frac{f(X_0)+\\cdots+f(X_{n-1})}{n}\\overset{\\text{a.s.}}{\\underset{n\\to\\infty}{\\longrightarrow}}\\mu(f):=\\int\\!f\\,d\\mu=\\sum_{k=1}^nf(k)\\mu(k).$<\/p>\n

Let $g:\\{1,\\ldots,n\\}\\to\\mathbb{R}$ be such that $(M-I)g=f-\\mu(f)$. Note that $L:=M-I$ is the generator of $M$ and $g$ solves the Poisson equation. Then the central limit theorem states that<\/p>\n

$\\displaystyle \\sqrt{n}\\left(\\frac{f(X_0)+\\cdots+f(X_{n-1})}{n}-\\mu(f)\\right)\\overset{\\text{law}}{\\underset{n\\to\\infty}{\\longrightarrow}}\\mathcal{N}(0,\\sigma(f)^2)$<\/p>\n

where $\\sigma(f)^2:=\\mu(g^2)-\\mu(g)^2$. Thus, if $M$ is reversible then<\/p>\n

$\\displaystyle\\sigma(f)^2\\leq \\frac{\\mu(f^2)-\\mu(f)^2}{\\mathrm{dist}(1,\\{\\lambda_2,\\ldots,\\lambda_n\\})^2}.$<\/p>\n

Note that when $M$ and $\\mu$ are not known, one may estimate $\\sigma(f)^2$ empirically. See e.g. the work of Trevezas and Limnios<\/a> and references therein.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Let $M$ be an $n\\times n$ Markov matrix (e.g. a stochastic matrix). This means that $M$ has entries in $[0,1]$ and each row sums up…<\/p>\n

Continue readingSpectrum of a Markov matrix<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":577},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/36"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=36"}],"version-history":[{"count":3,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/36\/revisions"}],"predecessor-version":[{"id":11643,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/36\/revisions\/11643"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=36"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=36"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}