The Friedman Urn Rule

Why Specify the Update Rule Precisely?

An urn rule determines how an observed response changes later treatment assignments. In a multi-arm design, the key question is not just whether a success or failure adds balls, but which treatment colors receive them. Under the Friedman urn rule, a success adds a ball of the treatment just assigned; a failure adds one ball for every other treatment. Thus, when there are more than two treatments, failure reinforces several alternatives at once.

The update is deterministic once the assigned treatment and response are known. The sequence of urn compositions is nevertheless random because the next treatment is selected by drawing a ball, and the patient’s response may also be random. The one-step composition recursion is useful for describing such changes; here the emphasis is the particular replacement rule that supplies its update.

Definition and Assumptions

Suppose there are \(K\geq 2\) treatments, labeled \(1,\ldots,K\). Let \(X_t=(X_{t1},\ldots,X_{tK})\) be the urn composition immediately before participant \(t\) is assigned, where \(X_{tj}\) is the number of balls of treatment color \(j\). Assume each initial count is a positive integer. A ball is drawn uniformly from the urn, its color determines the assigned treatment, and the ball is returned before any reinforcement is added.

Let \(I_t=i\) denote assignment to treatment \(i\), and let \(Y_t=1\) indicate success and \(Y_t=0\) indicate failure. The rule below concerns a binary response. For a probabilistic trial model, one possible assumption is that the response satisfies \(P(Y_t=1\mid I_t=i,\text{history before the response})=p_i\), with a fixed \(p_i\) for each treatment. The update itself does not require this probability model: it only requires that a response be classified as success or failure after assignment.

For \(j=1,\ldots,K\), let \(e_j\) be the length-\(K\) vector with a 1 in coordinate \(j\) and 0 elsewhere. The vector added after a success on treatment \(i\) is \(e_i\); the vector added after a failure on treatment \(i\) is \(\mathbf{1}-e_i\), where \(\mathbf{1}\) is the vector of \(K\) ones. Consequently, for either response,

This compact expression encodes all treatment-specific updates. When \(Y_t=1\), the second term vanishes and only the assigned treatment coordinate increases. When \(Y_t=0\), the first term vanishes and every unassigned treatment coordinate increases by one.

Replacement Matrices and Total Urn Size

A replacement matrix records the added balls for every possible assigned treatment. Use the convention that rows correspond to the treatment assigned and columns correspond to the colors added. The success replacement matrix is the identity matrix \(S=I_K\). The failure replacement matrix is \(F=J_K-I_K\), where \(J_K\) is the \(K\times K\) matrix of ones. The \(i\)th row of \(S\) is \(e_i\); the \(i\)th row of \(F\) is \(\mathbf{1}-e_i\).

For example, with three treatments, the replacement rows are:

Let \(T_t=\sum_{j=1}^K X_{tj}\) be the total number of balls before participant \(t\). A success adds one ball in total. A failure adds \(K-1\), because there is one added ball for each treatment other than the assigned one. Therefore,

This derivation follows by summing the coordinates of the response-specific addition: \(\sum_j(e_{I_t})_j=1\), while \(\sum_j(\mathbf{1}-e_{I_t})_j=K-1\). The increment is therefore response-dependent when \(K>2\). For \(K=2\), both a success and a failure add one ball.

Worked Updates

Checking an Update and Avoiding Common Errors

A reliable check is to identify the assigned treatment first, then select the response row for that treatment. Only after that should the addition be applied to the composition. For every update, verify that all coordinates remain nonnegative integers and that the changed coordinates match the response rule. The total-size check is especially efficient: a success must add exactly one ball, and a failure must add exactly \(K-1\) balls.

The most common mistake is to treat “failure reinforces the other treatments” as “failure adds one ball to every treatment.” The assigned treatment is not one of the “other treatments.” The correction is to put a zero in its coordinate and a one in every other coordinate. A second mistake is to add the reinforcement without returning the drawn ball; the definition requires the drawn ball to be returned, so its color remains represented in the pre-existing composition.

Interpretation and Limitations

The Friedman rule is one specific way to translate binary outcomes into reinforcement. It should not be confused with fixed randomization, in which assignment probabilities are set independently of observed responses, or with a multi-arm rule that selects only one alternative for reinforcement after failure. Its defining feature is the failure row \(\mathbf{1}-e_i\), not merely the fact that the design is adaptive.

This update rule alone does not establish that the resulting design is appropriate for a particular trial. It requires a meaningful binary response classification and an explicit choice of initial composition; positive initial counts ensure that every treatment color is initially available. The size of the urn changes according to the observed response, and with many treatments a failure adds several balls. These are design properties that should be recognized when specifying and assessing an urn design, not arithmetic details to ignore.

The rule also does not guarantee equal allocation, good estimation, or a particular ethical or inferential property. Those questions require additional analysis of the design and its objectives. In particular, the update vectors define how the urn changes; they do not by themselves summarize the distribution of future assignments or the operating characteristics of a trial.