State-Dependent Replacement Rules

Why Let the Replacement Rule Depend on the State?

A replacement rule determines how an urn changes after a treatment is assigned and the participant's response is observed. In a fixed outcome-specific rule, the response selects a replacement vector: for example, every success produces the same vector, whichever treatment was drawn and whatever the urn currently contains. A state-dependent rule can use more information. It may respond differently depending on which treatment was drawn and on the current treatment counts, as well as on the response.

That flexibility matters when a design is intended to react to the urn's current balance. For instance, a rule can give additional reinforcement to a treatment when it is underrepresented, while applying a different update when it is already more prevalent. The next allocation probabilities then depend on the history summarized by the current urn state. The aim here is to calculate that dependence carefully, not to claim that any particular rule is automatically desirable.

Definition and Assumptions

Consider two treatments, \(A\) and \(B\), and binary responses coded as success \(1\) and failure \(0\). Write the current urn state as \(n=(n_A,n_B)\), where \(n_A\) and \(n_B\) are the numbers of balls representing the two treatments. A ball is drawn at random; its treatment is assigned, and the ball is returned before the rule's additional balls are added.

Definition: A state-dependent replacement rule specifies an addition vector \(R(n,i,y)=(R_A(n,i,y),R_B(n,i,y))\) for each current state \(n\), drawn treatment \(i\in\{A,B\}\), and observed response \(y\in\{0,1\}\). The next state is \(n'=n+R(n,i,y)\). The rule is state-dependent if its addition vector can vary with \(n\); it is treatment-dependent if it can vary with \(i\); and it is response-dependent if it can vary with \(y\).

For the calculations below, counts are nonnegative integers and the total number of balls \(S(n)=n_A+n_B\) is positive. Additions are nonnegative integer counts, so this tutorial considers additions only. Given state \(n\), the probability of assigning treatment \(i\) is \(n_i/S(n)\). For numerical examples involving responses, assume a participant assigned to treatment \(i\) has success probability \(p_i\), so \(P(Y=1\mid i,n)=p_i\) and \(P(Y=0\mid i,n)=1-p_i\). These probabilities do not depend on the urn state in the examples. The random treatment draw and the response are generated in that order.

The rule must be specified for every state and treatment-response combination that can occur. If some treatment has zero balls, it cannot be drawn in that state; a rule still needs to keep the total positive. Also, a replacement vector describes additional balls: the drawn ball is already included in \(n\) and is returned. Counting that returned ball a second time would give the wrong update.

A Concrete State-Dependent Rule

Use the following rule to make the dependence explicit. After success on the drawn treatment \(i\), add one ball to \(i\), and add one more to \(i\) if that treatment had fewer balls than the other treatment before the draw. After failure on \(i\), add one ball to the other treatment, and add one more to the other treatment if \(i\) had more balls than the other treatment before the draw. In ties, neither extra ball is added. The comparison always uses the state before the update.

For example, when \(n=(3,5)\), success on \(A\) adds two balls to \(A\), since \(A\) is underrepresented; failure on \(A\) adds one ball to \(B\), since \(A\) is not overrepresented. When \(n=(6,2)\), failure on \(A\) adds two balls to \(B\), because \(A\) is overrepresented. Thus even with the same drawn treatment and response, the addition vector can change with the state.

Worked Example: Calculate Updates From the Current State

Suppose the urn contains \(n=(3,5)\), with three \(A\)-balls and five \(B\)-balls. Find the allocation probabilities and the next state if \(A\) is drawn and the response is a success, and if \(B\) is drawn and the response is a failure.

The total is \(S(n)=3+5=8\). Therefore, \(P(A\mid n)=3/8=0.3750\) and \(P(B\mid n)=5/8=0.6250\).

For a draw of \(A\), \(n_A=3<n_B=5\), so success adds two balls to \(A\): \(R((3,5),A,1)=(2,0)\). The next state is \((3,5)+(2,0)=(5,5)\).

For a draw of \(B\) followed by failure, \(n_B=5>n_A=3\), so failure adds two balls to the other treatment, \(A\): \(R((3,5),B,0)=(2,0)\). The next state is also \((5,5)\). These are different draw-response events that happen to lead to the same state.

One-Step Transition Probabilities

The rule can be translated into a transition probability: the chance of moving from the current state \(n\) to a particular state \(m\) in one participant's assignment. Let \(g_i(y\mid n)\) denote the conditional probability of response \(y\) after treatment \(i\) is assigned at state \(n\). Then the transition probability is

P(N'=m\mid N=n) = \sum_{i\in\{A,B\}}\sum_{y\in\{0,1\}} \frac{n_i}{S(n)}\,g_i(y\mid n)\, \mathbf{1}\{m=n+R(n,i,y)\}.

Here \(N\) is the random urn state and \(\mathbf{1}\{\cdot\}\) equals 1 when its condition is true and 0 otherwise. Each term is the probability of drawing treatment \(i\), observing response \(y\), and making the update prescribed for that event. The indicator retains the term only if that event produces \(m\). If multiple events produce the same next state, their probabilities are added.

For binary responses with state-independent success probabilities \(p_i\), the response probabilities are \(g_i(1\mid n)=p_i\) and \(g_i(0\mid n)=1-p_i\). The transition probabilities sum to 1: for each treatment, the two response probabilities sum to 1, and the treatment draw probabilities sum to 1. In symbols,

\sum_m P(N'=m\mid N=n) = \sum_{i\in\{A,B\}}\frac{n_i}{S(n)} \sum_{y\in\{0,1\}}g_i(y\mid n) = \sum_{i\in\{A,B\}}\frac{n_i}{S(n)} =1.

Worked Example: Combine Events That Reach the Same State

At \(n=(3,2)\), suppose \(p_A=0.70\) and \(p_B=0.40\), and use the state-dependent rule above. Calculate the probabilities of the possible next states.

The treatment probabilities are \(P(A\mid n)=3/5=0.60\) and \(P(B\mid n)=2/5=0.40\). Since \(n_A>n_B\), success on \(A\) adds one ball to \(A\), reaching \((4,2)\). Its event probability is \(0.60(0.70)=0.4200\). Failure on \(A\) adds two balls to \(B\), reaching \((3,4)\), with probability \(0.60(0.30)=0.1800\).

Since \(n_B<n_A\), success on \(B\) adds two balls to \(B\), reaching \((3,4)\), with probability \(0.40(0.40)=0.1600\). Failure on \(B\) adds one ball to \(A\), reaching \((4,2)\), with probability \(0.40(0.60)=0.2400\).

The two events leading to \((4,2)\) have combined probability \(0.4200+0.2400=0.6600\). The two leading to \((3,4)\) have combined probability \(0.1800+0.1600=0.3400\). The check \(0.6600+0.3400=1.000\) confirms that all one-step outcomes have been included.

Deriving a Short Path Probability

For a sequence of assignments and responses, multiply the conditional probability of each event given the state reached so far. This follows from the multiplication rule for conditional probabilities. The state after each event must be updated before calculating the next treatment probability; it is not generally correct to reuse the starting allocation probabilities.

Worked Example: A Two-Participant Path

Start at \(n=(2,1)\), use the stated replacement rule, and suppose \(p_A=0.50\) and \(p_B=0.25\). Find the probability of the particular path: assign \(A\), observe success; then assign \(A\), observe failure.

Initially, \(P(A\mid (2,1))=2/3\). Since \(A\) is overrepresented, success on \(A\) adds one ball to \(A\), giving state \((3,1)\). The probability of the first assignment-response event is \((2/3)(0.50)=1/3\).

At \((3,1)\), \(P(A\mid (3,1))=3/4\). Failure on \(A\), which is overrepresented, adds two balls to \(B\). The next state would be \((3,3)\), although only the specified two-event path probability is needed. The conditional probability of the second event is \((3/4)(1-0.50)=3/8\).

Multiplying the conditional probabilities gives \((1/3)(3/8)=1/8=0.1250\). Thus this particular two-participant assignment-and-response path has probability 0.1250 under the stated urn rule and response model.

How to Check a State-Dependent Calculation

Because an update depends on the current state, small bookkeeping errors can change both the update and all later allocation probabilities. A reliable calculation records the state immediately before each draw, identifies the treatment and response, applies the rule to that pre-update state, and then records the next state. The rule's comparison is not made using a state that already includes the new balls.

Calculate the draw probabilities.
At state \(n\), use \(n_i/S(n)\) for treatment \(i\), and check that these probabilities sum to 1.

Identify the response event.
Use the response probability for the treatment actually drawn. For binary responses, success and failure probabilities must sum to 1.

Apply the rule to the pre-update state.
Evaluate \(R(n,i,y)\) using the current counts, the drawn treatment, and the observed response.

Form and check the next state.
Set \(n'=n+R(n,i,y)\), verify the counts and total, and then use \(n'\) for the next participant.

Useful diagnostics include checking that the resulting state is a pair of nonnegative integer counts, that the update follows the stated rule, and that probabilities of distinct next states sum to 1. If a transition table has fewer total probability than 1, a draw-response event may have been omitted. If it has more than 1, an event may have been counted twice. If two different events reach the same state, combine their probabilities rather than treating the state as two different outcomes.

Comparison and Limitations

Rule type	What selects the addition vector?	Key calculation feature
Fixed outcome-specific rule	Observed response only	Each response has the same addition vector across states and drawn treatments.
Fixed treatment- and response-specific rule	Drawn treatment and response	The addition can differ by treatment and response, but not by current counts.
State-dependent rule	Current state, drawn treatment, and response, as specified	The same treatment-response event can produce different additions at different states.

A fixed rule is simpler to specify and may make state transitions easier to calculate. A state-dependent rule can encode a deliberate response to imbalance, but its behavior must be checked across the states the design can reach. For example, a local rule that favors an underrepresented treatment in one circumstance does not by itself establish that the design will remain balanced over a full trial.

These calculations describe the assignment mechanism conditional on the stated urn and response model. They do not establish that a rule improves precision, ensures a desired long-run allocation, or is appropriate for a particular trial. Such conclusions require further analysis and design goals. The rule also needs a clear definition for ties and boundary states, and its additions must keep the urn usable. This tutorial restricts attention to nonnegative additions; updates that remove balls require additional state-validity checks.

Common Mistake

Pitfall: Treating a state-dependent rule as if it were a fixed outcome-specific matrix. For example, one might say, “success on \(A\) always adds one ball to \(A\),” even though the stated rule adds an extra ball when \(A\) is underrepresented. The correction is to evaluate the rule at the current state every time: first determine whether \(n_A<n_B\), then determine the addition vector. Also distinguish the event probability from the next-state probability: when several events reach the same state, add their event probabilities.

Check Your Understanding

Answer each question, then compare with the solutions below.

Under the stated rule, at \(n=(4,4)\), what is the next state after a success on \(B\)?
At \(n=(5,2)\), what addition vector follows a failure on \(B\)?
At \(n=(2,3)\), suppose \(P(A\text{ succeeds})=0.60\) and \(P(B\text{ succeeds})=0.40\). What is the probability of a success on \(A\) followed by a move to the resulting next state?
Why must probabilities of different draw-response events be combined when they produce the same next state?

Solutions. (1) The counts are tied, so no extra ball is added. Success on \(B\) adds one ball to \(B\), giving \((4,5)\). (2) Treatment \(B\) is underrepresented, so failure on \(B\) adds one ball to the other treatment, \(A\), with no extra ball: \(R((5,2),B,0)=(1,0)\). (3) The initial probability of drawing \(A\) is \(2/5\). Success on \(A\) has probability \(0.60\), so the event probability is \((2/5)(0.60)=0.2400\). Since \(A\) is underrepresented, the update adds two \(A\)-balls and the next state is \((4,3)\). (4) A next state is an outcome of the state transition, and mutually exclusive events that reach it all contribute to its probability. Add their event probabilities to obtain the total probability of that state.