Convergence of Doubly Adaptive Biased Coin Designs

Why convergence is a separate question

A response-adaptive design changes its assignment probabilities as trial data accumulate. For a doubly adaptive biased coin design (DBCD), the probability of assigning the next participant to an arm depends both on an estimated target allocation and on the allocation already achieved. The convergence question is whether the realized fraction assigned to arm 1 approaches the target, not whether every finite-sample allocation exactly matches it.

The target may itself be estimated from responses, so the design uses a changing probability rather than a fixed one. The key distinction is that consistent target estimation is enough for convergence under the conditions below. Biased-coin feedback supplies an additional restoring force when the current allocation is off target, but it is not required for this convergence result.

Two-arm DBCD and its assumptions

Definition: Let $A_{n+1}=1$ if participant $n+1$ is assigned to arm 1, and $A_{n+1}=0$ otherwise. Let $X_n=\sum_{k=1}^{n}A_k$ be the number assigned to arm 1 among the first $n$ participants, and let $x_n=X_n/n$ for $n\geq1$. Let $\hat\rho_n$ be the estimated target fraction for arm 1, available before the next assignment. For a fixed $\gamma\geq0$, the linear two-arm DBCD assigns participant $n+1$ to arm 1 with conditional probability $$ q_{n+1}=\hat\rho_n+\gamma(\hat\rho_n-x_n). $$

The probability is conditional on the information available before assignment $n+1$. This includes the observed data and the design history up to participant $n$. In particular, the assignment indicator satisfies $E(A_{n+1}\mid\mathcal F_n)=q_{n+1}$, where $\mathcal F_n$ denotes that history.

Here is a sufficient set of conditions for the convergence result:

The target is fixed and interior: $\rho\in(0,1)$.
The estimated targets are consistent almost surely: $\hat\rho_n\to\rho$ almost surely.
For some $\delta>0$, $\hat\rho_n\in[\delta,1-\delta]$, and $\gamma\leq\delta/(1-\delta)$. This is a convenient sufficient condition ensuring $q_{n+1}$ is a valid probability for every $x_n\in[0,1]$.
Assignments follow the stated conditional probabilities, so $A_{n+1}-q_{n+1}$ is a bounded martingale difference.

The target estimator may be based on adaptive response data; no independence between the estimate and the earlier assignments is assumed. Its almost-sure consistency is an explicit premise. In applications, this premise must be justified using the response model and the allocation conditions that make the relevant arm-specific estimates consistent. Truncating estimates to a compact interval inside $(0,1)$ is one way to enforce the stated probability-bound condition without changing their limit when $\rho$ is interior.

Worked Example: Checking That the Assignment Probability Is Valid

Suppose the estimated targets are constrained to $[0.2,0.8]$, and $\gamma=0.2$. The sufficient bound is $0.2/(1-0.2)=0.25$, so the chosen $\gamma$ satisfies it. For an estimated target $\hat\rho_n=0.7$ and current allocation $x_n=0.4$, $$ q_{n+1}=0.7+0.2(0.7-0.4)=0.7+0.06=0.76. $$

This is a valid probability. The bound also protects the extreme allocation fractions: for any $\hat\rho_n\in[0.2,0.8]$ and $x_n\in[0,1]$, the smallest possible value is at $x_n=1$, and is at least $0.2-0.2(0.8)=0.04$. The largest is at $x_n=0$, and is at most $0.8+0.2(0.8)=0.96$. Thus the formula stays between 0 and 1, including when the current allocation is far from the target.

The convergence result and its justification

Theorem: Under the assumptions above, the allocation proportion converges almost surely to the target: $$ x_n\longrightarrow\rho\quad\text{almost surely}. $$ The result includes $\gamma=0$. Thus an additional biased-coin restoring term is not necessary for this convergence conclusion.

To see the mechanism, write the assignment as its conditional mean plus a martingale difference: $$ A_{n+1}=q_{n+1}+\xi_{n+1},\qquad \xi_{n+1}=A_{n+1}-q_{n+1}. $$ Then $E(\xi_{n+1}\mid\mathcal F_n)=0$ and $|\xi_{n+1}|\leq1$. Since $x_{n+1}=(nx_n+A_{n+1})/(n+1)$, subtracting $\rho$ gives the exact recursion $$ x_{n+1}-\rho = \left(1-\frac{1+\gamma}{n+1}\right)(x_n-\rho) +\frac{1+\gamma}{n+1}(\hat\rho_n-\rho) +\frac{\xi_{n+1}}{n+1}. $$

This recursion is a stochastic approximation with step size $1/(n+1)$. Its deterministic drift toward the target is $-(1+\gamma)(x_n-\rho)$, which points toward $\rho$ whenever $x_n\ne\rho$. The estimated-target error tends to zero by assumption, while the assignment noise has conditional mean zero and is bounded.

