A Worked Friedman Urn Path

Following One Urn Path

A response-adaptive urn is easiest to understand when its state is carried forward explicitly: record the number of balls of each treatment, draw according to the current composition, observe the assigned participant’s binary response, and then apply the specified replacement rule. This tutorial works through that sequence for three treatments. The calculations describe how the randomization mechanism changes; they do not, by themselves, estimate treatment effects or establish that one treatment is better.

We use the Friedman rule in which a success adds balls of the assigned treatment’s color, while a failure adds balls of every other treatment’s color. The ball drawn is returned in either case. The amounts added are fixed in advance. It is essential to state this convention because urn rules can use different replacement rules, and a path calculation is only meaningful once the rule is unambiguous.

Definition: Let \(x_i\) be the current number of balls for treatment \(i\), and let \(T=\sum_i x_i\) be the total number of balls. A treatment is drawn with probability \(x_i/T\). With binary response \(Y=1\) for success and \(Y=0\) for failure, the Friedman update adds \(\alpha\) balls of the assigned treatment’s color after success, and \(\beta\) balls of each other treatment’s color after failure. Here \(\alpha\) and \(\beta\) are fixed positive integers.

For this tutorial, the three treatments are \(A\), \(B\), and \(C\), with \(\alpha=2\), \(\beta=1\), and initial composition \((2,2,2)\). We assume the urn is used as specified: its current composition is known before each draw; the draw is made according to the current ball proportions; the binary response is recorded before the next draw; and the replacement rule is applied correctly. No model for the probabilities of response is needed to calculate the urn updates. Without such a model, however, we cannot calculate probabilities for response sequences or condition correctly on a complete response path.

A Complete Numerical Path

Write \(I_t\) for the treatment assigned at draw \(t\), and \(Y_t\) for the binary response observed after that assignment. The allocation probability at draw \(t\) is determined by the urn immediately before the draw. In particular, it is conditional on the assignments and responses already observed, not on responses that have not yet occurred.

P(I_t=i\mid H_{t-1})=\frac{x_{i,t}}{\sum_j x_{j,t}},

Here \(H_{t-1}\) denotes the observed assignment-and-response history before draw \(t\), and \(x_{i,t}\) is the number of balls of treatment \(i\) at that point. Start with \(x=(2,2,2)\). The hypothetical observed sequence is \(A\) with success, \(B\) with failure, \(C\) with success, and \(A\) with failure.

Worked Example: Updating a Three-Treatment Friedman Urn

Draw 1. Initially the total is \(2+2+2=6\). Thus the probability of assigning \(A\) is \(2/6=1/3\), and the three assignment probabilities are \((1/3,1/3,1/3)\). The response is a success. Return the drawn ball and add \(\alpha=2\) balls of color \(A\), giving the new composition \((4,2,2)\), with total \(8\).

Draw 2. Given the history through draw 1, the probabilities are \(4/8=1/2\) for \(A\), \(2/8=1/4\) for \(B\), and \(2/8=1/4\) for \(C\). Suppose \(B\) is assigned and the response is a failure. Add \(\beta=1\) ball to each treatment other than \(B\): \(A\) and \(C\). The new composition is \((5,2,3)\), whose entries sum to \(10\).

Draw 3. The probabilities are now \(5/10=1/2\) for \(A\), \(2/10=1/5\) for \(B\), and \(3/10\) for \(C\). Suppose \(C\) is assigned and the response is a success. Add two balls of color \(C\), giving \((5,2,5)\), with total \(12\).

Draw 4 and the next probabilities. From \((5,2,5)\), the assignment probabilities are \(5/12\), \(2/12=1/6\), and \(5/12\). Suppose \(A\) is assigned and the response is a failure. Add one ball to each of the other colors, \(B\) and \(C\). The composition becomes \((5,3,6)\), with total \(14\). The allocation probabilities for the next draw are therefore \(5/14\) for \(A\), \(3/14\) for \(B\), and \(6/14=3/7\) for \(C\). They sum to one.

