E-values.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "85b6a7c0-ef74-4a84-8065-efe9176d86ca",
   "metadata": {},
   "source": [
    "# $E$-values and Betting Scores\n",
    "\n",
    "Core references: \n",
    "\n",
    "+ Grünwald, P., R. de Heide, and W. Koolen, 2023. Safe Testing. https://arxiv.org/abs/1906.07801\n",
    "\n",
    "+ Shafer, G., 2021. Testing by betting: A strategy for statistical and scientific communication,\n",
    "_Journal of the Royal Statistical Society Series A: Statistics in Society_, _184_, 407–431, https://doi.org/10.1111/rssa.12647\n",
    "\n",
    "+ Vovk, V., and R. Wang, 2021. E-values: Calibration, combination and applications, _Ann. Statist. 49_ (3) 1736-1754. https://doi.org/10.1214/20-AOS2020\n",
    "\n",
    "+ Lecture notes by V. Vovk. https://www.isibang.ac.in/~statmath/pcm2020/talk1.pdf, https://www.isibang.ac.in/~statmath/pcm2020/talk2.pdf\n",
    "\n",
    "+ Wang, R., and A. Ramdas, 2021. False discovery rate control with e-values, https://arxiv.org/pdf/2009.02824.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7737414-543b-401e-b567-c2fa0f99efc4",
   "metadata": {},
   "source": [
    "$E$-values are a way of quantifying evidence about a statistical hypothesis. \n",
    "They are closely related to $P$-values, but more general in many ways, and possibly easier to understand.\n",
    "They have a frequentist interpretation, but they are often easier to construct than $P$-values, and they\n",
    "make it much easier to account for sequential testing and multiple testing than $P$-values do.\n",
    "\n",
    "\n",
    "In particular (paraphrasing Shafer, 2021, and Grünwald et al., 2023):\n",
    "\n",
    "+ An $E$-value is the observed value of a nonnegative random variable whose expected value under the null is 1: $\\mathbb{E}_0 E = 1$. In contrast, a $P$-value is the observed value of a nonnegative random variable whose probability distribution under the null is dominated by the uniform distribution: $\\mathbb{P}_0 \\{P \\le x\\} \\le x$, $\\forall x \\in [0, 1]$. It is generally a much more straightforward to construct $E$-values than $P$-values.\n",
    "\n",
    "+ $E$-values are like the returns on a bet. Most people know it's possible to win a lot of money by \"getting lucky\"\n",
    "and winning a bet with long odds, or by identifying bets where the payoff odds don't reflect the chance odds. Fewer people understand $P$-values. It's common to think that a small $P$-value means the alternative is true or that the probability that the null is true is small--two common misconceptions.\n",
    "\n",
    "+ Any particular bet implies an alternative hypothesis. The betting score is the likelihood of the alternative divided by the likelihood of the null. Likelihood ratios have intuitive appeal.\n",
    "\n",
    "+ Power calculations require a fixed significance level, not a $P$-value, so there's no direct analog of power for $P$-values. In contrast, a bet also implies a target: a value for the betting score that might be expected if the alternative hypothesis is true. \n",
    "\n",
    "+ Betting strategies can be \"informed\" by almost everything, provided the bets are \"predictable\" from the data available before the bet is made. Betting scores can include arbitrarily complex strategies to \"win\" that use all currently available data to inform the next bet, including prior probability distributions, hunches about what's really going on, changing sets of covariates, and more--all while rigorously maintaining the $E$-value property, and hence, frequentist validity. The decision of what experiment to perform next (or whether to perform another experiment) can be based on anything. In contrast, the validity of $P$-values generally requires pre-specifying the entire analysis.  Betting scores thus may correspond better to how Science is conducted: a single hypothesis might be tested many times, and each experiment (including its design, what is measured, and the test used) might be informed by previous experiments--and the alternative may evolve from new information in other fields, intuition, elicited expert opinion, etc.\n",
    "\n",
    "+ Betting scores can often be combined by multiplication, which corresponds to \"reinvesting\" the winnings in future bets. Betting scores can always be combined using averages (with or without weights). In contrast, combining $P$-values to get a valid $P$-value is much more subtle.\n",
    "\n",
    "+ There is a tendency to treat $P$-values as if they did not depend on models and methods, only on the data. This may contribute to the mistake of treating a large $P$-value as evidence that the null is true. In contrast, most people understand that there's more than one betting strategy in any particular game, so the fact that an $E$-value depends on the strategy might be easier to remember, and users might be less prone to interpreting a small $E$-value as evidence that the null is true, rather than simply that a particular way of betting against the null did not multiply the initial stake by a large factor.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7476acf-d419-4af1-9615-8d738ec87a68",
   "metadata": {},
   "source": [
    "## Notation\n",
    "In this chapter, we will use the notation $\\mathbb{P}(\\cdot) := \\mathbb{E}_\\mathbb{P} (\\cdot)$ to denote expectation with respect to the distribution $\\mathbb{P}$.\n",
    "The expected value of the indicator function of a measurable set $A$ is the \n",
    "probability of $A$; in some sense, this notation generalizes from $\\mathbb{E}_\\mathbb{P} (1_A) = \\mathbb{P}(A)$ to the expectation of other functions.\n",
    "\n",
    "Any distributions that appear in the same expression will be assumed to have a single dominating measure\n",
    "$\\mu$, so we can talk about densities with respect to $\\mu$.\n",
    "The density of $\\mathbb{P}$ with respect to $\\mu$ will be denoted $f_\\mathbb{P}$, so that \n",
    "$d\\mathbb{P}(\\omega) = f_\\mathbb{P}(\\omega) d\\mu(\\omega)$.\n",
    "\n",
    "Let $(\\Omega, \\mathcal{F}, \\mathbb{P})$ be a probability space.\n",
    "Let $\\mathcal{I}$ be a totally ordered set with order relation $\\le$.\n",
    "Suppose that for all $i \\in \\mathcal{I}$, $\\mathcal{F}_i$ is a sub-sigma-algebra of $\\mathcal{F}$,\n",
    "and that if $i < j$, $\\mathcal{F}_i \\subset \\mathcal{F}_j$.\n",
    "Then $\\mathbb{F} := \\{\\mathcal{F}_i\\}_{i \\in \\mathcal{I}}$ is a _filtration_ and $(\\Omega, \\mathcal{F}, \\mathbb{F}, \\mathbb{P})$ is\n",
    "a _filtered probability space_.\n",
    "\n",
    "Filtrations arise naturally in studying stochastic processes.\n",
    "Let $\\sigma(X)$ be the sigma-algebra generated by the random variable $X$ (the smallest sigma-algebra for which $X$ is measurable, i.e., the smallest sigma algebra that contains the pre-image $X^{-1}(B)$\n",
    "of every Borel subset $B \\subset \\mathcal{B}$), and let  $\\sigma(X_j : j \\le i) := \\sigma(\\cup_{j \\le i} \\sigma(X_j))$.\n",
    "As the process evolves, a richer and richer set of events becomes measurable.\n",
    "Let $(X_i)_{i \\in \\mathbb{N}}$ be a stochastic process on the probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$,\n",
    "and define $\\mathcal{F}_i := \\sigma(X_j : j \\le i)$.\n",
    "Then $\\mathbb{F} := \\{\\mathcal{F}_i\\}_{i \\in \\mathcal{I}}$ is a filtration."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7c17708-21e3-41f1-9048-c3fde20d6620",
   "metadata": {},
   "source": [
    "## Warm-up 1: betting as evidence\n",
    "\n",
    "A _predictor_ or _forecaster_ claims that $Y$ is a random variable with probability distribution $\\mathbb{P}_0$.\n",
    "The value $y$ of $Y$ will be revealed (to the predictor and you) later.\n",
    "The predictor backs up the claim by offering to sell you any payoff $S(y)$ for the price $\\mathbb{E}_0 S(Y) =: \\mathbb{P}_0 S(Y)$,\n",
    "the expected value of $S(Y)$ (before it is observed), computed\n",
    "on the assumption that the predictor is right--that $Y$ is indeed a random variable and has distribution $\\mathbb{P}_0$.\n",
    "The payoff is required to be nonnegative, so that all you risk is what you bet: the expected value of $S$ on the assumption that $Y \\sim \\mathbb{P}_0$.\n",
    "\n",
    "If you buy the bet $S$, your payoff is $S(y)$ if $Y=y$, and your _betting score_ is $S(y)/\\mathbb{P}_0 S(Y)$, the amount by which you multiplied your initial stake.\n",
    "Without loss of generality, we may assume that $\\mathbb{P}_0 S(Y) = 1$ and allow you to buy any multiple of the bet $S$ you can afford; then your (eventual) betting score is $S(y)$. \n",
    "You don't have to bet your whole fortune, but if you withhold a fraction $\\beta$ of your current fortune and \n",
    "bet the remaining fraction $1-\\beta$ on $S$, that is equivalent to betting your whole fortune on $S' = \\beta + (1-\\beta)S$, which also has expected value 1 under the null since $\\mathbb{P}_0 S = 1$.\n",
    "That is, betting only a fraction of your current fortune its just another bet that is expected to break even\n",
    "under the predictor's hypothesis, so without loss of generality, we can assume that you bet your entire fortune\n",
    "on some $S$.\n",
    "\n",
    "It isn't necessary that *you* believe $Y$ is really a random variable: you can still\n",
    "bet if you think the predictor's claim is wrong, that is, if you think you can make money betting on some\n",
    "$S$ with $\\mathbb{P}_0 S(Y) = 1$.\n",
    "\n",
    "Now suppose there is a series of trials, $(Y_j)$, which might or might not be random; and if they are random,\n",
    "they might or might not be independent.\n",
    "The predictor is allowed to make a series of predictions, say $\\mathbb{P}_{0j}$ for\n",
    "$j = 1, \\ldots$.\n",
    "The predictor need not make a prediction for every trial, \n",
    "and the prediction for the $j$th trial, $\\mathbb{P}_{0j}$, might depend on the outcome of previous trials, $\\{Y_i \\}_{i<j}$.\n",
    "(This is much closer to how science is conducted than the assumption that trials are independent\n",
    "and involve the same parameters.)\n",
    "Shafer (2021) writes:\n",
    "\n",
    "> The probabilistic predictions that can be associated with a scientific hypothesis usually go beyond a single comprehensive probability distribution. In some cases, a scientist may begin with a joint probability distribution P for a sequence of variables $Y_1 , \\ldots, Y_N$  and formulate a plan for successive experiments that will allow her to observe them. But the scientific enterprise is usually more opportunistic. A scientist might perform an experiment that produces $Y_1$’s value $y_1$ and then decide whether it is worthwhile to perform the further experiment that would produce $Y_2$’s value $y_2$. Perhaps no one even thought about $Y_2$ at the outset. One scientist or team tests the hypothesis using $Y_1$, and then, perhaps because the result is promising but not conclusive, some other scientist or team comes up with the idea of further testing the hypothesis with a second variable $Y_2$ from a hitherto uncontemplated new experiment or database.\n",
    "\n",
    "\n",
    "Suppose you start with \\\\$1, and you are allowed to bet on any or all of the predictions: before the $j$th \n",
    "trial the predictor offers the prediction $Y_j \\sim \\mathbb{P}_{j0}$, which can depend on previous trials.\n",
    "You are allowed to buy any nonnegative $S(Y_j)$ for the price $\\mathbb{P}_{j0} S(Y_j)$, which is assumed to\n",
    "be \\\\$1. \n",
    "Your fortune after the first bet is settled is $S_1(y_1)$. \n",
    "The predictor now offers to sell you any $S_2(Y_2)$ for its expected value under the null $Y_2 \\sim \\mathbb{P}_{02}$,\n",
    "again assumed to be \\\\$1.\n",
    "If you bet your current fortune to by a multiple of $S_2(Y_2)$, then\n",
    "your fortune when the second bet settles is $S_1(y_1)S_2(y_2)$, etc.: betting scores on successive bets multiply to give your current fortune.\n",
    "\n",
    "If you end up making a lot of money, that is evidence that the predictor was wrong--or that you were very lucky. \n",
    "If you don't end up making a lot of money, maybe the predictor was right--or maybe you chose bad bets (you didn't bet\n",
    "on the right alternative).\n",
    "Regardless, it is not evidence that the predictor was right.\n",
    "This is the same asymmetry involved in hypothesis tests: a large $P$-value is not evidence that the null is true."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6455d3c-298a-4bdf-b7d0-a1282b14f7ec",
   "metadata": {},
   "source": [
    "## Warm-up 2: hypothesis tests as bets\n",
    "\n",
    "See [hypothesis testing](./tests.ipynb).\n",
    "\n",
    "Core idea: if you can make money betting against the null hypothesis (by making bets\n",
    "that are expected to be break-even of the null hypothesis is true), that's evidence that the\n",
    "null hypothesis is false.\n",
    "\n",
    "In the typical setup for hypothesis testing, we observe data $X \\sim \\mathbb{P}$.\n",
    "To test the null hypothesis test $\\mathbb{P} = \\mathbb{P}_0$, we choose a function $\\phi(\\cdot)$ with the property that $\\mathbb{P}_{\\mathbb{P}_0,U}\\phi(X,U) = \\alpha$, where $U$ is an auxilliary uniform random variable\n",
    "independent of $X$, only needed for randomized tests.\n",
    "\n",
    "We reject the hypothesis $\\mathbb{P} = \\mathbb{P}_0$ if $U \\le \\phi(X)$.\n",
    "\n",
    "We can think of $\\phi(X)$ as an \"all-or-nothing\" bet that pays $1/\\alpha$ times the stake (which we will \n",
    "take to be \\\\$1) if $U \\le \\phi(X)$, and pays 0 otherwise. \n",
    "If the null is true, the expected value of such a bet is \\\\$1.\n",
    "That is, $X$ plays the role of $Y$, above, and $S(Y)$ is $1/\\alpha$ if $U \\le \\phi(Y)$ and zero otherwise.\n",
    "\n",
    "Two scenarios:\n",
    "+ bet once in a while, don't reinvest your winnings\n",
    "+ bet whenever you want, reinvest your winnings\n",
    "\n",
    "The first is like $P$-values and standard tests of significance: all-or-nothing bets, \n",
    "with no \"combining evidence\" across experiments.\n",
    "The second leads to betting scores and $E$-values."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd8cd95c-a60b-4c90-bec4-3b317f5b2da4",
   "metadata": {},
   "source": [
    "Multiple testing: suppose a hypothesis is tested 20 times at significance level 5%, producing one\n",
    "\"significant\" result. From a testing perspective, we have to adjust for multiplicity to understand\n",
    "how strong the evidence is that the null is false, and that adjustment requires knowing the dependence among the experiments. From an $E$-value perspective, the betting score is 1: \\\\$20 was wagered, and \\\\$20 was won."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ae1191e-8466-4567-9512-2ec7f6633d73",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Betting scores for simple nulls are likelihood ratios, and vice versa\n",
    "\n",
    "Suppose we have a nonnegative random variable $S(Y)$ with expected value $1$ under the null $Y \\sim \\mathbb{P}_0$,\n",
    "i.e., $\\int S(y) d\\mathbb{P}_0(y) = 1$. \n",
    "Thus the measure $\\mathbb{Q}$ defined by $d\\mathbb{Q}(y) := S(y) d\\mathbb{P}_0(y)$ is also a probability measure: $\\mathbb{Q}(y) \\ge 0$ and $\\int d\\mathbb{Q}(y) = 1$.\n",
    "Hence, $S(y) = f_\\mathbb{Q}(y)/f_{\\mathbb{P}_0}(y)$ is the likelihood ratio of $\\mathbb{Q}$ to $\\mathbb{P}_0$.\n",
    "The distribution $\\mathbb{Q}$ is called _the alternative implied by $S$_.\n",
    "\n",
    "Conversely, suppose $\\mathbb{Q}$ is a probability distribution for $Y$.\n",
    "Then $S(Y) := f_\\mathbb{Q}(Y)/f_{\\mathbb{P}_0}(Y)$ is a betting score, since it is nonnegative and\n",
    "\\begin{eqnarray}\n",
    "\\mathbb{P}_0 (f_\\mathbb{Q}(Y)/f_{\\mathbb{P}_0}(Y)) &=& \\int (f_\\mathbb{Q}(y)/f_{\\mathbb{P}_0}(y)) d\\mathbb{P}_0(y) \\\\\n",
    "&=& \\int (f_\\mathbb{Q}(y)/f_{\\mathbb{P}_0}(y)) f_{\\mathbb{P}_0}(y) d\\mu(y) \\\\\n",
    "&=& \\int f_\\mathbb{Q}(y) d\\mu(y) \\\\\n",
    "&=& \\int d\\mathbb{Q}(y) \\\\\n",
    "&=& 1.\n",
    "\\end{eqnarray}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8911d72-c024-4d8b-a5f6-c6b126a3695f",
   "metadata": {},
   "source": [
    "As mentioned above, the betting formulation makes sense even if $Y$ isn't a random variable.\n",
    "But suppose I think $Y \\sim \\mathbb{Q} \\ne \\mathbb{P}_0$.\n",
    "What payoff function $S$ should I bet on?\n",
    "\n",
    "If the goal is to grow my capital at the fastest rate (the Kelly criterion), I want to maximize\n",
    "\\begin{equation}\n",
    "\\mathbb{Q} \\ln S = \\mathbb{Q} \\ln \\left( f_\\mathbb{R}(Y)/f_{\\mathbb{P}_0}(Y) \\right)\n",
    "\\end{equation}\n",
    "for some measure $\\mathbb{R}$.\n",
    "Gibbs' inequality says that\n",
    "\\begin{equation}\n",
    "\\mathbb{Q} \\ln \\left ( f_\\mathbb{Q}(Y)/f_{\\mathbb{P}_0}(Y) \\right ) \\ge \\mathbb{Q} \\ln \\left ( f_\\mathbb{R}(Y)/f_{\\mathbb{P}_0}(Y) \\right )\n",
    "\\end{equation}\n",
    "for any distribution $\\mathbb{R}$ for $Y$ (dominated by $\\mu$).\n",
    "\n",
    "Thus the optimal payoff function to bet on is $S(Y) = f_\\mathbb{Q}(Y)/f_{\\mathbb{P}_0}(Y)$.\n",
    "\n",
    "(The Kullback-Leibler (KL) Divergence between a distribution $\\mathbb{Q}$ and a distribution or subdistribution $\\mathbb{P}$ that have densities $f_{\\mathbb{Q}}$ and $f_{\\mathbb{P}}$ with respect to a common dominating measure is\n",
    "\\begin{equation}\n",
    "D(\\mathbb{Q}||\\mathbb{P}) := \\mathbb{Q}[\\ln(f_{\\mathbb{Q}}/f_{\\mathbb{P}})].\n",
    "\\end{equation}\n",
    "Gibb's inequality is an inequality on the KL divergence.)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282e74e6-5084-4264-a879-7f4a8380c57a",
   "metadata": {},
   "source": [
    "## Picking the bet: why maximize the expected log payoff (rather than the expected payoff)?\n",
    "\n",
    "This is connected to the idea of repeated betting, rather than one-shot bets.\n",
    "As noted previously, if you maximize the expected return on a single bet, you risk going broke.\n",
    "Maximizing the expected return on a single bet puts all your money on the single outcome with the highest probability.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51938ad1-d862-4fd6-bc19-b2f42593a5db",
   "metadata": {},
   "source": [
    "## The Neyman-Pearson Lemma and the optimality of all-or-nothing bets\n",
    "\n",
    "Neyman and Pearson propose maximizing _power_: among all tests of $\\mathbb{P}_0$ with level $\\alpha$, find the test with greatest power against some alternative $\\mathbb{Q}$.\n",
    "\n",
    "The Neyman-Pearson lemma says that the optimal randomized test $\\phi(x,u)$ equals 1 for all $x$ with $f_\\mathbb{Q}(x)/f_{\\mathbb{P}_0}(x) > c$ for some $c$ and is randomized on the set $f_\\mathbb{Q}(x)/f_{\\mathbb{P}_0}(x) = c$ to make its level exactly $\\alpha$. \n",
    "For instance, let $I_c$ denote the subset of $\\mathcal{X}$ for which $f_\\mathbb{Q}(x)/f_{\\mathbb{P}_0}(x) > c$ and $P_c$ denote the subset of $\\mathcal{X}$ for which $f_\\mathbb{Q}(x)/f_{\\mathbb{P}_0}(x) = c$.\n",
    "Then $c = \\sup\\{b \\in \\Re^+ : \\mathbb{P}_0 I_b \\le \\alpha \\}$.\n",
    "Define \n",
    "\\begin{equation}\n",
    "u^* := \\frac{\\alpha-\\mathbb{P}_0 I_c}{\\mathbb{P}_0 P_c}.\n",
    "\\end{equation}\n",
    "Then the test function \n",
    "\\begin{equation}\n",
    "\\phi(x, u) := \\left \\{ \\begin{array}{ll}\n",
    "       1, & x \\in I_c, u \\in [0, 1] \\\\\n",
    "       1,  & x \\in P_c, u \\in [u^*, 1] \\\\\n",
    "       0, & \\mbox{ otherwise }\n",
    "       \\end{array}\n",
    "       \\right .\n",
    "\\end{equation}\n",
    "gives a most powerful test of $\\mathbb{P}_0$ against the alternative $\\mathbb{Q}$.\n",
    "If $\\mathbb{P}_0 I_c = \\alpha$, it is non-randomized, and it is the unique most powerful test.\n",
    "\n",
    "Among all \"all-or-nothing\" bets, the Neyman-Pearson test maximizes $\\mathbb{Q} (S(Y) \\ge 1/\\alpha)$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8268854-0d73-478d-a785-a7c8bb17f2ca",
   "metadata": {},
   "source": [
    "## Implied targets\n",
    "\n",
    "If you bet on $S$, implicitly you are suggesting that $Y \\sim \\mathbb{Q}$, \n",
    "where $f_\\mathbb{Q}(y) := S(y) f_{\\mathbb{P}_0}(y)$.\n",
    "Implicitly, you expect \n",
    "\\begin{eqnarray}\n",
    "\\mathbb{Q} [\\ln S(Y)] &=& \\int \\ln S(y) d\\mathbb{Q}(y) \\\\\n",
    "&=&  \\int \\ln S(y) S(y) d\\mathbb{P}_0(y) \\\\\n",
    "&=& \\mathbb{P}_0 [S(Y) \\ln S(Y)].\n",
    "\\end{eqnarray}\n",
    "The _implied target_ is the expected rate of growth in your wealth if the alternative $\\mathbb{Q}$ for which your\n",
    "bet $S$ is optimal is in fact true."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cde25bf-131a-4c33-aa13-21afd238b306",
   "metadata": {},
   "source": [
    "## Composite nulls\n",
    "\n",
    "Suppose that the forecaster claims that $Y \\sim \\mathbb{P}$ for some (otherwise unspecified) $\\mathbb{P} \\in \\mathcal{P}_0$, i.e., the null hypothesis is composite, rather than simple.\n",
    "We can test such a hypothesis using betting by using nonnegative payoffs $S(Y)$ that have expected value no greater than 1\n",
    "for any $\\mathbb{P} \\in \\mathcal{P}_0$.\n",
    "That is, the forecaster offers to sell any $S$ such that $\\sup_{\\mathbb{P} \\in \\mathcal{P}_0} \\mathbb{P}S(Y) \\le 1$\n",
    "for \\\\$1."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a13fff7-1ef3-4032-86eb-95d314a33864",
   "metadata": {},
   "source": [
    "## Composite alternatives\n",
    "\n",
    "The bets $S$ can be chosen in countless ways, including maximizing the expected\n",
    "growth rate for weighted mixtures of alternatives or maximizing the minimum growth rate over a set of alternatives.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d8acc27-6294-4182-9cc6-fc8500a4b4fb",
   "metadata": {},
   "source": [
    "# Betting-based testing protocols testing\n",
    "\n",
    "Suppose a statistical model gives a probability distribution $\\mathbb{P}_0$ for data $Y$\n",
    "\n",
    "The _Forecaster_ proposes a probability distribution for a future observation.\n",
    "The statistician is the _Skeptic_, who is testing the Forecaster. _Reality_ reveals the value of variables.\n",
    "\n",
    "**Protocol for a single experiment or prediction:**  \n",
    "\n",
    "+ Forecaster claims $Y \\sim \\mathbb{P}_0$\n",
    "+ Skeptic selects a random variable $S \\ge 0$ such that $\\mathbb{P}_0 S(Y) = 1$.  \n",
    "+ Reality announces $y$\n",
    "+ $K \\leftarrow S(y)$ is the Skeptic's winnings.\n",
    "\n",
    "$\\mathbb{P}_0 (K \\ge 1/\\alpha) \\le \\alpha$ for all $\\alpha \\in (0, 1]$, by Markov's inequality.\n",
    "\n",
    "**Protocol for a sequence of experiments or predictions, with side information:**  \n",
    "This protocol is for testing whether a forecaster is any good.\n",
    "The forecaster and the skeptic have access to extra information: at step $i$, Reality\n",
    "reveals a value $x_i$ (think of it as an independent variable).\n",
    "\n",
    "+ $K_0 := 1$ (Skeptic's initial bankroll is \\\\$1)\n",
    "+ For $j = 1, \\ldots$:\n",
    "    - Reality announces $x_j$, the independent variable\n",
    "    - Forecaster selects $\\mathbb{P}_{0j}$ and claims $Y_j \\sim \\mathbb{P}_{0j}$\n",
    "    - Skeptic selects $S_j$ such that $\\mathbb{P}_{0j} (S_j) = K_{j-1}$\n",
    "    - Reality announces $y_j$\n",
    "    - $K_j \\leftarrow S_j(y_j)$\n",
    "\n",
    "At each step, this process generates a value that would be a martingale if every $Y_j$ had the distribution $\\mathbb{P}_{0j}$ conditional on previous values $Y_i$, $i < j$. Thus Ville's inequality applies, and if\n",
    "the forecaster's forecasts (nulls) were correct, $\\mathbb{P} \\{ \\exists j \\in \\mathbb{N} : K_j \\ge 1/\\alpha \\} \\le \\alpha$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06f09a40-3478-44bf-901c-919f73f01150",
   "metadata": {},
   "source": [
    "**Protocol for an abstract bounded strategy game:** (see Shafer & Vovk, 2019)  \n",
    "This protocol is for a \"number-guessing game.\"\n",
    "\n",
    "+ Skeptic announces $K_0$ (initial bankroll)\n",
    "+ For $j = 1, \\ldots,$:\n",
    "    - Forecaster announces $m_j \\in [-1, 1]$ (a prediction)\n",
    "    - Skeptic announces $M_j \\in \\Re$ (the bet, which can be positive or negative)\n",
    "    - Reality announces $y_j \\in [-1, 1]$\n",
    "    - $K_j \\leftarrow K_{j-1} + M_j(y_j - m_j)$\n",
    "    \n",
    "In the protocol above,\n",
    "there's no loss in generality in setting $m_j=0$ (since reality can always announce $y_j' = y_j-m_j$ and everything else stays the same), and no increase in generality in replacing $[-1, 1]$ by $[-C, C]$ (by rescaling).\n",
    "We will take $m_j = 0$ in the following discussion, in essence, removing Forecaster from the protocol.\n",
    "\n",
    "It's possible that the Skeptic could get arbitrarily rich, with $K_j \\rightarrow \\infty$.\n",
    "But Reality can always prevent that by setting $y_j = m_j$ (or $y_j = 0$ in the special case).\n",
    "So Skeptic can't guarantee they will get rich. \n",
    "But to prevent Skeptic from becoming infinitely rich, Forecaster and Reality might have to behave in a particular way.\n",
    "\n",
    "**Notation:** (See Table 1.1 of Shafer & Vovk, 2019)  \n",
    "\n",
    "Concept          |   Definition | <div style=\"width:400px\">Notation</div>   |\n",
    ":----------------|:---------------------|:-------------------------------------- |\n",
    "situation        | sequence of moves by Reality | $s= y_1 \\cdots y_j$ |\n",
    "situation space  | set of all situations        | $\\mathbb{S}$ |\n",
    "initial situation| empty sequence               | $\\Box$ |\n",
    "path             | complete sequence of moves by Reality | $\\omega = y_1y_2 \\cdots$ |\n",
    "$j$th element of a path |  | $\\omega_j$ |\n",
    "prefix of a path | first $j$ elements of the path | $\\omega^j = \\omega_1 \\omega_2 \\cdots \\omega_j$ |\n",
    "sample space     | set of all paths             | $\\Omega$ |\n",
    "process | real-valued function on $\\mathbb{S}$ | $S: \\Omega \\rightarrow \\mathbb{R}^\\infty$ |\n",
    "$j$th term in the process $S$ | | $S_j : \\omega \\in \\Omega \\mapsto S(\\omega^j) \\in \\mathbb{R}$ |\n",
    "predictable process | function $T$ on $\\mathbb{S} \\setminus \\{\\Box\\}$ for which $T_j$ depends only on $\\omega^{j-1}$ | |\n",
    "event            | subset of sample space       | $A \\subset \\Omega$ |\n",
    "variable         | function on the sample space | $X: \\Omega \\rightarrow \\mathbb{R}$ |\n",
    "strategy for Skeptic | initial stake and predictable process of \"moves\" | $\\psi = (\\psi^\\mathrm{stake}, \\psi^M)$ |\n",
    "capital process for strategy $\\psi$ | sequence of fortunes that result from playing strategy $\\psi$ | $K^\\psi$, where $K_0^\\psi := \\psi^\\mathrm{stake}$; $K_j^\\psi := K_{j-1}^\\psi + \\psi_j^My_j$ |\n",
    "\n",
    "In the next-to-last definition, $\\psi^\\mathrm{stake}$ is the initial stake $K_0$ for\n",
    "the strategy and $\\psi^M(\\omega^j)$ is the move $M_j$ the strategy $\\psi$ makes in situation $\\omega^{j-1}$.\n",
    "\n",
    "The set of strategies comprises a vector space: for any real number $\\beta$, if $\\psi = (\\psi^\\mathrm{stake}, \\psi^M)$\n",
    "is a strategy, so is \n",
    "\\begin{equation}\n",
    "\\beta \\psi := (\\beta \\psi^\\mathrm{stake}, \\beta\\psi^M),\n",
    "\\end{equation}\n",
    "and if\n",
    "$\\psi^1$ and $\\psi^2$ are strategies, so is \n",
    "\\begin{equation}\n",
    "\\psi^1 + \\psi^2 := (\\psi^{1,\\mathrm{stake}}+\\psi^{2,\\mathrm{stake}}, \\psi^{1,M} + \\psi^{2,M}).\n",
    "\\end{equation}\n",
    "\n",
    "Suppose $\\beta \\in [0, 1]$ and the strategies $\\psi^1$ and $\\psi^2$ have the same initial stake $K_0$. \n",
    "Then the convex combination of strategies \n",
    "\\begin{equation}\n",
    "\\beta \\psi^1 + (1-\\beta) \\psi^2\n",
    "\\end{equation}\n",
    "amounts to splitting the initial stake across the two strategies ($\\beta K_0$ for the first and $(1-\\beta)K_0$ for the\n",
    "second), and playing them in parallel. The capital process for the combination is\n",
    "\\begin{equation}\n",
    "K^{\\beta \\psi_1 + (1-\\beta) \\psi_2} = \\beta K^{\\psi_1} + (1-\\beta) K^{\\psi_2}.\n",
    "\\end{equation}\n",
    "\n",
    "Suppose that $\\beta_i \\ge 0$, $i \\in \\mathbb{N}$ with $\\sum_{i \\in \\mathbb{N}} \\beta_i = 1$;\n",
    "that the strategies $\\psi^i$, $i \\in \\mathbb{N}$ have the same initial capital $K_0$;\n",
    "and that the sums $\\sum_i \\beta_i \\psi^{i,M}(s)$ converge for every $s \\in \\mathbb{S} \\setminus \\{\\Box\\}$,\n",
    "then \n",
    "\\begin{equation}\n",
    "\\sum_i \\beta_i K^{\\psi^i}\n",
    "\\end{equation}\n",
    "converges and is the capital process of the strategy $\\sum_i \\beta_i \\psi^i$.\n",
    "That amounts to splitting the initial capital across countably many accounts and playing the corresponding\n",
    "strategy with each such account.\n",
    "\n",
    "**Definition:**  \n",
    "If Skeptic has a strategy $\\psi$ that guarantees that $K_j^\\psi \\ge 0$ for all $j$ and either\n",
    "$\\lim_{j \\rightarrow \\infty} K_j^\\psi = \\infty$  \n",
    "or some event $A$ occurs, then Skeptic can _force $A$_.\n",
    "In the language of probability, we would say that $A$ is _almost sure_.\n",
    "\n",
    "If Skeptic has a strategy $\\psi$ that forces $A$, Skeptic has a strategy that forces $A$ and starts with $K_0 = 1$.\n",
    "If Skeptic has a strategy $\\psi$ that forces $A$, Skeptic has a strategy that forces $A$ and ensures $K_j \\ge c$\n",
    "for any $c \\in (-\\infty, K_0)$.\n",
    "\n",
    "\n",
    "**Definition:**  \n",
    "If Skeptic has a strategy $\\psi$ that guarantees that $K_j^\\psi \\ge 0$ for all $j$ and either\n",
    "$\\sup_{j \\rightarrow \\infty} K_j^\\psi = \\infty$  \n",
    "or some event $A$ occurs, then Skeptic can _weakly force $A$_.\n",
    "\n",
    "**Lemma:** (Shaver & Vovk, Lemma 1.5)    \n",
    "If Skeptic can weakly force $A$ in the protocol above, Skeptic can force $A$ in that protocol.\n",
    "\n",
    "_Proof_:  Suppose Skeptic can weakly force $A$ using the strategy $\\psi$.\n",
    "Define the strategy $\\psi'$ as follows:\n",
    "\n",
    "+ Play $\\psi$ starting from $K_0 := K_0^\\psi$ until $K_j \\ge K_0+1$ (or forever if that never happens). Let $m$ be the smallest $j$ s.t. $K_j \\ge K_1+1$. Starting at round $m+1$, play the strategy \n",
    "\\begin{equation}\n",
    "M_j := \\frac{K_m-1}{K_m} \\psi_j^M.\n",
    "\\end{equation}\n",
    "That amounts to setting aside one unit of capital that will never be lost in future play.\n",
    "+ Continue until $K_j \\ge K_m+1$, then set aside another unit of capital by scaling down the moves $\\psi_j^M$ further.\n",
    "+ Keep repeating that process\n",
    "\n",
    "The resulting strategy has a nonnegative capital process. If $\\omega \\notin A$, \n",
    "the original strategy $\\psi$ had a supremum of $\\infty$, so this modified strategy would set aside a unit of capital infinitely many times: its capital would tend to infinity. Thus it forces $A$.\n",
    "\n",
    "**Lemma:** (Shafer & Vovk, Lemma 1.6)  \n",
    "If Skeptic can weakly force each of the events $A_1, A_2, \\ldots$ in the previous protocol, then Skeptic can weakly force\n",
    "$\\cap_i A_i$ in that protocol.\n",
    "\n",
    "_Proof:_  \n",
    "Suppose strategy $\\psi^k$ weakly forces $A_k$ and (wlog) starts with initial capital $K_0 = 1$.\n",
    "Since the strategy guarantees $K_j^{\\psi^k} \\ge 0$ for all $j$, $M_j \\le K_{j-1}$; thus \n",
    "\\begin{equation}\n",
    "K_j^{\\psi^k} \\le 2K_{j-1}^{\\psi^k},\n",
    "\\end{equation}\n",
    "and hence $K_j^{\\psi^k} \\le 2^j$ and $|\\psi_j^{k,M}| \\le 2^j$ for all $k$ and all $j$.\n",
    "Now define \n",
    "\\begin{equation}\n",
    "\\psi := \\sum_{k \\in \\mathbb{N}} 2^{-k} \\psi^k.\n",
    "\\end{equation}\n",
    "The sums implicit in that sum all converge: the convex combination makes sense mathematically.\n",
    "Since $\\psi^k$ weakly forces $A_k$, $\\psi$ weakly forces $A_k$, starting with initial capital $2^{-k}$.\n",
    "The strategy $\\psi$ thus forces $\\cap_k A_k$.\n",
    "\n",
    "**Lemma:** (Shafer & Vovk, Lemma 1.7)  \n",
    "Suppose $\\kappa > 0$. In the protocol above, Skeptic can weakly force\n",
    "\\begin{equation}\n",
    "{\\lim \\sup}_{j \\rightarrow \\infty} \\bar{y}_j \\le \\kappa\n",
    "\\end{equation}\n",
    "and \n",
    "\\begin{equation}\n",
    "{\\lim \\inf}_{j \\rightarrow \\infty} \\bar{y}_j \\ge -\\kappa.\n",
    "\\end{equation}\n",
    "\n",
    "_Proof:_  \n",
    "Assume wlog that $\\kappa \\le 1/2$. Let $\\psi$ have $K_0 := 1$ and $M_j := \\kappa K_{j-1}$.\n",
    "Then $K_0^\\psi = 1$ and\n",
    "\\begin{equation}\n",
    " K_j^\\psi = \\prod_{i=1}^j (1 + \\kappa y_i).\n",
    "\\end{equation}\n",
    "Suppose $\\omega$ has $\\sup_j K_j^\\psi(\\omega) = C_\\omega < \\infty$.\n",
    "Then \n",
    "\\begin{equation}\n",
    "\\sum_{i=1}^j \\ln (1+\\kappa y_i) \\le \\ln C_\\omega, \\;\\; \\forall j.\n",
    "\\end{equation}\n",
    "Now $\\ln(1+t) \\ge t - t^2$ for $t \\ge -1/2$, so for all $j$, \n",
    "\\begin{equation}\n",
    "\\kappa \\sum_{i=1}^j y_i - \\kappa^2 \\sum_{i=1}^j y_i^2 \\le \\ln C_\\omega.\n",
    "\\end{equation}\n",
    "But $\\sum_{i=1}^j y_i^2 \\le j$, so\n",
    "\\begin{equation}\n",
    "\\kappa \\sum_{i=1}^j y_i - \\kappa^2 j \\le \\ln C_\\omega,\n",
    "\\end{equation}\n",
    "i.e.,\n",
    "\\begin{equation}\n",
    "\\bar{y}_j \\le \\frac{\\ln C_\\omega}{\\kappa j} + \\kappa,\n",
    "\\end{equation}\n",
    "so the lim sup holds for that $\\omega$.\n",
    "The same argument, mutatis mutandi, shows that the lim inf holds too.\n",
    "\n",
    "**Proposition:** (Shafer & Vovk, Proposition 1.2)  \n",
    "Skeptic can force $\\lim_{j \\rightarrow \\infty} \\bar{y}_j = 0$.\n",
    "\n",
    "_Proof:_  \n",
    "Skeptic can weakly force $\\lim \\sup \\le \\kappa$ and $\\lim \\inf \\ge -\\kappa$ for $\\kappa = 2^{-k}$, $k = 1, \\ldots$.\n",
    "Hence Skeptic can weakly force the intersection.\n",
    "Hence Skeptic can force the intersection.\n",
    "\n",
    "These ideas can be used to prove important theorems in probability (e.g., the weak law or large numbers)\n",
    "without mentioning or defining probability.\n",
    "The basic equivalence is that the occurrence of an event with probability zero corresponds to the Skeptic winning an unbounded amount of money.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72bc2261-3762-451b-8bbb-94cde1da72e7",
   "metadata": {},
   "source": [
    "### Warranties\n",
    "\n",
    "A _warranty_ is a claim that a set of hypotheses contains the truth, analogous to a confidence set.\n",
    "A _$1/\\alpha$_ warranty corresponds to a $1-\\alpha$ confidence set: the set of parameters for which the betting score is not greater than $1/\\alpha$.\n",
    "The Skeptic's bet against any of the hypotheses (i.e., parameters) in the warranty set would not have turned \\\\$1 into as much as \\\\$$1/\\alpha$, but the Skeptic would have won at least \\\\$$1/\\alpha$ betting against any hypothesis not in the $1/\\alpha$-warranty set.\n",
    "Warranty sets are automatically nested: the $1/\\alpha$-warranty set contains the $1/\\alpha'$-warranty set if $\\alpha \\ge \\alpha'$ for any given betting scheme."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8920d2c6-02e0-40c3-bd7f-feb42a8e1471",
   "metadata": {},
   "source": [
    "## E-values formalized\n",
    "\n",
    "**Definition.**  \n",
    "Let $(\\Omega, \\mathcal{F}, \\mathbb{P})$ be a probability space,\n",
    "and let $E$ be a random variable $E: \\Omega \\rightarrow [0, \\infty]$ such that\n",
    "$\\mathbb{P}(E) := \\int_{\\Omega} E(\\omega) d\\mathbb{P}(\\omega) \\le 1$. \n",
    "(Note that $E$ may take the value $\\infty$, which\n",
    "corresponds to the strongest possible evidence that the data do not come from $\\mathbb{P}$.)\n",
    "Then **$E$ is an $E$-variable for $\\mathbb{P}$.**\n",
    "\n",
    "Let $\\mathcal{P}$ be a collection of probability distributions on the measurable space $(\\Omega, \\mathcal{F})$,\n",
    "and let $E$ be a random variable $E: \\Omega \\rightarrow [0, \\infty]$ such that for all $\\mathbb{P} \\in \\mathcal{P}$,\n",
    "$\\mathbb{P}(E) \\le 1$.\n",
    "Then **$E$ is an $E$-variable for $\\mathcal{P}$.**\n",
    "\n",
    "The set of all $E$-variables for a collection $\\mathcal{P}$ of probability distributions is $\\mathcal{E}(\\mathcal{P})$.\n",
    "\n",
    "The observed value of an $E$-variable is an $E$-value (or $e$-value).\n",
    "\n",
    "**Definition.**     \n",
    "Suppose $\\Omega$ is a sample space, $\\mathcal{F}$ is a sigma-algebra on $\\Omega$,\n",
    "and $\\mathbb{F}$ is a filtration on $\\mathcal{F}$ indexed by $\\mathbb{N}$.\n",
    "Let $\\mathcal{P}_0$ be a collection of distributions such that for each $\\mathbb{P} \\in \\mathcal{P}_0$,\n",
    "$(\\Omega, \\mathcal{F}, \\mathbb{F}, \\mathbb{P})$ is a filtered probability space.\n",
    "The nonnegative random variable $E_j$ is a $\\mathcal{F}_{j-1}$-conditional $E$-variable (for the null hypothesis $\\mathcal{P}_0$) if it is $\\mathcal{F}_j$-measurable and \n",
    "\\begin{equation}\n",
    "\\forall \\mathbb{P} \\in \\mathcal{P}_0, \\;\\; \\mathbb{P} \\left ( \\mathbb{E}_\\mathbb{P} (E_j | \\mathcal{F}_{j-1}) \\le 1 \\right ) = 1.\n",
    "\\end{equation}\n",
    "If for every $j \\in \\mathbb{N}$, $E_j$ is a $\\mathcal{F}_{j-1}$-conditional $E$-variable\n",
    "for $\\mathcal{P}_0$,\n",
    "$\\{E_j\\}_{j \\in \\mathbb{N}}$ is a _conditional $E$-variable collection relative to $\\mathbb{F} = \\{\\mathcal{F}_j\\}_{j \\in \\mathbb{N}}$ for $\\mathcal{P}_0$_, or an _$E$-process for $\\mathcal{P}_0$_.\n",
    "\n",
    "The running product of an $E$-process for $\\mathcal{P}_0$ is a test supermartingale for $\\mathcal{P}_0$:\n",
    "define $E^j := \\prod_{i=1}^j E_j$.\n",
    "Then for every $\\mathbb{P} \\in \\mathcal{P}_0$, $(E^j)_{j \\in \\mathbb{N}}$ is\n",
    "a nonnegative supermartingale starting at 1.\n",
    "\n",
    "Conversely, suppose $(T_i)_{i \\in \\mathbb{N}}$ is a test supermartingale for every $\\mathbb{P} \\in \\mathcal{P}_0$.\n",
    "Then $(T_i)_{i \\in \\mathbb{N}}$ is an $E$-process for $\\mathcal{P}_0$. (Ramdas et al., 2021)\n",
    "Hence, for any stopping time $\\tau$, $T_\\tau$ is an $E$-value for $\\mathcal{P}_0$.\n",
    "(This allows us to use Ville's inequality to turn $E$-processes into sequentially valid\n",
    "$P$-values.)\n",
    "\n",
    "\n",
    "**Definition.**  \n",
    "Let $(\\Omega, \\mathcal{F}, \\mathbb{P})$ be a probability space,\n",
    "and let $P$ be a random variable $P: \\Omega \\rightarrow [0, 1]$ such that\n",
    "$\\forall p \\in [0, 1]$,\n",
    "$\\mathbb{P}(P \\le p) \\le p$.\n",
    "Then **$P$ is a P-variable for $\\mathbb{P}$.**\n",
    "\n",
    "Let $\\mathcal{P}$ be a collection of probability distributions on the measurable space $(\\Omega, \\mathcal{F})$,\n",
    "and let $P$ be a random variable $P: \\Omega \\rightarrow [0, 1]$ such that for all $\\mathbb{P} \\in \\mathcal{P}$,\n",
    "$\\forall p \\in [0, 1]$,\n",
    "$\\mathbb{P}(P \\le p) \\le p$.\n",
    "Then **$P$ is a P-variable for $\\mathcal{P}$.**\n",
    "\n",
    "The set of all $P$-variables for a collection $\\mathcal{P}$ of probability distributions is $\\mathcal{P}(\\mathcal{P})$.\n",
    "\n",
    "\n",
    "The observed value of a $P$-variable is a $P$-value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2009f18a-aec3-4aac-b2e3-12823b11872a",
   "metadata": {},
   "source": [
    "## Picking the bets\n",
    "\n",
    "The _GRO (growth rate optimal) criterion_ for testing the null $\\mathcal{P}_0$\n",
    "against a simple alternative $\\mathbb{Q}$ is\n",
    "\\begin{equation}\n",
    " \\mathrm{GRO}(\\mathbb{Q}) := \\sup_{E \\in \\mathcal{E}(\\mathcal{P}_0)} \\mathbb{Q} \\ln E\n",
    "\\end{equation}\n",
    "Grünwald et al. (2023) show this is equal to\n",
    "$D(\\mathbb{Q} || \\mathbb{P}_0^*)$ for a particular essentially unique\n",
    "subdistribution $\\mathbb{P}_0^*$.\n",
    "\n",
    "The _GROW (growth rate optimal in the worst case) criterion_ for testing the composite null \n",
    "$\\mathcal{P}_0$ against the composite alternative $\\mathcal{Q}$ is\n",
    "\\begin{equation}\n",
    "\\mathrm{GROW}(\\mathcal{Q}) := \\sup_{E \\in \\mathcal{E}(\\mathcal{P}_0)} \\inf_{\\mathbb{Q} \\in \\mathcal{Q}}\n",
    "\\mathbb{Q} \\ln E.\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "The _REGROW (relative growth rate in the worst case) criterion_ requires a bit of math and definitions\n",
    "to set up, but the idea is first to imagine that, if $\\mathcal{Q}$ is true, we\n",
    "know _which_ $\\mathbb{Q} \\in \\mathcal{Q}$ is true, so we could pick $E \\in \\mathcal{E}(\\mathcal{P}_0)$ to maximize $\\mathbb{Q} \\ln E$.\n",
    "Then we consider picking $E$ so that no matter which $\\mathbb{Q} \\in \\mathcal{Q}$ is true, the expected\n",
    "growth rate would be near that optimum. This is analogous to _regret_ in the context of decision theory.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c47748ee-5f48-4dfe-b31b-edc7f8443331",
   "metadata": {},
   "source": [
    "## Converting between $E$-variables and $P$-variables\n",
    "\n",
    "Because an $E$-variable is nonnegative and has expected value 1 under the null, the chance that it exceeds $1/\\alpha$\n",
    "is at most $\\alpha$ if the null is true.\n",
    "Thus it's easy to convert an $E$-value into a $P$-value.\n",
    "But it isn't as easy to convert an $P$-variable into an $E$-variable, because all an $E$-variable has to satisfy is nonnegativity and unit expectation, while a $P$-variable has to have $\\mathbb{P} (P \\le p) \\le p$ for all $p \\in [0, 1]$.\n",
    "There are transformations that force that inequality, but there is no clear choice among them."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1029036d-a146-4b18-ac35-f0e6afd62e28",
   "metadata": {},
   "source": [
    "### $P$ to $E$ calibration function\n",
    "\n",
    "Suppose $f : [0, 1] \\rightarrow [0, \\infty]$  is a ($P$-to-$E$) calibrator if, for any probability space \n",
    "$(\\Omega, \\mathcal{F}, \\mathbb{P})$ and any $P$-variable $P \\in  \\mathcal{P}_\\mathbb{P}$,\n",
    "$f(P) \\in \\mathcal{E}(\\mathcal{P})$.\n",
    "\n",
    "A calibrator $f$ *dominates* a calibrator $g$ if $f \\ge g$; $f$ *strictly dominates* $g$ if $f \\ge g$ and $f \\ne g$.\n",
    "A calibrator is *admissible* if it is not strictly dominated by any other calibrator.\n",
    "\n",
    "The following proposition (Vovk & Wang, 2021 Proposition 2.2)\n",
    "says that a calibrator is a nonnegative decreasing\n",
    "function on $[0, 1]$ whose integral is at most 1.\n",
    "\n",
    "**Proposition.**  \n",
    "A decreasing function $f : [0, 1] \\rightarrow [0, \\infty]$ is a calibrator if\n",
    "and only if $\\int_0^1 fdp \\le 1$. \n",
    "It is admissible if and only if it is upper semicontinuous,\n",
    "$f(0) = \\infty$, and $\\int_0^1 fdp = 1$.\n",
    "\n",
    "Examples.\n",
    "\n",
    "\\begin{equation}\n",
    "f^\\kappa(p) := \\kappa p^{\\kappa−1}, \\;\\; \\kappa \\in (0, 1).\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "f(p) := \\int_0^1 \\kappa p^{\\kappa-1} d\\kappa = \\frac{1 + p - p\\ln p}{p (\\ln p)^2}.\n",
    "\\end{equation}\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28119c24-d418-4b0b-a244-69b29bdab4c9",
   "metadata": {},
   "source": [
    "### $E$ to $P$ calibration function\n",
    "\n",
    "An $E$-to-$P$ calibrator transforms $E$-variables to $P$-variables.\n",
    "A decreasing function $f : [0, \\infty] \\rightarrow [0, 1]$ is an $E$-to-$P$ calibrator if, \n",
    "for any probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$ and any $E$-variable $E$\n",
    "$f(E)$ is a $P$-variable for $\\mathbb{P}$. \n",
    "There is a clear \"best\" $E$-to-$P$ calibrator: $\\min(1, 1/x)$.\n",
    "\n",
    "\n",
    "**Proposition:** Vovk & Wang (2020)  \n",
    "The function $f : [0, \\infty] \\rightarrow [0, 1]$, $f(x) := \\min(1, 1/x)$\n",
    "is an $E$-to$P$ calibrator.\n",
    "It dominates every other $E$-to-$P$ calibrator, so it is the only admissible $E$-to-$P$ calibrator.\n",
    "\n",
    "_Proof:_   \n",
    "For any nonnegative random variable $E$ with expected value $1$ and any $x \\in [0, 1]$, \n",
    "\\begin{eqnarray}\n",
    " \\mathbb{P}\\{f(E) \\le x \\} &=& \\mathbb{P}\\{E \\ge 1/x \\} \\\\\n",
    " &\\le & \\frac{1/x}{ \\mathbb{P}E} \\mbox{ (by Markov's inequality)}\\\\\n",
    " &=& 1/x \\mbox{ (since } \\mathbb{P}E \\le 1 \\mbox{ )}\n",
    "\\end{eqnarray}\n",
    "To show $\\min(1, 1/x)$ is admissible, let $f$ be any other $E$-to-$P$-calibrator, and suppose\n",
    "there is some $x \\in [0, \\infty]$ for which $f(x) < \\min(1, 1/x)$.\n",
    "\n",
    "+ Suppose $f(x) < \\min(1, 1/x) = 1/x$ for some particular $x > 1$. \n",
    "Define an $E$-variable $E$ that has two possible values, 0 and $1/x$, with\n",
    "$\\mathbb{P} \\{E = 0 \\} = 1-1/x$ and $\\mathbb{P} \\{E = x \\} = 1/x$.\n",
    "Then \n",
    "Then \n",
    "\\begin{equation}\n",
    " \\mathbb{P} \\{f(E) \\le f(x)\\} = \\mathbb{P} \\{f(E) = f(x)\\} = 1/x > f(x),\n",
    "\\end{equation}\n",
    "so $f(E)$ is not a $P$-variable. \n",
    "\n",
    "+ Suppose $f(x) < \\min(1, 1/x) = 1$ for some particular $x \\in [0, 1]$.\n",
    "Define an $E$-variable $E$ with $\\mathbb{P}\\{ E = x \\} = 1$. \n",
    "Then $\\mathbb{P} \\{f(E) \\le f(x) \\} = 1$, but $f(x) < 1$, so $f(E)$ is not a $P$-variable.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18d2780a-13dd-4aa0-a811-f8a943acdfbc",
   "metadata": {},
   "source": [
    "## Combining $E$-values\n",
    "\n",
    "Combining $P$-variables is difficult, because the combination needs to have a distribution that\n",
    "satisfies $\\mathbb{P}_0\\{P_{\\mathrm{combined}} \\le x\\} \\le x$, $ \\forall x \\in [0, 1]$: in general, linear combinations and products of $P$-values do not satisfy that requirement.\n",
    "(See [combining tests](./tests-combo.ipynb).)\n",
    "Fisher's combining function is an example that works for independent $P$-values.\n",
    "Sequentially valid $P$-values are also in general difficult to construct; the notable exception is\n",
    "$P$-values based on nonnegative supermartingales--which are examples of $E$-values.\n",
    "\n",
    "In contrast, every convex linear combination of nonnegative random variables that each have expected value 1 is a nonnegative random variable with expected value 1, and a product of independent nonnegative random variables with expected value 1 is a nonnegative random variable with expected value 1.\n",
    "The relative simplicity of combining $E$-variables may be a good reason to use them in applications that involve testing\n",
    "multiple hypotheses, intersection hypotheses, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b42ec94-657c-4eaa-9b26-960be6458c76",
   "metadata": {},
   "source": [
    "**Definition.**  \n",
    "An $E$-merging function of $K$ $E$-values is an increasing Borel function \n",
    "$F : [0, \\infty]^K \\rightarrow [0, \\infty]$\n",
    "such that, for any probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$,\n",
    "if $\\{E_j\\}_{j=1}^K$ are $E$-variables variables on that space, so is $F(E_1, \\ldots, E_K)$.\n",
    "\n",
    "An $E$-merging function $F$ is _symmetric_ if it is invariant under permutations of its arguments,\n",
    "i.e., if $F(E_1, \\ldots, E_K) = F(E_{\\pi_1}, \\ldots, E_{\\pi_K})$ for every permutation $\\pi$ of $\\{1, \\ldots, K\\}$.\n",
    "\n",
    "**Definition.**  \n",
    "An $E$-merging function $F$ _essentially dominates_ an $E$-merging function $G$ if, for all $e \\in [0, \\infty)^K$,\n",
    "\\begin{equation}\n",
    "G(e) > 1 \\;\\; \\Rightarrow \\;\\; F(e) \\ge G(e).\n",
    "\\end{equation}\n",
    "That is, whenever the $E$-values merged by $G$ gives evidence against the null, the same $E$-values\n",
    "merged by $F$ gives stronger evidence against the null.\n",
    "\n",
    "**Proposition.**  (Vovk & Wang)  \n",
    "The arithmetic mean $M_K(e_1, \\ldots, e_K) := \\frac{1}{K}\\sum_{i=1}^K e_i$ essentially dominates\n",
    "all other symmetric $E$-merging functions.\n",
    "\n",
    "**Definition.**  \n",
    "An _independent $E$-merging function ($iE$-merging function)_ of $K$ \n",
    "independent $E$-values is an increasing Borel function \n",
    "$F : [0, \\infty]^K \\rightarrow [0, \\infty]$\n",
    "such that, for any probability space $(\\Omega, \\mathcal{F}, \\mathbb{P})$,\n",
    "if $\\{E_j\\}_{j=1}^K$ are independent $E$-variables variables on that space, then $F(E_1, \\ldots, E_K)$\n",
    "is an $E$-value on that space.\n",
    "\n",
    "Examples of $iE$-merging functions include multiplication and averaging. In particular, the $U$-statistics\n",
    "are valid $iE$-merging functions:\n",
    "\\begin{equation}\n",
    "   U_n(e_1, \\ldots, e_K) := \\frac{1}{{K \\choose n}} \\sum_{\\{k_1, \\ldots, k_n \\} \\subset \\{1, \\ldots, K\\}} \n",
    "   e_{k_1}e_{k_1} \\cdots e_{k_n}, \\;\\;\\; n \\in \\{0, 1, \\ldots, K\\}.\n",
    "\\end{equation}\n",
    "For $n=0$, $U_n = 1$. For $n=1$, $U_n$ is the mean of all $K$ $E$-values. For $n=K$, $U_n$ is the product of all $K$\n",
    "$E$-values.\n",
    "Convex combinations of $U$-statistics of $E$-values are also $iE$-merging functions.\n",
    "\n",
    "**Definition.**\n",
    "An $iE$-merging function $F$ _weakly dominates_ an $iE$-merging function $G$ if, for all \n",
    "$(e_1, \\ldots , e_K) \\in [1, \\infty)^K$  (_not necessarily in_ $[0, \\infty)^K$, \n",
    "\\begin{equation}\n",
    "F(e_1, \\ldots ,e_K) \\ge G(e_1, \\ldots , e_K).\n",
    "\\end{equation}\n",
    "\n",
    "**Proposition.** (Vovk & Wang)  \n",
    "The product $(e_1, \\ldots, e_K) \\rightarrow \\prod_{i=1}^K e_j$\n",
    "weakly dominates every $iE$-merging function.\n",
    "\n",
    "\n",
    "Multiplication can also be used to combine sequential $E$-values: if the expected value of the next bet given the outcome of all previous bets is always 1, then the betting scores can be multiplied."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f480b94-3245-48e1-bcdd-f9b0699e026e",
   "metadata": {},
   "source": [
    "It isn't always desirable to use symmetric $E$-merging functions.\n",
    "\n",
    "Suppose $(E_{jt})_{t \\in \\mathbb{N}}$ is an $E$-process for $\\mathcal{P}_0$ for the filtration $(\\mathcal{F}_{jt})_{t \\in \\mathbb{N}}$, $j = 1, \\ldots, K$, \n",
    "and let $(\\gamma_{jt})_{t \\in \\mathbb{N}}$ be predictable with respect to $(\\mathcal{F}_{jt})$\n",
    "and satisfy $\\gamma_{jt} \\ge 0$ and $\\sum_{j=1}^K \\gamma_{jt} \\le 1$.\n",
    "\n",
    "Define $\\gamma_t \\cdot E_t := \\sum_{j=1}^K  \\gamma_{jt} E_{jt}$.\n",
    "Then $(\\gamma_t \\cdot E_t)_{t \\in \\mathbb{N}}$ is an $E$-process for $\\mathcal{P}_0$.\n",
    "\n",
    "\n",
    "Can adaptively bet more on $E$-processes that are growing large."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d176b8fd-faca-42cb-97af-cfa48b9d0e40",
   "metadata": {},
   "source": [
    "## Testing multiple hypotheses using $E$-values\n",
    "\n",
    "See:\n",
    "+ Marcus, R., E. Peritz, and K.R. Gabriel, 1976. On Closed Testing Procedures with Special Reference to Ordered Analysis of Variance, _Biometrika, 63_, 655-660, https://doi.org/10.2307/2335748\n",
    "\n",
    "+ pp1743ff of Vovk & Wang. \n",
    "\n",
    "We have a set of $K$ composite null hypotheses, $\\{\\mathcal{P}_k \\}_{k=1}^K$.\n",
    "We want to test all $K$ hypotheses in such a way that the chance of erroneously rejecting one or more true nulls is \n",
    "at most $\\alpha$; that is,\n",
    "we want the _familywise error rate_ to be at most $\\alpha$.\n",
    "\n",
    "Let $\\mathcal{P}$ denote the set of all intersections of subsets of $\\{\\mathcal{P}_k\\}$.\n",
    "The _closure principle_ says that if we test as follows.\n",
    "Suppose we have a level $\\alpha$ test of every (composite) null in $\\mathcal{P}$.\n",
    "If we reject a null $\\mathcal{P}_0 \\in \\mathcal{P}$ only if its test and the \n",
    "test of every hypothesis in $\\mathcal{P}$ that is a subset of $\\mathcal{P}_0$ all reject, then\n",
    "the familywise error rate is at most $\\alpha$.\n",
    "\n",
    "The proof is simple. Let $A$ be the event that any _true_ $\\mathcal{P}_k$ is rejected.\n",
    "Let $B$ be the event that the intersection of all the true nulls is rejected (that _every_ true null is rejected).\n",
    "Because $\\mathcal{P}$ is closed under intersections, the intersection of all true nulls is one of the hypotheses in $\\mathcal{P}$.\n",
    "Then\n",
    "\\begin{equation}\n",
    "\\mathbb{P} \\{A \\cap B \\} = \\mathbb{P}(A | B) \\mathbb{P}(B) \\le \\alpha\n",
    "\\end{equation}\n",
    "since the intersection is tested at level $\\alpha$.\n",
    "Clearly $\n",
    "But since this procedure will only reject a true null if it has also rejected the intersection of all\n",
    "true nulls, $\\{A \\cap B \\} = A$, and hence $\\mathbb{P}(A) \\le \\alpha$.\n",
    "\n",
    "Let's translate this into tests using $E$-values.\n",
    "Suppose that for each hypothesis $k$, we have an $E$-variable $E_k$, i.e., a nonnegative extended-real-valued random variable such that\n",
    "\\begin{equation}\n",
    "   \\mathbb{P}E_k \\le 1 \\;\\;\\; \\forall \\mathbb{P} \\in \\mathcal{P}_k.\n",
    "\\end{equation}\n",
    "Vovk & Wang give two algorithms, one for any $E$-values and one for sequential $E$-values.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ee252b0-6f41-4e0c-85a4-24ab04ffdd2f",
   "metadata": {},
   "source": [
    "### Algorithm 1: adjusting $E$-values for multiplicity\n",
    "\n",
    "+ Input: a multiset of $E$-values $e_1, \\ldots, e_K$.\n",
    "+ Order them so that $e_{(1)} \\le e_{(2)} \\le \\cdots \\le e_{(K)}$.\n",
    "+ Set $S_0 := 0$.\n",
    "+ for $i = 1, \\ldots, K$:\n",
    "    - $S_i := S_{i-1} + e_{(i)}$\n",
    "+ for $k=1, \\ldots, K$:\n",
    "    - $e_{(k)}^* := e_{(k)}$\n",
    "    - for $i = 1, \\ldots, k-1$:\n",
    "        + $e := \\frac{e_{(k)} + S_i}{i+1}$\n",
    "        + $e_{(k)}^* := \\min(e_{(k)}^*, e)$\n",
    "    \n",
    "### Algorithm 2: adjusting sequential $E$-values for multiplicity\n",
    "\n",
    "+ Input: a sequence of $E$-values $e_1, \\ldots, e_K$.\n",
    "+ let $a$ be the product of all the $E$-values that are less than $1$, or $1$ if there are none\n",
    "+ for $k=1, \\ldots, K$:\n",
    "    - $e_k^* := ae_k$\n",
    "    \n",
    "Both of these ways of adjusting the $E$ values gives familywise valid $E$-values, in the sense that the expected\n",
    "value of the maximum (across composite nulls) $E$-value is not greater than $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a692d6c7-9984-4ae9-9841-f6eaf5149f80",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Controlling the false discovery rate (FDR) with $P$-values and $E$-values\n",
    "\n",
    "See:\n",
    "\n",
    "+ Benjamini, Y. and Y. Hochberg, 1995. Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing, _JRSSB, 57_, 289-300. https://www.jstor.org/stable/2346101\n",
    "\n",
    "+ Benjamini, Y. and D. Yekutieli, 2001. The control of the false discovery rate in multiple testing under dependency, _Ann. Statist., 29_, (4) 1165-1188. https://doi.org/10.1214/aos/1013699998\n",
    "\n",
    "+ Wang and Ramdas, 2022. False Discovery Rate Control with E-values, _Journal of the Royal Statistical Society Series B, 84_, 822–852. https://doi.org/10.1111/rssb.12489 \n",
    "\n",
    "The _False Discovery Rate_ (FDR) of a testing procedure is the expected fraction of rejected null hypotheses that were indeed false. That is, let $V$ denote the number of incorrectly rejected null hypotheses and let $R$ denote the total number of rejected null hypotheses, and define\n",
    "\\begin{equation}\n",
    "  \\mbox{FDR} := \\mathbb{E}(V/R | R>0) \\mathbb{P}(R>0).\n",
    "\\end{equation}\n",
    "(The conditioning is to prevent division by zero; it amounts to defining $V/R$ to be zero when $V$ (and therefore also $R$)\n",
    "is 0.\n",
    "This makes sense because if no hypothesis was rejected, no hypothesis was erroneously rejected.)\n",
    "\n",
    "The Benjamini-Hochberg procedure for testing $K$ hypotheses at FDR level $\\alpha$ is as follows:\n",
    "Let $\\{P_1, \\ldots, P_K\\}$ be the $P$-values of the $K$ hypotheses, \n",
    "and let $\\{\\{P_{(1)}, \\ldots, P_{(K)}\\}$\n",
    "be the $P$-values ordered so that $P_{(1)} \\le \\cdots \\le P_{(K)}$.\n",
    "\n",
    "+ Find the largest $k$ such that $P_{(k)} \\le \\frac{k}{K} \\alpha$.\n",
    "+ Reject the corresponding null hypotheses.\n",
    "\n",
    "This procedure works for independent $P$-values and $P$-values that have _positive regression dependence_.\n",
    "It guarantees that $\\mbox{FDR} \\le \\frac{m_0}{m}\\alpha \\le \\alpha$, where $m_0$ is the number of true null\n",
    "hypotheses.\n",
    "The Benjamini-Yekutieli procedure works for arbitrary dependence. It involves an additional\n",
    "function $c(K):= \\sum_{i=1}^K 1/i$:\n",
    "\n",
    "+ Find the largest $k$ such that $P_{(k)} \\le \\frac{k}{Kc(K)} \\alpha$.\n",
    "+ Reject the corresponding null hypotheses.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d331df9f-b9f2-4c73-bd14-b5fc26bc9cbd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}