Corrections to: Fast computation of exact confidence intervals for randomized experiments with binary outcomes

The problem

Algorithm 4.3 defines its upper endpoint through this search (“The precise definition of this binary search is given as Algorithm B.1”), and the printed steps are part of the algorithm. The steps fail on a range with two points. Suppose that $k_2=k_1+1$. Step 2 evaluates $f$ at $c=k_1$. If $f(k_1)=0$, then $a=k_1$ and $b=k_2=a+1$, and both end conditions of Step 3 hold. The clause for $a=k_1$ comes first and returns $k_1$ without evaluating $f(k_2)$, which is wrong when $f(k_2)=0$, that is, when $r=k_2$. If $f(k_1)=1$, then Step 2 sets $b=k_1$, the pair $(a,b)=(k_1,k_1)$ repeats, and the condition $b=a+1$ never holds. The search does not stop, which contradicts Lemma B.2. Both inputs satisfy the stated conditions.

The stated conditions also exclude ranges that Algorithm 4.3 passes to the search. Its range is $[\![nT(\mathbf n),n\max\mathcal C(\mathbf n)]\!]$. The left endpoint can be zero or negative (it is $-12$ in the first row of Table 1), and the range is the single point $\{n\}$ when $n_{11}=m$ and $n_{01}=0$. In a balanced design the range of the upper search is $[\![2(n_{11}-n_{01}),\,n_{11}-n_{01}+m]\!]$. It has two points exactly when $n_{11}-n_{01}=m-1$, and then Algorithm 4.3 as printed returns $T(\mathbf n)=(m-1)/m$ as its upper endpoint, although $U_\alpha(\mathbf n)=(2m-1)/(2m)$ for every $\alpha\in(0,1)$. This occurs for every $m\ge2$, including the range $n\ge15$ of Theorem 4.1.

Evidence an exact counterexample

The evidence is an exact counterexample, computed in integer and rational arithmetic, and a derivation of the corrected search.

In the third row, I have $T(\mathbf n)=7/8$ and $n\max\mathcal C(\mathbf n)=15$, and the range is $\{14,15\}$. The count vector $\mathbf v=(0,15,0,1)$ is possible given $\mathbf n$ and has $\tau(\mathbf v)=15/16$. Over the 12870 assignments, $T$ takes the values $7/8$ and $1$, each 6435 times, and both are at distance $1/16$ from $15/16$, which is also the observed distance. I obtain $p(\mathbf v,\mathbf n)=1$ and $U_\alpha(\mathbf n)=15/16$. Enumerating all 144 possible count vectors gives $\mathcal I_\alpha(\mathbf n)=[1/2,15/16]$. The value $14/16=T(\mathbf n)$ is accepted as well, through the table $(0,14,0,2)$, and I have $f(14)=f(15)=0$. The printed search evaluates $f(14)$ twice, never evaluates $f(15)$, and returns 14. The upper endpoint of Algorithm 4.3 as printed is then $14/16$. If $(0,15,0,1)$ is the true table, these are the observed counts at 6435 of the 12870 assignments, and at each of them the printed upper endpoint is below the true effect $15/16$.

For the corrected search (given under Corrected), let $N=k_2-k_1+1$. The inequalities $k_1-1\le a\le r<b\le k_2+1$ hold at the start. If $b-a\ge2$, then $a<c<b$, and $f$ is evaluated only at points of $[\![k_1,k_2]\!]$. If $f(c)=0$, then $c\le r$, and if $f(c)=1$, then $r<c$. In both cases the update preserves the inequalities. Each update replaces $b-a$ by at most $\lceil(b-a)/2\rceil$, and the search stops with $b=a+1$. Then $a\le r<a+1$, and I obtain $r=a$. The width $b-a$ is $N+1$ at the start and at most $\lceil(N+1)/2^t\rceil$ after $t$ evaluations. Since $N+1\le2^q$ for $q=\lfloor\log_2N\rfloor+1$, the search uses at most $\lfloor\log_2N\rfloor+1$ evaluations.

