\n",
" \n",
" \n",
" \n",
"

"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# A Problem that Stumped Milton Friedman\n",
"\n",
"(and that Abraham Wald solved by inventing sequential analysis)\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Contents\n",
"\n",
"- [A Problem that Stumped Milton Friedman](#A-Problem-that-Stumped-Milton-Friedman) \n",
" - [Overview](#Overview) \n",
" - [Origin of the Problem](#Origin-of-the-Problem) \n",
" - [A Dynamic Programming Approach](#A-Dynamic-Programming-Approach) \n",
" - [Implementation](#Implementation) \n",
" - [Analysis](#Analysis) \n",
" - [Comparison with Neyman-Pearson Formulation](#Comparison-with-Neyman-Pearson-Formulation) \n",
" - [Sequels](#Sequels) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In addition to what’s in Anaconda, this lecture will need the following libraries:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": true
},
"outputs": [],
"source": [
"!pip install quantecon\n",
"!pip install interpolation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Overview\n",
"\n",
"This lecture describes a statistical decision problem encountered by Milton\n",
"Friedman and W. Allen Wallis during World War II when they were analysts at\n",
"the U.S. Government’s Statistical Research Group at Columbia University.\n",
"\n",
"This problem led Abraham Wald [[Wal47]](https://python-programming.quantecon.org/zreferences.html#wald47) to formulate **sequential analysis**,\n",
"an approach to statistical decision problems intimately related to dynamic programming.\n",
"\n",
"In this lecture, we apply dynamic programming algorithms to Friedman and Wallis and Wald’s problem.\n",
"\n",
"Key ideas in play will be:\n",
"\n",
"- Bayes’ Law \n",
"- Dynamic programming \n",
"- Type I and type II statistical errors \n",
" - a type I error occurs when you reject a null hypothesis that is true \n",
" - a type II error is when you accept a null hypothesis that is false \n",
"- Abraham Wald’s **sequential probability ratio test** \n",
"- The **power** of a statistical test \n",
"- The **critical region** of a statistical test \n",
"- A **uniformly most powerful test** \n",
"\n",
"\n",
"We’ll begin with some imports:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"from numba import jit, prange, float64, int64\n",
"from numba.experimental import jitclass\n",
"from interpolation import interp\n",
"from math import gamma"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This lecture uses ideas studied in [this lecture](https://python-programming.quantecon.org/likelihood_ratio_process.html), [this lecture](https://python-programming.quantecon.org/likelihood_bayes.html).\n",
"and [this lecture](https://python-programming.quantecon.org/exchangeable.html)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Origin of the Problem\n",
"\n",
"On pages 137-139 of his 1998 book *Two Lucky People* with Rose Friedman [[FF98]](https://python-programming.quantecon.org/zreferences.html#friedman98),\n",
"Milton Friedman described a problem presented to him and Allen Wallis\n",
"during World War II, when they worked at the US Government’s\n",
"Statistical Research Group at Columbia University.\n",
"\n",
"Let’s listen to Milton Friedman tell us what happened\n",
"\n",
"> In order to understand the story, it is necessary to have an idea of a\n",
"simple statistical problem, and of the standard procedure for dealing\n",
"with it. The actual problem out of which sequential analysis grew will\n",
"serve. The Navy has two alternative designs (say A and B) for a\n",
"projectile. It wants to determine which is superior. To do so it\n",
"undertakes a series of paired firings. On each round, it assigns the\n",
"value 1 or 0 to A accordingly as its performance is superior or inferior\n",
"to that of B and conversely 0 or 1 to B. The Navy asks the statistician\n",
"how to conduct the test and how to analyze the results.\n",
"\n",
"\n",
"> The standard statistical answer was to specify a number of firings (say\n",
"1,000) and a pair of percentages (e.g., 53% and 47%) and tell the client\n",
"that if A receives a 1 in more than 53% of the firings, it can be\n",
"regarded as superior; if it receives a 1 in fewer than 47%, B can be\n",
"regarded as superior; if the percentage is between 47% and 53%, neither\n",
"can be so regarded.\n",
"\n",
"\n",
"> When Allen Wallis was discussing such a problem with (Navy) Captain\n",
"Garret L. Schyler, the captain objected that such a test, to quote from\n",
"Allen’s account, may prove wasteful. If a wise and seasoned ordnance\n",
"officer like Schyler were on the premises, he would see after the first\n",
"few thousand or even few hundred [rounds] that the experiment need not\n",
"be completed either because the new method is obviously inferior or\n",
"because it is obviously superior beyond what was hoped for\n",
"$ \\ldots $.\n",
"\n",
"\n",
"Friedman and Wallis struggled with the problem but, after realizing that\n",
"they were not able to solve it, described the problem to Abraham Wald.\n",
"\n",
"That started Wald on the path that led him to *Sequential Analysis* [[Wal47]](https://python-programming.quantecon.org/zreferences.html#wald47).\n",
"\n",
"We’ll formulate the problem using dynamic programming."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A Dynamic Programming Approach\n",
"\n",
"The following presentation of the problem closely follows Dmitri\n",
"Berskekas’s treatment in **Dynamic Programming and Stochastic Control** [[Ber75]](https://python-programming.quantecon.org/zreferences.html#bertekas75).\n",
"\n",
"A decision-maker observes a sequence of draws of a random variable $ z $.\n",
"\n",
"He (or she) wants to know which of two probability distributions $ f_0 $ or $ f_1 $ governs $ z $.\n",
"\n",
"Conditional on knowing that successive observations are drawn from distribution $ f_0 $, the sequence of\n",
"random variables is independently and identically distributed (IID).\n",
"\n",
"Conditional on knowing that successive observations are drawn from distribution $ f_1 $, the sequence of\n",
"random variables is also independently and identically distributed (IID).\n",
"\n",
"But the observer does not know which of the two distributions generated the sequence.\n",
"\n",
"For reasons explained in [Exchangeability and Bayesian Updating](https://python.quantecon.org/exchangeable.html), this means that the sequence is not\n",
"IID and that the observer has something to learn, even though he knows both $ f_0 $ and $ f_1 $.\n",
"\n",
"The decision maker chooses a number of draws (i.e., random samples from the unknown distribution) and uses them to decide\n",
"which of the two distributions is generating outcomes.\n",
"\n",
"He starts with prior\n",
"\n",
"$$\n",
"\\pi_{-1} =\n",
"\\mathbb P \\{ f = f_0 \\mid \\textrm{ no observations} \\} \\in (0, 1)\n",
"$$\n",
"\n",
"After observing $ k+1 $ observations $ z_k, z_{k-1}, \\ldots, z_0 $, he updates this value to\n",
"\n",
"$$\n",
"\\pi_k = \\mathbb P \\{ f = f_0 \\mid z_k, z_{k-1}, \\ldots, z_0 \\}\n",
"$$\n",
"\n",
"which is calculated recursively by applying Bayes’ law:\n",
"\n",
"$$\n",
"\\pi_{k+1} = \\frac{ \\pi_k f_0(z_{k+1})}{ \\pi_k f_0(z_{k+1}) + (1-\\pi_k) f_1 (z_{k+1}) },\n",
"\\quad k = -1, 0, 1, \\ldots\n",
"$$\n",
"\n",
"After observing $ z_k, z_{k-1}, \\ldots, z_0 $, the decision-maker believes\n",
"that $ z_{k+1} $ has probability distribution\n",
"\n",
"$$\n",
"f_{{\\pi}_k} (v) = \\pi_k f_0(v) + (1-\\pi_k) f_1 (v) ,\n",
"$$\n",
"\n",
"which is a mixture of distributions $ f_0 $ and $ f_1 $, with the weight\n",
"on $ f_0 $ being the posterior probability that $ f = f_0 $ **[1]** The decision maker acts as if he believes that the sequence of random variables\n",
"$ [z_{0}, z_{1}, \\ldots] $ is *exchangeable*. See [Exchangeability and Bayesian Updating](https://python.quantecon.org/exchangeable.html) and\n",
"[[Kre88]](https://python-programming.quantecon.org/zreferences.html#kreps88) chapter 11, for discussions of exchangeability."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sequels\n",
"\n",
"We’ll dig deeper into some of the ideas used here in the following lectures:\n",
"\n",
"- [this lecture](https://python-programming.quantecon.org/exchangeable.html) discusses the key concept of **exchangeability** that rationalizes statistical learning \n",
"- [this lecture](https://python-programming.quantecon.org/likelihood_ratio_process.html) describes **likelihood ratio processes** and their role in frequentist and Bayesian statistical theories \n",
"- [this lecture](https://python-programming.quantecon.org/likelihood_bayes.html) discusses the role of likelihood ratio processes in **Bayesian learning** \n",
"- [this lecture](https://python-programming.quantecon.org/navy_captain.html) returns to the subject of this lecture and studies whether the Captain’s hunch that the (frequentist) decision rule\n",
" that the Navy had ordered him to use can be expected to be better or worse than the rule sequential rule that Abraham Wald designed "
]
}
],
"metadata": {
"date": 1615288263.4707997,
"filename": "wald_friedman.rst",
"kernelspec": {
"display_name": "Python",
"language": "python3",
"name": "python3"
},
"next_doc": {
"link": "exchangeable",
"title": "Exchangeability and Bayesian Updating"
},
"prev_doc": {
"link": "likelihood_ratio_process",
"title": "Likelihood Ratio Processes"
},
"title": "A Problem that Stumped Milton Friedman"
},
"nbformat": 4,
"nbformat_minor": 2
}