Deriving Friedman Urn Allocation Probabilities

Why Condition on Both the Draw and the Response?

A response-adaptive urn has two sources of randomness at each patient: the urn determines which treatment is assigned, and the patient's response determines how the urn changes. To find a one-step transition probability, account for both sources in order. The probability of a particular next state is the sum of the probabilities of all draw-response combinations that produce it.

For a Friedman urn, a successful response reinforces the treatment just drawn. A failure reinforces every other treatment. Consequently, the allocation probabilities after the update depend on the entire new composition, not only on whether the response was a success. The derivation below makes that dependence explicit.

Model and Assumptions

Definition: Consider \(k\geq 2\) treatments. Immediately before patient \(n+1\) is assigned, let the urn composition be \(\mathbf{X}_n=(X_{n1},\ldots,X_{nk})\), where each \(X_{ni}\) is a positive integer number of balls for treatment \(i\). Write \(T_n=\sum_{i=1}^k X_{ni}\), and let \(\mathbf{e}_i\) be the vector with 1 in position \(i\) and 0 elsewhere. The next treatment \(A_{n+1}\) is drawn with probability \(P(A_{n+1}=i\mid\mathbf{X}_n=\mathbf{x})=x_i/T_n\). Conditional on treatment \(i\) and the history so far, the binary response \(Y_{n+1}\) is a success with fixed probability \(\theta_i\), where \(0\leq\theta_i\leq1\). Under the Friedman update, the next composition is \(\mathbf{x}+\mathbf{e}_i\) after a success on treatment \(i\), and \(\mathbf{x}+\mathbf{1}-\mathbf{e}_i\) after a failure, where \(\mathbf{1}\) is the vector of \(k\) ones.

The drawn ball is returned; the displayed increments describe the additional reinforcement. We assume the response is observed before the urn is updated and the next patient is assigned. The treatment-specific success probabilities are fixed, and the response distribution for the current patient depends on the past through the assigned treatment, not through an additional hidden state. Under these assumptions, the composition is sufficient to determine the next allocation distribution. If a response is delayed until after another patient is assigned, this simple update sequence does not apply without an additional rule.

Deriving the One-Step Transition Formula

Fix the current composition \(\mathbf{x}\), with total \(T=\sum_i x_i\). For treatment \(i\), the probability of drawing its ball is \(x_i/T\). Given that draw, the success probability is \(\theta_i\), so the joint probability of drawing \(i\) and observing success is \((x_i/T)\theta_i\). The corresponding failure probability is \((x_i/T)(1-\theta_i)\). Multiplication is justified by conditioning: first select the treatment, then use its conditional response probability.

Each such joint event has a deterministic next state under the Friedman rule. Thus, for any possible next composition \(\mathbf{z}\), the transition probability is:

P(\mathbf{X}_{n+1}=\mathbf{z}\mid\mathbf{X}_n=\mathbf{x}) =\sum_{i=1}^k \frac{x_i}{T} \left[ \theta_i\,\mathbb{I}\{\mathbf{z}=\mathbf{x}+\mathbf{e}_i\} +(1-\theta_i)\,\mathbb{I}\{\mathbf{z}=\mathbf{x}+\mathbf{1}-\mathbf{e}_i\} \right].

Here \(\mathbb{I}\{\cdot\}\) equals 1 when the statement in braces is true and 0 otherwise. This indicator form is useful because distinct draw-response events can lead to the same next composition; their probabilities must then be added. For \(k\geq3\), the success and failure destinations in this formula are all distinct across treatment-response pairs. For \(k=2\), a success on one treatment and a failure on the other can produce the same state, so aggregation is essential.

As a check, summing the formula over all possible next states gives 1. Each treatment contributes \((x_i/T)[\theta_i+(1-\theta_i)]=x_i/T\), and \(\sum_i x_i/T=1\). This verifies that the branches include every possible draw and response exactly once, with aggregation only when their destination states coincide.

Worked Example: All Transitions in a Three-Treatment Urn

Suppose the current composition is \(\mathbf{x}=(2,1,3)\), so \(T=6\). Let the hypothetical success probabilities be \((\theta_1,\theta_2,\theta_3)=(0.50,0.80,0.25)\). The treatment draw probabilities are \(2/6,\ 1/6,\ 3/6\), respectively. The assumptions above hold by stipulation: each response is observed before the update, and the treatment-specific probabilities are fixed for this calculation.