What survives

The interval $\mathcal I_\alpha$, Proposition 3.2, Lemma 4.2 and the compatibility test inside Algorithm 4.3 are unaffected. The corrected search retains the bound in Theorem 4.1. The range has at most $n+1$ points, an evaluation of $f$ at a nonzero point costs at most $n+1$ permutation tests, and the evaluation at $0$, which occurs at most once, costs at most $2(n+1)$. Each endpoint costs at most $(n+1)(\lfloor\log_2(n+1)\rfloor+2)\le(n+1)\lfloor\log_2(n+1)+3\rfloor$ tests, and (B.10) implies the bound $4n\log_2n$. Algorithm 4.5 inherits the search and needs the same correction (see P003-E003); Algorithm 5.3 does not use it. The replication code treats short ranges differently: it skips the midpoint loop when the range has one or two points and always tests the outer upper bound (see P003-N007). No reported simulation or application number is shown to be affected.

The problem

In Algorithm 4.3, the compatibility of one value $\tau_0$ is decided by testing several tables in turn and stopping at the first acceptance. Algorithm 4.5 does the same with a fresh set of Monte Carlo draws for each table. The sequences $\mathbf a$ and $\mathbf b$ record the decisions on single tables, and $J$ is the first index at which they differ. The proof asserts that the direction of this first disagreement decides the order of the final upper endpoints. It does not. Suppose that $b_J=0$, that is, the approximate test accepts a table that the exact test rejects. The exact search may accept the next table for the same $\tau_0$. Both searches then declare $\tau_0$ compatible and continue from the same midpoint, and a later rejection by the approximate test can still produce $U_{\alpha,\varepsilon,K}<U_\alpha$. In the other direction, a first disagreement with $b_J=1$ can be followed by the acceptance of the next table for the same $\tau_0$, after which the approximate search can end above the exact endpoint. The identity before (B.81) and the identity (B.85) are therefore false, and so are the equalities of probabilities drawn from them, including (B.86).

The argument has a second error. After the two searches separate, the $i$th tests of the two sequences can concern different tables. The event $\{b_i=1\text{ and }a_i=0\}$ is then not the rejection of a fixed table whose $p$-value is at least $\alpha$, Lemma B.14 does not bound its probability, and the bound (B.81) on the sum can fail.

The printed argument therefore does not prove Lemma B.15, and the proof of Proposition 4.6 cites the lemma. The counterexamples to the first-disagreement argument do not refute either probability bound. With the corrected search of P003-E001, both bounds hold with the same constants by the argument given under Evidence. The literal printed search has a separate defect: if an execution that returns no endpoint is assigned the empty interval, then (B.78) fails at $\mathbf v=(0,2,0,0)$, $m=1$, $\alpha=3/4$, $\varepsilon=1/4$ and $K=200$. Its inclusion event has probability zero, whereas its claimed lower bound is $1-24e^{-25}\ge1/13>0$. Without this convention, the printed interval is undefined at this input. This example does not refute (B.79) or either bound for the corrected search.

Evidence an exact counterexample

I base this finding on an exact counterexample, computed in rational arithmetic, and a derivation of the lemma by a different argument.

Let $n=30$, $m=15$, $\alpha=1/20$, $\varepsilon=1/200$ and $K=1$, and let the observed counts be $\mathbf n=(2,13,1,14)$. With $K=1$, an approximate test accepts a table with probability equal to its exact $p$-value. The upper search runs over the effects $x/30$ with $x\in[\![2,16]\!]$, and $U_\alpha=U_{\alpha-2\varepsilon}=10/30$.

