Why Enumerate Urn States?
An urn rule may be simple to state but produce several possible compositions after only a few draws. The number of possible sequences of treatment assignments can grow quickly, and different sequences can lead to the same composition. Finite-state enumeration keeps these two facts explicit: it lists the compositions reachable within a fixed number of draws and gives the transition probabilities between them.
The goal here is to enumerate states and transitions exactly, not to approximate a long-run behavior. Exact enumeration is useful for checking a rule, tracing short sequences, and confirming that probability calculations are internally consistent. A composition is the vector of counts currently in the urn; a path is an ordered sequence of transitions through such compositions.
States and One-Step Transitions
Suppose there are \(K\) treatment types. Write the urn composition after \(t\) draws as \(\mathbf{N}_t=(N_{t,1},\ldots,N_{t,K})\), where \(N_{t,i}\) is the number of balls of type \(i\). The total number of balls is \(N_t=\sum_{i=1}^K N_{t,i}\). Assume the initial composition is specified, every component is a nonnegative integer, and the total is positive whenever a draw is made.
In the standard proportional-draw rule, a ball is drawn at random and its type determines the treatment allocated to the next participant. Given a state \(\mathbf{n}\), the probability of allocating treatment \(i\) is \(n_i/N\), where \(N=\sum_i n_i\). After observing the response, the urn is updated according to the specified rule.
To calculate transitions when responses affect the update, let \(q_{iy}\) be the probability of response \(y\) for a participant assigned to treatment \(i\), and let \(\boldsymbol{\Delta}_{i,y}(\mathbf{n})\) be the change in composition after that assignment and response. The update may depend on the current state, but it must be specified before enumerating transitions. Under the proportional-draw rule and these response probabilities, the one-step transition probability is
Here \(\mathbb{1}\{\cdot\}\) is 1 when the stated equality holds and 0 otherwise. The sums matter: more than one assignment-response combination can produce the same next state. If a particular combination has probability zero, it contributes no reachable transition.
How to Enumerate a Finite Horizon
Start with the initial state as the only reachable state at time 0. For each state at time \(t\), list every assignment and response combination with positive probability, apply the update rule, and record the resulting state at time \(t+1\). If multiple combinations lead to the same next composition, list that composition once and add their transition probabilities. Repeat until the chosen number of draws has been reached.
Record the initial composition, allocation rule, response probabilities if relevant, update rule, and fixed horizon. Check that updates never create negative counts.
From each state at the current time, calculate the probability and resulting composition for every possible assignment-response combination.
When different combinations produce the same next composition, add their probabilities for that transition.
For each state, verify that outgoing transition probabilities sum to 1. Use the distinct successor states as the starting set for the next draw.
The justification for adding probabilities is elementary but important. For a fixed starting state, the possible assignment-response combinations on the next draw are mutually exclusive. The event of reaching a particular next state is the union of all such combinations that produce it. Therefore, the probability of that next state is the sum of the probabilities of those combinations. This is why duplicate destinations must be merged by addition, rather than treated as separate states or counted only once without their probabilities.
Worked Example: Two Draws With Same-Type Reinforcement
Consider two treatments, A and B, with initial composition \((2,1)\). Each draw allocates the treatment matching the ball drawn, and then one ball of that same type is added. Enumerate the reachable compositions through two draws and the probabilities of the ordered paths.
The model has positive total size at every draw, and the update adds one ball, so all resulting counts are nonnegative. At the initial state, \(N=3\), giving probabilities \(2/3\) for A and \(1/3\) for B. After the first draw, the two possible states and their transitions are
From \((3,1)\), whose total is 4, the next draw is A with probability \(3/4\) and B with probability \(1/4\). From \((2,2)\), each treatment is drawn with probability \(1/2\). Thus the four ordered paths are
The two different paths AB and BA reach the same composition \((3,2)\). Their combined probability is \(1/6+1/6=1/3\). The distinct states reachable after two draws are therefore \((4,1)\), \((3,2)\), and \((2,3)\), with path probabilities \(1/2\), \(1/3\), and \(1/6\), respectively. They sum to 1, as required.
Outcome-Dependent Transitions
When responses affect the replacement rule, enumerate the assignment and response separately before combining outcomes that produce the same state. The response probability is conditional on the assigned treatment; it is not generally the same for both treatments. The example below assumes that outcomes on a draw follow the stated probabilities, conditional on the assigned treatment and current state, and that the update is deterministic once treatment and response are known.
Worked Example: Combining Response-Specific Routes
There are two treatments, A and B, and the initial composition is \((1,1)\). A is drawn with probability \(1/2\), as is B. A participant assigned A responds successfully with probability \(0.8\); a participant assigned B responds successfully with probability \(0.4\). On success, add one ball of the assigned treatment. On failure, add one ball of the other treatment. Find the one-step transitions.
These probabilities specify all possible responses, with failure probabilities \(1-0.8=0.2\) for A and \(1-0.4=0.6\) for B. Each update adds exactly one ball, so it preserves nonnegative counts and increases the total from 2 to 3. The four routes from \((1,1)\) are:
- Assign A and observe success: probability \((1/2)(0.8)=0.4\), producing \((2,1)\).
- Assign A and observe failure: probability \((1/2)(0.2)=0.1\), producing \((1,2)\).
- Assign B and observe success: probability \((1/2)(0.4)=0.2\), producing \((1,2)\).
- Assign B and observe failure: probability \((1/2)(0.6)=0.3\), producing \((2,1)\).
There are only two distinct successor compositions. Adding the probabilities of the routes with the same destination gives
The outgoing probabilities sum to \(0.7+0.3=1\). In particular, the transition to \((2,1)\) includes both success on A and failure on B. It would be incorrect to calculate that transition from the A-success route alone.
Unequal Updates and Path Merging
Different treatments need not receive the same reinforcement. The state graph remains finite over a fixed horizon when each state has finitely many possible successors. Even if the total number of balls changes by different amounts on different transitions, each path can still be enumerated by applying the specified rule at each step.
Worked Example: Unequal Reinforcement Over Two Draws
Start with composition \((1,1)\). Whenever A is drawn, add one A ball; whenever B is drawn, add two B balls. There are no response-dependent updates. Enumerate the states after two draws and combine the paths that reach the same composition.
At the initial state, each treatment is drawn with probability \(1/2\). If the first draw is A, the state becomes \((2,1)\), where the next A probability is \(2/3\) and the next B probability is \(1/3\). If the first draw is B, the state becomes \((1,3)\), where the next A probability is \(1/4\) and the next B probability is \(3/4\). Hence
The AB and BA paths merge at \((2,3)\), so their combined path probability is
The other terminal compositions have probabilities \(1/3\) and \(3/8\). As a check, \(1/3+7/24+3/8=8/24+7/24+9/24=1\). The two paths merge even though their orders differ: after AB, the extra A ball was added first; after BA, the two extra B balls were added first.
Checks, Alternatives, and Limitations
Exact enumeration is dependable only when the model is specified precisely. Before trusting a state table, check that each state has a positive total before a draw, each allocation probability is calculated from the current state, every possible response is included, and the update rule is applied to the correct treatment-response pair. If updates can remove balls, verify that the resulting components remain nonnegative. If a rule permits a state with total zero, the experiment needs an explicit stopping or restart convention; proportional drawing is undefined there.
A useful numerical diagnostic is to check that, for every state being expanded, its outgoing transition probabilities sum to 1. Also check that every listed state is a nonnegative integer vector and that each claimed transition follows from the update rule. A path probability is a product of its successive conditional transition probabilities. Probabilities of distinct paths can be added when they are mutually exclusive and the question concerns their combined event, such as reaching the same state by the specified horizon.
A transition table is often clearer than a tree once multiple paths merge: it records each distinct state once and makes outgoing probability checks easy. A tree can be more transparent when the order of responses or assignments is itself important. Simulation is an alternative when the horizon or state space is too large for exhaustive enumeration, but simulation estimates probabilities with sampling error rather than giving exact values. Asymptotic approximations address different questions and are not needed for a small, fixed horizon.
Enumeration can become computationally expensive because the number of reachable states may grow with the horizon. Merging identical compositions controls avoidable duplication, but it does not make a large state space small. Moreover, the composition must contain enough information for the update and allocation rules to be determined. If future transitions depend on information omitted from the composition—for example, a separate history variable—then that information must be included in the state. Otherwise, the supposed transition probabilities from a state may not be well defined.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- At state \((3,2)\), a proportional draw selects A with probability \(3/5\). A adds \((1,0)\), while B adds \((0,1)\). What are the two successor states and transition probabilities?
- Two mutually exclusive routes to a state have probabilities \(0.12\) and \(0.18\). What is the probability of reaching that state by either route, and what condition allows you to add them?
- In an urn with initial state \((1,1)\), A is drawn with probability \(1/2\). A adds one A ball. What is the probability of the two-draw path AA?
- Why is a transition rule not fully specified if the same recorded composition can have different future updates depending on an unrecorded feature of the path?
Solutions. (1) Drawing A gives state \((4,2)\) with probability \(3/5\); drawing B gives \((3,3)\) with probability \(2/5\). (2) The combined probability is \(0.12+0.18=0.30\), provided the routes are mutually exclusive events. (3) After the first A, the state is \((2,1)\), so the next A probability is \(2/3\); thus \(P(AA)=(1/2)(2/3)=1/3\). (4) The recorded state would not determine the distribution of the next state. Include the relevant history feature in the state so the transition rule is well defined.