For completeness, the standard scalar recursion argument can be made explicit. Put $e_n=x_n-\rho$, $c=1+\gamma>0$, and $\eta_n=\hat\rho_n-\rho$. For all sufficiently large $n$, $a_n=1-c/(n+1)$ lies in $[0,1]$, and $$ e_{n+1}=a_ne_n+\frac{c\eta_n+\xi_{n+1}}{n+1}. $$ Iterating from any such index $m$ yields $$ e_n=\left(\prod_{j=m}^{n-1}a_j\right)e_m+ \sum_{k=m}^{n-1}\left(\prod_{j=k+1}^{n-1}a_j\right) \frac{c\eta_k+\xi_{k+1}}{k+1}. $$ The first product tends to zero because $\sum_j c/(j+1)=\infty$. For the target-error sum, the weights are nonnegative and their total is bounded: the identity $$ \sum_{k=m}^{n-1}\left(\prod_{j=k+1}^{n-1}a_j\right)\frac{c}{k+1} =1-\prod_{j=m}^{n-1}a_j\leq1 $$ shows that its absolute value is at most $\sup_{k\geq m}|\eta_k|$, which tends to zero as $m\to\infty$.

For the noise term, bounded martingale differences imply that $\sum_{k=m}^{\infty}\xi_{k+1}/(k+1)$ converges almost surely, since the sum of its conditional variances is bounded by $\sum_{k=m}^{\infty}1/(k+1)^2<\infty$. Summation by parts, together with the nonnegative, diminishing product weights in the displayed representation, implies that the weighted noise contribution tends to zero. Consequently $e_n\to0$ almost surely, proving the theorem. This argument needs no independent-assignment assumption: the conditional mean-zero property is what controls the allocation noise.

Worked Example: Estimated-Target-Only Allocation

Set $\gamma=0$, so $q_{n+1}=\hat\rho_n$. Suppose, hypothetically, that a target estimator converges almost surely to $\rho=0.6$, and that six successive pre-assignment estimates are $0.60, 0.58, 0.62, 0.61, 0.60, 0.59$. Their average is $$ \frac{0.60+0.58+0.62+0.61+0.60+0.59}{6} =\frac{3.60}{6}=0.60. $$

If the six observed assignments to arm 1 are $1,0,1,1,0,1$, then $X_6=4$, $x_6=4/6\approx0.667$. The realized fraction need not equal the average assignment probability in a short run. In general, $$ x_n=\frac{1}{n}\sum_{k=1}^{n}q_k+ \frac{1}{n}\sum_{k=1}^{n}(A_k-q_k). $$ When $\gamma=0$, $q_k=\hat\rho_{k-1}$ (apart from any initial assignment convention), and almost-sure target consistency makes the first average converge to $\rho$ by Cesàro convergence. The second average converges to zero almost surely by the martingale strong law for bounded differences. Therefore $x_n\to\rho$ almost surely even with no biased-coin correction. The six observations illustrate the decomposition, not a finite-sample guarantee.

Worked Example: What the Restoring Term Adds

Suppose $n=9$, $x_n=0.4$, $\hat\rho_n=0.6$, and $\gamma=0.25$. Then $$ q_{n+1}=0.6+0.25(0.6-0.4)=0.65. $$ The conditional expected next allocation fraction is $$ E(x_{n+1}\mid\mathcal F_n) =0.4+\frac{0.65-0.4}{10}=0.425. $$

If the next assignment is to arm 1, then $x_{n+1}=(9(0.4)+1)/10=0.46$. The martingale difference for that assignment is $\xi_{n+1}=1-0.65=0.35$, and the recursion gives $0.4+(0.25+0.35)/10=0.46$, as it should. The positive drift toward the target is present in the conditional expectation; the realized allocation can move more or less because of assignment noise.

What is essential, and what is not

The result separates two roles. Consistency makes the limiting target correct: if $\hat\rho_n\to\rho$, then the target used by the design settles at $\rho$. The allocation process averages its assignments over time, and the martingale difference average vanishes. These facts already give convergence when $\gamma=0$. For $\gamma>0$, the design also reacts to allocation imbalance: if $x_n<\hat\rho_n$, the next-arm-1 probability exceeds $\hat\rho_n$; if $x_n>\hat\rho_n$, it falls below $\hat\rho_n$. This feedback strengthens the restoring drift but is not a necessary ingredient in the stated theorem.