At $9/30$ the exact search rejects $(1,9,0,20)$, whose $p$-value is $412/10005<1/20$, and accepts $(2,9,0,19)$, whose $p$-value is $752/10005$. On the path in the table, the approximate search accepts $(1,9,0,20)$, so $J=1$ and $b_J=0$. It then rejects every table that it tests at $12/30$ and at $10/30$, including $(3,10,0,17)$, which the exact test accepts with $p$-value $7143/126730$. It returns $9/30<U_\alpha$. The same decisions have positive probability for every $K$.

For (B.85), the sequence $\mathbf a$ is computed at level $\alpha-2\varepsilon=1/25$, and the first exact test accepts $(1,9,0,20)$. Consider the path on which the approximate search rejects this table, then accepts $(2,9,0,19)$, and then accepts the first table tested at each of $12/30$, $14/30$, $15/30$ and $16/30$. On this path $J=1$ and $b_J=1$, and the search returns $16/30>U_{\alpha-2\varepsilon}$. The event (B.85) holds, and the event $\{U_{\alpha-2\varepsilon}\ge U_{\alpha,\varepsilon,K}\}$ does not. Summing over the whole search tree gives the probabilities below.

For (B.81), I keep the data and $\alpha$, and set $\varepsilon=1/50$ and $K=5000$. Then $N=16$ and $a_2=0$, and an approximate test accepts when $S\ge\alpha-\varepsilon=3/100$. The $p$-value $412/10005$ of $(1,9,0,20)$ is above this threshold. If the first approximate test accepts this table, the second approximate test is the test of $(1,12,0,17)$ at $12/30$, whose $p$-value $407/190095$ is below the threshold. Applying Chebyshev’s inequality to each of the two tests, I find that $\mathbb P(b_2=1\text{ and }a_2=0)>9/10$, while $N\exp(-2K\varepsilon^2)=16e^{-4}<48/103$.

For the replacement argument, fix the observed data, and set $D=(n+1)\lfloor\log_2(n+1)+3\rfloor$ and $\delta=\exp(-2K\varepsilon^2)$. With the corrected search, the upper search performs at most $D$ table tests, whatever their outcomes. I number the tests that the approximate search performs. The table $\mathbf W_i$ tested at step $i$ is determined by the outcomes of the earlier tests, and the draws used at step $i$ are independent of them. Conditional on the earlier tests, (B.75) implies that a table with $p(\mathbf W_i,\mathbf n)\ge\alpha$ is rejected with probability at most $\delta$, and (B.76) implies that a table with $p(\mathbf W_i,\mathbf n)<\alpha-2\varepsilon$ is accepted with probability at most $\delta$. By a union bound over at most $D$ steps, each of the following events has probability at least $1-D\delta$: no table with $p$-value at least $\alpha$ is rejected, and no table with $p$-value below $\alpha-2\varepsilon$ is accepted.

On the first event, every value $x/n\le U_\alpha$ in the range is declared compatible when it is tested. Indeed, by the proof of Theorem 4.1, the list of tables tested for such a value contains a table with $p$-value at least $\alpha$, and the approximate search accepts either an earlier table of the list or that one. The upper pointer $b$ of the search then stays above $nU_\alpha$, and the search returns $U_{\alpha,\varepsilon,K}\ge U_\alpha$. On the second event, every table that the approximate search accepts has $p$-value at least $\alpha-2\varepsilon$, and every value it declares compatible is at most $U_{\alpha-2\varepsilon}$. The lower pointer $a$ then stays at or below $nU_{\alpha-2\varepsilon}$, and the search returns $U_{\alpha,\varepsilon,K}\le U_{\alpha-2\varepsilon}$. The lower endpoints are treated in the same way after every outcome is replaced by its complement, which changes the signs of $T$ and $\tau$ and preserves the $p$-values. By a union bound over the two endpoints, each part of Lemma B.15 holds with probability at least $1-2D\delta$.

What survives

