Worked Randomization Test For A Play-The-Winner Urn

Why the Assignment Path Matters

In a play-the-winner trial, each response changes the urn that determines the next assignment. Consequently, an assignment sequence such as A, B, A is not generally as likely as B, A, A. A randomization test must reproduce this response-dependent mechanism; simply permuting treatment labels uniformly can give the wrong reference distribution.

This tutorial specifies one common two-treatment play-the-winner rule and works through a sharp-null test. The exact numerical rule matters: “play-the-winner” has variants, so an analysis must match the urn initialization, update rule, and timing actually used by the trial.

Definition: In the urn version used here, treatment A and treatment B are represented by balls in an urn. Before participant \(i\) is assigned, one ball is drawn uniformly and returned; its color determines \(Z_i\), the assigned treatment. After the response \(Y_i\) is observed, one additional ball is added: a success adds a ball of the assigned treatment’s color, while a failure adds a ball of the other color. If the urn contains \(u_A\) A-balls and \(u_B\) B-balls immediately before a draw, then \(P(Z_i=A)=u_A/(u_A+u_B)\) and \(P(Z_i=B)=u_B/(u_A+u_B)\).

For the worked calculations, take a fixed trial size, start with one ball of each color, and code a binary success as \(Y_i=1\) and a failure as \(Y_i=0\). The draw occurs before the response, and the response updates the urn before the next participant is assigned. No participants are dropped, and the trial does not stop early. Other initial urn compositions or update rules produce different path probabilities and must be analyzed as specified by their design.

The Sharp Null and the Test Statistic

The sharp null hypothesis says that treatment has no effect on any participant’s response: for every participant \(i\), the response under A equals the response under B. Under this null, each participant’s response is fixed regardless of the treatment assigned. In the sequential test, keep the participant-ordered responses fixed and regenerate assignments by running the urn rule forward. Each generated assignment determines which urn update follows, because the fixed response is then applied to the treatment assigned on that path.

A test statistic must be defined before looking at the reference distribution. For the small binary-response example below, use the signed difference in numbers of successes:

T=\sum_{i=1}^{n}(2I[Z_i=A]-1)Y_i =\text{successes assigned to A}-\text{successes assigned to B}.

This statistic is defined even if a path assigns everyone to one treatment. Its units are successes, not a difference in success proportions. For a two-sided test, define extremeness by \(|T|\), so paths with \(|T|\) at least as large as the observed \(|T|\) count in the tail. A different statistic or a different two-sided ordering can be appropriate for a different question, but it must be specified and applied consistently to the observed and generated paths.

Worked Example: Tracing an Observed Urn Path

Suppose three participants have the observed assignments A, B, A and the binary responses, in participant order, \(1,0,1\). Assume the urn began with one ball of each color and followed the rule above. Under the sharp null, treat these three responses as fixed when tracing alternative assignment paths.

First assignment. The urn is \((u_A,u_B)=(1,1)\), so A is drawn with probability \(1/2\). The first participant is assigned A and succeeds; add an A-ball. The urn is now \((2,1)\).

Second assignment. The probability of drawing B is now \(1/3\). The second participant is assigned B and fails. A failure adds a ball of the other color, A, so the urn becomes \((3,1)\).

Third assignment. The probability of drawing A from this urn is \(3/4\). Thus the probability of the observed assignment path A, B, A is

P(A,B,A)=\frac{1}{2}\times\frac{1}{3}\times\frac{3}{4} =\frac{1}{8}=0.1250.

The observed statistic is \(T=1-0+1=2\) successes. The path probability is not the p-value: a p-value sums the probabilities of every path at least as extreme as the observed statistic.

Exact Randomization Distribution

For a short trial, enumerate every possible assignment path. For each path, multiply its successive conditional draw probabilities, update the urn using the fixed response for that participant, and calculate the statistic. The next table does this for the same three fixed responses, \(1,0,1\). Each row is one path; the probability column is the probability of that entire path under the urn design and sharp null.

