4-3-Poisson-Properties.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Poisson Process: Section 3 - Properties\n",
    "\n",
    "So far, we have analyzed the Poisson process over time intervals $[0, t]$, using the fact that the number of arrivals $N(t) \\sim \\text{Poisson}(\\lambda t)$.  Unfortunately, this requires that we start counting from time $0$.  How can we analyze the arrivals over a later time interval?  In the bus stop problem, we only considered the first bus that departs at time $d$, with the Poisson process starting at time $0$.  What about the second bus that departs at time $2d$ and takes all the passengers that arrive between $(d, 2d]$?\n",
    "\n",
    "It turns out, due to some special properties of the Poisson process, that analyzing later time intervals is just as easy.  The main idea is that the counting process “renews” or starts over without any memory of the past."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Renewal and Memorylessness\n",
    "\n",
    "Let $\\{N(t),\\, t \\geq 0\\}$ be a Poisson process with rate $\\lambda$.  \n",
    "\n",
    "As usual, we will denote:\n",
    "* $X_i$ the time interval between the $i-1$st and $i$th arrivals, for $i = 1, 2, \\dots$\n",
    "* $S_n$ the time of the $n$th arrival, for $n = 1, 2, \\dots$\n",
    "\n",
    "We want to show that the Poisson process is “memoryless” (analogous to the Markov property in discrete time).  To do so, we will want to show that the future depends only on the present and is independent of the past.\n",
    "\n",
    "* The present is time 0; the process just begins.\n",
    "\n",
    "  There is no past (the process only begins at time $0$).  \n",
    "  \n",
    "  The future will be:\n",
    "    * $X_i \\sim \\text{Exponential}(\\lambda)$ is the time interval between future arrivals, for $i = 1, 2, \\dots$.\n",
    "    * $S_n \\sim \\text{Erlang}(n, \\lambda)$ is the time until the $n$th arrival, for $n = 1, 2, \\dots$\n",
    "    * $N(t) \\sim \\text{Poisson}(\\lambda t)$ is the number of future arrivals over the next $t$ time (the interval $(0, t]$), for $t \\geq 0$.  \n",
    "    \n",
    "    \n",
    "* The present is time $S_1$; the first arrival just occurred.  \n",
    "\n",
    "  The past is $[0, S_1)$.  \n",
    "  \n",
    "  The future will be:\n",
    "    * $X_i \\sim \\text{Exponential}(\\lambda)$ is the time interval between future arrivals, for $i = 2, 3, \\dots$.\n",
    "    * $S_{n+1} - S_1 \\sim \\text{Erlang}(n, \\lambda)$ is the time until the $n+1$st arrival, for $n = 1, 2, \\dots$\n",
    "    * $N(S_1+t) - 1 \\sim \\text{Poisson}(\\lambda t)$ is the number of future arrivals over the next $t$ time (the interval $(S_1, S_1+t]$), for $t \\geq 0$.\n",
    "    \n",
    "    \n",
    "* ...\n",
    "\n",
    "* The present is time $S_k$; the $k$th arrival just occurred.  \n",
    "  \n",
    "  The past is $[0, S_k)$.  \n",
    "  \n",
    "  The future will be:\n",
    "    * $X_i \\sim \\text{Exponential}(\\lambda)$ is the time interval between future arrivals, for $i = k+1, k+2, \\dots$.\n",
    "    * $S_{n+k} - S_k \\sim \\text{Erlang}(n, \\lambda)$ is the time until the $n+k$th arrival, for $n = 1, 2, \\dots$\n",
    "    * $N(S_k+t) - k \\sim \\text{Poisson}(\\lambda t)$ is the number of future arrivals over the next $t$ time (the interval $(S_k, S_k+t]$), for $t \\geq 0$.\n",
    "    \n",
    "    At time $S_k$, the next arrival is at $S_{n+1} = S_n + X_{n+1}$, so $S_{n+1} - S_n = X_{n+1} \\sim \\text{Exponential}(\\lambda)$ and $S_{n+k} - S_k \\sim \\text{Erlang}(n, \\lambda)$. \n",
    "\n",
    "Therefore **the process renews at every arrival**.  At any time $S_n$, the future of the process (additional arrivals) behaves the same (probabilistically) as if it restarted at time 0.\n",
    "\n",
    "What about between arrivals?\n",
    "* The present time is $t$; there have been $N(t)$ arrivals.  \n",
    "* The past is $[0, t)$; the previous arrival was at time $S_{N(t)}$.\n",
    "* The future will be:\n",
    "    * The next arrival occurs at time $S_{N(t)+1}$, so the time until the next arrival is $S_{N(t)+1} - t$.\n",
    "    * The time interval between all subsequent arrivals $i = N(t)+2, N(t)+3, \\dots$ will be $X_i \\sim \\text{Exponential}(\\lambda)$.\n",
    "    * How long until the next arrival?  \n",
    "\n",
    "      Let $r = t - S_{N(t)}$ be the time since the previous arrival, so $S_{N(t)+1} - t = X_{N(t)+1} - r$ and note that $\\{S_{N(t)+1} > t\\} = \\{X_{N(t)+1} > r\\}$.\n",
    "\n",
    "        $$\\begin{aligned}\n",
    "            \\mathsf{P}(S_{N(t)+1} - t > s\\,|\\, S_{N(t)+1} > t) &= \\mathsf{P}(X_{N(t)+1} - r > s\\,|\\, X_{N(t)+1} > r) \\\\\n",
    "            &= \\mathsf{P}(X_{N(t)+1} > r+s\\,|\\, X_{N(t)+1} > r) \\\\\n",
    "            &= \\mathsf{P}(X_{N(t)+1} > s) & \\text{(memoryless property of exponential)} \\\\\n",
    "            &= e^{-\\lambda s}\n",
    "          \\end{aligned}$$\n",
    "      Note that this **does not depend on the past** (the time of the previous arrival does not matter).\n",
    "\n",
    "      The time until the next arrival is **always exponentially distributed** (with rate $\\lambda$), no matter how long it has been since the previous arrival.\n",
    "\n",
    "Therefore **the process renews at any time $t$ and has no memory of the past** (even if $t$ is between arrivals).  At any time $t$, , the future of the process (additional arrivals) behaves the same (probabilistically) as if it restarted from time 0.\n",
    "\n",
    "### Remark (optional)\n",
    "\n",
    "This feature that the process renews at every arrival time $S_n$ does not rely on exponentially distributed $X_i$ (time interval between arrivals) and its memoryless property.  It holds true for any $X_i$ that are independent and identically distributed (according to a continuous non-negative distribution).  For example, if $X_i \\sim \\text{Uniform}[a,b]$, then at every arrival time, the future of the process would behave the same as if it restarted at time 0.  \n",
    "\n",
    "However, for times $t$ between arrivals, renewal requires the exponentially distributed $X_i$.  In the case of $X_i \\sim \\text{Uniform}[a,b]$, it would no longer be true that the process renews at times $t$ between arrivals because the time since the previous arrival matters — for instance, if the time since the previous arrival is $r = t - S_{N(t)}$ then it is impossible for the next arrival to occur after $t + (b - r)$ (since it must be that $X_{N(t)+1} < b$): $$\\mathsf{P}(S_{N(t)+1} > t + (b - r)) = \\mathsf{P}(S_{N(t)+1} - t > b - r) = 0 \\neq \\mathsf{P}(X_1 > b - r)$$\n",
    "\n",
    "This type of process is called a “renewal process”: it renews at every arrival time (but not necessarily at every time between arrivals) and is a generalization of the Poisson process.  In other words, the Poisson process is a special type of renewal process where $X_i \\sim \\text{Exponential}(\\lambda)$ and has the additional property that it renews at any time $t$, not just arrival times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stationary and Independent Increments\n",
    "\n",
    "For any time interval $(a, b]$ we can define the “increment” of the Poisson process as the number of arrivals that occur during that time interval:\n",
    "$$ N(b) - N(a) = \\text{number of arrivals in the time interval $(a, b]$}$$\n",
    "\n",
    "The increments of a Poisson process are **stationary**: \n",
    "$$ N(b) - N(a) \\overset{\\mathsf{dist}}{=} N(b - a) \\sim \\text{Poisson}(\\lambda (b - a))$$\n",
    "That is, the probability distribution of the number of arrivals during an interval **only depends on the length of the inteval**,  not the starting point of the interval.  (In this way, the stochastic dynamics do not change over time, hence “stationary.”)\n",
    "\n",
    "The increments of a Poisson process are **independent**.  If $(a, b]$ and $(c, d]$ are **non-overlapping** time intervals, then\n",
    "$$N(b) - N(a) \\text{ and } N(d) - N(c) \\text{ are independent}$$\n",
    "\n",
    "Each of these properties follows easily from the result that the Poisson process is memoryless and renews at any time $t$.\n",
    "\n",
    "**The Poisson process is the only counting process that has stationary and independent increments.**  In fact, it is possible to start from the assumption of stationary and independent increments, then conclude that the interarrival times must be independent and identically distributed according to an $\\text{Exponential}(\\lambda)$ distribution.  This is similar to the fact that the exponential distribution is the only (continuous) distribution with the memoryless property.  It is possible to start from the assumption of the memoryless property and then conclude that the distribution must be exponential (a proof is given [here](https://en.wikipedia.org/wiki/Memorylessness#Continuous_memorylessness))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Bus Stop\n",
    "\n",
    "Consider the bus stop example where passengers arrive according to a Poisson process with rate $\\lambda = 2$ passengers per minute and buses depart every $d = 10$ minutes.\n",
    "\n",
    "The number of passengers who arrive during a time period $(a, b]$ is $N(b) - N(a)$, a Poisson increment, which we now know has probability distribution $\\text{Poisson}(\\lambda (b - a))$.  (We can now view the analysis in Section 2 as the special case of $a = 0$.)\n",
    "\n",
    "Moreover, non-overlapping increments are independent, so the number of passengers that arrive in the first minute $(0, 1]$ is independent of the number of passengers that arrive in the last minute $(9, 10]$ before the first bus departs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.1\n",
    "\n",
    "Continuing with the bus stop example where passengers arrive according to a Poisson process with rate $\\lambda = 2$ passengers per minute and buses depart every $d = 10$ minutes.  Assume that the bus stop is empty at time $0$ and the first bus departs at time $10$ minutes, the second bus departs at time $20$ minutes, etc.\n",
    "* What is the probability that at least one passenger arrives in the last minute before the first bus departs?\n",
    "* What is the expected number of passengers on the first bus that wait one minute or less? \n",
    "* What is the expected number of passengers on the second bus that wait one minute or less? \n",
    "* What is the probability that there are exactly 5 passengers on the first bus who waited less than 3 minutes?\n",
    "* What is the probability that there are 20 passengers on the first bus and 1 passenger on the second bus?\n",
    "* What is the expected number of passengers on a bus that waited at least 3 minutes but no more than 7 minutes?\n",
    "* Given that there are $10$ passengers waiting at $t = 5$ minutes, what is the expected arrival time of the $12$th passenger?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Superposition and Partition Properties\n",
    "\n",
    "**Superposition Property:** “merging” multiple Poisson processes into a single process.\n",
    "\n",
    "Suppose there are two independent independent Poisson processes: $\\{N_1(t),\\, t \\geq 0\\}$ with rate $\\lambda_1$ and $\\{N_2(t),\\, t \\geq 0\\}$ with rate $\\lambda_2$:\n",
    "* $\\{N_1(t),\\, t \\geq 0\\}$ is the counting process of “type 1” arrivals\n",
    "* $\\{N_2(t),\\, t \\geq 0\\}$ is the counting process of “type 2” arrivals\n",
    "\n",
    "So $N_1(t) + N_2(t)$ is the total number of arrivals (of either type) by time $t$.  \n",
    "\n",
    "Then $\\{N(t),\\, t \\geq 0\\}$ is a Poisson process with rate $\\lambda_1 + \\lambda_2$.\n",
    "\n",
    "**Partition Property:** “splitting” a single Poisson process into multiple processes.\n",
    "\n",
    "Let $\\{N(t),\\, t \\geq 0\\}$ be a Poisson process with rate $\\lambda$ and suppose we randomly categorize each arrival as either “type 1” or “type 2” where:\n",
    "$$\\mathsf{P}(\\text{arrival is type 1}) = p = 1 - \\mathsf{P}(\\text{arrival is type 2})$$\n",
    "and this categorization is independent of everything else.  (You can think of flipping a coin that lands heads with probability $p$ and categorizing an arrival as type 1 if it lands heads and type 2 if it lands tails.)\n",
    "\n",
    "We can therefore partition (or split) the Poisson process $\\{N(t),\\, t \\geq 0\\}$ into two separate arrival processes:\n",
    "* Let $\\{N_1(t),\\, t \\geq 0\\}$ be the counting process of type 1 arrivals (so $N_1(t)$ is the number of type 1 arrivals by time $t$)\n",
    "* Let $\\{N_2(t),\\, t \\geq 0\\}$ be the counting process of type 2 arrivals (so $N_2(t)$ is the number of type 2 arrivals by time $t$)\n",
    "\n",
    "Then $\\{N_1(t),\\, t \\geq 0\\}$ is a Poisson process with rate $p \\lambda$ and $\\{N_2(t),\\, t \\geq 0\\}$ is a Poisson process with rate $(1 - p) \\lambda$ and the two processes are independent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.2 (Optional)\n",
    "\n",
    "Prove the superposition property using the fact that the Poisson process is the only counting process with stationary and independent increments:\n",
    "\n",
    "Assume that:\n",
    "* $\\{N_1(t),\\, t \\geq 0\\}$ has stationary and independent increments.  That is, for non-overlapping intervals $(a, b]$ and $(c, d]$:\n",
    "    $$\\begin{aligned}\n",
    "        N_1(b) - N_1(a) &\\overset{\\mathsf{dist}}{=} N_1(b - a) & \\text{(stationary)}\\\\\n",
    "        N_1(b) - N_1(a) &\\perp N_1(d) - N_1(c) & \\text{(independent)}\n",
    "      \\end{aligned}$$\n",
    "\n",
    "* $\\{N_2(t),\\, t \\geq 0\\}$ has stationary and independent increments.\n",
    "  \n",
    "* Any increment of $N_1(t)$ is independent of any increment of $N_2(t)$.\n",
    "\n",
    "Show that $\\{N_1(t) + N_2(t),\\, t \\geq 0\\}$ has stationary and independent increments:\n",
    "$$\\begin{aligned}\n",
    "    (N_1(b) + N_2(b)) - (N_1(a) + N_2(a)) &\\overset{\\mathsf{dist}}{=} N_1(b - a) + N_2(b - a) \\\\\n",
    "    (N_1(b) + N_2(b)) - (N_1(a) + N_2(a)) &\\perp (N_1(d) + N_2(d)) - (N_1(c) + N_2(c))\n",
    "  \\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.3 (Optional)\n",
    "\n",
    "For each of these properties, it is important that the pieces are independent.  To see why this is the case, consider the following counterexamples.\n",
    "\n",
    "**Superposition:** Let $\\{N_1(t),\\, t \\geq 0\\}$ be a Poisson process with rate $\\lambda_1$ and define $N_2(t) = N_1(t/2)$ for all $t \\geq 0$. ($\\{N_2(t),\\, t \\geq 0\\}$ is just the original process at half-speed).  It is (fairly) easy to check that $\\{N_2(t),\\, t \\geq 0\\}$ is a Poisson process with rate $\\frac{1}{2}\\lambda_1$, but it is obviously not independent of $\\{N_1(t),\\, t \\geq 0\\}$.  Argue that $\\{N_1(t) + N_2(t),\\, t \\geq 0\\}$ **is not** a Poisson process.\n",
    "\n",
    "**Partition:** Let $\\{N(t),\\, t \\geq 0\\}$ be a Poisson process with rate $\\lambda$ and categorize each arrival as follow: every odd arrival is type 1 and every even arrival is type 2 (so the types simply alternate).  Argue that $\\{N_i(t),\\, t \\geq 0\\}$, the arrival process of type $i$, **is not** a Poisson process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.4\n",
    "\n",
    "Suppose that we model passengers arriving to the bus stop (Stanford Circle) as those going to stop 1 (Metrorail) or stop 2 (Ponce Garage) (and for simplicity, no other destinations).  In particular:\n",
    "* Passengers going to stop 1 arrive according to $\\{N_1(t),\\, t \\geq 0\\}$, a Poisson process with rate $\\lambda_1 = 1.2$.\n",
    "* Passengers going to stop 2 arrive according to $\\{N_2(t),\\, t \\geq 0\\}$, a Poisson process with rate $\\lambda_2 = 0.8$.\n",
    "* The two Poisson processes are independent.\n",
    "\n",
    "Assume that buses depart every $d = 10$ minutes and that at time $0$, a bus has just departed.\n",
    "* What is the probability that the first bus has 20 passengers?\n",
    "* What is the probability that the first bus has 13 passengers and all of them get off at stop 1?\n",
    "* What is the expected number of passengers on a bus that are going to each stop?\n",
    "* What is the probability that the first passenger to arrive at the bus stop is going to stop 2?  \n",
    "  (*Hint:* Use the result from Homework 3, Problem 3(b).)\n",
    "* What is the probability that the first passenger to arrive after 5 minutes is going to stop 1?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.5\n",
    "\n",
    "Customers arrive to the drive-through of a fast-food restaurant according to a Poisson process with rate $\\lambda = 2$ per minute.  Suppose that there are only two menu options and a customer selects Meal #1 with probability $p = 0.8$ and Meal #2 with probability $1 - p = 0.2$ (independent of all else).\n",
    "\n",
    "* What is the expected number of drive-through customers in one hour?\n",
    "* What is the expected number of #1 Meals sold in an hour?  #2 Meals?  (Sold in the drive-through.)\n",
    "* What is the probability that the drive-through sells 20 #2 Meals in an hour?\n",
    "* A customer just ordered Meal #1.  What is the probability that the next customer orders the same?\n",
    "* Over the past 20 minutes the drive-through served 30 customers and every one of them ordered Meal #1.  What is the probability that the next customer orders Meal #2?\n",
    "* Suppose the price of Meal #1 is \\\\$5 and the price of Meal #2 is \\\\$7.  What is the expected revenue from the drive-through in one hour?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "Let $\\{N(t),\\, t \\geq 0\\}$ be a Poisson process with rate $\\lambda$.\n",
    "\n",
    "Then:\n",
    "* The process renews at any time $t$.\n",
    "* The process has stationary increments:\n",
    "  $$\\mathsf{P}(N(b) - N(a) \\leq n) = \\mathsf{P}(N(b - a) \\leq n)$$\n",
    "  for any time interval $(a, b]$.\n",
    "* The process has independent increments:\n",
    "  $$N(b) - N(a) \\text{ and } N(d) - N(c) \\text{ are independent}$$\n",
    "  for any non-overlapping intervals $(a, b]$ and $(c, d]$.\n",
    "* “Superposition property”: If $\\{N_1(t),\\, t \\geq 0\\}$ and $\\{N_2(t),\\, t \\geq 0\\}$ are independent Poisson processes with rates $\\lambda_1$ and $\\lambda_2$ (respectively), then $\\{N_1(t) + N_2(t),\\, t \\geq 0\\}$ is a Poisson process with rate $\\lambda_1 + \\lambda_2$.\n",
    "* “Partition property”: If each arrival of the Poisson process is categorized as “type 1” with probability $p$ and “type 2” with probability $1 - p$ then the arrival process of “type 1” arrivals is a Poisson process with rate $p \\lambda$ and the process of “type 2” arrivals is a Poisson process with rate $(1 - p) \\lambda$ and these two processes are independent."
   ]
  }
 ],
 "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
}