uc_mc_semigroups.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dd5b5293",
   "metadata": {},
   "source": [
    "# UC Markov Semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b88521ba",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "In our previous lecture we covered some of the general theory of operator\n",
    "semigroups.\n",
    "\n",
    "Next we translate these results into the setting of Markov semigroups.\n",
    "\n",
    "The Markov semigroups are defined on a countable set $ S $.\n",
    "\n",
    "The main aim is to give an exact one-to-one correspondence between\n",
    "\n",
    "- UC Markov semigroups  \n",
    "- “conservative” intensity matrices and  \n",
    "- jump chains with state dependent jump intensities  \n",
    "\n",
    "\n",
    "Conservativeness is defined below and relates to “nonexplosiveness” of the\n",
    "associated Markov chain.\n",
    "\n",
    "We will also give a brief discussion of intensity matrices that do not have\n",
    "this property, along with the processes they generate."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e24f61d2",
   "metadata": {},
   "source": [
    "## Notation and Terminology\n",
    "\n",
    "Let $ S $ be an arbitrary countable set.\n",
    "\n",
    "Let $ \\ell_1 $ be the Banach space of **summable functions** on $ S $; that is, all $ g \\, \\colon S \\to \\RR $ with\n",
    "\n",
    "$$\n",
    "\\| g \\| := \\sum_x |g(x)| < \\infty\n",
    "$$\n",
    "\n",
    "Note that $ \\dD $, the set of all distributions on $ S $, is contained in $ \\ell_1 $.\n",
    "\n",
    "Each Markov matrix $ P $ on $ S $ can and will be identifed with a linear operator\n",
    "$ f \\mapsto fP $ on $ \\ell_1 $ via\n",
    "\n",
    "\n",
    "<a id='equation-mmismo'></a>\n",
    "$$\n",
    "(fP)(y) = \\sum_x f(x) P(x, y)\n",
    "    \\qquad (f \\in \\ell_1, \\; y \\in S) \\tag{7.1}\n",
    "$$\n",
    "\n",
    "To be consistent with earlier notation, we are writing the argument of $ P $ to\n",
    "the left and applying $ P $ to it as if premultiplying $ P $ by a row vector.\n",
    "\n",
    "In the exercises you are asked to verify that [(7.1)](#equation-mmismo) defines\n",
    "a bounded linear operator on $ \\ell_1 $ such that\n",
    "\n",
    "\n",
    "<a id='equation-propp'></a>\n",
    "$$\n",
    "\\|P\\| = 1 \\text{ and } \\phi P \\in \\dD \\text{ whenever } \\phi \\in \\dD \\tag{7.2}\n",
    "$$\n",
    "\n",
    "Note that composition of $ P $ with itself is equivalent to powers of the matrix\n",
    "under matrix multiplication.\n",
    "\n",
    "For an intensity matrix $ Q $ on $ S $ we can try to introduce the associated\n",
    "operator analogously, via\n",
    "\n",
    "\n",
    "<a id='equation-imislo'></a>\n",
    "$$\n",
    "(fQ)(y) = \\sum_x f(x) Q(x, y)\n",
    "    \\qquad (f \\in \\ell_1, \\; y \\in S) \\tag{7.3}\n",
    "$$\n",
    "\n",
    "However, the sum in [(7.3)](#equation-imislo) is not always well defined.<sup>[1](#fnim)</sup>\n",
    "\n",
    "We say that an intensity matrix $ Q $ is **conservative** if the sum in\n",
    "[(7.3)](#equation-imislo) is well defined at all $ y $ and, in addition, the mapping $ f\n",
    "\\mapsto fQ $ in [(7.3)](#equation-imislo) is a bounded linear operator on $ \\ell_1 $.\n",
    "\n",
    "Below we show how this property can be checked in applications."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82af4043",
   "metadata": {},
   "source": [
    "## UC Markov Semigroups and their Generators\n",
    "\n",
    "Let $ Q $ be a conservative intensity matrix on $ S $.\n",
    "\n",
    "Since $ Q $ is in $ \\linopell $, the operator exponential $ e^{tQ} $ is well defined\n",
    "as an element of $ \\linopell $ for all $ t \\geq 0 $.\n",
    "\n",
    "Moreover, by [Example 6.3](generators.ipynb#ecuc), the family $ (P_t) $ in $ \\lL(\\ell_1) $ defined by\n",
    "$ P_t = e^{tQ} $ defines a UC Markov semigroup on $ \\ell_1 $.\n",
    "\n",
    "(Here, a Markov semigroup $ (P_t) $ is both a collection of Markov matrices and a\n",
    "collection of operators, as in [(7.1)](#equation-mmismo).)\n",
    "\n",
    "The next theorem says that this is the only way UC Markov semigroups can arise."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42ae89da",
   "metadata": {},
   "source": [
    "## \n",
    "\n",
    "If $ (P_t) $ is a UC Markov semigroup on $ \\ell_1 $, then there\n",
    "exists a conservative intensity matrix $ Q $ such that $ P_t = e^{tQ} $ for all $ t \\geq 0 $.\n",
    "\n",
    "Proof. Let $ (P_t) $ be a UC Markov semigroup on $ \\ell_1 $.\n",
    "\n",
    "Since $ (P_t) $ is a UC semigroup on $ \\ell_1 $, it follows from\n",
    "[Theorem 6.1](generators.ipynb#ucsgec) that there exists a $ Q \\in \\lL(\\ell_1) $ such that\n",
    "$ P_t = e^{tQ} $ for all $ t \\geq 0 $.\n",
    "\n",
    "We only need to show that $ Q $ is a conservative intensity matrix.\n",
    "\n",
    "Because $ (P_t) $ is a Markov semigroup, $ P_t $ is a Markov matrix for all $ t $,\n",
    "and, since $ P_t = e^{tQ} $ for all $ t $, it follows that $ Q $ is an intensity\n",
    "matrix.\n",
    "\n",
    "We proved this for the case $ |S| < \\infty $ in [Theorem 5.1](kolmogorov_fwd.ipynb#intvsmk) and\n",
    "one can verify that the same arguments go through when $ |S| = \\infty $.\n",
    "\n",
    "As $ Q \\in \\lL(\\ell_1) $, we know that $ Q $ is a bounded operator, so $ Q $ is a\n",
    "conservative intensity matrix.\n",
    "\n",
    "From [Theorem 7.1](#usmg) we can easily deduce that\n",
    "\n",
    "- $ P_t $ is differentiable at every $ t \\geq 0 $,  \n",
    "- $ Q $ is the generator of $ (P_t) $ and  \n",
    "- $ P_t' = Q P_t = P_t Q $ for all $ t \\geq 0 $.  \n",
    "- $ P_0' = Q $  \n",
    "\n",
    "\n",
    "In fact these results are just a special case of the claims in [Theorem 6.1](generators.ipynb#ucsgec).\n",
    "\n",
    "The second last of these results is the Kolmogorov forward and backward equations.\n",
    "\n",
    "The last of these results shows that we can obtain the intensity matrix $ Q $ by differentiating $ P_t $ at $ t=0 $."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14dfa8d1",
   "metadata": {},
   "source": [
    "## \n",
    "\n",
    "Let us consider again the Poisson process $ (N_t) $ with rate $ \\lambda > 0 $\n",
    "in light of the discussion above.\n",
    "\n",
    "The corresponding semigroup $ (P_t) $ is UC and hence there exists a\n",
    "conservative intensity matrix $ Q $ with $ P_t = e^{tQ} $ for all $ t \\geq 0 $.\n",
    "\n",
    "This fact can be established by proving UC property and then appealing to\n",
    "[Theorem 7.1](#usmg).\n",
    "\n",
    "Another alternative, easier in this case, is to supply the intensity matrix\n",
    "$ Q $ directly and then verify that $ P_t = e^{tQ} $ holds.\n",
    "\n",
    "The semigroup for a Poisson process with rate $ \\lambda $ was given in\n",
    "[(3.9)](markov_prop.ipynb#equation-poissemi) and is repeated here:\n",
    "\n",
    "\n",
    "<a id='equation-poissemi2'></a>\n",
    "$$\n",
    "P_t(j, k) \n",
    "    = \n",
    "    \\begin{cases}\n",
    "    e^{-\\lambda t} \\frac{ (\\lambda t)^{k-j} }{(k-j)!}  \n",
    "        & \\text{ if } j \\leq k\n",
    "        \\\\\n",
    "    0 & \\text{ otherwise}\n",
    "    \\end{cases} \\tag{7.4}\n",
    "$$\n",
    "\n",
    "For the intensity matrix we take\n",
    "\n",
    "\n",
    "<a id='equation-poissonq'></a>\n",
    "$$\n",
    "Q := \n",
    "    \\begin{pmatrix}\n",
    "    -\\lambda & \\lambda & 0 & 0 & 0 & \\cdots\n",
    "    \\\\\n",
    "    0 & -\\lambda & \\lambda & 0 & 0 & \\cdots\n",
    "    \\\\\n",
    "    0 & 0 & -\\lambda & \\lambda & 0 & \\cdots\n",
    "    \\\\\n",
    "    0 & 0 & 0 & -\\lambda & \\lambda & \\cdots\n",
    "    \\\\\n",
    "    \\vdots & \\vdots  & \\vdots  & \\vdots  & \\vdots \n",
    "    \\end{pmatrix} \\tag{7.5}\n",
    "$$\n",
    "\n",
    "The form of $ Q $ is intuitive: probability flows out of state $ i $ and into\n",
    "state $ i+1 $ at the rate $ \\lambda $.\n",
    "\n",
    "It is immediate that $ Q $ is an intensity matrix, as claimed.\n",
    "\n",
    "The exercises ask you to confirm that $ Q $ is in $ \\lL(\\ell_1) $.\n",
    "\n",
    "To prove that $ P_t = e^{tQ} $ for any $ t \\geq 0 $, we first decompose $ Q $ as $ Q\n",
    "= \\lambda (K - I) $, where $ K $ is defined by\n",
    "\n",
    "$$\n",
    "K(i, j) = \\mathbb 1\\{j = i + 1\\}\n",
    "$$\n",
    "\n",
    "For given $ t \\geq 0 $, we then have\n",
    "\n",
    "$$\n",
    "e^{tQ}\n",
    "    = e^{\\lambda t (K-I)}\n",
    "    = e^{-\\lambda t} e^{\\lambda t K}\n",
    "    = e^{-\\lambda t} \n",
    "    \\sum_{m \\geq 0} \\frac{(\\lambda t K)^m}{m!}\n",
    "$$\n",
    "\n",
    "The exercises ask you to verify that, for the powers of $ K $, we have $ K^m(i,\n",
    "j) = \\mathbb 1\\{j = i + m\\} $.\n",
    "\n",
    "Inserting this expression for $ K^m $ leads to\n",
    "\n",
    "$$\n",
    "e^{tQ}(i, j)\n",
    "    = e^{-\\lambda t} \n",
    "    \\sum_{m \\geq 0} \\frac{(\\lambda t )^m}{m!} \\mathbb 1\\{j = i + m\\}\n",
    "    = e^{-\\lambda t} \n",
    "    \\sum_{m \\geq 0} \\frac{(\\lambda t )^m}{m!} \\mathbb 1\\{m = j-i\\}\n",
    "$$\n",
    "\n",
    "This is identical to [(7.4)](#equation-poissemi2).\n",
    "\n",
    "It now follows that $ t \\mapsto P_t \\in \\lL(\\ell_1) $ is differentiable at every\n",
    "$ t \\geq 0 $ and $ Q $ is the generator of $ (P_t) $, with $ P_0' = Q $."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c707d296",
   "metadata": {},
   "source": [
    "### A Necessary and Sufficient Condition\n",
    "\n",
    "Our definition of a conservative intensity matrix works for the theory above\n",
    "but can be hard to check in appliations and lacks probabilistic intuition.\n",
    "\n",
    "Fortunately, we have the following simple characterization."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cfc6baad",
   "metadata": {},
   "source": [
    "### \n",
    "\n",
    "An intensity matrix $ Q $ on $ S $ is conservative if and only if $ \\sup_x |Q(x,\n",
    "x)| $ is finite.\n",
    "\n",
    "The proof is a solved exercise."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9928215a",
   "metadata": {},
   "source": [
    "### \n",
    "\n",
    "Recall the jump chain setting where, repeating [(4.4)](kolmogorov_bwd.ipynb#equation-kolbackeq), we defined $ Q $\n",
    "via\n",
    "\n",
    "\n",
    "<a id='equation-kolbackeq-inf'></a>\n",
    "$$\n",
    "Q(x, y) := \\lambda(x) (K(x, y) - I(x, y)) \\tag{7.6}\n",
    "$$\n",
    "\n",
    "The function $ \\lambda \\colon S \\to \\RR_+ $ gives the jump rate at each state,\n",
    "while $ K $ is the Markov matrix for the embedded discrete time jump chain.\n",
    "\n",
    "Previously we discussed this in the case where $ S $ is finite but there is no\n",
    "need to restrict attention to that case.\n",
    "\n",
    "For general countable $ S $, the matrix $ Q $ defined in [(7.6)](#equation-kolbackeq-inf) is\n",
    "still an intensity matrix.\n",
    "\n",
    "If we continue to assume that $ K(x,x) = 0 $ for all $ x $, then $ Q(x,x) = -\n",
    "\\lambda(x) $.\n",
    "\n",
    "Hence, $ Q $ is conservative if and only if $ \\sup_x \\lambda(x) $ is finite.\n",
    "\n",
    "In other words, $ Q $ is conservative if the set of jump rates is bounded.\n",
    "\n",
    "This example shows that requiring $ Q $ to be conservative is a relatively mild\n",
    "restriction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18a42fe0",
   "metadata": {},
   "source": [
    "### The Finite State Case\n",
    "\n",
    "It is immediate from [Lemma 7.1](#scintcon) that every intensity matrix is\n",
    "conservative when the state space $ S $ is finite.\n",
    "\n",
    "Hence, in this setting, every intensity matrix $ Q $ on $ S $ defines a UC Markov\n",
    "semigroup $ (P_t) $ via $ P_t = e^{tQ} $.\n",
    "\n",
    "Conversely, if $ S $ is finite, then any Markov semigroup $ (P_t) $ is a UC Markov\n",
    "semigroup.\n",
    "\n",
    "To see this, recall that, as a Markov semigroup, $ (P_t) $ satisfies\n",
    "$ \\lim_{t \\to 0} P_t(x, y) = I(x,y) $ for all $ x,y $ in $ S $.\n",
    "\n",
    "In any finite dimensional space, pointwise convergence implies norm\n",
    "convergence, so $ P_t \\to I $ in operator norm as $ t \\to 0 $ from above.\n",
    "\n",
    "As we saw previously, this is enough to ensure that $ t \\mapsto P_t $ is norm\n",
    "continuous everywhere on $ \\RR_+ $.\n",
    "\n",
    "Hence $ (P_t) $ is a UC Markov semigroup, as claimed.\n",
    "\n",
    "Combining these results with [Theorem 7.1](#usmg), we conclude that, when $ S $ is\n",
    "finite, there is a one-to-one correspondence between Markov semigroups and\n",
    "intensity matrices."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb7382f5",
   "metadata": {},
   "source": [
    "## From Intensity Matrix to Jump Chain\n",
    "\n",
    "We now understand that there is a one-to-one pairing between conservative\n",
    "intensity matrices and UC Markov semigroups.\n",
    "\n",
    "These ideas are important from an analytical perspective.\n",
    "\n",
    "Now we provide another point of view, more connected to probability.\n",
    "\n",
    "This point of view is important for both theory and computation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b09910a",
   "metadata": {},
   "source": [
    "### Jump Chain Pairs\n",
    "\n",
    "Let us agree to call $ (\\lambda, K) $ a **jump chain pair** if $ \\lambda $ is a\n",
    "map from $ S $ to $ \\RR_+ $ and $ K $ is a Markov matrix on $ S $.\n",
    "\n",
    "It is easy to verify that the matrix $ Q $ on $ S $ defined by\n",
    "\n",
    "\n",
    "<a id='equation-jcinmat'></a>\n",
    "$$\n",
    "Q(x, y) := \\lambda(x) (K(x, y) - I(x, y)) \\tag{7.7}\n",
    "$$\n",
    "\n",
    "is an intensity matrix.\n",
    "\n",
    "(We saw in [an earlier lecture](kolmogorov_bwd.ipynb) that $ Q $ is the intensity\n",
    "matrix for the jump chain $ (X_t) $ built via [Algorithm 4.1](kolmogorov_bwd.ipynb#ejc_algo) from jump\n",
    "chain pair $ (\\lambda, K) $.)\n",
    "\n",
    "As we now show, every intensity matrix admits the decomposition in\n",
    "[(7.7)](#equation-jcinmat) for some jump chain pair."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78ed578a",
   "metadata": {},
   "source": [
    "### Jump Chain Decomposition\n",
    "\n",
    "Given an intensity matrix $ Q $, set\n",
    "\n",
    "\n",
    "<a id='equation-lambdafromq'></a>\n",
    "$$\n",
    "\\lambda(x) := -Q(x, x)\n",
    "    \\qquad (x \\in S) \\tag{7.8}\n",
    "$$\n",
    "\n",
    "Next we build $ K $, first along the principle diagonal via\n",
    "\n",
    "\n",
    "<a id='equation-kfromqxx'></a>\n",
    "$$\n",
    "K(x,x) = \n",
    "    \\begin{cases}\n",
    "        0 & \\text{ if } \\lambda(x) > 0\n",
    "        \\\\\n",
    "        1 & \\text{ otherwise}\n",
    "    \\end{cases} \\tag{7.9}\n",
    "$$\n",
    "\n",
    "Thus, if the rate of leaving $ x $ is positive, we set $ K(x,x) = 0 $, so that the\n",
    "embedded jump chain moves away from $ x $ with probability one when the next\n",
    "jump occurs.\n",
    "\n",
    "Otherwise, when $ Q(x,x) = 0 $, we stay at $ x $ forever, so $ x $ is an **absorbing\n",
    "state**.\n",
    "\n",
    "Off the principle diagonal, where $ x \\not= y $, we set\n",
    "\n",
    "\n",
    "<a id='equation-kfromqxy'></a>\n",
    "$$\n",
    "K(x,y) = \n",
    "    \\begin{cases}\n",
    "        \\frac{Q(x,y)}{\\lambda(x)} & \\text{ if } \\lambda(x) > 0\n",
    "        \\\\\n",
    "        0 & \\text{ otherwise }\n",
    "    \\end{cases} \\tag{7.10}\n",
    "$$\n",
    "\n",
    "The exercises below ask you to confirm that, for $ \\lambda $ and $ K $ just defined,\n",
    "\n",
    "1. $ (\\lambda, K) $ is a jump chain pair and  \n",
    "1. the intensity matrix $ Q $ satisfies [(7.7)](#equation-jcinmat).  \n",
    "\n",
    "\n",
    "We call $ (\\lambda, K) $ the **jump chain decomposition** of $ Q $.\n",
    "\n",
    "We summarize in a lemma."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54fc2f5b",
   "metadata": {},
   "source": [
    "### \n",
    "\n",
    "A matrix $ Q $ on $ S $ is an intensity matrix if and only if there exists a jump\n",
    "chain pair $ (\\lambda, K) $ such that [(7.7)](#equation-jcinmat) holds."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e7cb37b",
   "metadata": {},
   "source": [
    "### The Conservative Case\n",
    "\n",
    "We know from [Example 7.2](#jccs) that an intensity matrix $ Q $ is conservative\n",
    "if and only if $ \\lambda $ is bounded.\n",
    "\n",
    "Moreover, we saw in [Theorem 7.1](#usmg) that the pairing between conservative\n",
    "intensity matrices and UC Markov semigroups is one-to-one.\n",
    "\n",
    "This leads to the following result."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a96a60c6",
   "metadata": {},
   "source": [
    "### \n",
    "\n",
    "On $ S $, there exists a one-to-one correspondence between the following sets of\n",
    "objects:\n",
    "\n",
    "1. The set of all jump chain pairs $ (\\lambda, K) $ such that $ \\lambda $ is bounded.  \n",
    "1. The set of all conservative intensity matrices.  \n",
    "1. The set of all UC Markov semigroups.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88a5091d",
   "metadata": {},
   "source": [
    "### Simulation\n",
    "\n",
    "In view of the preceding discussion, we have a simple way to simulate a Markov\n",
    "chain given any conservative intensity matrix $ Q $.\n",
    "\n",
    "The steps are\n",
    "\n",
    "1. Decompose $ Q $ into a jump chain pair $ (\\lambda, K) $.  \n",
    "1. Simulate via [Algorithm 4.1](kolmogorov_bwd.ipynb#ejc_algo).  \n",
    "\n",
    "\n",
    "Recalling our discussion of the Kolmogorov backward equation, we know that\n",
    "this produces a Markov chain with Markov semigroup\n",
    "$ (P_t) $ where $ P_t = e^{tQ} $ for $ Q $ satisfying [(7.7)](#equation-jcinmat).\n",
    "\n",
    "(Although our argument assumed finite $ S $, the proof goes through when\n",
    "$ S $ is countably infinite and $ Q $ is conservative with very minor changes.)\n",
    "\n",
    "In particular, $ (X_t) $ is a continuous time Markov chain with intensity matrix\n",
    "$ Q $."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b4ee7b0",
   "metadata": {},
   "source": [
    "## Beyond Bounded Intensity Matrices\n",
    "\n",
    "If we do run into an application where an intensity matrix $ Q $ is not\n",
    "conservative, what might we expect?\n",
    "\n",
    "In this scenario, we can at least hope that $ Q $ is the generator of a $ C_0 $\n",
    "semigroup.\n",
    "\n",
    "Since $ Q $ is an intensity matrix, we can be sure that this semigroup will be a\n",
    "Markov semigroup.\n",
    "\n",
    "To know when $ Q $ will be the generator of a $ C_0 $\n",
    "semigroup, we need to look to the [Hille-Yoshida\n",
    "Theorem](https://en.wikipedia.org/wiki/Hille%E2%80%93Yosida_theorem) and\n",
    "sufficient conditions derived from it.\n",
    "\n",
    "While we omit a detailed treatment, it is worth noting that the issue is\n",
    "linked to explosions.\n",
    "\n",
    "To see the connection, recall that some initial value problems do not lead to a\n",
    "valid solution defined for all $ t \\in \\RR_+ $.\n",
    "\n",
    "An example is the scalar problem $ x'_t = 1 + x_t^2 $, which has solution $ x_t =\n",
    "\\tan (t - c) $ for some constant $ c $.\n",
    "\n",
    "But this solution equals $ +\\infty $ for $ t \\geq c + \\pi/2 $.\n",
    "\n",
    "The problem is that the time path explodes to infinity in finite time.\n",
    "\n",
    "The same issue can occur for Markov processes, if jump rates grow sufficiently\n",
    "quickly.\n",
    "\n",
    "For more discussion, see, for example, Section 2.7 of [[Norris, 1998](zreferences.ipynb#id12)]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "445e65f7",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44f68975",
   "metadata": {},
   "source": [
    "## Exercise 7.1\n",
    "\n",
    "Let $ P $ be a Markov matrix on $ S $ and identify it with the linear operator in\n",
    "[(7.1)](#equation-mmismo).  Verify the claims in [(7.2)](#equation-propp)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19c15e01",
   "metadata": {},
   "source": [
    "## Exercise 7.2\n",
    "\n",
    "Prove the claim in [Lemma 7.1](#scintcon)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38d5465c",
   "metadata": {},
   "source": [
    "## Exercise 7.3\n",
    "\n",
    "Confirm that $ Q $ defined in [(7.5)](#equation-poissonq) induces a bounded linear operator on\n",
    "$ \\ell_1 $ via [(7.3)](#equation-imislo)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a0ea3d6",
   "metadata": {},
   "source": [
    "## Exercise 7.4\n",
    "\n",
    "Let $ K $ be defined on $ \\ZZ_+ \\times \\ZZ_+ $ by $ K(i, j) = \\mathbb 1\\{j = i + 1\\} $.\n",
    "\n",
    "Show that, with $ K^m $ representing the $ m $-th matrix product of $ K $ with itself,\n",
    "we have $ K^m(i, j) = \\mathbb 1\\{j = i + m\\} $ for any $ i, j \\in \\ZZ_+ $."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "755fcf10",
   "metadata": {},
   "source": [
    "## Exercise 7.5\n",
    "\n",
    "Let $ Q $ be any intensity matrix on $ S $.\n",
    "\n",
    "Prove that the jump chain decomposition of $ Q $ is in fact a jump chain pair.\n",
    "\n",
    "Prove that, in addition, this decomposition $ (\\lambda, K) $ satisfies [(7.7)](#equation-jcinmat)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e052df4",
   "metadata": {},
   "source": [
    "## Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "530077e2",
   "metadata": {},
   "source": [
    "## Solution to[ Exercise 7.1](#uc-mc-semigroups-ex-1)\n",
    "\n",
    "To determine the norm of $ P $, we use the definition in [(6.2)](generators.ipynb#equation-norml).\n",
    "\n",
    "If $ f \\in \\ell_1 $ and $ \\| f \\| \\leq 1 $, then\n",
    "\n",
    "$$\n",
    "\\| f P \\| \n",
    "    \\leq \\sum_y \\sum_x |f(x)| P(x, y)\n",
    "    = \\sum_x |f(x)| \\sum_y P(x, y)\n",
    "    = \\sum_x |f(x)| \n",
    "    = \\| f \\|\n",
    "$$\n",
    "\n",
    "Hence $ \\| P \\| \\leq 1 $.\n",
    "\n",
    "To see that equality holds we can repeat this argument with $ f \\geq 0 $,\n",
    "obtaining $ \\| fP \\| = \\|f\\| $.\n",
    "\n",
    "Now pick any $ \\phi \\in \\dD $.\n",
    "\n",
    "Clearly $ \\phi P \\geq 0 $, and\n",
    "\n",
    "$$\n",
    "\\sum_y (\\phi P)(y)\n",
    "    =\\sum_y \\sum_x \\phi (x) P(x, y)\n",
    "    =\\sum_x \\phi (x) \\sum_y P(x, y)\n",
    "    = 1\n",
    "$$\n",
    "\n",
    "Hence $ \\phi P \\in \\dD $ as claimed."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4e0aec6",
   "metadata": {},
   "source": [
    "## Solution to[ Exercise 7.2](#uc-mc-semigroups-ex-2)\n",
    "\n",
    "Here is one solution.\n",
    "\n",
    "Let $ Q $ be an intensity matrix on $ S $.\n",
    "\n",
    "Suppose first that $ m := \\sup_x |Q(x,x)| $ is finite.\n",
    "\n",
    "Set $ \\hat P := I + Q / m $.\n",
    "\n",
    "It is not hard to check that $ \\hat P $ is a Markov matrix and that $ Q = m( \\hat\n",
    "P - I) $.\n",
    "\n",
    "Since $ \\hat P $ is a Markov matrix, it induces a bounded linear operator on\n",
    "$ \\ell_1 $ via [(7.1)](#equation-mmismo).\n",
    "\n",
    "As $ \\lL(\\ell_1) $ is a linear space, we see that $ Q $ is likewise in\n",
    "$ \\lL(\\ell_1) $.\n",
    "\n",
    "In particular, $ Q $ is a bounded operator, and hence conservative.\n",
    "\n",
    "Next, suppose that $ Q $ is conservative and yet $ \\sup_x |Q(x,x)| $ is infinite.\n",
    "\n",
    "Choose $ x \\in S $ such that $ |Q(x, x)| > \\| Q\\| $\n",
    "\n",
    "Let $ f \\in \\ell_1 $ be defined by $ f(z) = \\mathbb 1\\{z = x\\} $.\n",
    "\n",
    "Since $ \\|f\\| = 1 $, we have\n",
    "\n",
    "$$\n",
    "\\| Q \\| \n",
    "    \\geq \\| f Q \\|\n",
    "    = \\sum_y \\left| \\sum_z f(z) Q(z, y) \\right|\n",
    "    = \\sum_y | Q(x, y) |\n",
    "    \\geq | Q(x, x) |\n",
    "$$\n",
    "\n",
    "Contradiction."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b1e3bc0",
   "metadata": {},
   "source": [
    "## Solution to[ Exercise 7.3](#uc-mc-semigroups-ex-3)\n",
    "\n",
    "Linearity is obvious so we focus on boundedness.\n",
    "\n",
    "For any $ f \\in \\ell_1 $ and this choice of $ Q $, we have\n",
    "\n",
    "$$\n",
    "\\sum_y |(fQ)(y)|\n",
    "    \\leq \\sum_y \\sum_x |f(x) Q(x, y)|\n",
    "    \\leq \\lambda \\sum_y \\sum_x |f(y) - f(y+1)|\n",
    "$$\n",
    "\n",
    "Applying the triangle inequality, we see that the right hand side is dominated\n",
    "by $ 2 \\lambda \\| f\\| $.\n",
    "\n",
    "Hence $ \\| fQ \\| \\leq 2 \\lambda \\|f\\| $, which implies that $ Q \\in \\lL(\\ell_1) $\n",
    "as required."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5f2784b",
   "metadata": {},
   "source": [
    "## Solution to[ Exercise 7.4](#uc-mc-semigroups-ex-4)\n",
    "\n",
    "The statement $ K^m(i, j) = \\mathbb 1\\{j = i + m\\} $ holds by definition when\n",
    "$ m=1 $.\n",
    "\n",
    "Now suppose it holds at arbitrary $ m $.\n",
    "\n",
    "We then have, by definition of composition (matrix multiplication),\n",
    "\n",
    "$$\n",
    "K^{m+1}(i, j)\n",
    "    = \\sum_n K(i, n) K^m (n, j)\n",
    "    = \\sum_n K(i, n) \\mathbb 1\\{j = n + m\\}\n",
    "    = K(i, j-m)\n",
    "$$\n",
    "\n",
    "Applying the definition $ K(i, j) = \\mathbb 1\\{j = i + 1\\} $ completes verification of the claim."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06466eba",
   "metadata": {},
   "source": [
    "## Solution to[ Exercise 7.5](#uc-mc-semigroups-ex-5)\n",
    "\n",
    "Let $ Q $ be an intensity matrix and let $ (\\lambda, K) $ be the jump chain\n",
    "decomposition of $ Q $.\n",
    "\n",
    "Nonnegativity of $ \\lambda $ is immediate from the definition of an intensity\n",
    "matrix.\n",
    "\n",
    "To see that $ K $ is a Markov matrix we fix $ x \\in S $ and suppose first that\n",
    "$ \\lambda(x) > 0 $.\n",
    "\n",
    "Then\n",
    "\n",
    "$$\n",
    "\\sum_y K(x, y) \n",
    "    = \\sum_{y \\not= x} K(x,y) \n",
    "    = \\sum_{y \\not= x} \\frac{Q(x,y)}{\\lambda(x)}\n",
    "    = 1\n",
    "$$\n",
    "\n",
    "If, on the other hand, $ \\lambda(x) = 0 $, then\n",
    "$ \\sum_y K(x, y) = 1 $, is immediate from the definition.\n",
    "\n",
    "As $ K $ is nonnegative, we see that $ K $ is a Markov matrix.\n",
    "\n",
    "Thus, $ (\\lambda, K) $ is a valid jump chain pair.\n",
    "\n",
    "The proof that $ Q $ and $ (\\lambda, K) $ satisfy [(7.7)](#equation-jcinmat) is mechanical and\n",
    "the details are omitted.\n",
    "\n",
    "(Try working case-by-case, with $ \\lambda(x) = 0, x=y $, $ \\lambda(x) > 0, x=y $, etc.)\n",
    "\n",
    "<a id='fnim'></a>\n",
    "**[1]** Previously, we introduced the notion of an intensity matrix when $ S $\n",
    "is finite and the definition is essentially unchanged in the current\n",
    "setting.  In particular, $ Q \\colon S \\times S \\to \\RR $ is called an\n",
    "**intensity matrix** if $ Q $ has zero row sums and $ Q(x, y) \\geq 0 $ whenever\n",
    "$ x \\not= y $."
   ]
  }
 ],
 "metadata": {
  "date": 1732753874.0770118,
  "filename": "uc_mc_semigroups.md",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "UC Markov Semigroups"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}