```python
from __future__ import division
import math
import numpy as np
import numpy.random
import scipy as sp
import scipy.stats
from hypergeometric import *

%matplotlib inline
import matplotlib
import matplotlib.pyplot as plt

```

# Tri-hypergeometric test using the diluted margin as the test statistic

We will sample individual ballots without replacement from a population of $N$ ballots, of which
$N_w$ ballots have a vote for $w$ but not for $\ell$, $N_\ell$ ballots have a vote for $\ell$ but not for $w$, and $N_u = N - N_w - N_\ell$ ballots have votes for both $w$ and $\ell$ or neither $w$ nor $\ell$, including undervotes and invalid ballots.
We might draw a simple random sample of $n$ ballots ($n$ fixed ahead of time), or we might draw 
sequentially, so the sample size $B$ could be random, including stopping rules that depend on the data.

Regardless, we assume that, conditional on the attained sample size $n$, the ballots are a simple random sample
of size $n$ from the $N$ ballots in the population.
Then, conditional on $B=n$, the joint distribution of
$(B_w, B_\ell, B_u)$ is tri-hypergeometric.

That is,

\begin{equation}
    \mathbb{P}_{N_w, N_\ell, N} \{ B_w = i, B_\ell = j \vert B=n \} = 
     \frac{ {N_w \choose i}{N_\ell \choose j}{N - N_w - N_\ell \choose n-i-j}}{{N \choose n}}.
\end{equation}

To test, we will condition on the event $B=n$. (In contrast, the BRAVO ballot-polling
method conditions on $B_w+B_\ell = m$;
we might instead consider conditioning on $B=n$ _and_ $B_w + B_\ell = m$.)
The test statistic will be the diluted sample margin, $D \equiv (B_w - B_\ell)/B$.
This is the sample difference in the number of ballots for the winner and for the loser, divided by the 
total number of ballots in the sample.
We want to test the compound hypothesis $N_w - N_\ell \le c$ against the compound alternative
$N_w - N_\ell > c$.
(To use Wald's Sequential Probability Ratio Test, we might pick a simple alternative instead, e.g.,
$N_w = V_w$ and $N_\ell = V_\ell$, the reported values, assuming $V_w - V_\ell > c$.)
Hence, we will reject for large values of $D$.
Conditional on $B=n$, the event $D = (B_w - B_\ell)/B = d$ is the event $B_w - B_\ell = nd$.

Suppose we observe $D=d$.
The $p$-value of the simple hypothesis that there are $N_w$ ballots with
a vote for $w$ but not for $\ell$, $N_\ell$ ballots with a vote for $\ell$ but not for $w$, and $N - N_w - N_\ell$ ballots with votes for both $w$ and $\ell$ or neither $w$ nor $\ell$ (including undervotes and
invalid ballots) is

\begin{equation}
   \mathbb{P}_{N_w, N_\ell, N} \left \{ D \geq d \vert B = n \right \} = 
   \mathbb{P}_{N_w, N_\ell, N}\{ B_w - B_\ell \geq nd \vert B = n \} =
   \sum_{(i, j) : i - j \geq nd; i+j \leq n; i, j\geq 0} 
         \frac{ {N_w \choose i}{N_\ell \choose j}{N - N_w - N_\ell \choose n-i-j}}{{N \choose n}}.
\end{equation}
Below we show empirically (but do not prove) that this tail probability is monotone increasing in $N_w$.

This expression can be simplified for numerical stability:

\begin{equation}
\frac{ {N_w \choose i}{N_\ell \choose j}{N - N_w - N_\ell \choose n-i-j}}{{N \choose n}} =
  \frac{ N_w! N_\ell! (N - N_w - N_\ell)! n! (N-n)!}
       {i! (N_w-i)! j! (N_\ell - j)! (n-i-j)! (N - N_w - N_\ell - n +i+j)! N!}
\end{equation}