Worked Example: Calculating the Exact Two-Sided P-Value

Starting from \((1,1)\), the first draw has probability \(1/2\) for either color. After the first response, the urn is \((2,1)\) if the first assignment was A and \((1,2)\) if it was B. The second response is a failure, so its update adds the color opposite the second assignment. Applying those updates gives the following complete enumeration.

Path	Path probability	\(T\)	\(\|T\|\geq 2\)?
AAA	\(1/6\)	2	Yes
AAB	\(1/6\)	0	No
ABA	\(1/8\)	2	Yes
ABB	\(1/24\)	0	No
BAA	\(1/24\)	0	No
BAB	\(1/8\)	\(-2\)	Yes
BBA	\(1/6\)	0	No
BBB	\(1/6\)	\(-2\)	Yes

The probabilities sum to one:

\frac{1}{6}+\frac{1}{6}+\frac{1}{8}+\frac{1}{24} +\frac{1}{24}+\frac{1}{8}+\frac{1}{6}+\frac{1}{6}=1.

The observed path ABA has \(T_{\mathrm{obs}}=2\). The two-sided exact p-value is the total probability of paths with \(|T|\geq |T_{\mathrm{obs}}|\):

p_{\mathrm{exact}} =P(|T|\geq 2) =\frac{1}{6}+\frac{1}{8}+\frac{1}{8}+\frac{1}{6} =\frac{7}{12}=0.5833.

For this design and statistic, the exact p-value is 0.5833. It is the probability, under the sharp null and the specified urn mechanism, of a statistic at least as extreme as the observed one. It is not the probability that the sharp null is true.

Why the Exact Calculation Is Valid

The argument depends on the sharp null and on correctly reproducing the assignment mechanism. Under the sharp null, the ordered responses are fixed for every assignment path. At each step, the urn state and the next assignment probability are therefore determined by the path so far and the fixed response for the current participant. The probability of a complete path is the product of those conditional probabilities.

To see why the enumeration forms a probability distribution, begin at the initial urn. From any state, the probabilities of the next A and B draws sum to one. Each draw leads to an updated state once the fixed response is applied. Repeating this branching until the fixed trial size is reached partitions all possible sequences into complete paths. The probabilities of all complete paths therefore sum to one, as they do in the table.

Under the sharp null, the observed assignment path is itself generated by this same distribution. The tail probability \(P(|T|\geq |T_{\mathrm{obs}}|)\), calculated using that distribution, is consequently a valid randomization p-value: under the null, the probability that it is no greater than \(\alpha\) is at most \(\alpha\). The inequality can be strict because a discrete distribution may not have a tail probability equal to every possible \(\alpha\); including ties in the tail preserves validity.

Monte Carlo Approximation and Practical Checks

Worked Example: Approximating the Tail by Simulation

If a larger trial has too many paths to enumerate, simulate paths by drawing from the urn repeatedly. For every simulated path, use the same fixed participant-ordered responses, apply each response-dependent urn update, and calculate \(T\). Suppose a hypothetical run generates \(M=10{,}000\) paths and \(b=5{,}831\) have \(|T|\geq 2\). The raw estimated tail probability is

\widehat{p}_{\mathrm{MC}}=\frac{b}{M} =\frac{5831}{10000}=0.5831.

When reporting a Monte Carlo randomization test, a common finite-simulation correction is \((b+1)/(M+1)\), which includes the observed statistic as one member of the comparison. Here it gives

\widehat{p}_{+1}=\frac{5831+1}{10000+1} =\frac{5832}{10001}=0.5831.

The simulation error is separate from uncertainty about the treatment effect. Using the raw estimate, its approximate Monte Carlo standard error is

SE_{\mathrm{MC}} \approx\sqrt{\frac{\widehat{p}_{\mathrm{MC}}(1-\widehat{p}_{\mathrm{MC}})}{M}} =\sqrt{\frac{0.5831(0.4169)}{10000}} \approx 0.00493.

