{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Poisson Processes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Overview\n", "\n", "Counting processes count the number of “arrivals” occurring by a given time\n", "(e.g., the number of visitors to a website, the number of customers arriving at a restaurant, etc.)\n", "\n", "Counting processes become Poisson processes when the time interval between\n", "arrivals is IID and exponentially distributed.\n", "\n", "Exponential distributions and Poisson processes have deep connections to\n", "continuous time Markov chains.\n", "\n", "For example, Poisson processes are one of the simplest nontrivial examples of\n", "a continuous time Markov chain.\n", "\n", "In addition, when continuous time Markov chains jump between states, the time\n", "between jumps is *necessarily* exponentially distributed.\n", "\n", "In discussing Poisson processes, we will use the following imports:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import quantecon as qe\n", "from numba import njit\n", "from scipy.special import factorial, binom" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Counting Processes\n", "\n", "Let’s start with the general case of an arbitrary counting process." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Jumps and Counts\n", "\n", "Let $(J_k)$ be an increasing sequence of nonnegative random variables\n", "satisfying $J_k \\to \\infty$ with probability one.\n", "\n", "For example, $J_k$ might be the time the $k$-th customer arrives at a shop.\n", "\n", "Then\n", "\n", "\n", "\n", "$$\n", "N_t := \\sum_{k \\geq 0} k \\mathbb{1} \\{ J_k \\leq t < J_{k+1} \\} \\tag{2.1}\n", "$$\n", "\n", "is the number of customers that have visited by time $t$.\n", "\n", "The next figure illustrate the definition of $N_t$ for a given jump sequence $\\{J_k\\}$." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "Ks = 0, 1, 2, 3\n", "Js = 0, 0.8, 1.8, 2.1, 3\n", "n = len(Ks)\n", "\n", "fig, ax = plt.subplots()\n", "\n", "ax.plot(Js[:-1], Ks, 'o')\n", "ax.hlines(Ks, Js[:-1], Js[1:], label='$N_t$')\n", "ax.vlines(Js[:-1], (0, Ks, Ks, Ks), Ks, alpha=0.25)\n", "\n", "ax.set(xticks=Js[:-1],\n", " xticklabels=[f'$J_{k}$' for k in range(n)],\n", " yticks=(0, 1, 2, 3),\n", " xlabel='$t$')\n", "\n", "ax.legend(loc='lower right')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An alternative but equivalent definition is\n", "\n", "$$\n", "N_t := \\max \\{k \\geq 0 \\,|\\, J_k \\leq t \\}\n", "$$\n", "\n", "As a function of $t$, the process $N_t$ is called a **counting process**.\n", "\n", "The jump times $(J_k)$ are sometimes called **arrival times** and the\n", "intervals $J_k - J_{k-1}$ are called **wait times** or **holding times**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exponential Holding Times\n", "\n", "A Poisson process is a counting process with independent exponential holding times.\n", "\n", "In particular, suppose that the arrival times are given by $J_0 = 0$ and\n", "\n", "$$\n", "J_k := W_1 + \\cdots W_k\n", "$$\n", "\n", "where $(W_i)$ are IID exponential with some fixed rate $\\lambda$.\n", "\n", "Then the associated counting process $(N_t)$ is called a **Poisson process** with rate $\\lambda$.\n", "\n", "The rationale behind the name is that, for each $t > 0$, the random variable\n", "$N_t$ has the Poisson distribution with parameter $t \\lambda$.\n", "\n", "In other words,\n", "\n", "\n", "\n", "$$\n", "\\PP\\{N_t = k\\} \n", " = e^{-t \\lambda} \\frac{(t \\lambda)^k }{k!}\n", " \\qquad (k = 0, 1, \\ldots) \\tag{2.2}\n", "$$\n", "\n", "For example, since $N_t = 0$ if and only if $W_1 > t$, we have\n", "\n", "$$\n", "\\PP\\{N_t =0\\} \n", " = \\PP\\{W_1 > t\\}\n", " = e^{-t \\lambda}\n", "$$\n", "\n", "and the right hand side agrees with [(2.2)](#equation-poissondist) when $k=0$.\n", "\n", "This sets up a proof by induction, which is time consuming but not difficult\n", "— the details can be found in $\\S29$ of [[Howard, 2017](https://jstac.github.io/continuous_time_mcs/zreferences.html#id13)].\n", "\n", "Another way to show that $N_t$ is Poisson with rate $\\lambda$ is to appeal to\n", "[Lemma 1.1](https://jstac.github.io/continuous_time_mcs/memoryless.html#erlexp).\n", "\n", "We observe that\n", "\n", "$$\n", "\\PP\\{N_t \\leq n\\} \n", " = \\PP\\{J_{n+1} > t\\} \n", " = 1 - \\PP\\{J_{n+1} \\leq t\\}\n", "$$\n", "\n", "Inserting the expression for the Erlang CDF in [(1.5)](https://jstac.github.io/continuous_time_mcs/memoryless.html#equation-erlcdf) with shape $n+1$ and\n", "rate $\\lambda$, we obtain\n", "\n", "$$\n", "\\PP\\{N_t \\leq n\\} \n", " = \\sum_{k=0}^{n} \\frac{(t \\lambda )^k}{k!} e^{-t \\lambda}\n", "$$\n", "\n", "This is the (integer valued) CDF for the Poisson distribution with parameter\n", "$t \\lambda$.\n", "\n", "An exercise at the end of the lecture asks you to verify that $N_t$ is Poisson-$(t \\lambda )$ informally via simulation.\n", "\n", "The next figure shows one realization of a Poisson process $(N_t)$, with jumps\n", "at each new arrival." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "np.random.seed(1234)\n", "T = 5\n", "Ws = np.random.exponential(size=T)\n", "Js = np.cumsum(Ws)\n", "Ys = np.arange(T)\n", "\n", "fig, ax = plt.subplots()\n", "\n", "ax.plot(np.insert(Js, 0, 0)[:-1], Ys, 'o')\n", "ax.hlines(Ys, np.insert(Js, 0, 0)[:-1], Js, label='$N_t$')\n", "ax.vlines(Js[:-1], Ys[:-1], Ys[1:], alpha=0.25)\n", "\n", "ax.set(xticks=[],\n", " yticks=range(Ys.max()+1),\n", " xlabel='time')\n", "\n", "ax.grid(lw=0.2)\n", "ax.legend(loc='lower right')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Stationary Independent Increments\n", "\n", "One of the defining features of a Poisson process is that it has stationary\n", "and independent increments.\n", "\n", "This is due to the memoryless property of exponentials.\n", "\n", "It means that\n", "\n", "1. the variables $\\{N_{t_{i+1}} - N_{t_i}\\}_{i \\in I}$ are independent for any\n", " strictly increasing finite sequence $(t_i)_{i \\in I}$ and \n", "1. the distribution of $N_{t+h} - N_t$ depends on $h$ but not $t$. \n", "\n", "\n", "A detailed proof can be found in Theorem 2.4.3 of [[Norris, 1998](https://jstac.github.io/continuous_time_mcs/zreferences.html#id12)].\n", "\n", "Instead of repeating this, we provide some intuition from a discrete\n", "approximation.\n", "\n", "In the discussion below, we use the following well known fact: If\n", "$(\\theta_n)$ is a sequence such that $n \\theta_n$ converges, then\n", "\n", "\n", "\n", "$$\n", "\\text{Binomial}(n, \\theta_n) \n", " \\approx\n", " \\text{Poisson}(n \\theta_n)\n", " \\quad \\text{for large } n \\tag{2.3}\n", "$$\n", "\n", "(The exercises ask you to examine this claim visually.)\n", "\n", "We now return to [the environment](https://jstac.github.io/continuous_time_mcs/memoryless.html#geomtoexp) where we linked the\n", "geometric distribution to the exponential.\n", "\n", "That is, we fix small $h > 0$ and let $t_i := ih$ for all $i \\in \\ZZ_+$.\n", "\n", "Let $(V_i)$ be IID binary random variables with $\\PP\\{V_i = 1\\} = h \\lambda$ for some $\\lambda > 0$.\n", "\n", "Linking to our previous discussion,\n", "\n", "- either one or zero customers visits a shop at each $t_i$. \n", "- $V_i = 1$ means that a customer visits at time $t_i$. \n", "- Visits occur with probability $h \\lambda$, which is proportional to the\n", " length of the interval between grid points. \n", "\n", "\n", "We learned that the wait time until the first visit is\n", "approximately exponential with rate $t \\lambda$.\n", "\n", "Since $(V_i)$ is IID, the same is true for the second wait time and so on.\n", "\n", "Moreover, these wait times are independent, since they depend on separate\n", "subsets of $(V_i)$.\n", "\n", "Let $\\hat N_t$ count the number of visits by time $t$, as shown in the next figure.\n", "\n", "($V_i = 1$ is indicated by a vertical line at $t_i = i h$.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "fig, ax = plt.subplots()\n", "np.random.seed(1)\n", "T = 10\n", "p = 0.25\n", "B = np.random.uniform(size=T) < p\n", "N = np.cumsum(B)\n", "m = N[-1] # max of N\n", "\n", "t_grid = np.arange(T)\n", "t_ticks = [f'$t_{i}$' for i in t_grid]\n", "ax.set_yticks(range(m+1))\n", "ax.set_xticks(t_grid)\n", "ax.set_xticklabels(t_ticks, fontsize=12)\n", "\n", "ax.step(t_grid, np.insert(N, 0, 0)[:-1], label='$\\hat N_t$')\n", "\n", "for i in t_grid:\n", " if B[i]:\n", " ax.vlines((i,), (0,), (m,), ls='--', lw=0.5)\n", "\n", "ax.legend(loc='center right')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We expect from the discussion above that $(\\hat N_t)$ approximates a Poisson process.\n", "\n", "This intuition is correct because, fixing $t$, letting $k := \\max\\{i \\in\n", "\\ZZ_+ \\,:\\, t_i \\leq t\\}$ and applying [(2.3)](#equation-binpois), we have\n", "\n", "$$\n", "\\hat N_t \n", " = \\sum_{i=1}^k V_i\n", " \\sim \\text{Binomial}(k, h \\lambda)\n", " \\approx\n", " \\text{Poisson}(k h \\lambda )\n", "$$\n", "\n", "Using the fact that $kh = t_k \\approx t$ as $h \\to 0$, we see\n", "that $\\hat N_t$ is approximately Poisson with rate $t \\lambda$, just as we\n", "expected.\n", "\n", "This approximate construction of a Poisson process helps illustrate the\n", "property of stationary independent increments.\n", "\n", "For example, if we fix $s, t$, then $\\hat N_{s + t} - \\hat N_s$ is the number of visits\n", "between $s$ and $s+t$, so that\n", "\n", "$$\n", "\\hat N_{s+t} - \\hat N_s\n", " = \\sum_i V_i \\mathbb 1\\{ s \\leq t_i < s + t \\}\n", "$$\n", "\n", "Suppose there are $k$ grid points between $s$ and $s+t$, so that $t \\approx\n", "kh$.\n", "\n", "Then\n", "\n", "$$\n", "\\hat N_{s+t} - \\hat N_s\n", " \\sim \\text{Binomial}(k, h \\lambda )\n", " \\approx \n", " \\text{Poisson}(k h \\lambda )\n", " \\approx \n", " \\text{Poisson}(t\\lambda)\n", "$$\n", "\n", "This illustrates the idea that, for a Poisson process $(N_t)$, we have\n", "\n", "$$\n", "N_{s+t} - N_s \n", " \\sim \\text{Poisson}(t\\lambda)\n", "$$\n", "\n", "In particular, increments are stationary (the distribution depends on $t$ but not $s$).\n", "\n", "The approximation also illustrates independence of increments, since, in the\n", "approximation, increments depend on separate subsets of $(V_i)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Uniqueness\n", "\n", "What other counting processes have stationary independent increments?\n", "\n", "Remarkably, the answer is none:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## (Characterization of Poisson Processes)\n", "\n", "If $(M_t)$ is a stochastic process supported on $\\ZZ_+$ and starting at 0 with\n", "the property that its increments are stationary and independent, then $(M_t)$ is a Poisson process.\n", "\n", "In particular, there exists a $\\lambda > 0$ such that\n", "\n", "$$\n", "M_{s + t} - M_s\n", " \\sim \\text{Poisson}(t\\lambda)\n", "$$\n", "\n", "for any $s, t$.\n", "\n", "The proof is similar to our earlier proof that the exponential distribution is\n", "the only memoryless distribution.\n", "\n", "Details can be found in Section 6.2 of [[Pardoux, 2008](https://jstac.github.io/continuous_time_mcs/zreferences.html#id11)] or\n", "Theorem 2.4.3 of [[Norris, 1998](https://jstac.github.io/continuous_time_mcs/zreferences.html#id12)].\n", "\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The Restarting Property\n", "\n", "An important consequence of stationary independent increments is the\n", "restarting property, which means that, when simulating, we can freely stop and\n", "restart a Poisson process at any time:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### (Poisson Processes can be Paused and Restarted)\n", "\n", "If $(N_t)$ is a Poisson process, $s > 0$ and\n", "$(M_t)$ is defined by $M_t = N_{s+t} - N_s$ for $t \\geq 0$, then $(M_t)$ is a\n", "Poisson process independent of $(N_r)_{r \\leq s}$.\n", "\n", "Proof. Independence of $(M_t)$ and $(N_r)_{r \\leq s}$ follows from indepenence of the\n", "increments of $(N_t)$.\n", "\n", "In view of the uniqueness statement above, we can verify that $(M_t)$ is a\n", "Poisson process by showing that $(M_t)$ starts at zero, takes values in\n", "$\\ZZ_+$ and has stationary independent increments.\n", "\n", "It is clear that $(M_t)$ starts at zero and takes values in $\\ZZ_+$.\n", "\n", "In addition, if we take any $t < t'$, then\n", "\n", "$$\n", "M_{t'} - M_t = N_{s+t'} - N_{s + t}\n", " \\sim \\text{Poisson}((t' - t) \\lambda)\n", "$$\n", "\n", "Hence $(M_t)$ has stationary increments and,\n", "using the relation $M_{t'} - M_t = N_{s+t'} - N_{s + t}$ again,\n", "the increments are independent as well.\n", "\n", "We conclude that $(N_{s+t} - N_s)_{t \\geq 0}$ is indeed a\n", "Poisson process independent of $(N_r)_{r \\leq s}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise \n", "\n", "Fix $\\lambda > 0$ and draw $\\{W_i\\}$ as IID exponentials with rate $\\lambda$.\n", "\n", "Set $J_n := W_1 + \\cdots W_n$ with $J_0 = 0$ and\n", "$N_t := \\sum_{n \\geq 0} n \\mathbb 1\\{ J_n \\leq t < J_{n+1} \\}$.\n", "\n", "Provide a visual test of the claim that $N_t$ is Poisson with parameter $t\n", "\\lambda$.\n", "\n", "Do this by fixing $t = T$, generating many independent draws of $N_T$ and\n", "comparing the empirical distribution of the sample with a Poisson\n", "distribution with rate $T \\lambda$.\n", "\n", "Try first with $\\lambda = 0.5$ and $T=10$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercise \n", "\n", "In the lecture we used the fact that $\\Binomial(n, \\theta) \\approx \\Poisson(n \\theta)$ when $n$ is large and $\\theta$ is small.\n", "\n", "Investigate this relationship by plotting the distributions side by side.\n", "\n", "Experiment with different values of $n$ and $\\theta$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solutions\n", "\n", ">**Note**\n", ">\n", ">code is currently not supported in sphinx-exercise\n", "so code-cell solutions are immediately after this\n", "solution block." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Solution to Exercise 2.1](https://jstac.github.io/continuous_time_mcs/#poisson-ex-1)\n", "\n", "Here is one solution.\n", "\n", "The figure shows that the fit is already good with a modest sample size.\n", "\n", "Increasing the sample size will further improve the fit." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "λ = 0.5\n", "T = 10\n", "\n", "def poisson(k, r):\n", " \"Poisson pmf with rate r.\"\n", " return np.exp(-r) * (r**k) / factorial(k)\n", "\n", "@njit\n", "def draw_Nt(max_iter=1e5):\n", " J = 0\n", " n = 0\n", " while n < max_iter:\n", " W = np.random.exponential(scale=1/λ)\n", " J += W\n", " if J > T:\n", " return n\n", " n += 1\n", "\n", "@njit\n", "def draw_Nt_sample(num_draws):\n", " draws = np.empty(num_draws)\n", " for i in range(num_draws):\n", " draws[i] = draw_Nt()\n", " return draws\n", "\n", "\n", "sample_size = 10_000\n", "sample = draw_Nt_sample(sample_size)\n", "max_val = sample.max()\n", "vals = np.arange(0, max_val+1)\n", "\n", "fig, ax = plt.subplots()\n", "\n", "ax.plot(vals, [poisson(v, T * λ) for v in vals],\n", " marker='o', label='poisson')\n", "ax.plot(vals, [np.mean(sample==v) for v in vals],\n", " marker='o', label='empirical')\n", "\n", "ax.legend(fontsize=12)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## [Solution to Exercise 2.2](https://jstac.github.io/continuous_time_mcs/#poisson-ex-2)\n", "\n", "Here is one solution. It shows that the approximation is good when $n$ is\n", "large and $\\theta$ is small." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide-output": false }, "outputs": [], "source": [ "def binomial(k, n, p):\n", " # Binomial(n, p) pmf evaluated at k\n", " return binom(n, k) * p**k * (1-p)**(n-k)\n", "\n", "θ_vals = 0.5, 0.2, 0.1\n", "\n", "n_vals = 50, 75, 100\n", "\n", "fig, axes = plt.subplots(len(n_vals), 1, figsize=(6, 12))\n", "\n", "for n, θ, ax in zip(n_vals, θ_vals, axes.flatten()):\n", "\n", " k_grid = np.arange(n)\n", " binom_vals = [binomial(k, n, θ) for k in k_grid]\n", " poisson_vals = [poisson(k, n * θ) for k in k_grid]\n", " ax.plot(k_grid, binom_vals, 'o-', alpha=0.5, label='binomial')\n", " ax.plot(k_grid, poisson_vals, 'o-', alpha=0.5, label='Poisson')\n", " ax.set_title(f'$n={n}$ and $\\\\theta = {θ}$')\n", " ax.legend(fontsize=12)\n", "\n", "fig.tight_layout()\n", "plt.show()" ] } ], "metadata": { "date": 1634710782.8210518, "filename": "poisson.md", "kernelspec": null, "title": "Poisson Processes" }, "nbformat": 4, "nbformat_minor": 4 }