Why Enumerate Complete Paths?
In an adaptive trial, the probability of an assignment can depend on earlier assignments and responses. A single fixed allocation count, such as “three participants receive treatment,” does not describe the full assignment mechanism: different sequences with the same treatment count can have different probabilities. Enumerating complete paths retains the order of assignments and the history that generated each probability.
The goal here is to construct the probability distribution of a chosen statistic under a specified assignment mechanism. The mechanism must be known, including its initial rule, its updates after each observed history, and any forced or zero-probability assignments. To calculate a statistic along paths under a sharp null, the outcomes must also be determined for every assignment path. Under that null, each participant’s outcome is unchanged by assignment, so the observed outcomes can be held fixed while paths are enumerated. This construction by itself does not establish the validity of a particular test.
Write \(p_i(h_i)=P(A_i=1\mid H_i=h_i)\), where \(H_i\) is the history available immediately before assignment \(i\), and let \(A_i=1\) denote treatment and \(A_i=0\) control. If the mechanism’s probability of each assignment is known from its history, the probability of a complete path is
Here \(h_i(a)\) is the history that would occur along path \(a\), including the responses implied by the stipulated outcome model or null. Each factor is \(p_i(h_i)\) when \(a_i=1\), and \(1-p_i(h_i)\) when \(a_i=0\). The product is the chain rule for probability; it is not generally valid to multiply probabilities that ignore the path’s changing history.
Enumerating and Weighting the Paths
For two possible assignments at each of \(n\) stages, there are at most \(2^n\) assignment paths. Some may have probability zero because the rule forces an assignment. For each nonzero path, calculate its probability by following the rule from the first assignment onward. Then calculate the statistic of interest using the assignments and the outcomes specified for that path. Paths with the same statistic contribute their probabilities to the same point of the randomization distribution.
A short justification uses the assignment tree. At any history, the probabilities of its possible next assignments sum to one: \(p_i(h_i)+[1-p_i(h_i)]=1\). Starting at the final stage, the total probability of all continuations from each history is therefore one. Applying this fact successively back to the first assignment shows that the total probability across all leaves—the complete paths—is one. More formally, if \(Q(h)\) is the sum of probabilities of all continuations from history \(h\), then at the last stage \(Q(h)=p_i(h)+(1-p_i(h))=1\); recursively, \(Q(h)=p_i(h)Q(h,1)+[1-p_i(h)]Q(h,0)=1\) whenever both child continuation sums equal one. A forced assignment has one child with probability one and gives the same result.
Worked Example: Eight Paths Under a Response-Adaptive Rule
Consider three participants and two assignments, with 1 denoting treatment and 0 denoting control. For this hypothetical calculation, suppose a sharp null fixes the three binary outcomes at \(y=(1,0,1)\), regardless of assignment. The first participant is assigned to treatment with probability 0.5. For participants 2 and 3, treatment has probability 0.8 if at least one earlier participant assigned to treatment has had a success; otherwise treatment has probability 0.2. Thus the rule responds to outcomes observed on treatment. Use the statistic \(T\), the treatment-group outcome total minus the control-group outcome total. This total contrast is defined even if one group is empty.
If the first assignment is 0, no treatment success has yet occurred. If it is 1, participant 1 has a treatment success, so the probability of treatment at both later stages is 0.8. When participant 1 is assigned to control, assigning participant 2 to treatment does not create a treatment success because \(y_2=0\). The complete calculations are:
| Path \(a\) | Conditional-probability product | \(P(A=a)\) | \(T\) |
|---|---|---|---|
| 000 | \(0.5(0.8)(0.8)\) | 0.32 | \(-2\) |
| 001 | \(0.5(0.8)(0.2)\) | 0.08 | 0 |
| 010 | \(0.5(0.2)(0.8)\) | 0.08 | \(-2\) |
| 011 | \(0.5(0.2)(0.2)\) | 0.02 | 0 |
| 100 | \(0.5(0.2)(0.2)\) | 0.02 | 0 |
| 101 | \(0.5(0.2)(0.8)\) | 0.08 | 2 |
| 110 | \(0.5(0.8)(0.2)\) | 0.08 | 0 |
| 111 | \(0.5(0.8)(0.8)\) | 0.32 | 2 |
For example, path 100 begins with treatment, which is a success under the stipulated outcomes. Control therefore has probability 0.2 at both stages 2 and 3, giving \(P(A=100)=0.5(0.2)(0.2)=0.02\). Likewise, path 101 has probability \(0.5(0.2)(0.8)=0.08\). The table’s path probabilities are correct, and their total is 1.
Grouping paths by statistic gives \(P(T=-2)=0.32+0.08=0.40\), \(P(T=0)=0.08+0.02+0.02+0.08=0.20\), and \(P(T=2)=0.08+0.32=0.40\). These masses sum to 1.
The example above illustrates why path-by-path verification is essential: a path’s probability must use the factor associated with each digit in its sequence, not merely the probability of reaching a broad branch of the tree. The next example gives a smaller tree whose arithmetic can be checked directly from its rule and path list.
Worked Example: A Two-Stage Adaptive Tree
In a hypothetical two-participant design, the first participant receives treatment with probability 0.4. Under the sharp null, suppose the first participant’s outcome is a success. At stage 2, treatment has probability 0.75 if participant 1 was assigned to treatment and probability 0.25 otherwise. The assignment-dependent rule determines the branch probabilities; the fixed null outcome is used to calculate the statistic. For a simple statistic, let \(T\) be the treatment outcome total minus the control outcome total, with fixed outcomes \(y=(2,1)\).
The four path probabilities are:
For path 00, both outcomes are in control, so \(T=0-(2+1)=-3\). For 01, participant 2 is treated, so \(T=1-2=-1\). For 10, participant 1 is treated, so \(T=2-1=1\). For 11, both outcomes are in treatment, so \(T=(2+1)-0=3\). The randomization distribution therefore assigns probabilities 0.45, 0.15, 0.10, and 0.30 to \(-3,-1,1,3\), respectively. The probabilities add to 1. The unequal weights matter: treating the four paths as equally likely would not represent this adaptive mechanism.
Worked Example: Forced Assignments and Repeated Statistic Values
Suppose a three-participant rule assigns participant 1 to treatment with probability 0.5. At stage 2, treatment is forced if participant 1 was assigned to treatment and had a success; otherwise treatment has probability 0.5. At stage 3, treatment has probability 0.5 at every reachable history. Under a sharp null, take the fixed outcomes \(y=(1,0,1)\), and use the treatment-total-minus-control-total statistic \(T\).
If \(a_1=1\), the stage-2 assignment is forced to treatment, so paths 100 and 101 have probability zero. The nonzero path probabilities are \(P(000)=0.5(0.5)(0.5)=0.125\), \(P(001)=0.125\), \(P(010)=0.125\), \(P(011)=0.125\), \(P(110)=0.5(1)(0.5)=0.25\), and \(P(111)=0.25\). Their sum is \(4(0.125)+2(0.25)=1\).
The corresponding statistic values are \(-2,0,-2,0,0,2\), in the same order. Thus \(P(T=-2)=0.25\), \(P(T=0)=0.50\), and \(P(T=2)=0.25\). Although eight binary paths are structurally possible, two have zero probability under the rule. Keeping them in a table with zero weight is harmless; assigning them positive weight would be an error.
Diagnostics and Common Failure Modes
Enumeration is manageable only when the mechanism and the path history are recorded precisely. Before using the resulting distribution, check the following:
- Probability sum: all complete-path probabilities, including zero-probability paths if listed, must sum to 1 up to rounding.
- Conditional branch: for each factor, verify which history and response information are available immediately before that assignment.
- Path-digit match: a factor must be \(p_i(h_i)\) for a treatment digit and \(1-p_i(h_i)\) for a control digit.
- Outcome availability: under the null used to calculate the statistic, each path must have well-defined outcomes. Do not silently use outcomes that would not be known under the stipulated model.
- Statistic definition: check whether the statistic is defined for paths with empty groups or other boundary cases. If it is not, specify a suitable alternative or define the target distribution conditionally on an appropriate event.
- Precision: retain adequate precision in products and sums; premature rounding can make a valid total appear not to equal 1.
A frequent mistake is to list \(2^n\) paths and give each the same weight. That is correct only for a mechanism that makes those paths equiprobable. Another is to multiply the marginal chance of treatment at each stage as though it were fixed across paths. In an adaptive design, the stage-\(i\) chance is conditional on the history along that particular path. A third mistake is to enumerate assignments but omit outcomes from the history even though the rule updates in response to those outcomes. Reconstruct the algorithm first, then follow it separately down every branch.
Enumeration and Its Alternatives
Direct enumeration is transparent and useful when the number of reachable paths is small enough to inspect. It makes the role of each conditional assignment probability visible and allows the path table to be audited. As \(n\) increases, however, the number of paths can grow exponentially, so a full table may become computationally impractical.
| Approach | What it computes | Main trade-off |
|---|---|---|
| Complete path enumeration | Every reachable path and its probability, followed by probability-weighted statistic values | Transparent and exhaustive for small spaces; can require many paths |
| Recursive calculation | Accumulates probability or statistic mass through the assignment tree, sometimes combining equivalent histories | Can reduce repeated work, but merging is valid only when the retained state contains everything needed for future probabilities and the statistic |
| Simulation | Samples paths from the assignment mechanism to approximate a distribution or tail probability | Can handle larger spaces, but gives an approximation with simulation variability rather than a complete path table |
These approaches do not remove the need to specify the assignment mechanism correctly. Recursive methods must preserve all history information relevant to later assignment probabilities. Simulation must generate paths using the same sequential rule. Direct enumeration is limited by path count and by the need to specify outcomes along paths, but it is especially valuable as a verification tool for small adaptive designs.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- A two-stage rule has \(P(A_1=1)=0.3\), \(P(A_2=1\mid A_1=0)=0.2\), and \(P(A_2=1\mid A_1=1)=0.7\). Find the probabilities of paths 00, 01, 10, and 11.
- Why can two paths with the same number of treatment assignments have different probabilities?
- In a binary assignment design, a branch assigns treatment with probability 1. What is the probability of a path that takes the control branch there?
- Two paths produce the same statistic value \(t\), with path probabilities 0.12 and 0.18. What probability mass do they contribute at \(t\)?
- What check can reveal that one or more complete paths have been omitted or incorrectly weighted?
Solutions. (1) \(P(00)=0.7(0.8)=0.56\), \(P(01)=0.7(0.2)=0.14\), \(P(10)=0.3(0.3)=0.09\), and \(P(11)=0.3(0.7)=0.21\); these sum to 1. (2) Their probabilities depend on the ordered histories that determine each conditional assignment probability, not only on the final treatment count. (3) Zero, because control is forced to have probability \(1-1=0\) at that branch. (4) They contribute \(0.12+0.18=0.30\). (5) Sum the probabilities over all complete paths; the total must be 1, subject only to rounding. Also verify that each listed path follows the stated rule.