When Replacement Rules Add and Remove Balls

Why Removal Rules Need a Feasibility Check

When every update only adds balls, a valid urn composition stays nonnegative automatically. That guarantee disappears as soon as a rule can remove balls. An update that is sensible in a large urn may demand more balls of a color than are currently present. The rule must therefore be checked against the states where it can be applied, not just described in general terms.

This matters for response-adaptive randomization because the urn determines which treatment can be assigned next. A negative count is not a rare or inconvenient result of the arithmetic: it is not a possible urn state. A rule that produces one has not defined the intended randomization process at that state.

The word net is important. The increment describes the difference between the composition just before the draw and the composition after the replacement operation is complete. Thus, if the drawn ball is returned and two balls of another color are added, that is a net change of zero in the drawn color and plus two in the other color. If the drawn ball is not returned, its removal is part of the net change. This convention prevents a common ambiguity about whether the drawn ball is included in a stated replacement vector.

For a fixed composition and draw, feasibility is checked for each outcome that can occur. If an outcome has positive conditional probability, its update must be feasible. For a rule that depends on the current composition, the check must be repeated at every state the design can reach. Counts are integers because they represent balls, so noninteger changes also fail to define an ordinary urn.

The Coordinate-Wise Feasibility Condition

Let \(\Delta_j(\mathbf{x},i,y)\) denote the increment for color \(j\). The exact check is

for every positive-probability draw-and-outcome combination. Equivalently, if a rule removes \(r_j\) balls of color \(j\) and adds \(a_j\), with \(r_j,a_j\geq 0\), then its net increment is \(a_j-r_j\), and the check is \(x_j-r_j+a_j\geq 0\). It is not enough that the total number added across colors is large: an excess of one color cannot compensate for a negative count in another.

A nonnegative composition may still be unable to support another assignment. If the updated urn has no balls, then its counts are nonnegative but the next draw cannot be made. A design intended to continue randomizing must therefore also ensure a positive total count at each state from which another draw is required. Whether that condition holds can be checked by summing the updated counts; detailed analysis of total-size changes is a separate question.

Worked Examples

Why the Feasibility Condition Is Necessary

The check follows directly from what a composition represents. Before the update, there are \(x_j\) balls of color \(j\). The net change for that color is \(\Delta_j\), so after the update the count must be \(x_j+\Delta_j\). Since a count cannot be negative, feasibility requires \(x_j+\Delta_j\geq 0\) for each color. Conversely, if every updated coordinate is a nonnegative integer, the vector describes a valid composition. If continued sampling is required, at least one ball must remain, adding the separate requirement that the sum of the updated coordinates be positive.

This argument also explains why checking only the expected increment is insufficient. A favorable average can conceal an impossible outcome. For example, two outcomes might have increments \((-2,1)\) and \((1,0)\); their average could be nonnegative in a particular state even though the first branch creates a negative count. Feasibility concerns every possible realized update, not an average over them.

When the probability of drawing color \(i\) is \(x_i/\sum_j x_j\), and the conditional probability of response \(y\) is \(q(y\mid i,\mathbf{x})\), a particular branch has probability

Thus, an invalid branch can be excluded from the check only if its probability is exactly zero under the stated design. A small positive probability is still positive, as in the second example.

Diagnostics, Alternatives, and Limitations

A practical audit starts by listing the reachable compositions and the possible draws and outcomes at each one. For every branch, calculate the updated vector explicitly. Pay particular attention to colors with small counts: a removal that is harmless in a large state may fail when that color has zero or one ball. For a state-dependent rule, record the condition selecting each branch and verify that all relevant conditions are mutually intelligible and cover the states where the rule is supposed to apply.

Common warning signs include a negative coordinate, a fractional count, an unspecified fallback when a removal is impossible, or an update that leaves an empty urn when another assignment is required. A further warning sign is an implementation that silently clips negative values to zero. Clipping makes the actual update different from the stated update and can change which treatments are drawn later.

No remedy is universally best. A guarded rule can preserve the design's intended behavior in ordinary states while defining a feasible boundary action, but the guard itself affects the process. Stopping may be appropriate for a design that explicitly allows termination, but it is not a way to claim that an otherwise invalid update is valid. Add-only updates are easier to audit, although they may not express the desired reinforcement or removal behavior.

The central limitation of a feasibility check is that it establishes only whether the urn operation can be carried out. It does not show that the rule has desirable allocation properties, that it improves patient outcomes, or that later statistical analyses are valid. Those are distinct design questions. Here the essential requirement is more basic: every update that the stated randomization can actually select must correspond to a possible urn composition.

Common Mistake