Building an Urn Allocation Algorithm

From an urn rule to an allocation algorithm

A generalized urn rule becomes an allocation algorithm only when its operations are specified in order. At each trial step, the current urn determines the probability of each treatment; a random draw assigns a treatment; the participant's response is observed and classified; and the corresponding replacement rule changes the urn before the next allocation. The timing matters: a response cannot affect the treatment assignment that produced it, but it can affect later assignments.

This tutorial describes the procedure using counts rather than a literal collection of balls. A count-vector implementation is equivalent to drawing uniformly from a physical urn when each ball represents one treatment and the algorithm uses the current counts to compute the draw probabilities.

A complete specification also needs an initial composition, a list of response categories, and a rule mapping each treatment-response pair to a net-change vector. The categories should be mutually exclusive and exhaustive for the outcomes the algorithm can encounter. If a response cannot be classified, the algorithm needs a prespecified handling rule rather than an improvised update.

The net-change representation accommodates both additions and removals. Given treatment \(i\) and response \(j\), the next state is \(U_{t+1}=U_t+r_{ij}\). The result must have nonnegative integer counts and a positive total before another allocation can be made. If the rule describes a sequence of physical removals and additions, that sequence must itself be feasible; an acceptable final count vector does not make an impossible intermediate operation valid.

The allocation algorithm, in order

The following procedure makes explicit which state is used for each decision. Here, \(J_t\) denotes the response category observed after assigning the \(t\)th participant. If outcomes are not yet available when the next participant is enrolled, the algorithm must specify how it handles that delay; the steps below assume the response is available before the next update and draw.

A useful implementation keeps the randomization step separate from the update step. For example, the draw can be made by generating a uniform random number and dividing the interval from zero to one into consecutive segments with lengths \(u_{1,t}/S_t,\ldots,u_{K,t}/S_t\). The treatment corresponding to the segment containing the random number is selected. The particular software routine may differ, but the probabilities must match the current count vector.

Worked examples

Why the state update has this form

The update equation follows directly from defining \(r_{ij}\) as the net change from the pre-draw state. Conditional on \(U_t\), treatment \(i\) is drawn with probability \(u_{i,t}/S_t\). If the conditional probability of response category \(j\), after assigning treatment \(i\), is \(q_{j\mid i,t}\), then the probability of that treatment-response pair is the product of the two conditional probabilities:

For that pair, the next urn state is \(U_t+r_{ij}\). If two different pairs produce the same next state, the probability of that state is the sum of the probabilities of all such pairs. This calculation justifies the transition implied by an algorithm; it does not require the response probabilities to be equal across treatments. If the response distribution depends on information beyond \(U_t\), such as earlier outcomes, the state \(U_t\) alone need not determine the next-state probabilities. The algorithm still operates, but a transition description must include the relevant history or other conditioning information.

Checks, alternatives, and limitations

Before running an algorithm, test its specification with small, deliberate checks. Confirm that the initial state has positive total size; that every possible treatment-response pair has a defined update; and that each draw probability is between zero and one and the probabilities sum to one. After an update, check that the new counts are integers, no count is negative, and the total is positive. If removal rules are present, test them at states where the count to be removed is small, not only at the initial state.

A frequent implementation error is updating before drawing. The incorrect reasoning is that the current participant's response should influence the treatment they receive. But that response is not observed until after assignment and treatment; using it for the same allocation reverses the intended order and can introduce information that was not available at randomization. The correction is to draw from \(U_t\), observe the response, and use the response only to produce \(U_{t+1}\).

Two common implementation choices are to maintain a literal list of balls or to store only the count vector. A literal list can make the physical draw easy to visualize, while the count vector is compact and computes the same probabilities when draws are uniform over balls. Count vectors are particularly convenient for additions and removals, but they make explicit feasibility checks essential. A fixed allocation schedule is another kind of procedure: it does not use response-linked urn updates. It can serve as a conceptual contrast, but it is not a substitute for implementing the specified generalized urn rule.

The algorithm is only as well-defined as its response coding and replacement rule. Missing or delayed responses, an unlisted response category, a rule that removes a nonexistent ball, or a state with total zero prevents the next draw unless a handling policy has been specified. In practice, save a log of every pre-draw state, probability vector, assignment, response category, update vector, and resulting state. Such a log makes it possible to locate whether an unexpected allocation arose from the draw, the response classification, or the update.

Finally, writing the algorithm does not supply a response model, establish a treatment effect, or guarantee that the urn's allocation behavior is desirable for a particular study. Those are separate questions. Here the objective is narrower: to state and execute the randomization and replacement steps without ambiguity.