The composite null hypothesis does not specify $N_w$ or $N_\ell$ separately, only that $N_w - N_\ell \le c$ for
some fixed, known $c$.
The (conditional) $p$-value of this composite hypothesis for $D=d$ is
\begin{equation}
  \max_{N_w, N_\ell \in \{0, 1, \ldots, N \}: N_w - N_\ell \le c, N_w + N_\ell \le N}
   \sum_{(i, j) : i - j \geq nd; i+j \leq n; i, j\geq 0} 
         \frac{ {N_w \choose i}{N_\ell \choose j}{N - N_w - N_\ell \choose n-i-j}}{{N \choose n}},
\end{equation}
wherever the summand is defined. 
(Equivalently, define ${N \choose M} \equiv 0$ if $M > N$, $M < 0$, or $N \le 0$.)
If the empirical result mentioned above is true, then finding the maximum is trivial; if not,
it is still at most a one-dimensional optimization problem.

## Experiment 1 - few invalids

Testing the hypothesis $\pi_w - \pi_\ell \leq 0$ -- the same as testing whether the winner and the loser got exactly the same vote share. This is in blue.
Then we also test the hypotheses $N_w - N_\ell \leq 1$ (in green) and $N_w - N_\ell \leq 2$ (in red).

Let $N = 100$, $n=30$, $n_w = 15$, $n_\ell=10$, and $n_u = 5$.

Below, we plot the $p$-values for varying values of $N_w$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(47)
for B in range(47):
    pvalues[B] = diluted_margin_trihypergeometric(w=15, l=10, n=30, N_w=B, N_l=B, N=100)

pvalues2 = np.zeros(47)
for B in range(47):
    pvalues2[B] = diluted_margin_trihypergeometric(w=15, l=10, n=30, N_w=B+1, N_l=B, N=100)

pvalues3 = np.zeros(47)
for B in range(47):
    pvalues3[B] = diluted_margin_trihypergeometric(w=15, l=10, n=30, N_w=B+2, N_l=B, N=100)
    
