{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Stationarity and Ergodicity" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Overview\n", "\n", "In this lecture we discuss stability and equilibrium behavior for continuous\n", "time Markov chains.\n", "\n", "To give one example of why this theory matters, consider queues, which are\n", "often modeled as continuous time Markov chains.\n", "\n", "Queueing theory is used in applications such as\n", "\n", "- treatment of patients arriving at a hospital \n", "- optimal design of manufacturing processes \n", "- requests to a file server \n", "- air traffic \n", "- customers waiting on a helpline \n", "\n", "\n", "A key topic in queueing theory is average behavior over the long run.\n", "\n", "- Will the length of the queue grow without bounds? \n", "- If not, is there some kind of long run equilibrium? \n", "- If so, what is the average waiting time in this equilibrium? \n", "- What is the average length of the queue over a week, or a month? \n", "\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": [ "## Stationary Distributions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Definition\n", "\n", "Let $S$ be countable.\n", "\n", "Recall that, for a discrete time Markov chain with Markov matrix $P$ on $S$, a\n", "distribution $\\psi$ is called stationary for $P$ if $\\psi P = \\psi$.\n", "\n", "This means that if $X_t$ has distribution $\\psi$, then so does $X_{t+1}$.\n", "\n", "For continuous time Markov chains, the definition is analogous.\n", "\n", "Given a Markov semigroup $(P_t)$ on $S$, a distribution $\\psi^* \\in \\dD$ is called\n", "**stationary** for $(P_t)$ if\n", "\n", "$$\n", "\\psi^* P_t = \\psi^* \n", " \\text{ for all } t \\geq 0\n", "$$\n", "\n", "As one example, we look [again](https://jstac.github.io/continuous_time_mcs/kolmogorov_fwd.html#solvode) at the chain on $S = \\{0, 1,\n", "2\\}$ with intensity matrix" ] }, { "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": "markdown", "metadata": {}, "source": [ "The following figure was shown before, except that now there is a black dot\n", "that the three trajectories seem to be converging to.\n", "\n", "(Recall that, in the color scheme, trajectories cool as time evolves.)" ] }, { "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.set_pad(15)\n", " ax.yaxis.majorTicks.set_pad(15)\n", " ax.zaxis.majorTicks.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", "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=300, 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(ψ)\n", " y_vals.append(ψ)\n", " z_vals.append(ψ)\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", "# Add stationary distribution\n", "P_1 = expm(Q)\n", "mc = qe.MarkovChain(P_1)\n", "ψ = mc.stationary_distributions\n", "ax.scatter(ψ, ψ, ψ, c='k', s=30, depthshade=False)\n", "\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This black dot is the stationary distribution $\\psi^*$ of the Markov semigroup $(P_t)$ generated by $Q$.\n", "\n", "It was calculated using the stationary_distributions attribute of QuantEcon’s\n", "[MarkovChain class](https://quanteconpy.readthedocs.io/en/latest/markov.html), by arbitrarily setting $t=1$ and solving $\\psi P_1 = \\psi$.\n", "\n", "Below we show that, for this choice of $Q$, the stationary distribution\n", "$\\psi^*$ is unique in $\\dD$, due to irreducibility.\n", "\n", "Moreover, $\\psi P_t \\to \\psi^*$ as $t \\to \\infty$ for any $\\psi \\in \\dD$, as\n", "suggested by the figure." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Stationarity via the Generator\n", "\n", "In many cases, it is easier to use the generator of the semigroup to identify\n", "stationary distributions rather than the semigroup itself.\n", "\n", "This is analogous to the idea that a point $\\bar x$ in $\\RR^d$ is stationary for\n", "a vector ODE $x'_t = F(x_t)$ when $F(\\bar x) = 0$.\n", "\n", "(Here $F$ is the infinitesimal description, and hence analogous to the generator.)\n", "\n", "The next result holds true under weaker conditions but the version stated here\n", "is easy to prove and sufficient for applications we consider." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "Let $(P_t)$ be a UC Markov semigroup with generator $Q$. A distribution\n", "$\\psi$ on $S$ is stationary for $(P_t)$ if and only if $\\psi Q = 0$.\n", "\n", "Proof. Fix $\\psi \\in \\dD$ and suppose first that $\\psi Q = 0$.\n", "\n", "Since $(P_t)$ is a UC Markov semigroup, we have $P_t = e^{tQ}$ for all $t$,\n", "and hence, for any $t \\geq 0$,\n", "\n", "$$\n", "\\psi e^{tQ} = \\psi + t \\psi Q + t^2 \\frac{\\psi Q^2}{2!} \n", " + \\cdots\n", "$$\n", "\n", "From $\\psi Q = 0$ we get $\\psi Q^k = 0$ for all $k \\in \\NN$, so the last\n", "display yields $\\psi P_t = \\psi$.\n", "\n", "Hence $\\psi$ is stationary for $(P_t)$.\n", "\n", "Now suppose that $\\psi$ is stationary for $(P_t)$ and set $D_t := (1/t) (P_t -\n", "I)$.\n", "\n", "From the triangle inequality and the definition of the operator norm, for any given $t$,\n", "\n", "$$\n", "\\| \\psi Q \\| \n", " \\leq \\| \\psi (Q - D_t) \\| + \\| \\psi D_t \\|\n", " \\leq \\| Q - D_t \\| + \\| \\psi D_t \\|\n", "$$\n", "\n", "Since $(P_t)$ is UC and $Q$ is its generator, we have $\\| D_t - Q \\| \\to 0$ in\n", "$\\lL(\\ell_1)$ as $t \\to 0^+$.\n", "\n", "Hence $\\| \\psi Q \\| \\leq \\liminf_{t \\downarrow 0} \\| \\psi D_t \\|$.\n", "\n", "As $\\psi$ is stationary for $(P_t)$, we have $\\psi D_t = 0$ for all $t$.\n", "\n", "Hence $\\psi Q = 0$, as was to be shown." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Irreducibility and Uniqueness\n", "\n", "Let $(P_t)$ be a Markov semigroup on $S$ and consider arbitrary states $x, y \\in S$.\n", "\n", "We say that state $y$ is **accessible** from state $x$ if\n", "there exists a $t \\geq 0$ such that $P_t(x, y) > 0$.\n", "\n", "We say that $x$ and $y$ **communicate** if $x$ is accessible from $y$ and $y$\n", "is accessible from $x$.\n", "\n", "A Markov semigroup $(P_t)$ on $S$ is called **irreducible** if\n", "every pair $x,y$ in $S$ communicates.\n", "\n", "We seek a characterization of irreducibility of $(P_t)$ in terms of its\n", "generator.\n", "\n", "As a first step, we will say there is a **$Q$-positive probability flow** from $x$\n", "to $y$ if there exists a finite sequence $(z_i)_{i=0}^m$ in $S$ starting at\n", "$x=z_0$ and ending at $y=z_m$ such that $Q(z_i, z_{i+1}) > 0$ for all $i$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## \n", "\n", "Let $(P_t)$ be a UC Markov semigroup with generator $Q$.\n", "For distinct states $x$ and $y$, the following statements are equivalent:\n", "\n", "1. The state $y$ is accessible from $x$ under $(P_t)$. \n", "1. There is a $Q$-positive probability flow from $x$ to $y$. \n", "1. $P_t(x, y) > 0$ for all $t > 0$. \n", "\n", "\n", "Proof. Pick any two distinct states $x$ and $y$.\n", "\n", "It is obvious that statement 3 implies statement 1, so we need only prove\n", "(1 $\\implies$ 2) and (2 $\\implies$ 3).\n", "\n", "Starting with (1 $\\implies$ 2), recall that\n", "\n", "\n", "\n", "$$\n", "P_t(x, y) = t Q(x,y) + \\frac{t^2}{2!} Q^2(x, y) + \\cdots \\tag{8.1}\n", "$$\n", "\n", "If $x$ is accessible from $y$, then $P_t(x, y) > 0$ for some $t > 0$, so\n", "$Q^k(x,y) > 0$ for at least one $k \\in \\NN$.\n", "\n", "Writing out the matrix product as a sum, we now have\n", "\n", "\n", "\n", "$$\n", "Q^k(x,y) =\n", " \\sum_{z_1}\n", " \\sum_{z_2}\n", " \\cdots\n", " \\sum_{z_{k-1}}\n", " Q(x, z_1) Q(z_1, z_2) \\cdots Q(z_{k-1}, y) \n", " > 0 \\tag{8.2}\n", "$$\n", "\n", "It follows that at least one element of the sum must be strictly positive.\n", "\n", "Therefore, a $Q$-positive probability flow from $x$ to $y$ exists.\n", "\n", "Turning to (2 $\\implies$ 3), first note that, for arbitrary states $u$ and $v$, if $Q(u, v) > 0$ then $P_t(u, v) > 0$ for all $t > 0$.\n", "\n", "To see this, let $(\\lambda, K)$ be the jump chain pair constructed from $Q$ via\n", "[(7.8)](https://jstac.github.io/continuous_time_mcs/uc_mc_semigroups.html#equation-lambdafromq), [(7.9)](https://jstac.github.io/continuous_time_mcs/uc_mc_semigroups.html#equation-kfromqxx) and [(7.10)](https://jstac.github.io/continuous_time_mcs/uc_mc_semigroups.html#equation-kfromqxy).\n", "\n", "Observe that, since $Q(u, v) > 0$, we must have $\\lambda(u) > 0$.\n", "\n", "As a consequence, applying [(7.10)](https://jstac.github.io/continuous_time_mcs/uc_mc_semigroups.html#equation-kfromqxy), we have\n", "\n", "$$\n", "K(u, v) = \\frac{Q(u, v)}{\\lambda(u)} > 0\n", "$$\n", "\n", "Let $(Y_k)$ and $(J_k)$ be the embedded jump chain and jump sequence generated\n", "by [Algorithm 4.1](https://jstac.github.io/continuous_time_mcs/kolmogorov_bwd.html#ejc_algo), with $Y_0 = u$.\n", "\n", "With $E_1 \\sim \\Exp(1)$ and $E_2 \\sim \\Exp(1)$, we have, for any $t > 0$,\n", "\n", "\n", "\\begin{aligned}\n", " P_t(u, v) \n", " & \\geq \\PP \\{J_1 \\leq t, \\, Y_1 = v, \\, J_2 > t \\}\n", " \\\\\n", " & \\geq \\PP \\{E_1 \\leq t\\lambda(u), \\, E_2 > t\\lambda(v) \\} \\PP\\{ Y_1 = v \\}\n", " \\\\\n", " & = \\PP \\{E_1 \\leq t\\lambda(u)\\} \n", " \\PP \\{ E_2 > t\\lambda(v) \\} K(u, v) \n", " \\\\\n", " & > 0\n", "\\end{aligned}\n", "\n", "\n", "Now suppose there is a $Q$-positive probability flow $(z_i)_{i=0}^m$ from $x$\n", "to $y$.\n", "\n", "If we fix $t > 0$ and repeatedly apply [(3.7)](https://jstac.github.io/continuous_time_mcs/markov_prop.html#equation-chapkol-ct2) along with the last\n", "result, we obtain\n", "\n", "$$\n", "P_t(x, y)\n", " \\geq\n", " \\prod_{i=0}^{m-1} P_{t/m} (z_i, z_{i+1}) > 0\n", "$$\n", "\n", "[Theorem 8.2](#equivirr) leads directly to the following strong result." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## \n", "\n", "For a UC Markov semigroup $(P_t)$, the following statements are\n", "equivalent:\n", "\n", "1. $(P_t)$ is irreducible. \n", "1. $P_t(x,y) > 0$ for all $t > 0$ and all $(x,y) \\in S \\times S$. \n", "\n", "\n", ">**Note**\n", ">\n", ">To obtain stable long run behavior in discrete time Markov chains, it is\n", "common to assume that the chain is aperiodic.\n", "\n", "This needs to be assumed on top of irreducibility if one wishes to rule out\n", "all dependence on initial conditions.\n", "\n", "[Corollary 8.1](#perimposs) shows that periodicity is not a concern for irreducible\n", "continuous time Markov chains.\n", "\n", "Positive probability flow from $x$ to $y$ at some $t > 0$ immediately implies\n", "positive flow for all $t > 0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Asymptotic Stabilitiy\n", "\n", "We call Markov semigroup $(P_t)$ **asymptotically stable** if $(P_t)$ has a\n", "unique stationary distribution $\\psi^*$ in $\\dD$ and\n", "\n", "\n", "\n", "$$\n", "\\| \\psi P_t - \\psi^* \\| \\to 0 \\text{ as } t \\to \\infty\n", " \\text{ for all } \\psi \\in \\dD \\tag{8.3}\n", "$$\n", "\n", "Our aim is to establish conditions for asymptotic stability of Markov\n", "semigroups." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Contractivity\n", "\n", "Let’s recall some useful facts about the discrete time case.\n", "\n", "First, if $P$ is any Markov matrix, we have, in the $\\ell_1$ norm,\n", "\n", "\n", "\n", "$$\n", "\\| \\psi P \\| \\leq \\| \\psi \\|\n", " \\text{ for all } \\psi \\in \\dD \\tag{8.4}\n", "$$\n", "\n", "This is because, given $\\psi \\in \\dD$,\n", "\n", "$$\n", "\\| \\psi P \\|\n", " = \\sum_y \\left| \\sum_x \\psi(x) P(x, y) \\right|\n", " \\leq \\sum_y \\sum_x | \\psi(x) | P(x, y)\n", " = \\| \\psi \\|\n", "$$\n", "\n", "By linearity, for $\\psi, \\phi \\in \\dD$, we then have\n", "\n", "$$\n", "\\| \\psi P - \\phi P \\| \\leq \\| \\psi - \\phi \\|\n", "$$\n", "\n", "Hence every Markov operator is contracting on $\\dD$.\n", "\n", "Moreover, if $P$ is everywhere positive, then this inequality is strict:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### (Strict Contractivity)\n", "\n", "If $P$ is a Markov matrix and $P(x, y) > 0$ for all $x, y$, then\n", "\n", "$$\n", "\\| \\psi P - \\phi P \\| < \\| \\psi - \\phi \\|\n", " \\text{ for all } \\psi, \\phi \\in \\dD\n", " \\text{ with } \\psi \\not= \\phi\n", "$$\n", "\n", "The proof follows from the strict triangle inequality, as opposed to the weak\n", "triangle inequality we used to obtain [(8.4)](#equation-allmocontract).\n", "\n", "See, for example, Proposition 3.1.2 of [[Lasota and Mackey, 1994](https://jstac.github.io/continuous_time_mcs/zreferences.html#id3)] or Lemma 8.2.3 of [[Stachurski, 2009](https://jstac.github.io/continuous_time_mcs/zreferences.html#id4)]." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Uniqueness\n", "\n", "Irreducibility of a given Markov chain implies that there are no disjoint\n", "[absorbing sets](https://en.wikipedia.org/wiki/Absorbing_set).\n", "\n", "This in turn leads to uniqueness of stationary distributions:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "Let $(P_t)$ be a UC Markov semigroup on $S$. If $(P_t)$ is irreducible, then\n", "$(P_t)$ has at most one stationary distribution.\n", "\n", "Proof. Suppose to the contrary that $\\psi$ and $\\phi$ are both stationary for\n", "$(P_t)$.\n", "\n", "Since $(P_t)$ is irreducible, we know that $P_1(x,y) > 0$ for all $x,y \\in S$.\n", "\n", "If $\\psi \\not= \\phi$, then, due to positivity of $P_1$, the strict inequality\n", "in [Lemma 8.1](#strictcontract) holds.\n", "\n", "At the same time, by stationarity, $\\| \\psi P - \\phi P \\| = \\| \\psi - \\phi\n", "\\|$. Contradiction." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "An M/M/1 queue with parameters $\\mu, \\lambda$ is a continuous time Markov chain $(X_t)$ on $S = \\ZZ_+$ with with intensity matrix\n", "\n", "\n", "\n", "$$\n", "Q=\\begin{pmatrix}\n", " -\\lambda & \\lambda & 0 & 0 & \\cdots \\\\\n", " \\mu & -(\\mu + \\lambda) & \\lambda & 0 & \\cdots \\\\\n", " 0 & \\mu & -(\\mu + \\lambda) & \\lambda & \\cdots\\\\\n", " \\vdots & \\vdots & \\vdots & \\vdots & \\ddots\n", "\\end{pmatrix} \\tag{8.5}\n", "$$\n", "\n", "The chain $(X_t)$ records the length of the queue at each moment in time.\n", "\n", "The intensity matrix captures the idea that customers flow into the queue at\n", "rate $\\lambda$ and are served (and hence leave the queue) at rate $\\mu$.\n", "\n", "If $\\lambda$ and $\\mu$ are both positive, then there is a $Q$-positive\n", "probability flow between any two states, in both directions, so the\n", "corresponding semigroup $(P_t)$ is irreducible.\n", "\n", "[Theorem 8.3](#uniirr) now tells us that $(P_t)$ has at most one stationary\n", "distribution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Stability from the Skeleton\n", "\n", "Recall the definition of asymptotic stability given in [(8.3)](#equation-asyms).\n", "\n", "Analogously, we call an individual Markov operator $P$ asymptotically stable if\n", "$P$ has a unique stationary distribution $\\psi^*$ in $\\dD$ and\n", "$\\psi P^n \\to \\psi^*$ as $n \\to \\infty$ for all $\\psi \\in \\dD$.\n", "\n", "The next result gives a connection between discrete and continuous stability.\n", "\n", "The critical ingredient linking these two concepts is the contractivity in\n", "[(8.4)](#equation-allmocontract)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "Let $(P_t)$ be a Markov semigroup. If there exists an $s > 0$ such that the\n", "Markov matrix $P_s$ is asymptotically stable, then $(P_t)$ is asymptotically\n", "stable with the same stationary distribution.\n", "\n", "Proof. Let $(P_t)$ and $s$ be as in the statement of [Lemma 8.2](#stabskel).\n", "\n", "Let $\\psi^*$ be the stationary distribution of $P_s$. Fix $\\psi \\in \\dD$ and\n", "$\\epsilon > 0$.\n", "\n", "By stability of $P_s$, we can take an $n \\in \\NN$ such that\n", "$\\| \\psi P_s^n - \\psi^* \\| < \\epsilon$.\n", "\n", "Pick any $t > sn$. Set $h := t - sn$.\n", "\n", "By the contractivity in [(8.4)](#equation-allmocontract) and $P_{sn} = P_s^n$, we have\n", "\n", "$$\n", "\\| \\psi P_t - \\psi^* \\|\n", " = \\| \\psi P_{sn} P_h - \\psi^* P_h \\|\n", " \\leq \\| \\psi P_{sn} - \\psi^* \\|\n", " < \\epsilon\n", "$$\n", "\n", "Hence asymptotic stability holds for $(P_t)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Stability via Drift\n", "\n", "In this section we address drift conditions, which are a powerful method for\n", "obtaining asymptotic stability when the state space can be infinite.\n", "\n", "The idea is to show that the state tends to drift back to a finite set over\n", "time.\n", "\n", "Such drift, when combined with the contractivity in\n", "[Lemma 8.1](#strictcontract), is enough to give global stability.\n", "\n", "The next theorem gives a useful version of this class of results." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "Let $(P_t)$ be a UC Markov semigroup with intensity matrix $Q$. If $(P_t)$ is\n", "irreducible and there exists a function $v \\colon S \\to \\RR_+$, a finite set\n", "$F \\subset S$ and positive constants $\\epsilon$ and $M$ such that\n", "\n", "$$\n", "\\sum_y Q(x, y) v(y) \n", " \\leq \n", " \\begin{cases}\n", " M & \\text{ if } x \\in F \\text{ and }\n", " \\\\\n", " - \\epsilon & \\text{ otherwise } \n", " \\end{cases}\n", "$$\n", "\n", "then $(P_t)$ is asymptotically stable.\n", "\n", "The proof of [Theorem 8.4](#sdrift) can be found in [[Pichór *et al.*, 2012](https://jstac.github.io/continuous_time_mcs/zreferences.html#id2)]." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "Consider again the M/M/1 queue on $\\ZZ_+$ with intensity matrix [(8.5)](#equation-mm1q).\n", "\n", "Suppose that $\\lambda < \\mu$.\n", "\n", "It is intuitive that, in this case, the queue length will not\n", "tend to infinity (since the service rate is higher than the arrival rate).\n", "\n", "This intuition can be confirmed via [Theorem 8.4](#sdrift), after setting $v(j) =\n", "j$.\n", "\n", "Indeed, we have, for any $i \\geq 1$,\n", "\n", "$$\n", "\\sum_{j \\geq 0} Q(i, j) v(j) \n", " = (i-1) \\mu - i (\\mu + \\lambda) + (i+1) \\lambda\n", " = \\lambda - \\mu\n", "$$\n", "\n", "Setting $F=\\{0\\}$ and $M = \\lambda - \\mu = - \\epsilon$, we see that the conditions\n", "of [Theorem 8.4](#sdrift) hold.\n", "\n", "Hence the associated semigroup $(P_t)$ is asymptotically stable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### \n", "\n", "If $(P_t)$ is an irreducible UC Markov semigroup and $S$ is finite, then\n", "$(P_t)$ is asymptotically stable.\n", "\n", "A solved exercise below asks you to confirm this." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise \n", "\n", "Let $(P_t)$ be a Markov semigroup. True or false:\n", "for this semigroup, every state $x$ is accessible from itself." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise \n", "\n", "Let $(\\lambda_k)$ be a bounded non-increasing sequence in $(0, \\infty)$.\n", "\n", "A **pure birth process** starting at zero is a continuous time Markov process\n", "$(X_t)$ on state space $\\ZZ_+$ with intensity matrix\n", "\n", "$$\n", "Q=\\begin{pmatrix}\n", " -\\lambda_0 & \\lambda_0 & 0 & 0 & \\cdots \\\\\n", " 0 & -\\lambda_1 & \\lambda_1 & 0 & \\cdots \\\\\n", " 0 & 0 & -\\lambda_2 & \\lambda_2 & \\cdots\\\\\n", " \\vdots & \\vdots & \\vdots & \\vdots & \\ddots\n", "\\end{pmatrix}\n", "$$\n", "\n", "Show that $(P_t)$, the corresponding Markov semigroup, has no stationary\n", "distribution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise \n", "\n", "Confirm that [Theorem 8.4](#sdrift) implies [Corollary 8.2](#sfinite)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solutions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Solution to Exercise 8.1](https://jstac.github.io/continuous_time_mcs/#ergodicity-ex-1)\n", "\n", "The statement is true. With $t=0$ we have $P_t(x,x) = I(x,x) = 1 > 0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Solution to Exercise 8.2](https://jstac.github.io/continuous_time_mcs/#ergodicity-ex-2)\n", "\n", "Suppose to the contrary that $\\phi \\in \\dD$ and $\\phi Q = 0$.\n", "\n", "Then, for any $j \\geq 1$,\n", "\n", "$$\n", "(\\phi Q)(j) \n", " = \\sum_{i \\geq 0} \\phi(i) Q(i, j)\n", " = - \\lambda_j \\phi(j) + \\lambda_{j-1} \\phi(j-1) \n", " = 0\n", "$$\n", "\n", "Since $(\\lambda_k)$ is non-increasing, it follows that\n", "\n", "$$\n", "\\frac{\\phi(j)}{\\phi(j-1)} = \\frac{\\lambda_{j-1}}{\\lambda_j} \\geq 1\n", "$$\n", "\n", "Therefore, for any $j\\geq 1$, it must be:\n", "\n", "$$\n", "\\phi(j) \\geq \\phi(j-1)\n", "$$\n", "\n", "It follows that $\\phi$ is non-decreasing on $\\ZZ_+$.\n", "\n", "But $\\dD$ contains no non-decreasing functions when the state space is infinite.\n", "(Why?)\n", "\n", "Contradiction." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Solution to Exercise 8.3](https://jstac.github.io/continuous_time_mcs/#ergodicity-ex-3)\n", "\n", "Let $(P_t)$ be an irreducible UC Markov semigroup and let $S$ be finite.\n", "\n", "Pick any positive constants $M, \\epsilon$ and set $v = M$ and $F = S$.\n", "\n", "We then have\n", "\n", "$$\n", "\\sum_y Q(x, y) v(y)\n", " = M \\sum_y Q(x, y)\n", " = 0\n", "$$\n", "\n", "Hence the drift condition in [Theorem 8.4](#sdrift) holds and $(P_t)$ is\n", "asymptotically stable." ] } ], "metadata": { "date": 1634710782.192832, "filename": "ergodicity.md", "kernelspec": null, "title": "Stationarity and Ergodicity" }, "nbformat": 4, "nbformat_minor": 4 }