6-2-Queueing-CTMC.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queueing Theory: Section 2 - Continuous-Time Markov Chain Specification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the headcount process $\\{X(t),\\, t \\geq 0\\}$ where $X(t)$ represents the number of customers in the system at time $t$.  So $X(t) = 0$ if the system is empty (and the server is idle) at time $t$, $X(t) = 1$ if there is one customer in service and no customers waiting, $X(t) = 5$ if there is one customer in service and two customers waiting, etc.\n",
    "\n",
    "Assume that customers arrive according to a Poisson process with rate $\\lambda$ and each customer has a service requirement that is random and follows an $\\text{Exponential}(\\mu)$ distribution (independent of all else)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CTMC Formulation\n",
    "\n",
    "How can we model the headcount process as a continuous-time Markov chain on $\\mathcal{S} = \\{0, 1, 2, \\dots\\}$?  We want to come up with transition probabilities $p_{ij}$ (for the embedded DTMC) and holding time parameters $v_i$ for all $i, j \\in \\mathcal{S}$ and check that the dynamics of the system satisfy the Markov property.\n",
    "\n",
    "Suppose $X(t) = i$ for some $i \\geq 1$ (so there is a customer in service) and it has been $r$ time units since the last arrival and $s$ time units since the customer began service.  \n",
    "\n",
    "The process stays in state $i$ until the next customer arrives (moves to state $i+1$) or the customer completes service and departs (moves to state $i-1$).\n",
    "\n",
    "To figure out the transition probabilities $p_{i,i+1}$, $p_{i,i-1}$ and holding time parameter $v_i$, we need to get a handle on how long until the next arrival and departure.\n",
    "* The time until the next arrival is $A \\sim \\text{Exponential}(\\lambda)$ since the Poisson process renews at any time.\n",
    "* The time until the next departure is $D \\sim \\text{Exponential}(\\mu)$ due to the memoryless property of the exponential distribution (it does not matter that the customer has already been in service for $s$ time units).\n",
    "\n",
    "Therefore, for $X(t) = i$, $i \\geq 1$\n",
    "* The time until the next transition is $\\min\\{A, D\\} \\sim \\text{Exponential}(\\lambda + \\mu)$.\n",
    "* The probability that the next transition is an arrival is $\\mathsf{P}(A < D) = \\lambda/(\\lambda + \\mu)$\n",
    "* The probability that the next transition is a departure is $\\mathsf{P}(D < A) = \\mu/(\\lambda + \\mu)$\n",
    "\n",
    "For $X(t) = 0$, the next transition must be an arrival and the time until that occurs $\\sim \\text{Exponential}(\\lambda)$.\n",
    "\n",
    "Putting this together into a specification for CTMC on $\\mathcal{S} = \\{0, 1, 2, \\dots\\}$\n",
    "\n",
    "$$\\begin{aligned}\n",
    "    \\text{state $0$:}&& p_{01} &= 1 & v_0 &= \\lambda \\\\\n",
    "    \\ \\\\\n",
    "    \\text{state $i \\geq 1$:}&& p_{ij} &= \\begin{cases} \\displaystyle\\frac{\\lambda}{\\lambda+\\mu} & j = i+1 \\\\ \\displaystyle\\frac{\\mu}{\\lambda+\\mu} & j = i-1 \\\\ 0 & \\text{otherwise} \\end{cases} & v_i &= (\\lambda+\\mu)\n",
    "  \\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.1\n",
    "\n",
    "Uniformize the CTMC formulated above and find the stationary distribution of the embedded DTMC of the uniformized CTMC.\n",
    "\n",
    "(*Hint:* Compare to the reflected random walk from Section 3 of The Random Walk.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stationary Distribution\n",
    "\n",
    "Now that we've specified a CTMC, we can (try to) solve for its stationary distribution.  Since the state space is infinite, we are not guaranteed that a stationary distribution exists.\n",
    "\n",
    "We will often interpret the stationary distribution (when it exists) as the **“steady-state“ distribution**: $\\pi_j = \\lim_{t \\to \\infty} p_{ij}(t)$.  When the system has been running for a long time, then (no matter the initial starting state), it will be in state $j$ with probability $\\pi_j$; it has reached steady-state and remains (statistically) unchanged.\n",
    "\n",
    "The balance equations for this CTMC are:\n",
    "\n",
    "* state $0$\n",
    "    $$\\begin{aligned}\n",
    "        v_0 \\pi_0 &= v_1 \\pi_1 p_{10} \\\\\n",
    "        \\lambda \\pi_0 &= (\\lambda + \\mu) \\pi_1 \\frac{\\mu}{\\lambda + \\mu} \\\\\n",
    "        \\lambda \\pi_0 &= \\mu \\pi_1 \\\\\n",
    "      \\end{aligned}$$\n",
    "* state $1$\n",
    "    $$\\begin{aligned}\n",
    "        v_1 \\pi_1 &= v_0 \\pi_0 p_{01} + v_2 \\pi_2 p_{21} \\\\\n",
    "        (\\lambda + \\mu) \\pi_1 &= \\lambda \\pi_0 + (\\lambda + \\mu) \\pi_2 \\frac{\\mu}{\\lambda + \\mu} \\\\\n",
    "        (\\lambda + \\mu) \\pi_1 &= \\lambda \\pi_0 + \\mu \\pi_2 \\\\\n",
    "      \\end{aligned}$$\n",
    "* states $i \\geq 2$:\n",
    "    $$\\begin{aligned}\n",
    "        v_i \\pi_i &= v_{i-1} \\pi_{i-1} p_{i-1,i} + v_{i+1} \\pi_{i+1} p_{i+1,i} \\\\\n",
    "        (\\lambda + \\mu) \\pi_i &= (\\lambda+\\mu) \\pi_{i-1} \\frac{\\lambda}{\\lambda+\\mu} + (\\lambda+\\mu) \\pi_{i+1} \\frac{\\mu}{\\lambda+\\mu} \\\\\n",
    "        (\\lambda + \\mu) \\pi_i &= \\lambda \\pi_{i-1} + \\mu \\pi_{i+1} \\\\\n",
    "      \\end{aligned}$$\n",
    "\n",
    "That is,\n",
    "$$\\begin{aligned}\n",
    "    \\lambda \\pi_0 &= \\mu \\pi_1 \\\\\n",
    "    (\\lambda + \\mu) \\pi_i &= \\lambda \\pi_{i-1} + \\mu \\pi_{i+1} &i \\geq 1 \\\\\n",
    "  \\end{aligned}$$\n",
    "We can use induction to verify the recursion:\n",
    "$$\\lambda \\pi_{i-1} = \\mu \\pi_i$$.\n",
    "* Base case: $\\lambda \\pi_0 = \\mu \\pi_1$ is simply the first balance equation.\n",
    "* Inductive step:  \n",
    "    Assume $\\lambda \\pi_{i-1} = \\mu \\pi_i$ then:\n",
    "    $$\\begin{aligned}\n",
    "        (\\lambda + \\mu) \\pi_i &= \\lambda \\pi_{i-1} + \\mu \\pi_{i+1} \\\\\n",
    "        (\\lambda + \\mu) \\pi_i &= \\mu \\pi_i + \\mu \\pi_{i+1} \\\\\n",
    "        \\lambda \\pi_i &= \\mu \\pi_{i+1}\n",
    "      \\end{aligned}$$\n",
    "\n",
    "Therefore,\n",
    "$$\\pi_i = \\frac{\\lambda}{\\mu} \\pi_{i-1} \\qquad i = 1, 2, 3, \\dots$$\n",
    "which implies that\n",
    "$$\\pi_i = \\left(\\frac{\\lambda}{\\mu}\\right)^i \\pi_0 \\qquad i = 0, 1, 2, \\dots$$\n",
    "\n",
    "Finally, for $\\lambda < \\mu$:\n",
    "$$\\sum_{i=0}^\\infty \\pi_i = \\pi_0 \\sum_{i=0}^\\infty \\left(\\frac{\\lambda}{\\mu}\\right)^i = \\frac{\\pi_0}{1 - \\frac{\\lambda}{\\mu}} = 1$$\n",
    "so\n",
    "$$\\pi_0 = 1 - \\frac{\\lambda}{\\mu}$$\n",
    "and\n",
    "$$\\pi_i = \\left(\\frac{\\lambda}{\\mu}\\right)^i \\left(1 - \\frac{\\lambda}{\\mu}\\right)$$\n",
    "so the stationary distribution is geometric.  (This should be the same as what you obtained in Exercise 2.1.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.2\n",
    "\n",
    "What is the long-run proportion of time that the lab is idle?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2.3\n",
    "\n",
    "What is the steady-state expected number of samples in the lab?"
   ]
  }
 ],
 "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
}