Comparing Generalized Urn Update Rules

Why Compare Update Rules?

In an urn design, treatment assignment is randomized by drawing a ball: the chance of assigning a treatment is its share of the balls currently in the urn. The update rule determines how that share changes after a patient’s response is observed. Two rules can use the same starting urn and the same observed response yet produce different probabilities for the next assignment. Comparing them carefully means separating the state before the draw, the observed outcome, and the balls added under the rule.

This tutorial compares a fixed Friedman rule with a success-only rule for a fixed number of treatment arms. The calculations are one-step calculations: the assignment and response are specified, and the task is to determine the urn composition and allocation probabilities immediately afterward. No claim about long-run behavior is needed to make this comparison.

Definition: For \(K\) treatments, let \(x=(x_1,\ldots,x_K)\) be the urn state before a draw, where \(x_i\) is the number of balls for treatment \(i\), and let \(T=\sum_{i=1}^K x_i\). If \(T>0\), the probability of assigning treatment \(i\) on this draw is \(x_i/T\). After a patient is assigned treatment \(i\) and their response is observed, a replacement rule specifies the balls added to the urn. The next allocation probabilities are calculated from the updated state, not from the original state.

Specify the Rules Before Calculating

For consistency, use the following fixed replacement conventions. Under the Friedman rule used here, a success adds one ball of the assigned treatment; a failure adds one ball of every other treatment and none of the assigned treatment. Under the success-only rule, a success adds one ball of the assigned treatment, while a failure adds no balls. In both rules, the ball drawn is returned to the urn; the stated additions are in addition to that returned ball.

A replacement matrix records the additions. Rows index the treatment assigned to the patient, and columns index the treatment color of the ball being added. Let \(R^{(1)}\) denote the success replacement matrix and \(R^{(0)}\) the failure replacement matrix. For three treatments, the rules are:

R^{(1)}_{\text{Friedman}}=R^{(1)}_{\text{success-only}}= \begin{pmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{pmatrix}, \qquad R^{(0)}_{\text{Friedman}}= \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}, \qquad R^{(0)}_{\text{success-only}}= \begin{pmatrix} 0&0&0\\ 0&0&0\\ 0&0&0 \end{pmatrix}.

For example, row 2 of the Friedman failure matrix says that after a failure on treatment 2, one ball of treatment 1 and one ball of treatment 3 are added. The row of the applicable matrix gives the additions; it does not give the updated state by itself. To update the state, add those additions to the existing composition \(x\).

