4-0-Poisson-Preliminaries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# The Poisson Process: Section 0 - Preliminaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exponential Distribution\n",
    "\n",
    "The exponential distribution is a **continuous**, non-negative probability distribution on $[0, \\infty)$.\n",
    "\n",
    "Let $X \\sim \\text{Exponential}(\\lambda)$:\n",
    "* $\\displaystyle F(x) \\overset{\\mathsf{def}}{=} \\mathsf{P}(X \\leq x) = 1 - e^{-\\lambda x}$\n",
    "* $\\displaystyle f(x) \\overset{\\mathsf{def}}{=} \\frac{d F(x)}{dx} = \\lambda e^{-\\lambda x}$\n",
    "* $\\displaystyle M_X(\\theta) \\overset{\\mathsf{def}}{=} \\mathsf{E}\\left[e^{\\theta X}\\right] = \\frac{\\lambda}{\\lambda - \\theta}$ (for $\\theta < \\lambda$).\n",
    "\n",
    "It is the *unique* continuous distribution that satisfies the “memoryless” property:\n",
    "$$\\mathsf{P}(X > t+s\\,|\\,X > t) = \\mathsf{P}(X > s)$$\n",
    "Suppose $X \\sim \\text{Exponential}(\\lambda)$ represents the lifetime of a lightbulb – after $X$ hours, the bulb burns out.  If the bulb has lasted $t$ hours, what is the probability it lasts at least $s$ hours more?  By the memoryless property, it is the same as the probability a new lightbulb lasts $s$ hours.  In this sense, the lightbulb has no “memory” of being on for $t$ hours; it might as well be new."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Poisson Distribution\n",
    "\n",
    "The Poisson distribution is a **discrete**, non-negative probability distribution on $\\{0, 1, 2, \\dots\\}$\n",
    "\n",
    "Let $X \\sim \\text{Poisson}(\\lambda)$:\n",
    "* $\\displaystyle \\mathsf{P}(X = k) = \\frac{\\lambda^k}{k!} e^{-\\lambda}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Erlang Distribution\n",
    "\n",
    "The Erlang distribution is a **continuous**, non-negative probability distribution on $[0, \\infty)$.\n",
    "\n",
    "Let $X \\sim \\text{Erlang}(n, \\lambda)$:\n",
    "* $\\displaystyle F(x) = 1 - e^{-\\lambda x} \\sum_{k=0}^{n-1} \\frac{(\\lambda x)^k}{k!}$\n",
    "* $\\displaystyle f(x) = \\frac{\\lambda^n x^{n-1}}{(n-1)!} e^{-\\lambda x}$\n",
    "* $\\displaystyle M_X(\\theta) = \\left(\\frac{\\lambda}{\\lambda - \\theta}\\right)^n$ (for $\\theta < \\lambda$).\n",
    "\n",
    "(Note, this is a special case of the [Gamma distribution](https://en.m.wikipedia.org/wiki/Gamma_distribution) where the shape parameter is an integer.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Moment Generating Functions\n",
    "\n",
    "Suppose $X_1, \\dots, X_n$ are independent and identically distributed $\\text{Bernoulli}(p)$ random variables:\n",
    "$$\\mathsf{P}(X_i = 1) = p = 1 - \\mathsf{P}(X_i = 0)$$\n",
    "Define $S_n$ to be the sum\n",
    "$$S_n \\overset{\\mathsf{def}}{=} \\sum_{i=1}^n X_i$$\n",
    "What is the distribution of $S_n$?\n",
    "\n",
    "You may recall that $S_n \\sim \\text{Binomial}(n, p)$:\n",
    "$$\\mathsf{P}(S_n = k) = \\binom{n}{k} p^k (1 - p)^{n-k} \\qquad k = 0, 1, 2, \\dots, n$$\n",
    "How can we derive this using moment generating functions?\n",
    "\n",
    "The MGF of a $X \\sim \\text{Bernoulli}(p)$ random variable is:\n",
    "$$\\begin{aligned}\n",
    "    \\mathsf{E}\\left[e^{-\\theta X}\\right] &= \\sum_{k=0}^1 e^{-\\theta k} \\mathsf{P}(X = k) \\\\\n",
    "    %&= \\mathsf{P}(X = 0) + e^{-\\theta} \\mathsf{P}(X = 1) \\\\\n",
    "    %&= 1 - p + e^{-\\theta} p \\\\\n",
    "    &= p e^{-\\theta} + 1 - p\n",
    "  \\end{aligned}$$\n",
    "\n",
    "The MGF of a $Y \\sim \\text{Binomial}(n, p)$ random variable is:\n",
    "$$\\begin{aligned}\n",
    "    \\mathsf{E}\\left[e^{-\\theta Y}\\right] &= \\sum_{k=0}^n e^{-\\theta k} \\mathsf{P}(Y = k) \\\\\n",
    "    &= \\sum_{k=0}^n e^{-\\theta k} \\binom{n}{k} p^k (1 - p)^{n-k} \\\\\n",
    "    &= \\sum_{k=0}^n \\binom{n}{k} \\left(p e^{-\\theta}\\right)^k (1 - p)^{n-k} \\\\\n",
    "    &= (p e^{-\\theta} + 1 - p)^n\n",
    "  \\end{aligned}$$\n",
    "(The last step uses the [binomial theorem](https://en.m.wikipedia.org/wiki/Binomial_theorem#Theorem_statement).)\n",
    "\n",
    "We want to show that the MGF of $S_n$ is equal to the MGF of a binomial random variable:\n",
    "$$\\begin{aligned}\n",
    "    \\mathsf{E}\\left[e^{-\\theta S_n}\\right] &= \\mathsf{E}\\left[\\exp\\left(-\\theta \\sum_{i=0}^n X_i\\right)\\right] \\\\\n",
    "    &= \\mathsf{E}\\left[\\prod_{i=0}^n e^{-\\theta X_i}\\right] \\\\\n",
    "    &= \\prod_{i=0}^n \\mathsf{E}\\left[e^{-\\theta X_i}\\right] &\\text{(independent)} \\\\\n",
    "    &= \\left(\\mathsf{E}\\left[e^{-\\theta X_1}\\right]\\right)^n &\\text{(identically distributed)} \\\\\n",
    "    &= \\left(p e^{-\\theta} + 1 - p\\right)^n &\\text{(MGF of $\\text{Bernoulli}(p)$)} \\\\    \n",
    "  \\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 0.1\n",
    "\n",
    "Derive the MGF of a $X \\sim \\text{Exponential}(\\lambda)$ random variable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 0.2\n",
    "\n",
    "Derive the MGF of a $X \\sim \\text{Erlang}(n, \\lambda)$ random variable.\n",
    "\n",
    "*Hint:* If $n$ is an integer\n",
    "$$\\int_0^\\infty x^{n-1} e^{-x} = (n-1)!$$\n",
    "This is a special case of the [Gamma function](https://en.m.wikipedia.org/wiki/Gamma_function)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Memoryless Property of the Geometric Distribution\n",
    "\n",
    "Among continuous distributions, the memoryless property is unique to the Exponential distribution.  However, the Geometric distribution is a discrete distribution that also has the memoryless property.\n",
    "\n",
    "For $X \\sim \\text{Geometric}(p)$\n",
    "$$\\mathsf{P}(X = k) = (1 - p)^{k-1} p \\qquad\\qquad \\mathsf{P}(X > k) = (1 - p)^k$$\n",
    "for $k = 1, 2, \\dots$.\n",
    "\n",
    "Often, this is interpreted in the context of a sequence of independent and identically distributed $\\text{Bernoulli}(p)$ random variables where $X$ represents the number of attempts needed to reach the first “success” (a Bernoulli with value $1$).  For example, if $X = 10$ then the first $9$ attempts were failures and the $10$th attempt was the first success.  In this context, if you have observed $n$ failures without a success, what is the probability of observing an additional $m$ failures without a success?  The memoryless property says that it's the same as the probability of starting anew and observing $m$ failures without a success.  This should be almost obvious, since every attempt is independent, so there is no need to “remember” the first $n$ failures — they have no effect on any future attempt.\n",
    "\n",
    "Mathematically, we show that $X \\sim \\text{Geometric}(p)$ satisfies the memoryless property as follows:\n",
    "$$\\begin{aligned}\n",
    "    \\mathsf{P}(X > n+m \\,|\\, X > n) &= \\frac{\\mathsf{P}(X > n + m \\text{ and } X > n)}{\\mathsf{P}(X > n)} \\\\\n",
    "    &= \\frac{\\mathsf{P}(X > n + m)}{\\mathsf{P}(X > n)} &\\text{since }\\{X > n\\} \\subseteq \\{X > n + m\\}\\\\\n",
    "    &= \\frac{(1 - p)^{n+m}}{(1 - p)^{n}} \\\\\n",
    "    &= (1 - p)^m \\\\\n",
    "    &= \\mathsf{P}(X > m)\n",
    "  \\end{aligned}$$"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}