{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The Kolmogorov Forward Equation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Overview\n",
"\n",
"In this lecture we approach continuous time Markov chains from a more\n",
"analytical perspective.\n",
"\n",
"The emphasis will be on describing distribution flows through vector-valued\n",
"differential equations and their solutions.\n",
"\n",
"These distribution flows show how the time $ t $ distribution associated with a\n",
"given Markov chain $ (X_t) $ changes over time.\n",
"\n",
"Distribution flows will be identified with initial value problems generated by autonomous linear ordinary differential equations (ODEs) in vector space.\n",
"\n",
"We will see that the solutions of these flows are described by Markov semigroups.\n",
"\n",
"This leads us back to the theory we have already constructed – some care will\n",
"be taken to clarify all the connections.\n",
"\n",
"In order to avoid being distracted by technicalities, we continue to defer our\n",
"treatment of infinite state spaces, assuming throughout this lecture that $ |S|\n",
"= n $.\n",
"\n",
"As before, $ \\dD $ is the set of all distributions on $ S $.\n",
"\n",
"We will use the following imports"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"import scipy as sp\n",
"import matplotlib.pyplot as plt\n",
"import quantecon as qe\n",
"from numba import njit\n",
"from scipy.linalg import expm\n",
"\n",
"from matplotlib import cm\n",
"from mpl_toolkits.mplot3d import Axes3D\n",
"from mpl_toolkits.mplot3d.art3d import Poly3DCollection"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## From Difference Equations to ODEs\n",
"\n",
"[Previously](https://jstac.github.io/continuous_time_mcs/markov_prop.html#invdistflows) we generated this figure, which shows how distributions evolve over time for the inventory model under a certain parameterization:\n",
"\n",
"Probability flows for the inventory model. \n",
"(Hot colors indicate early dates and cool colors denote later dates.)\n",
"\n",
"We also learned how this flow is related to\n",
"the Kolmogorov backward equation, which is an ODE.\n",
"\n",
"In this section we examine distribution flows and their connection to\n",
"ODEs and continuous time Markov chains more systematically."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Review of the Discrete Time Case\n",
"\n",
"Let $ (X_t) $ be a discrete time Markov chain with Markov matrix $ P $.\n",
"\n",
"[Recall that](https://jstac.github.io/continuous_time_mcs/markov_prop.html#finstatediscretemc), in the discrete time case, the distribution $ \\psi_t $ of $ X_t $ updates according to\n",
"\n",
"$$\n",
"\\psi_{t+1} = \\psi_t P, \n",
" \\qquad \\psi_0 \\text{ a given element of } \\dD,\n",
"$$\n",
"\n",
"where distributions are understood as row vectors.\n",
"\n",
"Here’s a visualization for the case $ S = \\{0, 1, 2\\} $, so that $ \\dD $ is the [standard\n",
"simplex](https://en.wikipedia.org/wiki/Simplex#The_standard_simplex) in $ \\RR^3 $.\n",
"\n",
"The initial condition is ` (0, 0, 1)` and the Markov matrix is"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"P = ((0.9, 0.1, 0.0),\n",
" (0.4, 0.4, 0.2),\n",
" (0.1, 0.1, 0.8))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def unit_simplex(angle):\n",
" \n",
" fig = plt.figure(figsize=(8, 6))\n",
" ax = fig.add_subplot(111, projection='3d')\n",
"\n",
" vtx = [[0, 0, 1],\n",
" [0, 1, 0], \n",
" [1, 0, 0]]\n",
" \n",
" tri = Poly3DCollection([vtx], color='darkblue', alpha=0.3)\n",
" tri.set_facecolor([0.5, 0.5, 1])\n",
" ax.add_collection3d(tri)\n",
"\n",
" ax.set(xlim=(0, 1), ylim=(0, 1), zlim=(0, 1), \n",
" xticks=(1,), yticks=(1,), zticks=(1,))\n",
"\n",
" ax.set_xticklabels(['$(1, 0, 0)$'], fontsize=12)\n",
" ax.set_yticklabels(['$(0, 1, 0)$'], fontsize=12)\n",
" ax.set_zticklabels(['$(0, 0, 1)$'], fontsize=12)\n",
"\n",
" ax.xaxis.majorTicks[0].set_pad(15)\n",
" ax.yaxis.majorTicks[0].set_pad(15)\n",
" ax.zaxis.majorTicks[0].set_pad(35)\n",
"\n",
" ax.view_init(30, angle)\n",
"\n",
" # Move axis to origin\n",
" ax.xaxis._axinfo['juggled'] = (0, 0, 0)\n",
" ax.yaxis._axinfo['juggled'] = (1, 1, 1)\n",
" ax.zaxis._axinfo['juggled'] = (2, 2, 0)\n",
" \n",
" ax.grid(False)\n",
" \n",
" return ax\n",
"\n",
"\n",
"def convergence_plot(ψ, n=14, angle=50):\n",
"\n",
" ax = unit_simplex(angle)\n",
"\n",
" P = ((0.9, 0.1, 0.0),\n",
" (0.4, 0.4, 0.2),\n",
" (0.1, 0.1, 0.8))\n",
" \n",
" P = np.array(P)\n",
" colors = cm.jet_r(np.linspace(0.0, 1, n))\n",
"\n",
" x_vals, y_vals, z_vals = [], [], []\n",
" for t in range(n):\n",
" x_vals.append(ψ[0])\n",
" y_vals.append(ψ[1])\n",
" z_vals.append(ψ[2])\n",
" ψ = ψ @ P\n",
"\n",
" ax.scatter(x_vals, y_vals, z_vals, c=colors, s=50, alpha=0.7, depthshade=False)\n",
"\n",
" return ψ\n",
"\n",
"ψ = convergence_plot((0, 0, 1))\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There’s a sense in which a discrete time Markov chain “is” a homogeneous\n",
"linear difference equation in distribution space.\n",
"\n",
"To clarify this, suppose we\n",
"take $ G $ to be a linear map from $ \\dD $ to itself and\n",
"write down the difference equation\n",
"\n",
"\n",
"\n",
"$$\n",
"\\psi_{t+1} = G(\\psi_t)\n",
" \\quad \\text{with } \\psi_0 \\in \\dD \\text{ given}. \\tag{5.1}\n",
"$$\n",
"\n",
"Because $ G $ is a linear map from a finite dimensional space to itself, it can\n",
"be represented by a matrix.\n",
"\n",
"Moreover, a matrix $ P $ is a Markov matrix if and only if $ \\psi \\mapsto\n",
"\\psi P $ sends $ \\dD $ into itself (check it if you haven’t already).\n",
"\n",
"So, under the stated conditions, our difference equation [(5.1)](#equation-gdiff2) uniquely\n",
"identifies a Markov matrix, along with an initial condition $ \\psi_0 $.\n",
"\n",
"Together, these objects identify the joint distribution of a discrete time Markov chain, as [previously described](https://jstac.github.io/continuous_time_mcs/markov_prop.html#jdfin)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Shifting to Continuous Time\n",
"\n",
"We have just argued that a discrete time Markov chain can be identified with a\n",
"linear difference equation evolving in $ \\dD $.\n",
"\n",
"This strongly suggests that a continuous time Markov chain can be identified\n",
"with a linear ODE evolving in $ \\dD $.\n",
"\n",
"This intuition is correct and important.\n",
"\n",
"The rest of the lecture maps out the main ideas."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ODEs in Distribution Space\n",
"\n",
"Consider linear differential equation given by\n",
"\n",
"\n",
"\n",
"$$\n",
"\\psi_t' = \\psi_t Q, \n",
" \\qquad \\psi_0 \\text{ a given element of } \\dD, \\tag{5.2}\n",
"$$\n",
"\n",
"where\n",
"\n",
"- $ Q $ is an $ n \\times n $ matrix, \n",
"- distributions are again understood as row vectors, and \n",
"- derivatives are taken element by element, so that \n",
"\n",
"\n",
"$$\n",
"\\psi_t' =\n",
" \\begin{pmatrix}\n",
" \\frac{d}{dt} \\psi_t(x_1) &\n",
" \\cdots &\n",
" \\frac{d}{dt} \\psi_t(x_n)\n",
" \\end{pmatrix}\n",
"$$\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solutions to Linear Vector ODEs\n",
"\n",
"Using the matrix exponential, the unique solution to the initial value problem\n",
"[(5.2)](#equation-ode-mc) is\n",
"\n",
"\n",
"\n",
"$$\n",
"\\psi_t = \\psi_0 P_t \n",
" \\quad \\text{where } P_t := e^{tQ} \\tag{5.3}\n",
"$$\n",
"\n",
"To check that [(5.3)](#equation-cmc-sol) is a solution, we use [(4.7)](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#equation-expoderiv) again to get\n",
"\n",
"$$\n",
"\\frac{d}{d t} P_t = Q e^{tQ} = e^{tQ} Q\n",
"$$\n",
"\n",
"The first equality can be written as $ P_t' = Q P_t $ and this is just\n",
"the [Kolmogorov backward equation](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html).\n",
"\n",
"The second equality can be written as\n",
"\n",
"$$\n",
"P_t' = P_t Q\n",
"$$\n",
"\n",
"and is called the **Kolmogorov forward equation**.\n",
"\n",
"Applying the Kolmogorov forward equation, we obtain\n",
"\n",
"$$\n",
"\\frac{d}{d t} \\psi_t \n",
" = \\frac{d}{d t} \\psi_0 P_t \n",
" = \\psi_0 \\frac{d}{d t} P_t \n",
" = \\psi_0 P_t Q\n",
" = \\psi_t Q\n",
"$$\n",
"\n",
"This confirms that [(5.3)](#equation-cmc-sol) solves [(5.2)](#equation-ode-mc).\n",
"\n",
"Here’s an example of three distribution flows with dynamics generated by [(5.2)](#equation-ode-mc), one starting from each vertex.\n",
"\n",
"The code uses [(5.3)](#equation-cmc-sol) with matrix $ Q $ given by"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"Q = ((-3, 2, 1),\n",
" (3, -5, 2),\n",
" (4, 6, -10))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"Q = np.array(Q)\n",
"ψ_00 = np.array((0.01, 0.01, 0.99))\n",
"ψ_01 = np.array((0.01, 0.99, 0.01))\n",
"ψ_02 = np.array((0.99, 0.01, 0.01))\n",
"\n",
"ax = unit_simplex(angle=50) \n",
"\n",
"def flow_plot(ψ, h=0.001, n=400, angle=50):\n",
" colors = cm.jet_r(np.linspace(0.0, 1, n))\n",
"\n",
" x_vals, y_vals, z_vals = [], [], []\n",
" for t in range(n):\n",
" x_vals.append(ψ[0])\n",
" y_vals.append(ψ[1])\n",
" z_vals.append(ψ[2])\n",
" ψ = ψ @ expm(h * Q)\n",
"\n",
" ax.scatter(x_vals, y_vals, z_vals, c=colors, s=20, alpha=0.2, depthshade=False)\n",
"\n",
"flow_plot(ψ_00)\n",
"flow_plot(ψ_01)\n",
"flow_plot(ψ_02)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Distributions cool over time, so initial conditions are hot colors.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Forwards vs Backwards Equations\n",
"\n",
"As the above discussion shows, we can take the Kolmogorov forward equation\n",
"$ P_t' = P_t Q $ and premultiply by any distribution $ \\psi_0 $ to get the\n",
"distribution ODE $ \\psi'_t = \\psi_t Q $.\n",
"\n",
"In this sense, we can understand the Kolmogorov forward equation as pushing\n",
"distributions forward in time.\n",
"\n",
"Analogously, we can take the Kolmogorov backward equation\n",
"$ P_t' = Q P_t $ and postmultiply by any vector $ h $ to get\n",
"\n",
"$$\n",
"(P_t h)' = Q P_t h\n",
"$$\n",
"\n",
"Recalling that $ (P_t h)(x) = \\EE [ h(X_t) \\,|\\, X_0 = x] $, this vector\n",
"ODE tells us how expectations evolve, conditioning backward to time zero.\n",
"\n",
"Both the forward and the backward equations uniquely pin down the same solution $ P_t = e^{tQ} $ when combined with the initial condition $ P_0 = I $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Matrix- vs Vector-Valued ODEs\n",
"\n",
"The ODE $ \\psi'_t = \\psi_t Q $ is sometimes called the\n",
"**Fokker–Planck equation** (although this terminology is most commonly used\n",
"in the context of diffusions).\n",
"\n",
"It is a vector-valued ODE that describes the evolution of a particular\n",
"distribution path.\n",
"\n",
"By comparison, the Kolmogorov forward equation is (like the backward equation)\n",
"a differential equation in matrices.\n",
"\n",
"(And matrices are really maps, which send vectors into vectors.)\n",
"\n",
"Operating at this level is less intuitive and more abstract than working with the\n",
"Fokker–Planck equation.\n",
"\n",
"But, in the end, the object that we want to describe is a Markov\n",
"semigroup.\n",
"\n",
"The Kolmogorov forward and backward equations are the ODEs that define\n",
"this fundamental object."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Preserving Distributions\n",
"\n",
"In the simulation above, $ Q $ was chosen with some care, so that the flow\n",
"remains in $ \\dD $.\n",
"\n",
"What are the exact properties we require on $ Q $ such that $ \\psi_t $ is always\n",
"in $ \\dD $?\n",
"\n",
"This is an important question, because we are setting up an exact\n",
"correspondence between linear ODEs that evolve in $ \\dD $ and continuous\n",
"time Markov chains.\n",
"\n",
"Recall that the linear update rule $ \\psi \\mapsto \\psi P $ is invariant on\n",
"$ \\dD $ if and only if $ P $ is a Markov matrix.\n",
"\n",
"So now we can rephrase our key question regarding invariance on $ \\dD $:\n",
"\n",
"What properties do we need to impose on $ Q $ so that $ P_t = e^{tQ} $ is a Markov matrix\n",
"for all $ t $?\n",
"\n",
"A square matrix $ Q $ is called an **intensity matrix** if $ Q $ has zero row\n",
"sums and $ Q(x, y) \\geq 0 $ whenever $ x \\not= y $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### \n",
"\n",
"If $ Q $ is a matrix on $ S $ and $ P_t := e^{tQ} $, then the following statements\n",
"are equivalent:\n",
"\n",
"1. $ P_t $ is a Markov matrix for all $ t $. \n",
"1. $ Q $ is an intensity matrix. \n",
"\n",
"\n",
"The proof is related to that of [Lemma 4.2](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#jctosg) and is found as\n",
"a solved exercise below."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### \n",
"\n",
"If $ Q $ is an intensity matrix on finite $ S $ and $ P_t = e^{tQ} $ for all $ t \\geq 0 $,\n",
"then $ (P_t) $ is a Markov semigroup.\n",
"\n",
"We call $ (P_t) $ the Markov semigroup **generated** by $ Q $.\n",
"\n",
"Later we will see that this result extends to the case $ |S| = \\infty $ under\n",
"some mild restrictions on $ Q $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Jump Chains\n",
"\n",
"Let’s return to the chain $ (X_t) $ created from jump chain pair $ (\\lambda, K) $ in\n",
"[Algorithm 4.1](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#ejc_algo).\n",
"\n",
"We found that the semigroup is given by\n",
"\n",
"$$\n",
"P_t = e^{tQ}\n",
" \\quad \\text{where} \\quad\n",
" Q(x, y) := \\lambda(x) (K(x, y) - I(x, y))\n",
"$$\n",
"\n",
"Using the fact that $ K $ is a Markov matrix and the jump rate function\n",
"$ \\lambda $ is nonnegative, you can easily check that $ Q $ satisfies the\n",
"definition of an intensity matrix.\n",
"\n",
"Hence $ (P_t) $, the Markov semigroup for the jump chain $ (X_t) $, is the\n",
"semigroup generated by the intensity matrix $ Q(x, y) = \\lambda(x) (K(x, y) - I(x, y)) $.\n",
"\n",
"We can differentiate $ P_t = e^{tQ} $ to obtain the Kolmogorov forward equation\n",
"$ P_t' = P_t Q $.\n",
"\n",
"We can then premultiply by $ \\psi_0 \\in \\dD $ to get $ \\psi_t' = \\psi_t\n",
"Q $, which is the Fokker–Planck equation.\n",
"\n",
"More explicitly, for given $ y \\in S $,\n",
"\n",
"$$\n",
"\\psi_t'(y)\n",
" = \\sum_{x \\not= y} \\psi_t(x) \\lambda(x) K(x, y) - \\psi_t(y) \\lambda(y)\n",
"$$\n",
"\n",
"The rate of probability flow into $ y $ is equal to the inflow from other states\n",
"minus the outflow."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Summary\n",
"\n",
"We have seen that any intensity matrix $ Q $ on $ S $ defines a Markov semigroup via $ P_t = e^{tQ} $.\n",
"\n",
"Henceforth, we will say that $ (X_t) $ is **a Markov chain with intensity matrix** $ Q $ if\n",
"$ (X_t) $ is a Markov chain with Markov semigroup $ (e^{tQ}) $.\n",
"\n",
"While our discussion has been in the context of a finite state space, later we\n",
"will see that these ideas carry over to an infinite state setting under mild\n",
"restrictions.\n",
"\n",
"We have also hinted at the fact that *every* continuous time Markov chain\n",
"is a Markov chain with intensity matrix $ Q $ for some suitably chosen $ Q $.\n",
"\n",
"Later we will prove this to be universally true when $ S $ is finite and true\n",
"under mild conditions when $ S $ is countably infinite.\n",
"\n",
"Intensity matrices are important because\n",
"\n",
"1. they are the natural infinitesimal descriptions of Markov semigroups, \n",
"1. they are often easy to write down in applications and \n",
"1. they provide an intuitive description of dynamics. \n",
"\n",
"\n",
"Later, we will see that, for a given intensity matrix $ Q $, the elements are\n",
"understood as follows:\n",
"\n",
"- when $ x \\not= y $, the value $ Q(x, y) $ is the “rate of leaving $ x $ for $ y $” and \n",
"- $ -Q(x, x) \\geq 0 $ is the “rate of leaving $ x $” . "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise \n",
"\n",
"Let $ (P_t) $ be a Markov semigroup such that $ t \\mapsto P_t(x, y) $ is\n",
"differentiable at all $ t \\geq 0 $ and $ (x, y) \\in S \\times S $.\n",
"\n",
"(The derivative at $ t=0 $ is the usual right derivative.)\n",
"\n",
"Define (pointwise, at each $ (x,y) $),\n",
"\n",
"\n",
"\n",
"$$\n",
"Q := P'_0 = \\lim_{h \\downarrow 0} \\frac{P_h - I}{h} \\tag{5.4}\n",
"$$\n",
"\n",
"Assuming that this limit exists, and hence $ Q $ is well-defined, show that\n",
"\n",
"$$\n",
"P'_t = P_t Q\n",
" \\quad \\text{and} \\quad\n",
" P'_t = Q P_t\n",
"$$\n",
"\n",
"both hold. (These are the Kolmogorov forward and backward equations.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise \n",
"\n",
"Recall [our model](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#sdji) of jump chains with state-dependent jump\n",
"intensities given by rate function $ x \\mapsto \\lambda(x) $.\n",
"\n",
"After a wait time with exponential rate $ \\lambda(x) \\in (0, \\infty) $, the\n",
"state transitions from $ x $ to $ y $ with probability $ K(x,y) $.\n",
"\n",
"We found that the associated semigroup $ (P_t) $ satisfies the Kolmogorov\n",
"backward equation $ P'_t = Q P_t $ with\n",
"\n",
"\n",
"\n",
"$$\n",
"Q(x, y) := \\lambda(x) (K(x, y) - I(x, y)) \\tag{5.5}\n",
"$$\n",
"\n",
"Show that $ Q $ is an intensity matrix and that [(5.4)](#equation-genfl) holds."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise \n",
"\n",
"Prove [Theorem 5.1](#intvsmk) by adapting the arguments in [Lemma 4.2](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#jctosg).\n",
"(This is nontrivial but worth at least trying.)\n",
"\n",
"Hint: The constant $ m $ in the proof can be set to $ \\max_x |Q(x, x)| $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Solutions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## [Solution to Exercise 5.1](https://jstac.github.io/continuous_time_mcs/#kolmogorov-fwd-1)\n",
"\n",
"Let $ (P_t) $ be a Markov semigroup and let $ Q $ be as defined in the statement\n",
"of the exercise.\n",
"\n",
"Fix $ t \\geq 0 $ and $ h > 0 $.\n",
"\n",
"Combining the semigroup property and linearity with the restriction $ P_0 = I $, we get\n",
"\n",
"$$\n",
"\\frac{P_{t+h} - P_t}{h}\n",
" = \\frac{P_t P_h - P_t}{h}\n",
" = \\frac{P_t (P_h - I)}{h}\n",
"$$\n",
"\n",
"Taking $ h \\downarrow 0 $ and using the definition of $ Q $ give $ P_t' = P_t Q $,\n",
"which is the Kolmogorov forward equation.\n",
"\n",
"For the backward equation we observe that\n",
"\n",
"$$\n",
"\\frac{P_{t+h} - P_t}{h}\n",
" = \\frac{P_h P_t - P_t}{h}\n",
" = \\frac{(P_h - I) P_t}{h}\n",
"$$\n",
"\n",
"also holds. Taking $ h \\downarrow 0 $ gives the Kolmogorov backward equation."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## [Solution to Exercise 5.2](https://jstac.github.io/continuous_time_mcs/#kolmogorov-fwd-2)\n",
"\n",
"Let $ Q $ be as defined in [(5.5)](#equation-qeqagain).\n",
"\n",
"We need to show that $ Q $ is nonnegative off the diagonal and has zero row\n",
"sums.\n",
"\n",
"The first assertion is immediate from nonnegativity of $ K $ and $ \\lambda $.\n",
"\n",
"For the second, we use the fact that $ K $ is a Markov matrix, so that, with $ 1 $\n",
"as a column vector of ones,\n",
"\n",
"$$\n",
"Q 1\n",
" = \\lambda (K 1 - 1)\n",
" = \\lambda (1 - 1)\n",
" = 0\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## [Solution to Exercise 5.3](https://jstac.github.io/continuous_time_mcs/#kolmogorov-fwd-3)\n",
"\n",
"Suppose that $ Q $ is an intensity matrix, fix $ t \\geq 0 $ and set $ P_t = e^{tQ} $.\n",
"\n",
"The proof from [Lemma 4.2](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#jctosg) that $ P_t $ has unit row sums applies\n",
"directly to the current case.\n",
"\n",
"The proof of nonnegativity of $ P_t $ can be applied after some\n",
"modifications.\n",
"\n",
"To this end, set $ m := \\max_x |Q(x,x)| $ and $ \\hat P := I + Q / m $.\n",
"\n",
"You can check that $ \\hat P $ is a Markov matrix and that $ Q = m( \\hat P - I) $.\n",
"\n",
"The rest of the proof of nonnegativity of $ P_t $ is unchanged and we will not repeat it.\n",
"\n",
"We conclude that $ P_t $ is a Markov matrix.\n",
"\n",
"Regarding the converse implication, suppose that $ P_t = e^{tQ} $ is a Markov\n",
"matrix for all $ t $ and let $ 1 $ be a column vector of ones.\n",
"\n",
"Because $ P_t $ has unit row sums and differentiation is linear,\n",
"we can employ the Kolmogorov backward equation to obtain\n",
"\n",
"$$\n",
"Q 1\n",
" = Q P_t 1\n",
" = \\left( \\frac{d}{d t} P_t \\right) 1\n",
" = \\frac{d}{d t} (P_t 1)\n",
" = \\frac{d}{d t} 1\n",
" = 0\n",
"$$\n",
"\n",
"Hence $ Q $ has zero row sums.\n",
"\n",
"We can use the definition of the matrix exponential to obtain,\n",
"for any $ x, y $ and $ t \\geq 0 $,\n",
"\n",
"\n",
"\n",
"$$\n",
"P_t(x, y) = \\mathbb 1\\{x = y\\} + t Q(x, y) + o(t) \\tag{5.6}\n",
"$$\n",
"\n",
"From this equality and the assumption that $ P_t $ is a Markov matrix for all\n",
"$ t $, we see that the off diagonal elements of $ Q $ must be\n",
"nonnegative.\n",
"\n",
"Hence $ Q $ is an intensity matrix."
]
}
],
"metadata": {
"date": 1634710782.523278,
"filename": "kolmogorov_fwd.md",
"kernelspec": null,
"title": "The Kolmogorov Forward Equation"
},
"nbformat": 4,
"nbformat_minor": 4
}