{"id":9375,"date":"2017-02-11T22:32:24","date_gmt":"2017-02-11T21:32:24","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=9375"},"modified":"2020-06-22T15:05:17","modified_gmt":"2020-06-22T13:05:17","slug":"back-to-basics-irreducible-markov-kernels","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2017\/02\/11\/back-to-basics-irreducible-markov-kernels\/","title":{"rendered":"Back to basics - Irreducible Markov kernels"},"content":{"rendered":"

\"Markov<\/a><\/p>\n

Let \\( {{(X_n)}_{n\\geq0}} \\) be a Markov chain on an at most countable state space \\( {E} \\), with transition kernel \\( {\\mathbf{P}} \\). For any \\( {x,y\\in E} \\), the number of passages in \\( {y} \\) before returning to \\( {x} \\) is given by<\/p>\n

\\[ \\mu_x(y)=\\mathbb{E}_x\\left(\\sum_{n=0}^{T_x-1}\\mathbf{1}_{X_n=y}\\right) \\quad\\mbox{where}\\quad T_x=\\inf\\{n>0:X_n=x\\}. \\]<\/p>\n

Note that \\( {\\mu_x(x)=1} \\) and \\( {\\mu_x(E)=\\mathbb{E}(T_x)} \\).<\/p>\n

I like very much the following classical theorem about irreducible kernels:<\/p>\n

Irreducible kernels.<\/b> Suppose that \\( {\\mathbf{P}} \\) is irreducible. Then every invariant measure \\( {\\mu} \\) has full support and satisfies \\( {\\mu(y)\\geq\\mu(x)\\mu_x(y)} \\) for any \\( {x} \\) and \\( {y} \\) in \\( {E} \\). Moreover there are three cases:<\/p>\n

    \n
  1. \\( {\\mathbf{P}} \\) is transient. Then \\( {\\mu(E)=\\infty} \\) for every invariant measure \\( {\\mu} \\), \\( {E} \\) is infinite, and there is no invariant probability measure;<\/li>\n
  2. \\( {\\mathbf{P}} \\) is recurrent. Then \\( {\\mu_x} \\) is invariant for every \\( {x\\in E} \\); the invariant measures are all proportional; and if \\( {\\mu} \\) is invariant then \\( {\\mu(y)=\\mu(x)\\mu_x(y)} \\) for any \\( {x,y\\in E} \\). In particular \\( {\\mu_x(y)\\mu_y(x)=1} \\). There are two sub-cases:\n
      \n
    1. \\( {\\mathbf{P}} \\) is positive recurrent. Then there exists a unique invariant probability measure \\( {\\mu} \\) given by \\( {\\mu(x)=1\/\\mathbb{E}_x(T_x)} \\) for every \\( {x\\in E} \\);<\/li>\n
    2. \\( {\\mathbf{P}} \\) is null recurrent. Then \\( {\\mu(E)=\\infty} \\) for every invariant measure \\( {\\mu} \\), \\( {E} \\) is infinite, and there is no invariant probability measure.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

      Here are my three favorite examples with infinite countable state space:<\/p>\n

      Random walk on \\( {\\mathbb{Z}} \\).<\/b> The transition kernel is given by \\( {\\mathbf{P}(x,x+1)=p} \\) and \\( {\\mathbf{P}(x,x-1)=1-p} \\) for every \\( {x\\in\\mathbb{Z}} \\), with \\( {p\\in(0,1)} \\). The kernel is irreducible. A measure \\( {\\mu} \\) on \\( {\\mathbb{Z}} \\) is invariant for \\( {\\mathbf{P}} \\) iff for every \\( {x\\in\\mathbb{Z}} \\),<\/p>\n

      \\[ \\mu(x)=\\sum_{y\\in\\mathbb{Z}}\\mu(y)\\mathbf{P}(y,x)=p\\mu(x-1)+(1-p)\\mu(x+1). \\]<\/p>\n

      This gives that all invariant measures take the form<\/p>\n

      \\[ \\mu(x)=a+b\\left(\\frac{p}{1-p}\\right)^x,\\quad x\\in\\mathbb{Z}, \\]<\/p>\n

      where \\( {a,b\\geq0} \\) are parameters such that \\( {\\mu(0)=a+b>0} \\). We recover the counting measure if \\( {b=0} \\) and a sort of geometric measure when \\( {a=0} \\) which is reversible. If \\( {p=1\/2} \\) then both terms are the same and the counting measure is reversible.<\/p>\n

      The chain never admits an invariant probability measure. If \\( {p=1\/2} \\) then the chain is null recurrent, all invariant measures are proportional. If \\( {p\\neq 1\/2} \\) then the chain is transient, there is a two parameters family of invariant measures.<\/p>\n

      Random walk on \\( {\\mathbb{N}} \\).<\/b> The transition kernel is \\( {\\mathbf{P}(x,x+1)=p} \\) for \\( {x\\in\\{0,1,\\ldots\\}} \\) and \\( {\\mathbf{P}(x,x-1)=1-p} \\) for \\( {x\\in\\{1,2,\\ldots\\}} \\) and \\( {\\mathbf{P}(0,0)=1-p} \\). Here again \\( {p\\in(0,1)} \\). The kernel is irreducible. All invariant measures are geometric, reversible, and take the form<\/p>\n

      \\[ \\mu(x)=\\mu(0)\\left(\\frac{p}{1-p}\\right)^x,\\quad x\\geq0. \\]<\/p>\n

      If \\( {p<1\/2} \\) then the chain is positive recurrent and there is a unique invariant probability measure which is the geometric law on \\( {\\{0,1,\\ldots\\}} \\) with parameter \\( {p\/(1-p)} \\). If \\( {p=1\/2} \\) then the chain is null recurrent and the invariant measures are all proportional to the counting measure. If \\( {p>1\/2} \\) then the chain is transient and all invariant measures are proportional to a geometric blowing measure which cannot be normalized into a probability measure.<\/p>\n

      The continuous time analogue of this chain is known as the M\/M\/1 queue.<\/p>\n

      We could consider instead the reflected random walk on \\( {\\mathbb{N}} \\), by taking \\( {\\mathbf{P}(0,1)=1} \\). This deformation at the origin has a price: the invariant distribution in the case \\( {p<1\/2} \\) is no longer geometric, it is a mixture between a Dirac mass at \\( {0} \\) and the geometric law on \\( {\\{1,2,\\ldots\\}} \\).<\/p>\n

      Growth and collapse walk on \\( {\\mathbb{N}} \\).<\/b> The transition kernel is given by \\( {\\mathbf{P}(x,x+1)=p_x} \\) and \\( {\\mathbf{P}(x,0)=1-p_x} \\), for every \\( {x\\in\\mathbb{N}} \\), where \\( {p_0=1} \\), \\( {p_1,p_2,\\ldots\\in[0,1]} \\). The kernel is irreducible iff<\/p>\n

      \\[ \\{x\\in\\mathbb{N}:p_x>0\\}=\\mathbb{N} \\quad\\text{and}\\quad \\mbox{Card}\\{x\\in\\mathbb{N}:p_x<1\\}=\\infty. \\]<\/p>\n

      The very special growth-collapse nature of \\( {\\mathbf{P}} \\) gives<\/p>\n

      \\[ \\mathbb{P}_0(T_0>n)=\\prod_{x=0}^n\\mathbf{P}(x,x+1)=p_0p_1\\cdots p_n. \\]<\/p>\n

      Also, if the kernel is irreducible, then it is recurrent iff<\/p>\n

      \\[ \\lim_{x\\rightarrow\\infty}p_0p_1\\cdots p_x=0. \\]<\/p>\n

      If \\( {\\mu} \\) is invariant then for any \\( {x\\in\\mathbb{N}} \\) with \\( {x>0} \\),<\/p>\n

      \\[ \\mu(x)=\\sum_{y\\in\\mathbb{N}}\\mu(y)\\mathbf{P}(y,x)=\\mu(x-1)p_{x-1}=\\mu(0)p_0p_1\\cdots p_{x-1}. \\]<\/p>\n

      It follows that if the kernel is irreducible, then it is positive recurrent iff<\/p>\n

      \\[ \\sum_{x=0}^\\infty p_0p_1\\cdots p_x<\\infty, \\]<\/p>\n

      and in this case there exists a unique invariant probability measure given by<\/p>\n

      \\[ \\mu(x)=\\frac{1}{\\mathbb{E}_x(T_x)},\\quad x\\in\\mathbb{N}. \\]<\/p>\n

      Note that if \\( {p=\\prod_{x\\in\\mathbb{N}}p_x\\in(0,\\infty)} \\) and if \\( {\\mu} \\) is invariant then \\( {\\mu(x)\\geq p\\mu(0)} \\), and since \\( {\\mu(0)=\\sum_{x\\in\\mathbb{N}}(1-p_x)\\mu(x)} \\), we get \\( {\\mu(0)\\geq p\\mu(0)\\sum_{x\\in\\mathbb{N}}(1-p_x)} \\), which forces either \\( {\\mu(0)=0} \\) or \\( {\\mu(0)=\\infty} \\), and therefore there is no invariant measure in this case.<\/p>\n

      Further reading.<\/b> Markov chains, by James Norris.<\/p>\n","protected":false},"excerpt":{"rendered":"

      Let \\( {{(X_n)}_{n\\geq0}} \\) be a Markov chain on an at most countable state space \\( {E} \\), with transition kernel \\( {\\mathbf{P}} \\). For…<\/p>\n

      Continue readingBack to basics - Irreducible Markov kernels<\/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":369},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9375"}],"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=9375"}],"version-history":[{"count":26,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9375\/revisions"}],"predecessor-version":[{"id":13813,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/9375\/revisions\/13813"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=9375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=9375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=9375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}