5-2-CTMC-Specification.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Continuous-Time Markov Chains: Section 2 – Mathematical Specification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuous-time Markov chain (CTMC) is a *continuous-time* stochastic process $\\{X(t),\\, t \\geq 0\\}$ that exists on a *discrete* state space $\\mathcal{S}$ and satisfies the Markov property.  The path $\\{X(t),\\, t \\geq 0\\}$ represents the random path of the Markov chain over time (indexed by $t$).  That is, $X(t) = i$ if the Markov chain is in state $i$ at time $t$.\n",
    "\n",
    "## Markov Property\n",
    "\n",
    "In continuous time, the Markov property is stated as follows:\n",
    "$$\\mathsf{P}(X(s + t) = j\\,|\\, X(s) = i \\text{ and } \\{X(u)\\, 0 \\leq u < s\\}) = \\mathsf{P}(X(s + t) = j\\,|\\, X(s) = i)$$\n",
    "for all times $s, t \\geq 0$ and states $i, j \\in \\mathcal{S}$.\n",
    "\n",
    "The interpretation is once again:\n",
    "* The future $X(s + t)$,\n",
    "* given the present $X(s)$,\n",
    "* is independent of the past $\\{X(u)\\, 0 \\leq u < s\\}$.\n",
    "\n",
    "As with DTMCs (and the Poisson process), a CTMC effectively “restarts” at any time $t$, due to the Markov property:\n",
    "$$\\mathsf{P}(X(s + t) = j\\,|\\, X(s) = i) = \\mathsf{P}(X(t) = j\\,|\\, X(0) = i)$$\n",
    "\n",
    "We can therefore specify the dynamics of the CTMC in terms of transition probabilities:\n",
    "$$p_{ij}(t) = \\mathsf{P}(X(t) = j\\,|\\, X(0) = i)$$\n",
    "\n",
    "That is, $p_{ij}(t)$ represents the probability that the Markov chain is in state $j$ at time $t$, given that it starts in state $i$.\n",
    "\n",
    "The Chapman-Kolmogorov equations are:\n",
    "$$p_{ij}(t + s) = \\sum_{k \\in \\mathcal{S}} p_{ik}(t) p_{jk}(s)$$\n",
    "or, as a matrix equation\n",
    "$$\\mathbf{P}(t + s) = \\mathbf{P}(t) \\mathbf{P}(s)$$\n",
    "(**Note:** There are some technical conditions needed for this to be valid.  We will not discuss those in this course.  See Chapter 6.4 of Ross, “Introduction to Probability Models“ for more details.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Embedded DTMC Plus Holding Times\n",
    "\n",
    "A continuous-time Markov chain consists of:\n",
    "* an embedded discrete-time Markov chain (i.e., state space $\\mathcal{S}$ and one-step transition probabilities $\\mathbf{P}$)\n",
    "* holding time parameters $v_i$ for each $i \\in \\mathcal{S}$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Structure and Classification of States\n",
    "\n",
    "Analogous to DTMCs, we can define, in continuous-time, the concepts of accessibility and communication, as well as recurrence and transience:\n",
    "\n",
    "**Definition:** State $j$ is **accessible from** state $i$ if $p_{ij}(t) > 0$ for some $t \\geq 0$.\n",
    "\n",
    "**Notation:** $i \\rightarrow j$\n",
    "\n",
    "(*Intuition:* It is possible for the Markov chain to reach $j$ starting from $i$.  This path may pass through intermediate states.)\n",
    "\n",
    "With the CTMC definition of accessible, we can define “communicate”, ”communication class”, and ”irreducible” just as we did for DTMCs.\n",
    "\n",
    "**Definition:** State $i$ and state $j$ **communicate** if $i \\rightarrow j$ and $j \\rightarrow i$ (each is accessible from the other).\n",
    "\n",
    "**Notation:** $i \\leftrightarrow j$\n",
    "\n",
    "**Definition:** the set of all states that communicate with each other make up a **communication class** (which is a subset of the state space $\\mathcal{S}$)\n",
    "\n",
    "**Definition:** If all the states of a Markov chain belong to a single communication class, then the Markov chain is **irreducible**.\n",
    "\n",
    "Similarly, if we define $\\tau_{ii}$ to be the first return time to a state $i$ (after leaving), then:\n",
    "\n",
    "**Definition:** State $i$ is **transient** if $\\mathsf{P}(\\tau_{ii} < \\infty) < 1$.  Then the Markov chain will visit this state only a finite number of times (and eventually the Markov chain will leave this state and never return).\n",
    "\n",
    "**Definition:** State $i$ is **recurrent** if $\\mathsf{P}(\\tau_{ii} < \\infty) = 1$.  Then the Markov chain will visit this state an infinite number of times.\n",
    "\n",
    "**For a CTMC, all of the properties above are the same as its embedded DTMC.**\n",
    "\n",
    "**Note:** A recurrent state $i$ is positive recurrent if $\\mathsf{E}[\\tau_{ii}] < \\infty$ and null recurrent if $\\mathsf{E}[\\tau_{ii}] = \\infty$.  This property for a CTMC **may be different** from its embedded DTMC."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}