{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Memoryless Distributions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Overview\n",
"\n",
"Markov processes are, by definition, forgetful.\n",
"\n",
"In particular, for any Markov processes, the distribution over future outcomes\n",
"depends only on the current state, rather than the entire history.\n",
"\n",
"In the case of continuous time Markov chains, which jump between discrete\n",
"states, this requires that the amount of elapsed time since the last jump is\n",
"not helpful in predicting the timing of the next jump.\n",
"\n",
"In other words, the jump times are “memoryless”.\n",
"\n",
"It is remarkable that the only distribution on $ \\RR_+ $ with this\n",
"property is the exponential distribution.\n",
"\n",
"Similarly, the only memoryless distribution on $ \\ZZ_+ $ is the geometric\n",
"distribution.\n",
"\n",
"This lecture tries to clarify these ideas.\n",
"\n",
"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": [
"## The Geometric Distribution\n",
"\n",
"Consider betting on a roulette wheel and suppose that red has come up four times in a row.\n",
"\n",
"Since five reds in a row is an unlikely event, many people instinctively feel\n",
"that black is more likely on the fifth spin — “Surely black will come up this time!”\n",
"\n",
"But rational thought tells us such instincts are wrong: the four previous reds make no\n",
"difference to the outcome of the next spin.\n",
"\n",
"(Many casinos offer an unlimited supply of free alcoholic beverages in order to discourage this kind of rational analysis.)\n",
"\n",
"A mathematical restatement of this phenomenon is: the geometric distribution is memoryless."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Memorylessness\n",
"\n",
"Let $ X $ be a random variable supported on the nonnegative integers $ \\ZZ_+ $.\n",
"\n",
"We say that $ X $ is [geometrically distributed](https://en.wikipedia.org/wiki/Geometric_distribution) if, for some $ \\theta $ satisfying $ 0 \\leq \\theta \\leq 1 $,\n",
"\n",
"\n",
"\n",
"$$\n",
"\\PP\\{X = k\\} = (1-\\theta)^k \\theta \n",
" \\qquad (k = 0, 1, \\ldots) \\tag{1.1}\n",
"$$\n",
"\n",
"An example can be constructed from the discussion of the roulette wheel above.\n",
"\n",
"Suppose that,\n",
"\n",
"- the outcome of each spin is either red or black, \n",
"- spins are labeled by $ 0, 1, 2, \\ldots $, \n",
"- on each spin, black occurs with probability $ \\theta $ and \n",
"- outcomes across spins are independent. \n",
"\n",
"\n",
"Then [(1.1)](#equation-geodist) is the probability that the first occurrence of black is at spin $ k $.\n",
"\n",
"(The outcome “black” fails $ k $ times and then succeeds.)\n",
"\n",
"Consistent with our discussion in the introduction, the geometric distribution\n",
"is **memoryless**.\n",
"\n",
"In particular, given any nonnegative integer $ m $, we have\n",
"\n",
"\n",
"\n",
"$$\n",
"\\PP \\{X = m + 1 \\,|\\, X > m \\} = \\theta \\tag{1.2}\n",
"$$\n",
"\n",
"In other words, regardless of how long we have seen only red outcomes, the\n",
"probability of black on the next spin is the same as the unconditional\n",
"probability of getting black on the very first spin.\n",
"\n",
"To establish [(1.2)](#equation-memgeo), we use basic properties of the geometric\n",
"distribution to obtain.\n",
"\n",
"$$\n",
"\\frac{ \\PP \\{X = m + 1 \\text{ and } X > m \\} }\n",
" {\\PP \\{X \\geq m\\}}\n",
" =\n",
" \\frac{ \\PP \\{X = m + 1 \\} }\n",
" {\\PP \\{X > m\\}}\n",
" = \\frac{ (1-\\theta)^{m+1} \\theta }\n",
" {(1-\\theta)^{m+1} }\n",
" = \\theta\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The Exponential Distribution\n",
"\n",
"Later, when we construct continuous time Markov chains, we will need to\n",
"specify the distribution of the holding times, which are the time intervals\n",
"between jumps.\n",
"\n",
"As discussed above (and again below), the holding time distribution must be\n",
"memoryless, so that the chain satisfies the Markov property.\n",
"\n",
"While the geometric distribution is memoryless, its discrete support makes it\n",
"a poor fit for the continuous time case.\n",
"\n",
"Hence we turn to the [exponential distribution](https://en.wikipedia.org/wiki/Exponential_distribution), which is supported on $ \\RR_+ $.\n",
"\n",
"A random variable $ Y $ on $ \\RR_+ $ is called **exponential with rate $ \\lambda $**, denoted by $ Y \\sim \\Exp(\\lambda) $, if\n",
"\n",
"$$\n",
"\\PP\\{Y > y\\} = e^{-\\lambda y}\n",
" \\qquad (y \\geq 0)\n",
"$$\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### From Geometric to Exponential\n",
"\n",
"The exponential distribution can be regarded as the “limit” of the geometric\n",
"distribution.\n",
"\n",
"To illustrate, let us suppose that\n",
"\n",
"- customers enter a shop at discrete times $ t_0, t_1, \\ldots $ \n",
"- these times are evenly spaced, so that $ h = t_{i+1} - t_i $ for some $ h > 0 $ and all $ i \\in \\ZZ_+ $ \n",
"- at each $ t_i $, either zero or one customers enter (no more because $ h $ is small) \n",
"- entry at each $ t_i $ occurs with probability $ \\lambda h $ and is independent over $ i $. \n",
"\n",
"\n",
"The fact that the entry probability is proportional to $ h $ is important in\n",
"what follows.\n",
"\n",
"You can imagine many customers passing by the shop, each entering\n",
"independently.\n",
"\n",
"If we halve the time interval, then we also halve the probability that a\n",
"customer enters.\n",
"\n",
"Let\n",
"\n",
"- $ Y $ be the time of the first arrival at the shop, \n",
"- $ t $ be a given positive number and \n",
"- $ i(h) $ be the largest integer such that $ t_{i(h)} \\leq t $. \n",
"\n",
"\n",
"Note that, as $ h \\to 0 $, the grid becomes finer and $ t_{i(h)} = i(h) h \\to t $.\n",
"\n",
"Writing $ i(h) $ as $ i $ and using the geometric distribution, the probability that\n",
"the first arrival occurs after $ t_{i} $ is $ (1-\\lambda h)^{i} $.\n",
"\n",
"Hence\n",
"\n",
"$$\n",
"\\PP\\{Y > t_{i} \\}\n",
" = (1-\\lambda h)^i\n",
" = \\left( 1- \\frac{\\lambda i h}{i} \\right)^i\n",
"$$\n",
"\n",
"Using the fact that $ e^x = \\lim_{i \\to \\infty}(1 + x/i)^i $ for all $ x $ and $ i\n",
"h = t_i \\to t $, we obtain, for large $ i $,\n",
"\n",
"$$\n",
"\\PP\\{Y > t\\}\n",
" \\approx\n",
" e^{- \\lambda t}\n",
"$$\n",
"\n",
"In this sense, the exponential is the limit of the geometric distribution."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Memoryless Property of the Exponential Distribution\n",
"\n",
"The exponential distribution is the only memoryless distribution supported on $ \\RR_+ $, as the next theorem attests."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### (Characterization of the Exponential Distribution)\n",
"\n",
"If $ X $ is a random variable supported on $ \\RR_+ $, then there exists a\n",
"$ \\lambda > 0 $ such that $ X \\sim \\Exp(\\lambda) $ if and only if, for all\n",
"positive $ s, t $,\n",
"\n",
"\n",
"\n",
"$$\n",
"\\PP \\{X > s + t \\,|\\, X > s \\} = \\PP \\{X > t\\} \\tag{1.3}\n",
"$$\n",
"\n",
"Proof. To see that [(1.3)](#equation-memexpo) holds when $ X $ is exponential with rate $ \\lambda $,\n",
"fix $ s, t > 0 $ and observe that\n",
"\n",
"$$\n",
"\\frac{ \\PP \\{X > s + t \\text{ and } X > s \\} }\n",
" {\\PP \\{X > s\\}}\n",
" =\n",
" \\frac{ \\PP \\{X > s + t \\} }\n",
" {\\PP \\{X > s\\}}\n",
" = \\frac{e^{-\\lambda s - \\lambda t}}{e^{-\\lambda s}}\n",
" = e^{-\\lambda t}\n",
"$$\n",
"\n",
"To see that the converse holds, let $ X $ be a random variable supported on $ \\RR_+ $\n",
"such that [(1.3)](#equation-memexpo) holds.\n",
"\n",
"The “exceedance” function $ f(s) := \\PP\\{X > s\\} $ then has three properties:\n",
"\n",
"1. $ f $ is decreasing on $ \\RR_+ $, \n",
"1. $ 0 < f(t) < 1 $ for all $ t > 0 $, \n",
"1. $ f(s + t) = f(s) f(t) $ for all $ s, t > 0 $. \n",
"\n",
"\n",
"The first property is common to all exceedance functions, the second is due to\n",
"the fact that $ X $ is supported on all of $ \\RR_+ $, and the\n",
"third is [(1.3)](#equation-memexpo).\n",
"\n",
"From these three properties we will show that\n",
"\n",
"\n",
"\n",
"$$\n",
"f(t) = f(1)^t \\;\\; \\forall \\, t \\geq 0 \\tag{1.4}\n",
"$$\n",
"\n",
"This is sufficient to prove the claim because then $ \\lambda := - \\ln f(1) $ is a positive real number (by property 2) and, moreover,\n",
"\n",
"$$\n",
"f(t) \n",
" = \\exp( \\ln ( f(1) ) t) \n",
" = \\exp( - \\lambda t)\n",
"$$\n",
"\n",
"To see that [(1.4)](#equation-implex) holds, fix positive integers $ m,n $.\n",
"\n",
"We can use property 3 to obtain both\n",
"\n",
"$$\n",
"f(m/n) = f(1/n)^m\n",
" \\quad \\text{and} \\quad\n",
" f(1) = f(1/n)^n\n",
"$$\n",
"\n",
"It follows that $ f(m/n)^n = f(1/n)^{m n} = f(1)^m $ and, raising to the power\n",
"of $ 1/n $, we get [(1.4)](#equation-implex) when $ t=m/n $.\n",
"\n",
"The discussion so far confirms that [(1.4)](#equation-implex) holds when $ t $ is rational.\n",
"\n",
"So now take any $ t \\geq 0 $ and rational sequences $ (a_n) $ and $ (b_n) $\n",
"converging to $ t $ with $ a_n \\leq t \\leq b_n $ for all $ n $.\n",
"\n",
"By property 1 we have $ f(b_n) \\leq f(t) \\leq f(a_n) $ for all $ n $, so\n",
"\n",
"$$\n",
"f(1)^{b_n} \\leq f(t) \\leq f(1)^{a_n}\n",
" \\quad \\forall \\, n \\in \\NN\n",
"$$\n",
"\n",
"Taking the limit in $ n $ completes the proof.\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Failure of Memorylessness\n",
"\n",
"We know from the proceeding section that any distribution on $ \\RR_+ $ other\n",
"than the exponential distribution fails to be memoryless.\n",
"\n",
"Here’s an example that helps to clarify (although the support of the distribution is a proper subset of $ \\RR_+ $).\n",
"\n",
"A random variable $ Y $ has the Pareto distribution with positive parameters $ t_0, \\alpha $ if\n",
"\n",
"$$\n",
"f(t) \n",
" := \\PP\\{Y > t\\} \n",
" = \n",
" \\begin{cases}\n",
" 1 & \\text{ if } t \\leq t_0\n",
" \\\\\n",
" (t_0 / t)^\\alpha & \\text{ if } t > t_0\n",
" \\end{cases}\n",
"$$\n",
"\n",
"As a result, with $ s > t_0 $,\n",
"\n",
"$$\n",
"\\PP \\{Y > s + t \\,|\\, Y > s \\}\n",
" =\n",
" \\frac{ \\PP \\{Y > s + t \\} }\n",
" {\\PP \\{Y > s\\}}\n",
" = \\left( \\frac{t}{t + s} \\right)^\\alpha\n",
"$$\n",
"\n",
"Since this probability falls with $ s $, the distribution is not memoryless.\n",
"\n",
"If we have waited many hours for an event (i.e., $ s $ is large), then the\n",
"probability of waiting another hour is relatively small."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sums of Exponentials\n",
"\n",
"A random variable $ W $ on $ \\RR_+ $ is said to have the [Erlang\n",
"distribution](https://en.wikipedia.org/wiki/Erlang_distribution) if its\n",
"density has the form\n",
"\n",
"$$\n",
"f(t) = \\frac{\\lambda^n t^{n-1}}{(n-1)!} e^{-\\lambda t}\n",
" \\qquad (t \\geq 0)\n",
"$$\n",
"\n",
"for some $ n \\in \\NN $ and $ \\lambda > 0 $.\n",
"\n",
"The parameters $ n $ and $ \\lambda $ are called the **shape** and **rate**\n",
"parameters respectively.\n",
"\n",
"The next figure shows the shape for two parameterizations."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"t_grid = np.linspace(0, 50, 100)\n",
"\n",
"class Erlang:\n",
"\n",
" def __init__(self, λ=0.5, n=10):\n",
" self.λ, self.n = λ, n\n",
"\n",
" def __call__(self, t):\n",
" n, λ = self.n, self.λ\n",
" return (λ**n * t**(n-1) * np.exp(-λ * t)) / factorial(n-1)\n",
"\n",
"e1 = Erlang(n=10, λ=0.5)\n",
"e2 = Erlang(n=10, λ=0.75)\n",
"\n",
"fig, ax = plt.subplots()\n",
"for e in e1, e2:\n",
" ax.plot(t_grid, e(t_grid), label=f'$n={e.n}, \\lambda={e.λ}$')\n",
"\n",
"ax.legend()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The CDF of the Erlang distribution is\n",
"\n",
"\n",
"\n",
"$$\n",
"F(t) \n",
" = \\PP\\{W \\leq t\\}\n",
" = 1 - \\sum_{k=0}^{n-1} \\frac{(\\lambda t)^k}{k!} e^{-\\lambda t} \\tag{1.5}\n",
"$$\n",
"\n",
"The Erlang distribution is of interest to us because of the following fact."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## (Distribution of Sum of Exponentials)\n",
"\n",
"If, for some $ \\lambda > 0 $, the sequence $ (W_i) $ is IID and exponentially\n",
"distributed with rate $ \\lambda $, then $ J_n := \\sum_{i=1}^n W_i $ has the Erlang\n",
"distribution with shape $ n $ and rate $ \\lambda $.\n",
"\n",
"This connects to Poisson process theory, as we shall soon see."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise \n",
"\n",
"Due to its memoryless property, we can “stop” and “restart” an exponential\n",
"draw without changing its distribution.\n",
"\n",
"To illustrate this, we can think of fixing $ \\lambda > 0 $, drawing from\n",
"$ \\Exp(\\lambda) $, and stopping and restarting whenever a threshold $ s $ is crossed.\n",
"\n",
"In particular, consider the random variable $ X $ defined as follows:\n",
"\n",
"- Draw $ Y $ from $ \\Exp(\\lambda) $. \n",
"- If $ Y \\leq s $, set $ X = Y $. \n",
"- If not, draw $ Z $ independently from $ \\Exp(\\lambda) $ and set $ X = s + Z $. \n",
"\n",
"\n",
"Show that $ X \\sim \\Exp(\\lambda) $."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise \n",
"\n",
"Fix $ \\lambda = 0.5 $ and $ s=1.0 $.\n",
"\n",
"Simulate 1,000 draws of $ X $ using the algorithm above.\n",
"\n",
"Plot the fraction of the sample exceeding $ t $ for each $ t \\geq 0 $ (on a grid)\n",
"and compare to $ t \\mapsto e^{-\\lambda t} $.\n",
"\n",
"Is the fit good? How about if the number of draws is increased?\n",
"\n",
"Are the results in line with those of the previous exercise?"
]
},
{
"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 1.1](https://jstac.github.io/continuous_time_mcs/#memoryless-ex-1)\n",
"\n",
"Let $ X $ be constructed as in the statement of the exercise and fix $ t > 0 $.\n",
"\n",
"Notice that $ X > s + t $ if and only if $ Y > s $ and $ Z > t $.\n",
"\n",
"As a result of this fact and independence,\n",
"\n",
"$$\n",
"\\PP\\{X > s + t\\}\n",
" = \\PP\\{Y > s \\} \\PP\\{Z > t\\}\n",
" = e^{-\\lambda(s + t)}\n",
"$$\n",
"\n",
"At the same time, $ X > s-t $ if and only if $ Y > s-t $, so\n",
"\n",
"$$\n",
"\\PP\\{X > s - t\\}\n",
" = \\PP\\{Y > s - t \\} \n",
" = e^{-\\lambda(s - t)}\n",
"$$\n",
"\n",
"Either way, we have $ X \\sim \\Exp(\\lambda) $, as was to be shown."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## [Solution to Exercise 1.2](https://jstac.github.io/continuous_time_mcs/#memoryless-ex-2)\n",
"\n",
"Here’s one solution, starting with 1,000 draws."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"λ = 0.5 \n",
"np.random.seed(1234)\n",
"t_grid = np.linspace(0, 10, 200)\n",
"\n",
"@njit\n",
"def draw_X(s=1.0, n=1_000):\n",
" draws = np.empty(n)\n",
" for i in range(n):\n",
" Y = np.random.exponential(scale=1/λ)\n",
" if Y <= s:\n",
" X = Y\n",
" else:\n",
" Z = np.random.exponential(scale=1/λ)\n",
" X = s + Z\n",
" draws[i] = X\n",
" return draws\n",
"\n",
"fig, ax = plt.subplots()\n",
"draws = draw_X()\n",
"empirical_exceedance = [np.mean(draws > t) for t in t_grid]\n",
"ax.plot(t_grid, np.exp(- λ * t_grid), label='exponential exceedance')\n",
"ax.plot(t_grid, empirical_exceedance, label='empirical exceedance')\n",
"ax.legend()\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## [Solution to Exercise 1.2](https://jstac.github.io/continuous_time_mcs/#memoryless-ex-2)\n",
"\n",
"**Solution Continued:**\n",
"\n",
"The fit is already very close, which matches with the theory in Exercise 1.\n",
"\n",
"The two lines become indistinguishable as $ n $ is increased further."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"draws = draw_X(n=10_000)\n",
"empirical_exceedance = [np.mean(draws > t) for t in t_grid]\n",
"ax.plot(t_grid, np.exp(- λ * t_grid), label='exponential exceedance')\n",
"ax.plot(t_grid, empirical_exceedance, label='empirical exceedance')\n",
"ax.legend()\n",
"\n",
"plt.show()"
]
}
],
"metadata": {
"date": 1634710782.737995,
"filename": "memoryless.md",
"kernelspec": null,
"title": "Memoryless Distributions"
},
"nbformat": 4,
"nbformat_minor": 4
}