Lemma B.15 and Proposition 4.6 hold as stated, with the same constants, when the search is the corrected one and the intervals in their statements are defined (the second part of the lemma needs $\alpha-2\varepsilon>0$). This proof error does not affect the statements of Lemma B.14, Lemma 4.2 or Theorem 4.1, or the exact test. The simulations and the application do not use the false identities, and no reported number is shown to be affected.

The problem

Proposition 6.2 claims coverage for every allocation $m<n$ and for every distribution allowed in Section 6 for the indicator $\mathbf J$ of the missing outcomes, which may depend on $\mathbf Y$ and $\mathbf Z$. The claim fails in an unbalanced design. In the example given under Evidence, with $n=20$ and $m=3$, the interval (6.2) covers $\tau(\mathbf y)$ with probability $891/1140$, which is below $1-\alpha=391/500$.

The proof fails at the last inequality of (D.7). I call the vectors $\mathbf Y'\in\mathcal Y(\mathbf M)$ of (D.2) the completions of $\mathbf M$. By (D.5), the value $\tau_0$ lies above $U_\alpha(\mathbf Y^{(+)},\mathbf Z)$. By Algorithm 2.3, this means that every table with effect $\tau_0$ that is possible given $(\mathbf Y^{(+)},\mathbf Z)$ has a $p$-value below $\alpha$. The table $\mathbf w$ fixed in the proof may be possible given the completion $(\mathbf Y',\mathbf Z)$. When $\mathbf Y'\ne\mathbf Y^{(+)}$, it need not be possible given $(\mathbf Y^{(+)},\mathbf Z)$, and then (D.5) says nothing about its $p$-value. In the example, the true table is possible given the complete data, not possible given the upper imputation, and has the $p$-value $249/1140>\alpha$ for both. The inclusion (D.3) fails as well, since the exact interval of one completion, the complete data, is not contained in (6.2).

The correction changes the missing-outcome extension in Section 6; the complete-data results of Sections 2–5 do not depend on Proposition 6.2. One option is to add the hypothesis $n=2m$, under which Proposition 6.2 holds for the interval (6.2), whatever outcomes are missing; the guarantee then does not extend to unbalanced experiments. The other option is to keep general $m<n$ and replace (6.2) by the hull of the exact intervals over all completions. This interval can be wider, and it may require $(r_1+1)(r_0+1)$ interval computations in place of two, where $r_1$ and $r_0$ are the numbers of missing outcomes in the treatment and control groups.

The shortfall in the example is $1/2375$, at the level $\alpha=109/500$. No failure at $\alpha=0.05$ or $\alpha=0.10$ is established, nor a smallest example, nor a description of the allocations for which (6.2) fails.

Evidence an exact counterexample

The evidence is an exact counterexample, obtained by enumerating all assignments in integer and rational arithmetic, and derivations of the two corrections.

For the counterexample, let $n=20$, $m=3$ and $\alpha=109/500$. Units 1 to 11 have potential outcomes $(y_i(1),y_i(0))=(1,1)$, units 12 to 14 have $(0,1)$, and units 15 to 20 have $(0,0)$. The count vector is $(11,0,3,6)$ and $\tau(\mathbf y)=-3/20$. The outcome of unit 1 is missing exactly when the treated units are 12, 13 and 14, and no other outcome is ever missing. This rule depends on $\mathbf Z$ only and is allowed by Section 6. There are 1140 assignments. Since $1140\alpha=248.52$, a table is accepted when the two-sided tail in (2.12) contains at least 249 assignments.

At the assignment $\{12,13,14\}$, the complete data have observed counts $(0,3,11,6)$. Unit 1 is a control with outcome 1. The lower imputation restores this outcome, and the upper imputation replaces it by 0, which gives the counts $(0,3,10,7)$. The exact intervals are $\mathcal I_\alpha=[-7/10,-3/20]$ for the counts $(0,3,11,6)$ and $\mathcal I_\alpha=[-13/20,-1/5]$ for the counts $(0,3,10,7)$. Since $T(\mathbf Y^{(-)},\mathbf Z)=-11/17$ and $T(\mathbf Y^{(+)},\mathbf Z)=-10/17$, the interval (6.2) is