One-step update: If treatment \(i\) is assigned and response \(r\) is observed, let \(a^{(r)}_i\) be row \(i\) of the relevant replacement matrix. The updated state is \(x'=x+a^{(r)}_i\). The next-draw probability for treatment \(j\) is \(x'_j/\sum_{\ell=1}^K x'_\ell\).

Worked Calculations at a Three-Treatment State

The examples use hypothetical urns. Assume all counts are nonnegative integers, the total urn size is positive, exactly one ball is drawn for each assignment, and the specified response is observed before the next allocation. These conditions make the stated update rules applicable. The examples hold the state and observed assignment fixed when comparing the rules.

Worked Example: Success on Treatment 2

Suppose the state is \(x=(8,5,3)\), and a patient is assigned treatment 2 and has a success. Calculate the next allocation probabilities under both rules.

The current total is \(T=8+5+3=16\), so the current probabilities are \(8/16=0.5000\), \(5/16=0.3125\), and \(3/16=0.1875\). Since the observed response is a success, both rules add one ball of the assigned treatment, treatment 2. Thus:

x'=(8,5,3)+(0,1,0)=(8,6,3), \qquad T'=8+6+3=17.

The next-draw probabilities are \(8/17=0.4706\) for treatment 1, \(6/17=0.3529\) for treatment 2, and \(3/17=0.1765\) for treatment 3. They sum to \(17/17=1\). In this particular case, the two rules agree because their success updates are identical.

Worked Example: Failure on Treatment 2

Use the same starting state \(x=(8,5,3)\), but suppose the patient assigned to treatment 2 has a failure. Calculate the next allocation probabilities under each rule.

Under the Friedman rule, row 2 of the failure matrix adds one ball each to treatments 1 and 3. The state and total become:

x'_{\text{Friedman}}=(8,5,3)+(1,0,1)=(9,5,4), \qquad T'_{\text{Friedman}}=9+5+4=18.

Therefore the next-draw probabilities are \(9/18=0.5000\) for treatment 1, \(5/18=0.2778\) for treatment 2, and \(4/18=0.2222\) for treatment 3.

Under the success-only rule, a failure adds no balls. The state remains \((8,5,3)\), with total 16. The next-draw probabilities are \(8/16=0.5000\), \(5/16=0.3125\), and \(3/16=0.1875\), respectively. Thus, after this failure, the Friedman rule changes the next allocation probabilities, whereas the success-only rule leaves them unchanged.

Worked Example: A Failure on Treatment 1

Consider a two-treatment urn with state \(x=(4,2)\). A patient is assigned treatment 1 and has a failure. Find and compare the next-draw probabilities.

For the Friedman rule, a failure on treatment 1 adds one ball of the other treatment, treatment 2. The updated state is \((4,3)\), and its total is \(4+3=7\). The next probabilities are \(4/7=0.5714\) for treatment 1 and \(3/7=0.4286\) for treatment 2.

For the success-only rule, the failure produces no additions. The state stays \((4,2)\), with total 6, so the next probabilities are \(4/6=0.6667\) and \(2/6=0.3333\). The comparison is between two updated compositions: it is not obtained by comparing only the number of balls added, because the probabilities depend on each color’s count relative to the updated total.

Why the Probability Formula Works

The urn update changes the counts used in the next draw. Conditional on the updated state \(x'\), a draw is uniform over the \(T'=\sum_j x'_j\) individual balls. Exactly \(x'_j\) of those balls represent treatment \(j\). The event of drawing treatment \(j\) therefore contains \(x'_j\) of the \(T'\) equally likely balls, giving:

P(\text{next assignment is }j\mid x')= \frac{x'_j}{T'} = \frac{x_j+a^{(r)}_{ij}}{\sum_{\ell=1}^K(x_\ell+a^{(r)}_{i\ell})}.

This justifies both the numerator and the denominator: the numerator is the updated count for treatment \(j\), while the denominator is the total number of balls after all additions. In the Friedman failure example with treatment 2, the added row was \((1,0,1)\), so the total addition was \(1+0+1=2\). The denominator consequently increased from 16 to 18, not from 16 to 17.

Start with the state.
Record the count for each treatment and calculate the current total if needed.

Identify the assigned treatment and response.
Select the row for that treatment from the success or failure matrix.

Update every count.
Add each entry of that row to the corresponding treatment count.

Normalize the updated state.
Divide each updated count by the sum of all updated counts, then check that the probabilities sum to 1.

Comparison, Diagnostics, and Limitations

For the fixed rules defined here, successes produce the same one-ball reinforcement in both schemes. The difference is what happens after failure: the Friedman rule adds balls to the alternative treatments, while the success-only rule makes no additions. The distinction can be summarized as follows.

Observed response	Friedman additions after assignment to \(i\)	Success-only additions after assignment to \(i\)
Success	One ball of treatment \(i\)	One ball of treatment \(i\)
Failure	One ball of every treatment other than \(i\)	No balls

A replacement matrix is a direct way to specify a fixed rule for more than two treatments: the row identifies the assigned treatment and the outcome-specific matrix identifies the additions. This representation also makes clear why a one-step comparison is not a general ranking of the designs. The resulting probabilities depend on the starting counts, the assigned treatment, and the response; this calculation alone does not establish which rule performs better over a trial.

Several checks help catch arithmetic or interpretation errors:

Check the row and outcome. A failure on treatment 2 uses row 2 of the failure matrix, not row 2 of the success matrix.
Check whether the drawn ball is already in the state. In these examples, \(x\) includes the ball that was drawn and returned. Add only the specified replacement balls.
Check the denominator. Recalculate the total after updating every treatment count. The updated probabilities must sum to 1.
Check what is being compared. Current probabilities come from \(x\); next-draw probabilities come from \(x'\). Do not describe one as the other.

A common mistake is to treat “success-only” as adding one ball after every response, or to assume that a failure under that rule removes the ball assigned. Neither is part of the rule as defined here: a success adds one ball of the assigned treatment, and a failure adds none. Another mistake is to conclude that a treatment’s next probability must rise whenever its ball count rises. Its probability is a ratio, so both its count and the total can change. In a Friedman failure update, other treatments receive balls, which can change a treatment’s share even though its own count is unchanged.

These calculations assume that the response category is correctly recorded, that the stated replacement rule is applied consistently, and that the urn still contains at least one ball. They compare only the immediate next allocation probabilities for a specified state and response. They do not by themselves address state-dependent updates, changes in total urn size across a sequence, or the broader operating characteristics of a trial design.

Key takeaway: To compare fixed urn update rules, apply each rule’s outcome-specific replacement row to the same state, then divide every updated count by the updated total. A difference in additions matters only through the resulting proportions.

Check Your Understanding

Use the Friedman and success-only conventions stated above. Treat each situation as a separate hypothetical urn.

For \(x=(6,4,2)\), a patient assigned to treatment 3 has a success. Find the next allocation probabilities under both rules.
For \(x=(6,4,2)\), a patient assigned to treatment 1 has a failure. Find the updated state and next allocation probabilities under each rule.
In one sentence, explain why the two rules give the same next probabilities after a success.
A student updates a state \((5,3,2)\) after a failure on treatment 2 under the success-only rule, changing it to \((5,3,3)\). Identify the error and give the correct state.

Solutions. (1) Both rules add one ball to treatment 3, giving \((6,4,3)\) with total 13; the probabilities are \(6/13=0.4615\), \(4/13=0.3077\), and \(3/13=0.2308\). (2) Friedman adds one ball to treatments 2 and 3, giving \((6,5,3)\), total 14, and probabilities \(6/14=0.4286\), \(5/14=0.3571\), and \(3/14=0.2143\). Success-only adds none, leaving \((6,4,2)\), total 12, and probabilities \(0.5000\), \(0.3333\), and \(0.1667\). (3) Both rules use the same success update: one ball of the assigned treatment. (4) The student added a ball after a failure; success-only makes no additions after failure, so the correct state remains \((5,3,2)\).