Thus this run approximates the exact tail probability as 0.5831, with Monte Carlo standard error about 0.00493. More simulations generally reduce this simulation error; they do not repair an incorrectly specified urn rule.

For either enumeration or simulation, check the following before interpreting a result:

Confirm the design details. Check the initial ball counts, draw and return rule, response coding, update rule, and whether the update occurs before the next assignment.
Verify path probabilities. For enumeration, their sum must be one. For a traced path, every factor must be the draw probability from the urn state immediately before that draw.
Use outcomes in participant order. Under the sharp null, keep each participant’s response fixed; do not shuffle responses among participants while generating assignment paths.
Check the statistic on every path. A treatment-label switch should reverse the sign of this signed statistic while preserving its absolute value. Paths with no participants on one arm remain defined for this statistic.
Separate Monte Carlo error from design error. A small simulation standard error says the simulated tail is estimated precisely, not that the model, null, or urn implementation is correct.

Alternatives and Limitations

Exact enumeration and Monte Carlo simulation target the same randomization distribution. Enumeration is preferable when the number of paths is manageable: it gives the exact tail probability for the specified design, apart from arithmetic or coding errors. Simulation is useful when enumeration is too large, but adds Monte Carlo error. Neither approach allows equal weighting of paths unless the design actually makes those paths equally likely.

A fixed-allocation randomization test uses a different assignment mechanism: it generates assignments subject to the fixed allocation rule rather than updating an urn after each response. Its reference distribution is not a substitute for the play-the-winner distribution. Similarly, an asymptotic test may use an approximation rather than enumerate the design’s finite-sample paths. Such an approximation should not be described as the exact urn-based test.

The test shown here is exact for the sharp null that every participant’s response is unchanged by treatment, assuming the specified sequential design was followed. It does not, by itself, test every weaker claim about an average treatment effect. The statistic is a signed count difference, so its value is in successes and should not be presented as a difference in success rates or as an estimated causal effect. Other statistics may be more suitable for a particular scientific question, but the randomization distribution must be recomputed using the same urn mechanism and the null assumptions appropriate to that test.

Common mistake: Treating all treatment-label sequences as equally likely because each individual draw is random. In an urn design, the draw probabilities change with the urn state, and the state changes with earlier assignments and responses. The correction is to calculate each path’s probability as a product of its conditional draw probabilities, with the response-dependent update applied at every step.

Check Your Understanding

Answer the questions using the urn rule and sharp-null framework defined above.

Starting with urn counts \((2,1)\), participant \(i\) is assigned B and succeeds. What are the updated counts?
With initial counts \((1,1)\) and fixed responses \(1,0,1\), what is the probability of the path ABB?
For responses \(1,0,1\), what is \(T\) on path BAA?
Why is it generally incorrect to calculate the reference distribution by uniformly permuting A and B labels?
In a Monte Carlo test, what does increasing \(M\) improve, and what does it not correct?

Solutions. (1) B was assigned and the response was a success, so add a B-ball: \((2,1)\) becomes \((2,2)\). (2) For ABB, the first draw is A with probability \(1/2\); after response 1 the urn is \((2,1)\). The second draw is B with probability \(1/3\); response 0 adds an A-ball, giving \((3,1)\). The third draw is B with probability \(1/4\). Thus \(P(ABB)=(1/2)(1/3)(1/4)=1/24\). (3) On BAA, the first success assigned to B contributes \(-1\), the second response is zero, and the final success assigned to A contributes \(+1\). Therefore \(T=-1+0+1=0\). (4) The urn state depends on earlier draws and responses, so complete paths generally have different probabilities. Uniformly permuting labels assigns the wrong weights to paths. (5) Increasing \(M\) reduces Monte Carlo error in estimating the specified tail probability. It does not fix an incorrect urn rule, an invalid sharp-null assumption, or a wrongly calculated statistic.