The updates can also be checked treatment by treatment. After a success, only the assigned treatment’s count increases; after a failure, the assigned treatment’s count stays the same and each other count increases. The ball drawn is returned, so neither response removes a ball from the assigned treatment. This check helps catch a frequent error: treating a failure as if it removed the drawn ball, or adding failure balls to the assigned treatment rather than to the other treatments.

Why the Sequential Assignment Product Has a Limited Meaning

The path above contains four assignment probabilities, each evaluated using the composition just before that assignment. Their product is

\frac{2}{6}\cdot\frac{2}{8}\cdot\frac{3}{10}\cdot\frac{5}{12} =\frac{60}{5760} =\frac{1}{96}.

This product is the assignment factor along the displayed history: at each step, it uses the assignment probability conditional on the assignments and responses observed before that draw. It is not generally the probability of the assignment sequence conditional on the entire response path. Nor, in general, is it the probability of the assignment sequence after response histories have been left unspecified. The reason is that earlier responses change the urn, and therefore can change later assignment probabilities.

To obtain the probability of a joint assignment-and-response history, a response model is also needed. For example, if \(q_{i,h}\) is the probability of success for treatment \(i\) given the relevant prior history \(h\), the joint history probability is built from both kinds of factors: the assignment probability before each response and the response probability after that assignment. The assignment product alone omits the response factors. Conditioning on the complete response path is different again: it can require normalizing over possible assignments using Bayes’ rule.

Worked Example: Conditioning on a Response Can Change an Assignment Probability

Suppose a single participant is randomized between \(A\) and \(B\) with equal probabilities, and suppose the response probabilities are \(P(Y=1\mid I=A)=0.8\) and \(P(Y=1\mid I=B)=0.2\). These are hypothetical values used only to illustrate conditioning. Before observing the response, \(P(I=A)=0.5\). After observing a success, Bayes’ rule gives

P(I=A\mid Y=1) =\frac{P(Y=1\mid I=A)P(I=A)} {P(Y=1\mid I=A)P(I=A)+P(Y=1\mid I=B)P(I=B)} =\frac{0.8(0.5)}{0.8(0.5)+0.2(0.5)} =0.8.

Thus the probability of assigning \(A\) conditional on the observed success is \(0.8\), not the original allocation probability \(0.5\). A response-adaptive urn has the additional complication that earlier responses may affect later urn states. Consequently, multiplying the urn’s stepwise allocation probabilities does not generally give an assignment-sequence probability conditional on the full response path.

Deriving the One-Step Update

The treatment-by-treatment update can be written compactly. If \(I_t=i\) and \(Y_t=1\), the count of treatment \(j\) increases only when \(j=i\), by \(\alpha\). If \(I_t=i\) and \(Y_t=0\), the count increases by \(\beta\) when \(j\ne i\), and does not increase when \(j=i\). These cases give

x_{j,t+1} =x_{j,t} +\alpha\,\mathbf{1}\{I_t=j,Y_t=1\} +\beta\,\mathbf{1}\{I_t\ne j,Y_t=0\}.

Here \(\mathbf{1}\{E\}\) equals one when condition \(E\) is true and zero otherwise. To verify the formula, consider a fixed treatment \(j\). On success for \(j\), the first indicator is one and the second is zero, so \(\alpha\) is added. On success for another treatment, both indicators are zero, so \(j\)'s count is unchanged. On failure for \(j\), both indicators are zero, so the returned ball leaves \(j\)'s count unchanged. On failure for another treatment, the second indicator is one and \(\beta\) is added. These are precisely the stated replacements.

At every step, the next allocation probabilities are obtained by dividing the updated counts by their sum. For example, in the worked path, after draw 2 the composition \((5,2,3)\) gives probabilities \((5/10,2/10,3/10)\). This normalization is an immediate diagnostic: if the entries do not sum to one, either the composition total or a probability calculation is wrong.

Branching at the Same Urn State

Different responses to the same assigned treatment produce different next states. The following calculation makes that dependence explicit without requiring any assumptions about how likely either response is.

Worked Example: Success and Failure After the Same Assignment

Suppose the current composition is \((5,2,3)\), so the total is \(10\), and \(B\) is assigned. Its assignment probability at this draw is \(2/10=1/5\), conditional on the history that produced this composition.

