Lyapunov Criteria for Target Stability

Why Use a Lyapunov Function?

An allocation recursion may have a target \( \mathbf{x}^* \) without making it easy to solve its limiting differential equation explicitly. A Lyapunov function provides another route: it assigns a nonnegative measure of distance from the target and shows that this measure decreases along the dynamics. This is especially useful when allocation proportions are constrained, as on a simplex, or when the recursion includes random response noise.

The deterministic question and the stochastic question are distinct. A Lyapunov function can establish stability of the mean-field ordinary differential equation. To conclude that a noisy allocation recursion converges, one also needs conditions on its step sizes, noise, remainder, and state space. ODE limits for allocation proportions provide a complementary description of the limiting dynamics; a Lyapunov argument checks whether those dynamics move toward the target.

A standard way to establish the local result is to take a small sublevel set \( \{\mathbf{x}:V(\mathbf{x})\leq c\} \) contained in the neighborhood where the derivative is negative. The trajectory cannot leave that set because \(V\) decreases along it. Strict decrease away from the target then rules out convergence to any other point in the set. For a claim over a larger set, the same argument requires that \(V\) be positive definite there and that \( \dot V<0 \) at every other point, in addition to suitable existence and invariance conditions. Local strict decrease alone does not establish convergence from points outside that local neighborhood.

Scalar Allocation Dynamics

For a one-dimensional state \(x\), a natural candidate is the squared distance \(V(x)=(x-x^*)^2/2\). Its derivative is \( \dot V=(x-x^*)h(x) \). The sign is decisive: the drift must point toward the target strongly enough that this product is negative away from \(x^*\). A drift that is merely zero or nonpositive in some other region may allow additional equilibria or limit points.

Allocation Targets on the Simplex

For \(K\) treatment arms, allocation proportions lie in the simplex \( \Delta_K=\{\mathbf{p}:p_k\geq0,\ \sum_{k=1}^K p_k=1\} \). A target \( \mathbf{q}\in\Delta_K \) can be studied with the squared Euclidean distance \(V(\mathbf{p})=\|\mathbf{p}-\mathbf{q}\|^2/2\). The drift must preserve the simplex, meaning its coordinates sum to zero, and must point inward at its boundary. These are properties of the specified dynamics, not consequences of choosing \(V\).

From ODE Stability to Stochastic Drift

The stochastic approximation form makes the extra requirements explicit. Consider \( \mathbf{X}_{n+1}=\mathbf{X}_n+\gamma_{n+1}\{h(\mathbf{X}_n)+\mathbf{M}_{n+1}+\mathbf{r}_{n+1}\} \). Here \( \gamma_{n+1}>0 \) is the step size, \( \mathbf{M}_{n+1} \) is response or allocation noise, and \( \mathbf{r}_{n+1} \) is a remainder. Let \( \mathcal{F}_n \) contain the information available before step \(n+1\). The standard noise assumptions used below are \(E(\mathbf{M}_{n+1}\mid\mathcal{F}_n)=\mathbf{0}\) and \(E(\|\mathbf{M}_{n+1}\|^2\mid\mathcal{F}_n)\leq C_M\).

For the following drift calculation, assume the states and the entire line segments joining consecutive states remain in a compact convex set \(K\). Assume \(V\) is twice continuously differentiable on a neighborhood of \(K\), with bounded Hessian there; \(h\) is bounded on \(K\); and the remainder is \( \mathcal{F}_n \)-measurable and bounded. These conditions ensure that the Taylor expansion is valid along each step and that its second-order term has a conditional bound. For convergence, also assume \( \sum_n\gamma_{n+1}^2<\infty \), \( \sum_n\gamma_{n+1}=\infty \), and \( \sum_n\gamma_{n+1}\|\mathbf{r}_{n+1}\|<\infty \) almost surely.

The remainder appears as a predictable quantity because it is assumed measurable with respect to \( \mathcal{F}_n \). If it is not predictable, one must instead assume and use appropriate conditional bounds for it and for the Taylor remainder; its realized value cannot simply be substituted into a conditional-expectation inequality.

In particular, suppose on \(K\) the stronger drift condition \( \dot V(\mathbf{x})\leq-cV(\mathbf{x}) \) holds for some \(c>0\). Then the displayed inequality has the form \(E(V_{n+1}\mid\mathcal{F}_n)\leq V_n-c\gamma_{n+1}V_n+a_{n+1}\), where \(V_n=V(\mathbf{X}_n)\) and \( \sum_n a_{n+1}<\infty \) almost surely. The nonnegative-supermartingale convergence result commonly called the Robbins–Siegmund theorem implies that \(V_n\) converges and \( \sum_n\gamma_{n+1}V_n<\infty \) almost surely. Since the step sizes have a divergent sum, the limit of \(V_n\) must be zero: a positive limit would make that weighted sum infinite. If \(V\) is positive definite and the states remain in \(K\), this yields \( \mathbf{X}_n\to\mathbf{x}^* \) almost surely.

This conclusion uses a quantitative drift bound and controlled stochastic increments. Deterministic asymptotic stability alone does not supply those conditions. For a local rather than global argument, one must additionally justify that the process stays in the region where the Lyapunov and Taylor bounds apply, for example by a valid stopping or localization argument.

Diagnostics, Alternatives, and a Common Pitfall

Before applying a Lyapunov argument, check the equilibrium equation \(h(\mathbf{x}^*)=\mathbf{0}\), positive definiteness of \(V\), the sign of \( \dot V \) on the claimed region, and whether the dynamics keep trajectories in that region. For a stochastic recursion, also check the conditional mean and second moment of the noise, the measurability and summability assumptions on the remainder, and whether step segments stay where the Hessian bound applies. A failed sign check, excursions outside the set, or a remainder with uncontrolled conditional behavior invalidates the corresponding conclusion.

Directly solving a scalar differential equation or examining its phase line can be simpler when the solution is available. A Lyapunov function is useful when an explicit solution is cumbersome or when a common argument is needed across multiple dimensions. In stochastic approximation, the Lyapunov drift complements rather than replaces the ODE analysis: it supplies a route from a stable drift to convergence only after the random fluctuations are controlled.

Common mistake: nonincrease of \(V\) over a large set does not imply convergence to the designated target. For example, with \( \dot{x}=-x(x-1)^2 \) and \(V(x)=x^2/2\), \( \dot V=-x^2(x-1)^2\leq0 \). The compact sublevel set \(V\leq1.125\) is \([-1.5,1.5]\), and the drift points inward at its endpoints. Yet the trajectory starting at \(x=1.5\) moves toward and converges to \(1\), another equilibrium, not the target \(0\). To conclude convergence throughout such a set, require strict decrease at every non-target point (as well as invariance and existence), or establish conditions that rule out every other possible limiting invariant set.

Lyapunov criteria establish stability, not the rate of convergence or a distributional approximation for allocation counts. Those questions require additional analysis. A function with a derivative that is negative but very close to zero near the target can prove convergence while giving little information about how quickly it occurs.