The Gaffke Conjecture

Norbert Gaffke https://www.math.uni-magdeburg.de/institute/imst/ag_gaffke/files/pp1304.pdf and Learned-Miller and Thomas https://arxiv.org/abs/1905.06208 proposed a new test for the mean of a bounded population.

Suppose \(\{X_j\}_{j=1}^n\) are IID nonnegative random variables.

Let \(\{U_j\}_{j=1}^n\) be IID \(U[0, 1]\), and let \(U_{(j)}\) be the \(j\)th order statistic of \(\{U_j\}\). Define \(U_{(n+1)} := 1\). Let \(x = (x_j)_{j=1}^n\). Define

()\[\begin{equation} K(x) := \mathbb{P} \left ( \sum_{j=1}^n x_{(j)} (U_{(j+1)} - U_{(j)}) \le \mu \right ) \end{equation}\]

Gaffke conjectures that when \(X = (X_j)_{j=1}^n\) where \(\{X_j\}\) are IID with mean \(\mu\),

()\[\begin{equation} \mathbb{P}\{ K(X) \le \alpha \} \le \alpha. \end{equation}\]

Extensive simulations have not found a case where it fails, but the general case has not been proved to be valid.

For \(n=1\), the test is equivalent to Markov’s inequality. For arbitrary \(n\), if the population is binary, the test is equivalent to the usual Binomial test, and if the support of \(X_j\) contains only two points, the test is valid.

Suppose \(X_i \sim \mathrm{Bernoulli}(p)\), so