If the response is a success, add \(\alpha=2\) balls to \(B\). The new composition is \((5,4,3)\), with total \(12\), so the next allocation probabilities are \(5/12\) for \(A\), \(4/12=1/3\) for \(B\), and \(3/12=1/4\) for \(C\).

If the response is a failure, add \(\beta=1\) ball to each of \(A\) and \(C\). The new composition is \((6,2,4)\), also with total \(12\), so the next allocation probabilities are \(6/12=1/2\) for \(A\), \(2/12=1/6\) for \(B\), and \(4/12=1/3\) for \(C\). Both branches follow the same assignment, but their different responses lead to different next allocation probabilities.

Checks, Comparisons, and Limitations

A reliable path calculation uses the same short sequence each time: identify the current composition, calculate the draw probabilities, record the assignment and response, apply the correct replacement, and normalize the updated composition. The calculations rely on a correctly specified initial composition, a clearly chosen value of \(\alpha\) and \(\beta\), binary responses coded consistently, and the stipulated draw and replacement mechanism. If the response is missing, delayed, or coded inconsistently, the next urn state cannot be determined from the rule until that issue is resolved.

This design differs from fixed equal randomization, where assignment probabilities remain fixed regardless of responses, and from a play-the-winner rule, where an individual response changes the subsequent allocation according to a different update mechanism. The Friedman rule here can increase allocation to a successful treatment, while a failure adds balls to the other treatments. Those mechanics describe how the urn evolves; they do not guarantee a particular allocation balance or justify treating a response as proof of comparative efficacy.

A path calculation is also not a complete analysis of a trial. It does not account for uncertainty in treatment-effect estimates, establish that response probabilities are correctly modeled, or show that the realized allocation is optimal. Small urns can produce substantial variation in short runs, and a low current allocation probability is not a zero probability as long as that treatment still has balls. Monitor the actual urn counts and recorded responses, and verify that every assignment probability corresponds to the state that existed before that assignment.

Check the update: success adds to the assigned color; failure adds to every other color.
Check the state: all counts must remain nonnegative, and each update must match the specified rule.
Check normalization: current counts divided by their sum must produce probabilities that total one.
Check the conditioning: each draw probability uses only the history observed before that draw.
Do not infer efficacy from allocation: the urn is a randomization mechanism, not a treatment-effect test.

The central pitfall is to label the product of stepwise assignment probabilities as the probability of an assignment sequence “given the responses.” That wording conditions on the full response path, including outcomes that can change the urn and whose probabilities may depend on treatment. The correction is to call the product the sequential assignment factor along the realized history, with each factor conditioned only on the preceding observed history. A full conditional probability involving responses requires an explicit response model and the appropriate probability calculation.

Key takeaway: In a Friedman urn path, the next allocation probabilities come from the updated ball counts. Keep the response update and the probability’s conditioning history explicit; a pathwise product of assignment probabilities is not generally a probability conditional on the complete response path.

Check Your Understanding

Answer each question, then compare your work with the solutions below.

With \(\alpha=2\) and \(\beta=1\), a three-treatment urn has composition \((3,4,5)\). Treatment \(C\) is assigned and the response is a success. Find the updated composition and the next allocation probabilities.
From composition \((3,4,5)\), treatment \(A\) is assigned and the response is a failure. Find the updated composition and the next allocation probabilities.
What does the product of the sequential assignment probabilities along a realized path condition on at each draw?
Why is the assignment-probability product alone generally insufficient for the probability of the assignments conditional on the complete response path?

Solutions. (1) Add two balls to \(C\), producing \((3,4,7)\) with total \(14\); the probabilities are \(3/14\), \(4/14=2/7\), and \(7/14=1/2\). (2) A failure after assignment to \(A\) adds one ball to each other treatment, producing \((3,5,6)\) with total \(14\); the probabilities are \(3/14\), \(5/14\), and \(6/14=3/7\). (3) At each draw it conditions only on assignments and responses observed before that draw, which determine the current urn. (4) The response path can be associated with different assignment probabilities, particularly when response probabilities depend on treatment. Conditioning on that complete path therefore generally requires a response model and a calculation such as Bayes’ rule.

What You'll Learn