which excludes $\tau(\mathbf y)=-3/20$. The tail of the true table contains the assignments in which none or all three of the treated units are among units 1 to 11, for both sets of counts, and their number is $\binom93+\binom{11}3=249$. The true table is possible given the complete data. It is not possible given the upper imputation: since no treated unit has outcome 1, all eleven units of type $(1,1)$ are controls and show eleven control outcomes equal to 1, while the upper imputation has ten. Among the tables that are possible given the upper imputation and have effect at least $-3/20$, the largest tail count is 248, attained by $(8,0,3,9)$ and $(9,0,3,8)$. With $\mathbf w=\mathbf y$, $\tau_0=-3/20$ and $\mathbf Y'=\mathbf Y$, the hypothesis (D.5) holds and both probabilities in (D.7) equal $249/1140>\alpha$.

With complete data, $\tau(\mathbf y)$ is covered at 892 assignments. The missing outcome changes the interval at one assignment, and the interval (6.2) covers at 891. The coverage is $891/1140=297/380$, and $391/500-297/380=1/2375>0$.

For the balanced case, suppose that $n=2m$. Fix an assignment, a pattern of missing outcomes, a completion $\mathbf Y'$, and a table $\mathbf w$ that is possible given $(\mathbf Y',\mathbf Z)$ with $p(\mathbf w,\mathbf Y',\mathbf Z)\ge\alpha$. Set $\tau_0=\tau(\mathbf w)$. If $\tau_0\le T(\mathbf Y^{(+)},\mathbf Z)$, then $\tau_0$ does not exceed the upper endpoint of (6.2). Otherwise, let $d$ be the number of units at which $\mathbf Y'$ and $\mathbf Y^{(+)}$ differ; their outcomes are missing. Define $\mathbf w^+$ from $\mathbf w$ by replacing $w_i(Z_i)$ by $Y^{(+)}_i$ at each of these units. Then $\mathbf w^+$ is possible given $(\mathbf Y^{(+)},\mathbf Z)$. Each replacement raises the effect of its unit by 1 and raises $T$ by $1/m=2/n$. I have $\tau(\mathbf w^+)=\tau_0+d/n$ and $T(\mathbf Y^{(+)},\mathbf Z)=T(\mathbf Y',\mathbf Z)+2d/n$. For an assignment $\mathbf z$, let $N(\mathbf z)$ be the number of replaced entries that are realized under $\mathbf z$. Then $0\le N(\mathbf z)\le d$ and $T(\mathbf w^+,\mathbf z)=T(\mathbf w,\mathbf z)+2N(\mathbf z)/n$, and I obtain

Set $\Delta=\tau_0-T(\mathbf Y',\mathbf Z)$, which satisfies $\Delta>2d/n$. The observed distance is $\Delta$ for $\mathbf w$ and $\Delta-d/n$ for $\mathbf w^+$. If $|T(\mathbf w,\mathbf z)-\tau_0|\ge\Delta$, then $|T(\mathbf w^+,\mathbf z)-\tau(\mathbf w^+)|\ge\Delta-d/n$. The tail of $\mathbf w$ is contained in the tail of $\mathbf w^+$, and I find that $p(\mathbf w^+,\mathbf Y^{(+)},\mathbf Z)\ge p(\mathbf w,\mathbf Y',\mathbf Z)\ge\alpha$. Since $\mathbf w^+$ is possible and accepted, Algorithm 2.3 implies that $U_\alpha(\mathbf Y^{(+)},\mathbf Z)\ge\tau(\mathbf w^+)\ge\tau_0$. The lower endpoint is treated in the same way after every outcome and potential outcome is replaced by its complement. I conclude that (D.3) holds when $n=2m$, and (D.1) then implies (6.3).