From an Urn Rule to a Valid Calculation
A generalized urn rule can be easy to state and surprisingly easy to miscalculate. A response may add balls to several arms, remove balls from the assigned arm, or change the urn total. In a multi-arm problem, each update must be applied to the correct coordinates, and the next allocation probabilities must use the updated state—not the original composition.
The reliable approach is to separate three operations: calculate which arm is drawn, calculate which response occurs given that arm, and apply the corresponding replacement rule. This distinction also makes it possible to check a single sample path without confusing its probability with the probability of reaching its final state by any route.
For a simple transition calculation, suppose the response probabilities \(q_{jr}=P(R=r\mid A=j)\) are specified, sum to one over response categories \(r\) for each arm \(j\), and do not depend on earlier history once the assigned arm is given. Here \(A\) denotes the allocated arm and \(R\) the response. The replacement rule is also assumed to depend only on the current allocation and response. Every reachable updated state must have nonnegative counts and positive total, so that the next allocation is defined. If response probabilities instead depend on the past, the same calculation uses those conditional probabilities, but the urn composition alone may not determine the next-state distribution.
Deriving One-Step and Path Probabilities
The probability of a particular allocation-response pair is the allocation probability multiplied by the conditional response probability. Its destination is found by adding the corresponding net replacement vector. Several pairs can lead to the same destination, so a state-transition probability must include all of them.
The indicator is one when the indicated update gives \(y'\), and zero otherwise. This formula covers both distinct destinations and collisions, where different response events produce the same next state. Summing over all possible destination states counts each allocation-response pair once. Since \(\sum_j y_j/S(y)=1\) and \(\sum_r q_{jr}=1\), the transition probabilities sum to one, provided the rule gives valid states.
For a specified path of allocations \(a_1,\ldots,a_m\) and responses \(r_1,\ldots,r_m\), update the urn in order. Its joint probability is the product of the conditional allocation and response probabilities at each step. The urn used at step \(t\) is the state after the first \(t-1\) updates.
This is a probability for one specified sequence of allocations and responses. The probability of ending in a particular state can be larger, because it may be reached by multiple paths. A short derivation explains the product: at each step, conditional on the history so far, the probability of the specified allocation is the current color proportion; conditional on that allocation, the probability of the specified response is \(q_{a_t r_t}\). Multiplying these successive conditional probabilities gives the joint probability by the chain rule.
Worked Example: A Two-Step Path With Binary Responses
Suppose there are three arms, the initial composition is \(Y_0=(2,1,1)\), and responses are success or failure. The hypothetical success probabilities for arms 1, 2, and 3 are \(0.70\), \(0.50\), and \(0.30\), respectively. After a success, add two balls of the allocated arm’s color. After a failure, add one ball of each of the other two colors and none of the allocated color.
At the first allocation, \(S(Y_0)=2+1+1=4\), so the probability of allocating arm 1 and observing success is \(\frac{2}{4}(0.70)=0.35\). The success update is \((+2,0,0)\), giving \(Y_1=(4,1,1)\), with total \(6\).
Now consider allocating arm 2 and observing failure. Given \(Y_1\), the allocation probability is \(1/6\), and the failure probability on arm 2 is \(1-0.50=0.50\). The failure update adds one to arms 1 and 3, giving \(Y_2=(5,1,2)\), with total \(8\). The probability of this specified two-step path is \(\left(\frac{2}{4}\cdot0.70\right)\left(\frac{1}{6}\cdot0.50\right)=0.35\cdot\frac{1}{12}=\frac{7}{240}\approx0.02917\).
From the resulting state, the next allocation probabilities are \(5/8\), \(1/8\), and \(2/8\). They are calculated from \(Y_2\), not from the starting composition. Both updates preserve nonnegative counts, and the totals increase by two at each step, as the specified rules require.
Multi-Category Responses and Shared Destinations
A common source of error is to calculate each allocation-response event correctly but then report those event probabilities as though they were probabilities of distinct states. The next example shows why destinations must be checked and, when necessary, combined.
Worked Example: Aggregating a Three-Arm Transition Table
Suppose the initial composition is \(Y_0=(1,2,1)\). The response categories are G, M, and N. Their hypothetical probabilities by allocated arm are: arm 1, \((0.50,0.30,0.20)\); arm 2, \((0.40,0.40,0.20)\); arm 3, \((0.30,0.50,0.20)\). After G, add two balls of the allocated color. After M, add one of the allocated color and one of the next color in the cycle \(1\to2\to3\to1\). After N, add one ball to each of the two colors not allocated.
The initial allocation probabilities are \((1/4,1/2,1/4)\). Multiplying each by its response probabilities gives the following event-level transitions. The probability in each row is the probability of that particular allocation and response from \(Y_0\).
| Allocated arm | Response | Next state | Event probability |
|---|---|---|---|
| 1 | G | (3, 2, 1) | 0.125 |
| 1 | M | (2, 3, 1) | 0.075 |
| 1 | N | (1, 3, 2) | 0.050 |
| 2 | G | (1, 4, 1) | 0.200 |
| 2 | M | (1, 3, 2) | 0.200 |
| 2 | N | (2, 2, 2) | 0.100 |
| 3 | G | (1, 2, 3) | 0.075 |
| 3 | M | (2, 2, 2) | 0.125 |
| 3 | N | (2, 3, 1) | 0.050 |
For example, the arm 2, M row has probability \((2/4)(0.40)=0.20\). Its update adds one to arm 2 and one to arm 3, so \((1,2,1)\) becomes \((1,3,2)\). Arm 1, N also reaches \((1,3,2)\), with probability \((1/4)(0.20)=0.05\). Therefore the probability of that next state is \(0.20+0.05=0.25\), not either event probability alone.
After combining repeated destinations, the state probabilities are \(0.125\) for \((3,2,1)\), \(0.125\) for \((2,3,1)\), \(0.250\) for \((1,3,2)\), \(0.200\) for \((1,4,1)\), \(0.225\) for \((2,2,2)\), and \(0.075\) for \((1,2,3)\). Their sum is \(1.000\), a useful check. The event rows also sum to one before aggregation.
Checking Updates That Remove Balls
When a rule removes balls, arithmetic validity is not automatic. Each coordinate must remain nonnegative after every possible reachable update, and the total must remain positive. A negative count cannot be repaired by normalizing the remaining counts into probabilities: it means the specified urn process is not defined for that state and rule.
Worked Example: Verifying a Removal Rule at the Boundary
Start with \(Y_0=(2,2,1)\) and three arms. Suppose success, with probability \(0.60\) on each arm, adds one ball of the allocated color. On failure, with probability \(0.40\), remove one ball of the allocated color and add one ball of each other color. Consider the hypothetical path: allocate arm 3 and observe failure, then allocate arm 1 and observe success.
Initially, arm 3 is selected with probability \(1/5\). Its failure update is \((+1,+1,-1)\), so \(Y_1=(3,3,0)\). The first allocation-response probability is \((1/5)(0.40)=0.08\). The total changes from \(5\) to \(6\), since the net change is \(+1+1-1=+1\).
At the next step, arm 1 has probability \(3/6=0.50\). A success has probability \(0.60\), and its update gives \(Y_2=(4,3,0)\). The conditional probability of this second allocation-response pair is \((3/6)(0.60)=0.30\). The joint probability of the specified path is \(0.08(0.30)=0.024\).
Both states are valid: all counts are nonnegative and both totals are positive. Arm 3 has no balls after the first update, so it cannot be selected next unless a later rule adds balls of its color. This is a valid boundary state, not a reason to assign arm 3 a negative or artificially small allocation probability.
A Practical Workflow and Diagnostic Checks
For a longer problem, write each update as a vector before doing path arithmetic. A compact, repeatable workflow is:
Write every arm count in a fixed order and compute their sum. The color proportions are the allocation probabilities for the next draw.
Use the response probability conditional on the arm actually allocated. Confirm that the response probabilities for that arm sum to one.
Add the response-specific net-change vector coordinate by coordinate. Recompute the total from the new counts rather than assuming it is unchanged.
Verify nonnegative counts, positive total, and a valid next allocation distribution. For a transition table, combine events that share a destination.
Useful diagnostics follow directly from the calculation. At each state, allocation probabilities must sum to one. For each arm, its response probabilities must sum to one. Event probabilities over all allocation-response pairs must also sum to one, and aggregated state probabilities must do the same. Finally, the difference between consecutive totals must equal the sum of the coordinates in the applied update vector. These checks can reveal a misplaced increment even when every individual count looks plausible.
Hand tracing is best when the requested result is one short, specified path. A transition table is preferable when all one-step destinations are needed, especially if different events merge into the same state. Finite-state enumeration extends that table idea across multiple steps by collecting probability mass at each reachable state. Simulation can approximate path or state probabilities when enumeration becomes too large, but an approximate frequency is not a substitute for an exact calculation when only a few paths are involved.
The calculation depends on the stated response probabilities and replacement rules. If either is misspecified, correct arithmetic still describes the wrong model. Also, a finite list of paths is not generally a complete distribution: omitted paths carry probability too. This workshop concerns the urn’s allocation and state transitions; the computed path probabilities alone do not establish clinical benefit or the statistical properties of a treatment-effect analysis.
Common Mistakes
- Using the starting proportions at every step. That ignores adaptation. Recalculate the proportions from the current state after each update.
- Applying an update to the wrong arm. Write the full vector change and add it coordinate by coordinate to the state.
- Multiplying response probabilities without allocation probabilities. A specified event requires both: the probability of drawing its arm and the response probability conditional on that arm.
- Counting repeated destinations separately in a state distribution. They are separate events but their probabilities must be added when the target is a shared next state.
- Allowing a negative count because the other counts are positive. Every coordinate must be nonnegative after the update; a negative count invalidates that transition.
- Calling one path probability the probability of its final state. The final state may be reached through other paths, whose probabilities must also be included.
Check Your Understanding
Work each item from the state and rule given. Solutions are included after the questions so that each calculation can be checked.
- From state \((3,1,2)\), arm 2 is allocated. Success has probability \(0.40\) and adds two balls of the allocated color; failure has probability \(0.60\) and adds one ball to each other color. Find the two allocation-response probabilities and next states.
- In the three-category example above, what is the probability of reaching state \((2,2,2)\) in one step from \((1,2,1)\)?
- With three arms, an initial state \((1,1,0)\), and a failure update that removes one ball from the allocated arm and adds one to each other arm, what state follows a failure on arm 1? Is it valid?
- Why must transition probabilities be added when distinct allocation-response events lead to the same next state?
Solutions. (1) The total is \(6\), so arm 2 is allocated with probability \(1/6\). Success has event probability \((1/6)(0.40)=1/15\approx0.06667\) and gives \((3,3,2)\). Failure has event probability \((1/6)(0.60)=0.10\) and gives \((4,1,3)\). (2) The two events reaching \((2,2,2)\) are arm 2 with N, probability \(0.10\), and arm 3 with M, probability \(0.125\). The total is \(0.225\). (3) The failure update is \((-1,+1,+1)\), giving \((0,2,1)\). It is valid because the counts are nonnegative and the total is \(3>0\). (4) The events are mutually exclusive ways to reach the same destination, so the probability of their union is the sum of their probabilities.