kaplan-markov-taint.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "27ca0a1e-be70-4af8-9301-ba214b6bd4e7",
   "metadata": {},
   "source": [
    "## Kaplan-Markov batch-level comparison using PPEB\n",
    "\n",
    "Convert to SHANGRLA notation. \n",
    "\n",
    "Ballots are partitioned into batches $\\{\\mathcal{B}_k\\}_{k=1}^K$.\n",
    "Batch $\\mathcal{B}_k$ contains $N_k \\ge 0$ cards; there are $N = \\sum_k N_k$ cards in all.\n",
    "The assorter upper bound is $u$.\n",
    "The true assorter total for batch $k$ is $A_k^b \\in [0, N_k u]$; the reported total for batch $k$\n",
    "is $A_k^c \\in [0, N_k u]$;\n",
    "the _overstatement_ in batch $k$ is $e_k := A_k^c - A_k^b \\in [A_k^c-Nu, A_k^c]$ and\n",
    "the _taint_ in batch $k$ is $T_k := 1- e_k/A_k^c = 1- (A_k^c - A_k^b)/A_k^c \\in [0, Nu/A_k^c]$.\n",
    "The reported assorter total is $A_0^c := \\sum_k A_k^c = N\\bar{A}^c$;\n",
    "the true assorter total is $A_0^b := \\sum_k A_k^b = N\\bar{A}^b$; the _total overstatement_ is $e = A_0^c - A_0^b$;\n",
    "and the _total taint_ is $T_0 := 1-e/A_0^c$.\n",
    "\n",
    "Define $u := \\sum_k A_k^c$. This is an upper bound on the total overstatement.\n",
    "The assertion is true if $\\bar{A}^b > 1/2$, i.e., if $A_0^b > N/2$ or \n",
    "So the assertion holds if $e < u - N/2$, i.e., if $e/u < (u-N/2)/u = 1-N/(2u)$ or\n",
    "$1-e/u > N/(2u)$.\n",
    "\n",
    "We sample batches, with probability of selecting batch $j$ proportional to $u_j$.\n",
    "Let $J_i$ denote the index of the batch selected on the $j$th draw; let \n",
    "$T_i := 1 - e_{J_i}/u_{J_i} \\ge 0$ be the _taint_ of that batch.\n",
    "If the sample is drawn without replacement, let $\\mathcal{J}_i := \\cup_{j=1}^i J_i$ be the \n",
    "indices of the batches that have been selected\n",
    "up to and including the $i$th draw.\n",
    "If the sample is drawn with replacement, let $\\mathcal{J}_i := \\emptyset$.\n",
    "Let $\\bar{\\mathcal{J}}_i := \\{1, \\ldots, K\\} \\setminus \\mathcal{J}_i$ be the complement of $\\mathcal{J}_i$.\n",
    "For any $\\mathcal{J} \\subset \\{1, \\ldots, K\\}$, let\n",
    "\\begin{eqnarray}\n",
    "u_{\\mathcal{J}} &:=& \\sum_{j \\in \\mathcal{J}} u_j \\\\\n",
    "e_{\\mathcal{J}} &:=& \\sum_{j \\in \\mathcal{J}} e_j\n",
    "\\end{eqnarray}\n",
    "The chance of drawing batch $j$ in draw $i$ is zero if $j \\in \\mathcal{J}_i$; it is\n",
    "$u_j/(u-u_{\\mathcal{J}_i} )$ if $j \\notin \\mathcal{J}_i$.\n",
    "(For sampling with replacement, this is equal to $u_j/u$ in each draw.)\n",
    "Now\n",
    "\\begin{eqnarray}\n",
    "\\mathbb{E} (T_i | T_1, \\ldots, T_{i-1}) \n",
    "   &=& \\sum_{j \\in \\bar{\\mathcal{J}}_{i-1}} \\frac{u_j}{u_{\\bar{\\mathcal{J}}_{i-1}}} (1-e_j/u_j) \\\\\n",
    "   &=&  1 - e_{\\bar{\\mathcal{J}}_{i-1}}/u_{\\bar{\\mathcal{J}}_{i-1}}.\n",
    "\\end{eqnarray}\n",
    "Suppose $1-e/u = \\mu$, so $e = u(1-\\mu)$.\n",
    "Then $e_{\\bar{\\mathcal{J}}_{i-1}} = u(1-\\mu) - e_{\\mathcal{J}_{i-1}}$ and\n",
    "$u_{\\bar{\\mathcal{J}}_{i-1}} = u - u_{\\mathcal{J}_{i-1}}$.\n",
    "\\begin{eqnarray}\n",
    "\\mathbb{E} (T_i | T_1, \\ldots, T_{i-1}) \n",
    "  &=& 1 - \\frac{u(1-\\mu) - e_{\\mathcal{J}_{i-1}}}{u - u_{\\mathcal{J}_{i-1}}} \\\\\n",
    "  &=& \\frac{\\mu u + e_{\\mathcal{J}_{i-1}} - u_{\\mathcal{J}_{i-1}}}{u - u_{\\mathcal{J}_{i-1}}}.\n",
    "\\end{eqnarray}\n",
    "For sampling with replacement, that reduces to $\\mu$ because $\\mathcal{J}_{i-1} = \\emptyset$.\n",
    "Let $M_0 :=1$ and for $j>1$ define \n",
    "\\begin{equation}\n",
    "M_j := \\prod_{i \\le j} T_i \\cdot \\frac{u - u_{\\mathcal{J}_{i-1}}}{N/2 + e_{\\mathcal{J}_{i-1}} - u_{\\mathcal{J}_{i-1}}}.\n",
    "\\end{equation}\n",
    "Then $(M_i)_{i \\in \\mathbb{N}}$ is a nonnegative supermartingale starting at 1\n",
    "if $1-e/u \\le N/(2u)$. \n",
    "\n",
    "\n",
    "To estimate sample sizes for batch comparison audits, we will assume all $e_j$ are zero, so each term in the product contributes $2u/N$ to the supermartingale.\n",
    "The number of draws for the test statistic to exceed $1/\\alpha$ is $n = \\lceil \\log(1/\\alpha)/\\log(2u/N) \\rceil$.\n",
    "The chance batch $j$ is selected at least once in $n$ draws is $p_j := 1 - (1-u_j/u)^n$, so the\n",
    "expected sample size is $\\sum_j p_jN_j = \\sum_j N_j(1 - (1-u_j/u)^n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c65e69c-ea8e-4c5c-9df8-4b451602a06d",
   "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
}