Why Solve a Boundary by Root Finding?
In a sequential design, a boundary determines whether the study stops at a look. Sometimes the earlier boundaries are fixed and one remaining boundary must be chosen so that the cumulative crossing probability equals a specified target. The computation is not simply an inversion of a standard normal tail: crossing at a later look depends on which paths survived earlier looks. The target function must therefore be evaluated using the sequential probability calculation, and the boundary is found by solving a scalar equation.
This tutorial treats one unknown boundary at a time. The key numerical idea is to first find an interval whose endpoints give target-function values of opposite signs, then use a bracketed solver. A bracket is more than a starting guess: it protects the search from wandering away from the root, even when the probability function is evaluated numerically.
Model and Root Function
Consider upper-boundary monitoring at looks \(1,\ldots,K\). Let \(Z_j\) be the standardized statistic at look \(j\), and let \(t_j\) denote its information fraction, with \(0<t_1<\cdots<t_K=1\). Under the canonical null model, the joint statistics have the Gaussian dependence induced by Brownian information time: \(Z_j=B(t_j)/\sqrt{t_j}\), where \(B(t)\) is standard Brownian motion. Thus \(Z_j\sim N(0,1)\) and \(\operatorname{Corr}(Z_i,Z_j)=\sqrt{t_i/t_j}\) for \(i<j\).
Assume the canonical Gaussian model is appropriate, the information fractions and all but one boundary are fixed, and the crossing rule is specified in advance. Write \(b\) for the unknown upper boundary at look \(r\). The probability calculation must use the same state-space approximation and recursion at every trial value of \(b\); otherwise changes in the computed probability may reflect changing numerical methods rather than changing the boundary.
For a fixed set of earlier upper boundaries, the survivor-density recursion carries forward only paths that have not crossed. At a subsequent look, the crossing probability is the probability mass that exits the survivor region; the remaining mass is updated using the Gaussian transition kernel. When \(b\) changes, the relevant exit region at look \(r\) changes, and therefore so does the recursively calculated cumulative crossing probability.
Why a Bracketed Solver Works
In the common case where \(b\) is an upper boundary at a look and all other rules are fixed, increasing \(b\) cannot make a path that previously failed to cross at that look cross there. The earlier crossing events are unchanged. Consequently, \(C(b)\) is non-increasing. In a non-degenerate Gaussian model with positive probability of surviving to look \(r\), it is strictly decreasing over finite boundary values: raising the boundary removes positive probability mass from the crossing event.
A strictly decreasing continuous \(C(b)\) has at most one solution for a given target. If \(F(L)>0\) and \(F(U)<0\), continuity guarantees a root in \((L,U)\). Bisection repeatedly halves this interval and retains the sign change. This gives a robust method even when no convenient closed-form inverse exists.
Continuity and monotonicity are structural properties of the probability model, but computed values have numerical error. In practice, the recursion may use quadrature or a state grid. A reliable bracket must have endpoint signs that remain opposite after accounting for the accuracy of those evaluations. The earlier material on grid refinement and numerical convergence is relevant here: refine the probability calculation enough that the sign is not a numerical artifact.
Worked Example: Evaluating the Two-Look Crossing Probability
Worked Example: Evaluating the Two-Look Crossing Probability
Suppose there are two upper-boundary looks with \(t_1=0.5\), \(t_2=1\), first boundary \(a=2\), and second boundary \(b\). Under the canonical null model, \(\operatorname{Corr}(Z_1,Z_2)=\sqrt{0.5}\). Calculate the cumulative crossing probability at \(b=1.75\), and determine whether it exceeds a target of \(0.05\).
The first-look crossing probability is \(P(Z_1\geq2)\approx0.0227501\). Conditional on \(Z_1=x\), the second statistic has mean \(\sqrt{0.5}\,x\) and variance \(0.5\). Therefore \(P(Z_2\geq b\mid Z_1=x)=\Phi(x-b\sqrt{2})\), where \(\Phi\) is the standard normal cumulative distribution function. The recursion gives the total crossing probability as the first-look crossing mass plus the second-look crossing mass among first-look survivors:
At \(b=1.75\), the marginal second-look tail is \(P(Z_2\geq1.75)\approx0.0400592\). The joint tail is \(P(Z_1\geq2,Z_2\geq1.75)\approx0.010426\). Equivalently, inclusion-exclusion gives:
Thus \(F(1.75)=0.052383-0.05=0.002383>0\). The cumulative crossing probability at this boundary is about 0.05238, which is above the specified target. The conditional integral and the inclusion-exclusion calculation describe the same event; the latter is a useful numerical check.
Bisection and a Numerically Solved Boundary
At each bisection step, evaluate \(F\) at the midpoint and keep the half-interval whose endpoint values have opposite signs. If \(F(m)>0\) for midpoint \(m\), then the root is to the right for a decreasing function; replace \(L\) by \(m\). If \(F(m)<0\), replace \(U\) by \(m\). When \(F(m)=0\) to the desired accuracy, the search can stop, subject to the accuracy of the probability evaluation.
Evaluate the recursively calculated \(C(b)\) at candidate boundaries. Retain \(L<U\) with \(F(L)\geq0\) and \(F(U)\leq0\).
Set \(m=(L+U)/2\), calculate \(C(m)\) with the same recursion, and form \(F(m)=C(m)-\gamma\).
For a decreasing \(F\), if \(F(m)>0\), set \(L=m\); if \(F(m)<0\), set \(U=m\). This preserves the bracket.
Stop when the bracket is sufficiently narrow and the computed probability residual is acceptable relative to the probability-calculation error.
Worked Example: Bisection for a Target of 0.05
Continue the two-look example, holding \(a=2\) fixed and solving for \(b\) so that \(C(b)=0.05\). The converged probability calculation gives \(C(1.75)\approx0.052383\). At \(b=1.785\), the marginal tails are approximately \(0.0227501\) and \(0.03713\), and the joint tail is approximately \(0.01000\). Hence:
The interval \([1.75,1.785]\) is a valid bracket: the lower endpoint has positive residual and the upper endpoint has negative residual. Bisection proceeds as follows. The midpoints and recursively evaluated probabilities below are rounded; small differences in their last digits do not affect the sign decisions.
| Boundary \(b\) | Approximate \(C(b)\) | Sign of \(F(b)\) | Bracket update |
|---|---|---|---|
| 1.7675 | 0.05110 | Positive | Set \(L=1.7675\) |
| 1.77625 | 0.05049 | Positive | Set \(L=1.77625\) |
| 1.780625 | 0.05019 | Positive | Set \(L=1.780625\) |
| 1.7828125 | 0.05004 | Positive | Set \(L=1.7828125\) |
| 1.7839063 | 0.04996 | Negative | Set \(U=1.7839063\) |
For example, the first midpoint is \((1.75+1.785)/2=1.7675\), and its residual is approximately \(0.05110-0.05=0.00110\), so the lower endpoint moves up. Subsequent steps repeat the same calculation. The final displayed bracket has width \(1.7839063-1.7828125=0.0010938\). A safeguarded interpolation step within that bracket, followed by a fresh probability evaluation, gives a boundary of approximately \(b=1.7833\), for which \(C(b)\) rounds to \(0.05000\). The reported digits should be limited by the accuracy of the recursive probability calculation, not just by the small root-finding interval.
Feasibility, Diagnostics, and Alternatives
Worked Example: Detecting an Infeasible Target
In the same two-look setup, can a finite second-look boundary make the cumulative crossing probability equal to \(0.02\), while the first boundary remains \(a=2\)?
No. Crossing at the first look alone has probability \(P(Z_1\geq2)\approx0.0227501\), and that event is included in cumulative crossing regardless of the second boundary. Thus, for any finite \(b\), \(C(b)\geq0.0227501>0.02\). In the limit \(b\to\infty\), the second-look crossing probability tends to zero, so \(C(b)\) approaches \(0.0227501\), but it does not reach \(0.02\). No bracket with opposite residual signs can exist for this target. The target or the fixed design rules must change before a root-finding routine is applied.
Several checks help distinguish a failed search from a failed probability calculation:
- Check the direction. For an upper boundary, increasing \(b\) should not increase the cumulative crossing probability. A reversal may signal a coding error, inconsistent recursion, or numerical noise.
- Check the bracket signs. Verify the actual values of \(F(L)\) and \(F(U)\) before calling the solver. Do not infer a sign from a rounded value that is effectively zero.
- Check the probability calculation. Refine the state grid or quadrature and confirm that the endpoint signs and reported root are stable. If numerical error could change a sign, the bracket is not yet trustworthy.
- Check feasibility. A fixed earlier crossing probability can impose a lower bound on cumulative crossing. Targets outside the attainable range cannot be reached by changing only the selected boundary.
Bisection is slower than some alternatives but has a simple guarantee: with a continuous function and a valid bracket, it keeps the root enclosed and halves the interval at every step. A safeguarded secant or Brent-type method can converge faster by using interpolation, provided it falls back to a bracket-preserving step when needed. An unbracketed Newton method may be fast near a root, but it requires a reliable derivative and can jump outside the feasible boundary range. A dense grid scan can locate a likely interval, but it does not by itself establish the root or control the final error.
A narrow final bracket controls uncertainty in the boundary only if the probability evaluations themselves are accurate enough. If \(C(b)\) has a shallow slope near the root, even a small probability error can translate into a relatively large boundary error. Conversely, reporting many decimal places from a root solver is not justified when the survivor recursion changes materially under grid refinement. The numerical boundary is conditional on the model, the fixed boundaries, the target, and the accuracy of the probability calculation.
Common Mistake
Check Your Understanding
Answer each question, then compare with the solutions below.
- For a decreasing \(F\), what endpoint should be updated if the midpoint residual is positive?
- A valid bracket has endpoint residuals \(F(L)=0.003\) and \(F(U)=0.001\). What is wrong with it?
- In the two-look example with first boundary \(a=2\), why can no second-look boundary achieve a cumulative crossing target of \(0.02\)?
- If the computed root is stable to six decimal places but the probability changes noticeably under grid refinement, how many boundary digits should be reported?
- Name one advantage of bisection over an unbracketed Newton method and one advantage of a safeguarded interpolation method over bisection.
Solutions. (1) Set \(L\) equal to the midpoint, because a positive residual for a decreasing function places the root to its right. (2) Both residuals are positive, so the interval does not bracket a root; find an endpoint with nonpositive residual or investigate feasibility. (3) The first-look crossing probability alone is about \(0.0227501\), greater than \(0.02\), and is included for every second boundary. (4) Do not report six digits: refine or otherwise validate the probability calculation, then report only digits stable at that accuracy. (5) Bisection preserves the root bracket under its assumptions; safeguarded interpolation can use the bracket while converging faster than repeated halving.