()\[\begin{equation} F(x) := \left \{ \begin{array}{ll} 1-p, & x \in [0,1) \\ 1, & x \ge 1 \end{array} \right . \end{equation}\]

and

()\[\begin{equation} F^{-1}(q) = \begin{cases} 0, & q \in [0, 1-p) \\ 1, & q \in [1-p, 1]. \end{cases} \end{equation}\]

Let \(S := \sum_j X_j\) be the sample sum. Then \(S \sim \mathrm{Binom}(n,p)\) is independent of \(\mathbf{V}\).

()\[\begin{align} \sum_{i=1}^n X_{(i)} \left (V_{(i+1)} - V_{(i)} \right ) &= \sum_S^n \left (V_{(i+1)} - V_{(i)} \right ) \nonumber \\ &= 1 - V_{(S)}. \end{align}\]

By symmetry, \(1-V_{(S)}\) has the same distribution as \(V_{(n-S+1)}\). We are interested in \(\Pr \{V_{(n-S+1)} \le p\} = \mathbb{E} 1_{V_{(n-S+1)} \le p}\).

The event \(V_{(n-s+1)} \le p\) is the event that there are \(n-s+1\) or more “successes” in \(n\) independent \(\mathrm{Bernoulli}(p)\) trials, i.e., the upper tail probability of a \(\mathrm{Binom}(n,p)\) random variable.

Conditional on \(X\) (and thus on \(S=s\)),

()\[\begin{equation} \Pr_{\mathbf{V}} \{V_{(n-s+1)} \le p \} = \sum_{j=s}^{n} \binom{n}{j}p^j(1-p)^{n-j}. \end{equation}\]

We need \(\Pr_S (\sum_{j=S}^{n} \binom{n}{j}p^j(1-p)^{n-j} \le \alpha )\). Partitioning on \(S\) gives

()\[\begin{eqnarray} && \Pr_S \left ( \sum_{j=S}^n \binom{n}{j}p^j(1-p)^{n-j} \le \alpha \right ) = \sum_{s=0}^n \mathbf{1}_{\sum_{j=s}^n \binom{n}{j}p^j(1-p)^{n-j} \le \alpha} \Pr_S(S=s) \nonumber \\ &&= \sum_{s=0}^n \mathbf{1}_{\sum_{j=s}^n \binom{n}{j}p^j(1-p)^{n-j} \le \alpha} \binom{n}{s} p^s (1-p)^{n-s}. \end{eqnarray}\]

The indicator is zero when \(s\) is small, and becomes \(1\) once \(s\) is sufficiently large. The smallest \(s\) for which the indicator is \(1\) is the first \(s\) for which the upper tail probability is not greater than \(\alpha\). I.e.,

()\[\begin{eqnarray} \sum_{s=0}^n \mathbf{1}_{\sum_{j=s}^n \binom{n}{j}p^j(1-p)^{n-j} \le \alpha} \binom{n}{s} p^s (1-p)^{n-s} &=& \sum_{s: \sum_{j=s}^n \binom{n}{j}p^j(1-p)^{n-j} \le \alpha} \binom{n}{s} p^s (1-p)^{n-s} \nonumber \\ &\le& \alpha. \;\;\Box \end{eqnarray}\]

General 2-point distributions

We now consider IID nonnegative random variables \(\{X_i\}\) with two points of support, \(\{a, b\}\), \(0 \le a < b\). The mass at \(a\) is \((1-p)\) and the mass at \(b\) is \(p\); \(\mathbb{E} X_i := \mu = (1-p)a + pb\). If we knew \(a\) and \(b\), we could transform to \(Y_i := \frac{X_i-a}{b-a}\). These \(Y_i\) are IID \(\mathrm{Bernoulli}(p)\), for which we know Gaffke yields a valid P-value. We now relate the Gaffke P-values for \(X_i\) and \(Y_i\) to show that we do not actually need to transform \(X_i\) in order to obtain a valid P-value from Gaffke:

()\[\begin{eqnarray} \Pr_\mathbf{V} \left \{ \sum_{i=1}^n X_{(i)} \left (V_{(i+1)} - V_{(i)} \right ) \le \mu \right \} & = & \Pr_\mathbf{V} \left \{ \frac{\sum_{i=1}^n X_{(i)} \left (V_{(i+1)} - V_{(i)} \right ) - a}{b-a} \le \frac{\mu-a}{b-a} \right \} \nonumber \\ & = & \Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)}-a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) + \right . \nonumber \\ && \left . + \; \frac{a}{b-a} \left [ \sum_{i=1}^n \left (V_{(i+1)} - V_{(i)} \right ) -1 \right ] \le \frac{\mu-a}{b-a} \right \} \nonumber \\ &=& \Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)}-a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) + \right . \nonumber \\ && \left . + \; \frac{a}{b-a} \left [ 1 - V_{(1)} - 1 \right ] \le \frac{\mu-a}{b-a} \right \} \nonumber \\ &=& \Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)} -a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) \le \frac{\mu-a(1-V_{(1)})}{b-a} \right \} \nonumber \\ &\ge& \Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)} -a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) \le \frac{\mu-a}{b-a} \right \}. \nonumber \\ && {} \end{eqnarray}\]

The final inequality implies that Gaffke with \(X_i\) is only less than \(\alpha\) when Gaffke with (Bernoulli) \(Y_i\) is less than \(\alpha\). In symbols,

()\[\begin{equation} \left ( \Pr_\mathbf{V} \left \{ \sum_{i=1}^n X_{(i)} \left (V_{(i+1)} - V_{(i)} \right ) \le \mu \right \} \le \alpha \right ) \subset \left (\Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)} -a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) \le \frac{\mu-a}{b-a} \right \} \le \alpha \right ). \end{equation}\]

Then by the Gaffke result for Bernoulli random variables, we obtain:

()\[\begin{eqnarray} \Pr_\mathbf{X} \left ( \Pr_\mathbf{V} \left \{ \sum_{i=1}^n X_{(i)} \left (V_{(i+1)} - V_{(i)} \right ) \le \mu \right \} \le \alpha \right ) & \le & \Pr_\mathbf{X} \left (\Pr_\mathbf{V} \left \{ \sum_{i=1}^n \frac{X_{(i)} -a}{b-a} \left (V_{(i+1)} - V_{(i)} \right ) \le \frac{\mu-a}{b-a} \right \} \le \alpha \right ) \nonumber \\ &\le& \alpha \end{eqnarray}\]

Gaffke is conservative if the lower bound of the two-point distribution is greater than 0, even if we do not know what this lower bound is. Since the last inequality in (11) is strict if \(a > 0\), Gaffke is less sharp if we do not use the correct lower bound.