Design feature	Role in this convergence result	What it does not establish
Consistent estimated target	Ensures the probabilities are ultimately centered on $\rho$	Does not by itself prove that the estimate is consistent in a given response model
$\gamma=0$	Still gives convergence through averaging and vanishing martingale noise	Does not actively correct an allocation imbalance in each assignment probability
$\gamma>0$	Adds a restoring response to the current allocation error	Is not required for the convergence theorem, and does not alone guarantee a valid probability if chosen too large

Convergence is also distinct from a rate or distributional approximation for $x_n-\rho$. The theorem only states that this difference tends to zero almost surely. It does not specify its typical size at a finite $n$, its limiting distribution after rescaling, or the covariance between allocation and response estimates.

Diagnostics and failure modes

In a real analysis or simulation, the theorem’s assumptions should be checked rather than inferred from a plot that appears to stabilize. A practical diagnostic sequence is:

Check the target.
Confirm that the intended limiting fraction is fixed and interior, and examine whether the response-based estimator is consistent under the assumed response model and adaptive sampling scheme.

Check the probabilities.
Verify that the update rule stays in $[0,1]$ across the possible allocation fractions and estimated targets. A negative or greater-than-one value means the specified rule is not a valid assignment mechanism.

Separate target movement from random variation.
Track $\hat\rho_n$, $x_n$, and $q_{n+1}$ across runs. Persistent movement of $\hat\rho_n$ away from the claimed target is evidence against the consistency premise; temporary differences between $x_n$ and $\rho$ alone are not a contradiction.

A particularly important failure mode is an inconsistent target estimator. If $\hat\rho_n\to r\ne\rho$, the design is generally driven toward $r$, not the claimed $\rho$. For example, with $\gamma=0$, Cesàro averaging gives $x_n\to r$ under the same bounded martingale argument. The biased-coin correction does not repair a systematically wrong target: its drift is centered on the estimated target.

Worked Example: A Consistent Design Can Converge to the Wrong Claimed Target

Suppose a hypothetical design is described as targeting $\rho=0.6$, but its estimated target instead converges almost surely to $r=0.7$. With $\gamma=0$, the conditional probabilities converge to $0.7$. Their averages therefore converge to $0.7$, while the average martingale difference converges to zero, so $x_n\to0.7$ almost surely. The conclusion is not convergence to the claimed $0.6$.

This example does not violate the theorem: its consistency assumption is consistency for the claimed target, $\hat\rho_n\to0.6$, and that assumption fails here. If the target is at a boundary, such as $\rho=0$, the interior and probability-bound conditions also fail; boundary allocation requires a separate analysis rather than a direct appeal to this theorem.

Common mistake

Common mistake: “The allocation fraction can converge only if $\gamma>0$, because only biased-coin feedback pulls it back toward the target.” This is incorrect. When $\gamma=0$, the assignments have probabilities $\hat\rho_n$; if those probabilities converge to $\rho$, their average converges to $\rho$, and the bounded martingale difference between assignments and their probabilities has average tending to zero almost surely. Thus the allocation fraction still converges to $\rho$. A positive $\gamma$ adds a restoring mechanism; it is not necessary for this convergence result.

This conclusion should not be extended beyond its assumptions. In particular, it does not say that an arbitrary adaptive allocation rule converges, that an inconsistent estimated target will be corrected, or that convergence alone provides a useful finite-sample allocation balance. Those are different claims and require their own conditions.

Check Your Understanding

Answer each question using the definitions and conditions above. Brief solutions follow the questions.

For $\gamma=0$, state the two terms in the allocation-fraction decomposition that establish convergence.
With $\hat\rho_n=0.55$, $x_n=0.45$, and $\gamma=0.3$, calculate $q_{n+1}$. If $n=19$, calculate the conditional expected value of $x_{n+1}$.
If $\hat\rho_n\to0.72$ almost surely while the claimed target is $0.65$, what limit should be expected for the allocation fraction under the estimated-target-only design?
Why is almost-sure consistency of the estimated target a stronger premise than observing that estimates are close to the target in one finite simulation?

Solutions. (1) The first term is $n^{-1}\sum_{k=1}^n q_k$, which converges to $\rho$ when $q_k=\hat\rho_{k-1}\to\rho$ by Cesàro convergence. The second is $n^{-1}\sum_{k=1}^n(A_k-q_k)$, which converges almost surely to zero by the martingale strong law for bounded differences. (2) $q_{n+1}=0.55+0.3(0.55-0.45)=0.58$. Therefore $E(x_{n+1}\mid\mathcal F_n)=0.45+(0.58-0.45)/20=0.4565$. (3) The expected limit is $0.72$, not $0.65$, because the assignment probabilities settle at the limit of the estimated target. (4) Almost-sure consistency is a long-run probabilistic property of the estimator under the model and adaptive sampling. A finite simulation can look close by chance and does not establish that the estimator converges to the correct target.