For treatment 1, a success has probability \((2/6)(0.50)=0.1667\) and leads to \((3,1,3)\). A failure has probability \((2/6)(0.50)=0.1667\) and leads to \((2,2,4)\).

For treatment 2, a success has probability \((1/6)(0.80)=0.1333\) and leads to \((2,2,3)\). A failure has probability \((1/6)(0.20)=0.03333\) and leads to \((3,1,4)\).

For treatment 3, a success has probability \((3/6)(0.25)=0.1250\) and leads to \((2,1,4)\). A failure has probability \((3/6)(0.75)=0.3750\) and leads to \((3,2,3)\).

The six destinations are distinct, and the transition probabilities sum to \(0.1667+0.1667+0.1333+0.03333+0.1250+0.3750=1.000\). The probability of a success somewhere in this step is the sum of the three success branches:

\frac{2}{6}(0.50)+\frac{1}{6}(0.80)+\frac{3}{6}(0.25) =\frac{1.00+0.80+0.75}{6} =\frac{2.55}{6} =0.4250.

The failure probability is \(1-0.4250=0.5750\). This is a useful aggregate check, but it does not identify a single next composition: the destination still depends on which treatment was drawn.

From State Transitions to the Next Allocation

A transition probability describes the updated urn, while an allocation probability describes the treatment drawn from that updated urn. If the current patient produces next state \(\mathbf{z}\), the following patient's probability of receiving treatment \(j\) is \(z_j/\sum_i z_i\). Averaging over the possible next states gives the marginal probability:

P(A_{n+2}=j\mid\mathbf{X}_n=\mathbf{x}) =\sum_{\mathbf{z}} P(\mathbf{X}_{n+1}=\mathbf{z}\mid\mathbf{X}_n=\mathbf{x}) \frac{z_j}{\sum_{i=1}^k z_i}.

The sum is over the possible states after the current patient's response. It is important to divide by the total in each updated state. In a \(k\)-treatment Friedman urn, a success adds one ball in total, whereas a failure adds \(k-1\) balls in total. Therefore those denominators need not be the same.

Worked Example: Marginal Probability of the Next Patient's Treatment

Continue with the hypothetical three-treatment example, \(\mathbf{x}=(2,1,3)\) and \((\theta_1,\theta_2,\theta_3)=(0.50,0.80,0.25)\). The six transition branches have probabilities and destination states calculated above. To find the probability that the following patient receives treatment 1, multiply each branch probability by the treatment-1 fraction in its destination, then add:

\begin{aligned} P(A_{n+2}=1\mid\mathbf{X}_n=\mathbf{x}) ={}&0.1667\left(\frac{3}{7}\right) +0.1667\left(\frac{2}{8}\right) +0.1333\left(\frac{2}{7}\right)\\ &+0.03333\left(\frac{3}{8}\right) +0.1250\left(\frac{2}{7}\right) +0.3750\left(\frac{3}{8}\right)\\ ={}&0.3400\ \text{(approximately)}. \end{aligned}

For example, the first branch is a success on treatment 1: it occurs with probability \(0.1667\), leaves state \((3,1,3)\) with total 7, and gives treatment 1 probability \(3/7\) at the next draw. Repeating the calculation for treatments 2 and 3 gives \(0.2193\) and \(0.4406\), respectively. These sum to 1.000, as required. They are probabilities for the next allocation averaged over the current response and urn update; they are not the treatment probabilities in the current state, which are \(2/6,\ 1/6,\ 3/6\).

Worked Example: Aggregating Coincident States With Two Treatments

Let the hypothetical current state be \((2,3)\), and let the success probabilities be \(\theta_1=0.60\) and \(\theta_2=0.30\). The draw probabilities are \(2/5\) and \(3/5\). A success on treatment 1 occurs with probability \((2/5)(0.60)=0.24\) and produces state \((3,3)\); a failure on treatment 1 has probability \((2/5)(0.40)=0.16\) and produces \((2,4)\).

A success on treatment 2 occurs with probability \((3/5)(0.30)=0.18\) and produces \((2,4)\). A failure on treatment 2 has probability \((3/5)(0.70)=0.42\) and produces \((3,3)\). Therefore the two state-transition probabilities, after combining branches with the same destination, are:

P((3,3)\mid(2,3))=0.24+0.42=0.66, \qquad P((2,4)\mid(2,3))=0.16+0.18=0.34.