plt.plot(range(47), pvalues, 'blue', 
         range(1,48), pvalues2, 'green',
         range(2,49), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

## Experiment 2 - many invalids

Testing the hypothesis $\pi_w - \pi_\ell \leq 0$ -- the same as testing whether the winner and the loser got exactly the same vote share. This is in blue.
Then we also test the hypotheses $N_w - N_\ell \leq 1$ (in green) and $N_w - N_\ell \leq 2$ (in red).

Let $N = 100$, $n=30$, $n_w = 8$, $n_\ell=7$, and $n_u = 15$.

Below, we plot the $p$-values for varying values of $N_w$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(47)
for B in range(47):
    pvalues[B] = diluted_margin_trihypergeometric(w=8, l=7, n=30, N_w=B, N_l=B, N=100)

pvalues2 = np.zeros(47)
for B in range(47):
    pvalues2[B] = diluted_margin_trihypergeometric(w=8, l=7, n=30, N_w=B+1, N_l=B, N=100)

pvalues3 = np.zeros(47)
for B in range(47):
    pvalues3[B] = diluted_margin_trihypergeometric(w=8, l=7, n=30, N_w=B+2, N_l=B, N=100)
    
plt.plot(range(47), pvalues, 'blue', 
         range(47), pvalues2, 'green',
         range(47), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

# Hypergeometric test

Conditional on $B_{w\ell} = n_w+n_\ell$, the $p$-value is

\begin{equation}
\mathbb{P} \{ d \geq \frac{n_w - n_\ell}{n} | B_{w\ell} = n_w+n_\ell \} = \mathbb{P}\{ B_w - B_\ell \geq n_w - n_\ell | B_{w\ell} = n_w+n_\ell \} 
   = \sum_{(i, j) : i - j \geq n_w-n_\ell; i+j = n_w+n_\ell; i, j\geq 0} \frac{ {N_w \choose i}{N_\ell \choose j}}{{N_{w\ell} \choose n_w+n_\ell}}.
\end{equation}

Under the null hypothesis, $N_w - N_\ell \leq c$ for specified $c$, but neither parameter value is known.

We show empirically, but not analytically, below that the tail probability is monotone increasing in $N_w$.

Actually compute the $p$-value as

\begin{equation}
\mathbb{P} \{ d \geq \frac{n_w - n_\ell}{n} | B_{w\ell} = n_w+n_\ell \} = \mathbb{P}\{ B_w - B_\ell \geq n_w - n_\ell | B_{w\ell} = n_w+n_\ell \} 
   = \sum_{(i, j) : i - j \geq n_w-n_\ell; i+j = n_w+n_\ell; i, j\geq 0} \frac{ {N_\ell+c \choose i}{N_\ell \choose j}}{{2N_\ell+c \choose n_w+n_\ell}}.
\end{equation}

## Experiment 1 - few invalids

Testing the hypothesis $\pi_w - \pi_\ell \leq 0$ -- the same as testing whether the winner and the loser got exactly the same vote share. This is in blue.
Then we also test the hypotheses $N_w - N_\ell \leq 1$ (in green) and $N_w - N_\ell \leq 2$ (in red).

Let $N = 100$, $n=30$, $n_w = 15$, $n_\ell=10$, and $n_u = 5$.

Below, we plot the $p$-values for varying values of $N_w$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(47)
for B in range(1,47):
    pvalues[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B, N_l=B)

pvalues2 = np.zeros(47)
for B in range(1,47):
    pvalues2[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B+1, N_l=B)

pvalues3 = np.zeros(47)
for B in range(1,47):
    pvalues3[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B+2, N_l=B)
    
plt.plot(range(47), pvalues, 'blue', 
         range(1, 47+1), pvalues2, 'green',
         range(2, 47+2), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

## Experiment 1.5 - w < l

Testing the hypothesis $\pi_w - \pi_\ell \leq 0$ -- the same as testing whether the winner and the loser got exactly the same vote share. This is in blue.
Then we also test the hypotheses $N_w - N_\ell \leq 1$ (in green) and $N_w - N_\ell \leq 2$ (in red).

Let $N = 100$, $n=30$, $n_w = 10$, $n_\ell=15$, and $n_u = 5$.

Below, we plot the $p$-values for varying values of $N_w$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(47)
for B in range(1,47):
    pvalues[B] = diluted_margin_hypergeometric(w=10, l=15, N_w=B, N_l=B)

pvalues2 = np.zeros(47)
for B in range(1,47):
    pvalues2[B] = diluted_margin_hypergeometric(w=10, l=15, N_w=B+1, N_l=B)

pvalues3 = np.zeros(47)
for B in range(1,47):
    pvalues3[B] = diluted_margin_hypergeometric(w=10, l=15, N_w=B+2, N_l=B)
    
plt.plot(range(47), pvalues, 'blue', 
         range(1, 47+1), pvalues2, 'green',
         range(2, 47+2), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

## Experiment 2 - c < 0

Testing the hypothesis $\pi_w - \pi_\ell \leq 0$ -- the same as testing whether the winner and the loser got exactly the same vote share. This is in blue.
Then we also test the hypotheses $N_w - N_\ell \leq -1$ (in green) and $N_w - N_\ell \leq -2$ (in red).

Let $N = 100$, $n=30$, $n_w = 15$, $n_\ell=10$, and $n_u = 5$.

Below, we plot the $p$-values for varying values of $N_w$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(47)
for B in range(1,47):
    pvalues[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B, N_l=B)

pvalues2 = np.zeros(47)
for B in range(1,47):
    pvalues2[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B-1, N_l=B)

pvalues3 = np.zeros(47)
for B in range(1,47):
    pvalues3[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B-2, N_l=B)
    
plt.plot(range(47), pvalues, 'blue', 
         range(1, 47+1), pvalues2, 'green',
         range(2, 47+2), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

# Experiment 3 - varying the margin in the sample

Testing the hypothesis $N_w - N_\ell \leq 2$.

Let $N = 100$, $n=30$, and vary $n_w - n_\ell$ with $n_u = 15$.

Below, we plot the $p$-values for varying values of $N_w$. We see that the $p$-value is *not* always monotonically increasing in $N_w$.


```python
pvalues = np.zeros(47)
for B in range(1,47):
    pvalues[B] = diluted_margin_hypergeometric(w=8, l=7, N_w=B+2, N_l=B)

pvalues2 = np.zeros(47)
for B in range(1,47):
    pvalues2[B] = diluted_margin_hypergeometric(w=9, l=6, N_w=B+2, N_l=B)

pvalues3 = np.zeros(47)
for B in range(1,47):
    pvalues3[B] = diluted_margin_hypergeometric(w=10, l=5, N_w=B+2, N_l=B)
    
plt.plot(range(47), pvalues, 'blue', 
         range(47), pvalues2, 'green',
         range(47), pvalues3, 'red')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

# Comparing tri-hypergeometric and plain hypergeometric

## Experiment 1

Testing the hypothesis $\pi_w - \pi_\ell \leq 2/N$.
The tri-hypergeometric $p$-values are in blue and the hypergeometric $p$-values are in green, for increasing values of the parameter $N_w$.

Let $N = 100$, $n=30$, $n_w = 15$, $n_\ell=10$, and $n_u = 15$.

The $p$-value is maximized for each contour at the largest possible value of $N_w$, and the contours have increasing $p$-values as the constant $N_w - N_\ell$ decreases.


```python
pvalues = np.zeros(42)
for B in range(42):
    pvalues[B] = diluted_margin_trihypergeometric(w=15, l=10, n=30, N_w=B+2, N_l=B, N=100)
    
pvalues2 = np.zeros(42)
for B in range(42):
    pvalues2[B] = diluted_margin_hypergeometric(w=15, l=10, N_w=B+2, N_l=B)
    
plt.plot(range(2, 42+2), pvalues, 'blue', 
         range(2, 42+2), pvalues2, 'green')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

# Comparing tri-hypergeometric and plain hypergeometric

## Experiment 2

Testing the hypothesis $N_w - N_\ell \leq 2$.
The tri-hypergeometric $p$-values are in blue and the hypergeometric $p$-values are in green, for increasing values of the parameter $N_w$.

Let $N = 100$, $n=30$, $n_w = 8$, $n_\ell=7$, and $n_u = 15$.


```python
pvalues = np.zeros(42)
for B in range(42):
    pvalues[B] = diluted_margin_trihypergeometric(w=8, l=7, n=30, N_w=B+2, N_l=B, N=100)
    
pvalues2 = np.zeros(42)
for B in range(42):
    pvalues2[B] = diluted_margin_hypergeometric(w=8, l=7, N_w=B+2, N_l=B)

plt.plot(range(2, 42+2), pvalues, 'blue', 
         range(2, 42+2), pvalues2, 'green')
plt.xlabel("N_w")
plt.ylabel("p-value")
```

## Takeaways

* Not consistent whether the hypergeometric or tri-hypergeometric has more power. Perhaps hypergeometric actually is better!
* The $p$-value of each test is maximized at the smallest or largest value of $N_w$. Thus, to construct a conservative test, take $N_w + N_\ell = N - n_u$ or $N_w+N_\ell = w+\ell$, where $n_u$ is the number of invalid ballots or ballots for other candidates *in the sample*. These are crude upper and lower bounds on how many valid ballots for the winner or loser exist in the population.
* The p-values seem to be **increasing in c, the null hypothesis margin**. Thus, when testing a null hypothesis, the most conservative test lies on the boundary $N_w - N_\ell = c$, with $N_w$ as large as possible.

5b7d7b2a2d2726e903cc55ea5fd2170720416058
ipynb
Jupyter Notebook
code/tri-hypergeometric-tests.ipynb
zwt16300180060/CORLA18
9e5826245f80aeb8923c84550b8f8e39ed0325c5
CC-BY-4.0
2018-09-10T08:15:44.000Z
2021-02-04T08:35:06.000Z
code/tri-hypergeometric-tests.ipynb
ElectionAuditWare/CORLA18
f03af7a7b514746f40426bb204c531fabcd10baf
CC-BY-4.0
2018-08-14T16:43:48.000Z
2018-11-27T22:23:38.000Z
code/tri-hypergeometric-tests.ipynb
ElectionAuditWare/CORLA18
f03af7a7b514746f40426bb204c531fabcd10baf
CC-BY-4.0
2018-09-12T03:06:12.000Z
2018-12-01T13:43:19.000Z
Qwen/Qwen-72B
1. YES
2. YES