They sum to 1. The next patient's probability of treatment 1 is \(0.66(3/6)+0.34(2/6)=0.4433\); the probability of treatment 2 is \(1-0.4433=0.5567\). Treating the four draw-response branches as four different states would be wrong: the state is the composition, and two different events can produce the same composition.

A Further Check: Expected Change in Urn Composition

The transition branches also provide a check on the expected number of balls added to each treatment. Let \(\Delta X_j=X_{n+1,j}-X_{nj}\). Treatment \(j\) gains a ball after success on \(j\), and also after failure on any other treatment. Consequently:

E(\Delta X_j\mid\mathbf{X}_n=\mathbf{x}) =\frac{x_j}{T}\theta_j +\sum_{i\ne j}\frac{x_i}{T}(1-\theta_i).

This follows by adding the probability of every branch that increments coordinate \(j\); all other branches contribute zero to \(\Delta X_j\). Summing over \(j\) gives \(P(\text{success}\mid\mathbf{x})+(k-1)P(\text{failure}\mid\mathbf{x})\), the expected total increase in urn size.

Worked Example: Checking the Expected Total Increase

For \((2,1,3)\) and response probabilities \((0.50,0.80,0.25)\), the success probability is \(0.4250\), and the failure probability is \(0.5750\). With three treatments, success adds one ball and failure adds two. Thus the expected increase in total urn size is:

$$ 1(0.4250)+2(0.5750)=1.575. $$

The coordinate calculation gives \(E(\Delta X_1)=0.5750\), \(E(\Delta X_2)=0.6750\), and \(E(\Delta X_3)=0.3250\). Their sum is \(0.5750+0.6750+0.3250=1.575\), matching the total-size calculation. A mismatch signals that a failure branch, a coordinate increment, or a treatment probability has been omitted or miscalculated.

Diagnostics, Comparisons, and Limitations

A reliable calculation can be checked in several ways. First, the treatment draw probabilities \(x_i/T\) must sum to 1. Second, the success and failure branches for each treatment must sum to \(x_i/T\). Third, all state-transition probabilities, after combining duplicate destinations, must sum to 1. Finally, each destination must reflect the specified rule: a success adds one ball to the drawn treatment, while a failure adds one ball to each other treatment. Check the denominator again when calculating a later allocation, because failure changes the total by \(k-1\), not by 1.

The Friedman rule differs from the play-the-winner rule in how a failure changes the urn: under Friedman, failure reinforces all treatments other than the one drawn, rather than just selecting a single alternative for reinforcement. Both are response-adaptive urn rules, but they therefore have different destination states and transition probabilities. Fixed randomization is another contrast: its allocation probabilities are set independently of the accrued responses, whereas an urn's next allocation probabilities depend on its updated composition.

These transition calculations do not establish that the design is optimal, guarantee balance, or remove the need for sound trial conduct. They rely on the stated reinforcement rule, observed binary responses, and fixed treatment-specific response probabilities. If treatment effects change over time, outcomes are missing, or the update rule is different, the formula must be modified to represent that process. A common mistake is to say, “The next patient has probability \(x_j/T\) of receiving treatment \(j\), so that is also the probability after this patient's response.” The correction is that \(x_j/T\) is the current allocation probability; after the response, average the updated-state allocation fractions over the transition distribution.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

In a three-treatment urn, what state follows a failure after treatment 2 is drawn from state \((4,2,1)\)?
For state \((1,2)\) and two treatments with success probabilities \((0.50,0.25)\), find the probability that the next state is \((2,2)\).
Why must the transition probabilities from one fixed current state sum to 1?
In a four-treatment Friedman urn, how much does total urn size increase after a failure?

Solutions. (1) A failure adds a ball to every treatment except treatment 2, so \((4,2,1)+(1,0,1)=(5,2,2)\). (2) The draw probabilities are \(1/3\) and \(2/3\). A success on treatment 1 produces \((2,2)\) with probability \((1/3)(0.50)=1/6\). A failure on treatment 2 also produces \((2,2)\), with probability \((2/3)(0.75)=1/2\). Add the coincident branches: \(1/6+1/2=2/3\). (3) The branches exhaust all treatment draws and, conditional on each draw, success and failure probabilities sum to 1; aggregating duplicate destinations preserves the total probability 1. (4) Failure adds one ball to each of the other three treatments, so total urn size increases by 3.