Squared-logarithmic randomized k-server on arbitrary metrics

Proof. After C_t is revealed, take a minimum matching from A_{t-1} to C_t. If A_{t-1} does not contain r_t, move the actual server matched to a chosen occurrence of r_t in C_t to that point. Keeping the same matching after the move shows that

If the request was already covered, make no move and the inequality holds with equality. Composing minimum matchings gives

Summing and discarding the nonnegative final matching distance proves the claim. Minimum matchings exist because there are only k! permutations, even with repeated positions. Fixed orders resolve all ties, so this procedure is causal.□

Proof. Extend A_j before the coarsest index of the interval by the value K. Ball inclusion gives B_j\le A_{j-p} whenever the shifted index remains in the interval, and the same inequality follows from B_j\le K at the coarse boundary. Thus the sum is at most \sum_j(\log A_{j-p}-\log A_j). All interior terms cancel, leaving at most p coarse-end terms minus at most p fine-end terms. Each resulting difference is at most \log(K/c).□

Proof. Set t_*=s_*-p_*=7/12 and

For 0\le z\le1/100 define

The identities

show that both values and first derivatives match at p_*. They also show that g is p on the first interval and (s_*-p)^2(c_*'+d_*'(p-p_*)) on the second.

Writing x=s_*-p, the middle expression for l^{3+z} is

Its two coefficients are nonnegative, with A_*-zb_*'>2. Consequently it is positive before the cutoff, has nonpositive p-derivative, and has positive second derivative. Its value and first derivative are zero at the cutoff. Together with the matching at p_*, this proves global convexity and monotonicity. On the first interval the function is bounded away from zero, so its square root has bounded derivative. On the middle interval its square root is x\sqrt{A_*-zb_*'+zd_*'x}, which also has bounded derivative, uniformly in z. The matching and cutoff give the global Lipschitz bound.

For p\in[p_*/4,p_*], the quotient g(p)/l^{3+z}(p)=p/(1-(3+z)p) lies between 1/96 and 1. On the middle interval the quotient is

It is at least c_*'/A_*=1/21 and at most b_*'/(A_*-(1/100)b_*')<1. Beyond the cutoff both functions vanish. This proves (3.5).□

Proof. Suppose there are d children. Pool their dk rank probabilities and sort them increasingly, obtaining a vector x. Let y be the parent’s k increasingly ordered rank probabilities followed by (d-1)k ones. Their total sums agree and equal dk-m_v. If the first n coordinates of x contain n_i coordinates from child i, those coordinates can be chosen as the first n_i of that child. Since N_v=\sum_iN_i, conditional expectation gives

The last identity also holds for n>k, precisely because of the padding. For every real b, an increasing vector z satisfies

Thus the sum of every convex hinge (b-p)_+ on x is no larger than its sum on y. Affine functions have equal sums. Every convex piecewise linear function is an affine function plus a nonnegative linear combination of these hinges. Approximating a continuous convex function by its linear interpolants proves the same comparison for that function. Apply it to l^\beta and l^{\mathrm{siz}}; the padded ones contribute zero. Finally convexity and the endpoint values give l^{\mathrm{siz}}(p)\le1-p, and \sum_a(1-p_{va})=m_v.□

Proof. Initialize a reference p^\circ=p_0 and hold f(p^\circ) until the displayed factor comparison fails, then replace p^\circ by p_t. With the reference held, use

This is affine in p, lies in [0,1], and has slope of absolute value at most one. At every step, first evaluate its change from p_{t-1} to p_t^- and then from p_t^- to p_t, holding the old reference. The former change has conditional expectation zero, and the latter is at most |p_t-p_t^-|. A reference reset then decreases \Phi by exactly (p_t-p^\circ)^2. Telescoping gives

For two nonnegative values a,b failing factor 1+\xi comparison,

The inequality includes the case in which exactly one value is zero. The Lipschitz bound for \sqrt f therefore implies (p_t-p^\circ)^2\ge c\xi|f(p_t)-f(p^\circ)| at every reset, proving (3.10). The same potential proves the absolute-threshold claim, since every reset then releases more than \delta^2. Filtering was evaluated at every step before the reset test; no expectation was restricted to a selected reset event.□

Proof. We give the amortization details because paying a large size on every small refresh would not suffice. Lemma 3.4, summed over the fixed collection of size terms, bounds the expected total variation of their estimates by CE_v plus a fixed initialization constant. It bounds \E\sum_tK_t in the same way. Constants may depend on the fixed absolute tolerances but never on k or the degree.

For a scalar estimate x held at a reference b>0, a factor 1+\delta failure gives

The last difference is bounded by the variation of x since its previous reference setting; these intervals are disjoint. This pays all active to active changes of a_i and all changes of H_v. Turning a child on after an off period costs its new size, and is paid by the variation from a previous value at most 2c_* to a value at least 5c_*. The first such event may instead use an initialization charge. For a turn-off, if the last held size exceeds 4c_*, variation since that setting pays it because the new estimate is at most 2c_*. Otherwise the charge is at most 4c_* and is paid by the traversal from at least 5c_* at the start of this on period to at most 2c_* at its end. Each on period and each off period is used only once in these latter arguments. They overlap the scalar refresh intervals only a bounded number of times. This proves the budget for all changed-a_i charges. Clipping the parent sum below at c_* does not increase its variation, so the same argument applies to H_v.

When \beta^+ changes, the old and new active totals are at most C(X_v^-+X_v^+)\le C(H_v^-+H_v^+), and are therefore paid by that parent refresh. For a wholesale event from the vector-variation test, let R be the cumulative variation since the previous epoch started and let A be that epoch’s initial total. The old total is at most 1.01A, the new total is at most 1.01A+R, and R>A/100. Their sum is consequently at most 203R. The intervals of variation assigned to successive epochs are disjoint. If A=0, the new total is at most R, and the same conclusion holds. Discarding unused variation credit when a parent refresh intervenes cannot increase its total use. This proves the wholesale budget.

On a fixed marked epoch, variation of T_{\mathrm{side}} is at most \sum_i|\Delta a_i|. The scalar relative-refresh argument pays every U refresh by variation since its previous setting. The actual old side total is within factor 1+\delta_s of that reference, so the old plus new side totals have the same bound. A zero crossing is included: the variation then pays the positive reference or positive new total. Setting U at a wholesale change is paid by the wholesale total. Thus all its asserted charges are covered.

At a non-wholesale step the dominant index is unchanged. The variation of (3.19) is at most the summed variation of its coarse term estimates plus CK_t: a changed flag inserts or removes one term, each at most one. At a wholesale step, its old and new values are at most C(a_o^-+a_o^+), interpreted as zero when that mark is absent; this follows from the relative estimates and (3.13). The wholesale totals pay these changes. This proves (3.21).

For the gaps, at every state of an epoch with A>0 the current active total is in [0.99A,1.01A]. In an unmarked epoch every child has a_i\le0.86A. In a marked epoch the marked size is at least 0.84A, and the side total is at most 0.16A; in particular the mark stays active. Therefore every regular child has a_i\le0.86A. By (3.15) and superadditivity,

For x=A/a_i\ge1/0.86, the logarithm of the last expression is at least c(1+\log x) for an absolute c>0. To see the uniformity, the ratio to 1+\log x is continuous and positive on this interval and tends to one as x\to\infty; on a sufficiently large tail it is at least 1/2, and on the remaining compact interval it has a positive minimum. This proves the regular comparison. For the dominant child, use the first inequality in (3.23), the comparisons T_{\mathrm{side}}\asymp U, and a_o\le1.01A to obtain

Here u\le(1+\delta_s)0.16<1/4, so \log(1+cu)\ge c'u. If no sides exist, u=0 and the claimed inequality is automatic.

At every active child M_i\ge c_* and M_v\ge M_i, so the clipping in (3.8) is inactive at both vertices. Hence

which proves the gap in (3.22). Active held sizes have an absolute positive lower bound and A\le1.1k, proving h_i\le C\ell. On a side, a_i\le T_{\mathrm{side}}\le(1+\delta_s)uA, whence

The final bounds on core and flex data follow from (3.13), B_i\le n_i, and (3.15). Inactivity was addressed in (3.14).□

Proof. For every rank, at both endpoint parameters 3 and 3+\epsilon_*, run separate relative trackers with tolerance \rho/\ell, where \rho>0 is a small absolute constant to be selected. Interpolate their estimates by the convex coefficients expressing \beta^+ between these endpoints, and sum over the current noncore ranks at child i. Call the result \widetilde f_i. The affinity in \beta and the relative endpoint estimates imply

Every noncore rank has p>3p_*/8, so (3.5) applies to it. Together with (3.17), this yields

For example, f_i^{\beta_v}-f_i^{\beta^+} =(\beta^+-\beta_v)\sum_{\mathrm{noncore}}g(p_{ia}) \le(\epsilon/\ell)f_i^{\beta_v}. If the true sum is zero then both endpoint estimates, and therefore the interpolated sum, are exactly zero, since all the functions have the same cutoff.

For a regular child, h_i\ge1 and the parameter gap gives

Choose an absolute 0<\lambda_b\le\min\{\gamma/4,\epsilon_b/4,1/4\}, and then choose \rho,\epsilon so small that the e in (3.26) is at most \lambda_b/4. Define

For a regular child the upper estimate is at most f_i^{\beta_v}, because e\le\lambda_b; the lower estimate is at least (1-(\lambda_b+e)/\ell)f_i^{\beta_v}, which dominates (3.27). For a dominant child, (1+\lambda_b/\ell)(1-e/\ell)\ge1, whereas (1+\lambda_b/\ell)(1+e/\ell)\le1+\epsilon_b/\ell. This proves the cap comparisons.

On the noncore range (3.5) also gives

The coarse tracker defining D therefore satisfies

These choices give the claimed c_D,C_D and show that their values precede all fine choices. The bound d_i\le C M_i follows from (3.13) and the relative estimates.

It remains to account for variation. Lemma 3.4 with tolerance \rho/\ell pays the summed variation of all endpoint estimates by C\ell E_v plus a fixed constant. On a non-wholesale step, \beta^+ and the dominant mark are unchanged, so their interpolation coefficients and the factors 1\pm\lambda_b/\ell are fixed. Changes of the noncore sets cost at most CK_t, as does the variation of n_i. An inactive child has zero true endpoint values and hence zero endpoint estimates; setting its cap to zero therefore adds no variation beyond the same term and flag changes. This proves (3.25). At a wholesale step, d_i^-+d_i^+\le C(a_i^-+a_i^+), including zero inactive values, and summing proves the remaining statement.□

Proof. The regular integral equals 1. For the marked child, split at 1:

Since \log(1/u)=H-1 and \log(1+H/u)\le H-1+\log(1+H)\le2H, these bounds are absolute.

For the second assertion put y_i=\log(1/\alpha_i) at positive coordinates. If i is regular and y_i\le4h_i, its contribution is at most 25\alpha_i h_i. If y_i>4h_i, then h_i\ge1 and

Thus the regular tail is at most C without a marked child and at most Cu with one. Without a marked child, \sum_i\alpha_i h_i\ge1, which pays this tail.

With a marked child use the elementary inequality e^{-y}y(1+y)\le C(1-e^{-y}), valid for all y\ge0. It follows, including the endpoint \alpha_o=0, that

By (4.1), \sum_i\alpha_i h_i bounds this last expression up to an absolute factor. It also bounds u up to an absolute factor: its dominant contribution is \alpha_o u, and its side contribution is at least cH(1-\alpha_o)\ge cu(1-\alpha_o). This pays the regular tail and completes the proof.□

Proof. Continuity and compactness give a global minimizer, and comparison with \alpha^0 gives (4.9). If S=0, then every B_i=0, the potential vanishes identically, and feasibility is automatic. We may retain \alpha^0. Suppose henceforth that S>0 and the domain is nonsingleton. For a positive coordinate write

for the derivative of its primitive. If \alpha_i=0 and B_i>0, the inward derivative is -\infty: the negative term has size proportional to 1/(sF_i(\log(1/s))), which tends to infinity as s\downarrow0.

There must be a coordinate with derivative less than -2S, with this convention at zero. Otherwise all zero coordinates have B_i=0, and the inequalities \gamma_i\ge-2S give

There is a fixed bound \eta_i\le\eta_{\max}, so, with T_\alpha=\sum_i\alpha_i h_i,

The extra sum in (4.10) is at most CT_\alpha/(C_\alpha\ell) by (4.4). Choose C_\alpha so this is less than half the displayed deficit. Since T_\alpha>0 on every nonsingleton domain, this is a contradiction, however small u and T_\alpha may be.

If a coordinate violates (4.2), it is positive and has strictly positive primitive derivative. Transfer a small amount \varepsilon from it to a coordinate whose derivative is below -2S. These coordinates are distinct and the transfer stays in the simplex. The primitive sum decreases at a rate greater than 2S, whereas the movement penalty can increase by at most 2S\varepsilon. At a zero receiving coordinate the one-sided derivative -\infty gives the same strict improvement for sufficiently small \varepsilon. This contradicts global minimality and proves feasibility.□

Proof. Compactness gives existence and comparison with w^0 gives the payment. Suppose first that D>0, and abbreviate b=\beta^+, \theta=\theta_i, z=z_i, and s=w_i. At an upper violation, B_i<Ds/(b+\theta). The numerator in (4.13) is consequently greater than

Because b+\theta has an absolute upper bound, a large C'_w makes the primitive derivative greater than 2D. The violating coordinate is positive and can be decreased while remaining in the side domain. The penalty changes by at most D times this decrease, a contradiction to minimality.

Having proved upper feasibility, assume S\le2D. Then

Thus every coordinate has room for a small increase. At a lower violation, B_i>D(s+\theta z)/b. Substitution makes the same numerator strictly less than

The derivative is therefore less than -2D when C'_w is large. Increasing this coordinate strictly improves the objective, again a contradiction. This proves the lower inequality.

If D=0, the upper inequality is automatic. The lower inequality is required only when S=0, in which case every B_i=0 and it too is automatic. The potential need not vanish when D=0<S, but minimization and its payment remain valid. If both D=S=0, the potential vanishes, and retaining the old side vector is allowed. The empty side domain consists of its unique zero vector.□

Proof. We give the schedule and its entire accounting. All comparisons below are made on a finite set of child and rank indices.

Filtering and drift precede every update decision. At the start of step t, hold the old proportion states, old parameters, old D, and old core flags. First evaluate the potentials with the filtered old hidden counts, and then with the new hidden counts under the new conditioning, still using those old flags and parameters. With these quantities held, each potential is affine in the rank probabilities: for G^w, its term linear in the held D is simply constant on these two legs. The signed expected filtering change is therefore zero. By (4.6) and (4.15), the absolute drift change is at most C\ell times the sum of absolute child-rank drifts. Summed over all steps, its expectation is at most C\ell E_v. These statements concern all steps before selecting any refresh or domain-change events.

Denote the input at the end of this evaluation by \overline B: it uses the final rank probabilities and the old flags. Thus \overline B_i\le n_i^{\rm old} even if filtering made the current ranks very different. We now compute the new flags, sizes, and all other held parameters by the rules already given.

Wholesale steps. At a wholesale step reinitialize the proportion domains, choose any vector in each new compact domain, and apply the appropriate minimizing updates; use the automatic rules for empty or singleton domains. The absolute old potential, evaluated at \overline B and old D, is at most C\ell times the old total active size. To see this for G^\alpha, sum (4.7) and use \sum_i\overline B_i\le\sum_i n_i^{\rm old}\le C\sum_i a_i^{\rm old}. For G^w, use (4.15), \|w\|_1\le C_w, and D^{\rm old}\le C\sum_i a_i^{\rm old}. The new potential is bounded by the corresponding new total. Thus the entire potential jump at this step is bounded by its coarse wholesale charge times C\ell. No movement at this step is included in (4.18).

Preparing a non-wholesale domain change. On a non-wholesale step A, \beta^+, and the presence and identity of the dominant mark are fixed. Empty/nonempty active transitions are wholesale, and a marked dominant coordinate cannot disappear within its epoch. Let I^- and I^+ be the old and new active domains. Define the synthetic input on the fixed child set by

If K_t is the number of changed core flags, then

For common indices, the first discrepancy is just the sum over changed flags, and each rank probability lies in [0,1]. For an index leaving the active domain, all its new flags are zero, so every old flag there is changed. For an entering index, all its old flags were zero, so every new flag there is changed. These observations prove all three bounds.

Replace \overline B by B^* and old D by D^{\rm new}, holding the old domains and their other parameters. The input slope bounds charge this potential change to C\ell(K_t+|D^{\rm new}-D^{\rm old}|). Run the minimizing updates on the old domains with inputs (B^*,S^*,D^{\rm new}). Denote the resulting vectors by \alpha^1,w^1. Lemmas 4.2 and 4.3 apply because their feasibility proofs use only nonnegativity of these inputs and the held parameter bounds. They pay

by decreases of the respective potentials.

Next delete departing coordinates and insert zero coordinates at entering indices. If S^*>0, a departing coordinate has B_i^*=0, so (4.2) forces \alpha_i^1=0. Deletion and zero insertion then preserve the simplex and cause no movement. If S^*=0, every B_i^*=0, the alpha potential is zero, and we may redistribute the simplex mass to any vector in the new nonempty domain at zero weighted cost. If D^{\rm new}>0, the upper inequality in (4.11) forces w_i^1=0 at each departing side. If D^{\rm new}=0, deletion of side coordinates has zero weighted cost, and their primitive components vanish because B_i^*=D^{\rm new}=0 there. Inserting a coordinate at zero always gives zero component potential. Write \alpha^2,w^2 for the vectors on the new domains after this operation.

Changing the held parameters. Continue to use B^* and D^{\rm new}. At common regular coordinates the prepared state satisfies

The assertions also hold at inserted zero coordinates, and at S^*=0 or D^{\rm new}=0 with the evident zero left side. The regular parameters h_i,\eta_i,F_i and, on sides, \theta_i,z_i change only if a_i changes. Bound the absolute old and new component values using (4.7), (4.15), and (4.22). Their jump is at most C\ell B_i^*\le C\ell n_i^{\rm new}\le C\ell a_i^{\rm new}, which is paid by the old-plus-new size charge at that coordinate. Departing and inserted components have already been seen to give zero extra jump.

For a change in u, the prepared alpha vector satisfies

The first inequality follows by summing prepared side feasibility when S^*>0 and is automatic when S^*=0; the last uses the new core-size bound and the epoch comparison of total size with A. Applying the dominant component bound on both sides of the parameter change shows that its jump is at most

This is a side-total charge, not a dominant-size charge. It includes the appearance of the first side or disappearance of the last side. To spell out these endpoints, on a singleton domain the potential is zero. If S^*>0, preparation forces all mass onto o when the common side input is zero, and the dominant primitive at \alpha_o=1 is zero. If S^*=0, the whole alpha potential is zero. Thus assigning the singleton potential to be zero is compatible with the estimates on both sides of either transition. The side vector on an empty side domain is its unique zero vector.

The final update and its movement weight. With the new domains and parameters now installed, replace B^* by B^{\rm new}, paying at most C\ell K_t by (4.20) and the input slope bounds. Run the two minimizing updates once more, now starting at \alpha^2,w^2 and using the final inputs. This pays S^{\rm new}\|\alpha^{\rm new}-\alpha^2\|_1 and D^{\rm new}\|w^{\rm new}-w^2\|_1.

The triangle inequality converts these payments to the differences between the final and old states. The alpha vectors at all these substeps have norm one, hence any two are at distance at most two. The domain-transition movement has weight zero at S^*. Writing \delta=S^{\rm new}-S^*\ge0, we obtain

The first error is at most 4K_t. The second inequality needs no change of weight, since both side updates used D^{\rm new}. These statements also cover zero weights and singleton states.

Telescoping and uniformity. Let \mathcal G_t=G_t^\alpha+G_t^w after the final update. On non-wholesale steps the sum of the paid minimizing movements is at most \mathcal G_{t-1}-\mathcal G_t, plus the signed old-parameter filtering/drift change and the parameter/input charges just listed. On wholesale steps the same inequality holds with no movement term and with the wholesale charge. Summing over all steps retains the zero expected filtering sum; it does not condition that assertion on an adaptively selected subset of steps. Expected drift costs at most C\ell E_v, and all remaining changes cost at most C\ell times the coarse charges. Equation (4.23) therefore gives (4.18), apart from the initial and terminal potential magnitudes.

Those magnitudes have a uniform finite bound. At a valid state, \sum_iB_i\le\sum_i n_i\le Ck, D\le Ck, \|\alpha\|_1\le1, and \|w\|_1\le C_w. The component bounds give |\mathcal G_t|\le C\ell k, including arbitrarily small positive u. Only the fixed collection of rank and parameter trackers contributes the other finite initialization allowances. Their states persist through all epochs and inactive intervals; no new allowance is assigned when a label or coordinate returns. Thus D'_v is independent of the number of steps, histories, refreshes, and domain changes. The schedule uses only current observed posteriors and prior states. Global minimizers can be selected by fixed tie-breaking on the compact finite-dimensional domains, so it is causal.□

Proof. Superadditivity at the single parameter \beta_v gives

Inactive children have no core ranks and no positive lower-bound terms, so their required lower bounds and their outputs are both zero. For active children, expand L_i^{\beta_v}=n_i-\beta_vB_i+f_i^{\beta_v}. Set e_o=b_o-T when a dominant child exists, and e_o=0 otherwise. Lemma 3.6 implies

To obtain the second inequality, subtract (5.8) from \sum_i d_i: regular flex caps contribute nonpositive errors, and only the dominant cap can contribute the error e_o.

First consider Rule I with S>0. If there is a dominant child, (5.4) and D\ge c_DT give

The same bound on the error holds with error zero when there is no dominant child. At a regular child, (4.2) and (5.9) yield

By \eta_i=c_th_i/\ell, \eta_i\le1, and (5.6),

Thus R_0\alpha_i\le\beta_iB_i, and the lower cap bound gives q_i\ge n_i-\beta_iB_i+f_i^{\beta_i}=L_i^{\beta_i}. For the dominant coordinate use \alpha_o\le1 on the error term:

Here h_o=u, so the same small choice of c_t works even for arbitrarily small positive u, and gives equality in the relevant error when u=0. Since b_o-e_o=T\ge f_o^{\beta_o}, this proves the dominant lower bound as well.

If S=0 in Rule I, the presence of a dominant child forces D=0 by its allowed range, and therefore T=e_o=0. Without a dominant child the error is zero by definition. In either case (5.9) gives R_0=0, so no division by S is used: the outputs are their caps. At regular children the cap lower bound suffices, and at the dominant child B_o=T=0 gives the claim. For any nonempty active set, the simplex identity gives

Every hole is nonnegative, so q_i\le d_i; the proved lower bound ensures nonnegativity.

Now consider Rule II. Its side holes satisfy, by (4.11) and (5.7),

The side lower bounds follow from b_i\ge f_i^{\beta_i}, exactly by subtracting these holes from n_i+b_i. Write q_o^{\mathrm{rem}}=q_v-\sum_{i\ne o}(d_i-Dw_i) for the uncapped remaining amount. The upper flex caps on the sides and (5.8) imply

The second line uses the lower inequality of (4.11), which applies because Rule II has S\le2D, together with \beta^+\ge\beta_v. The last line uses (5.5) and (5.6). Independently, d_o=n_o+b_o\ge n_o+f_o^{\beta_o}\ge L_o^{\beta_o}. Taking the smaller of these two admissible dominant amounts preserves its lower bound. It also gives the parent budget and the upper cap.

For completeness, when D=0 in Rule II its range forces S=0, and the comparison with T forces T=0. All side holes vanish and (5.9) gives R_0=0; thus the dominant cap also fits within the remaining budget. When there are no sides, u=0, the side sums are empty, and both rules simply give q_o=\min\{d_o,q_v\}. No side denominator or proportion is needed in this case. An empty active set was already assigned zero outputs. Finally the cap estimate d_i\le CM_i, together with M_i\le m_i, proves the claimed domination in every case.□

Proof. Compare the vectors of holes \zeta_i=d_i-q_i, adding cap variation at the end. By Lemma 5.1 these vectors are nonnegative. In Rule I one has

In Rule II let \omega_i=Dw_i on the sides and W_{\mathrm{side}}=\sum_{i\ne o}\omega_i. The definition of the dominant output gives the exact identities

Indeed before replacing the signed excess by its positive part the dominant hole equals (\sum_i d_i-q_v-W_{\mathrm{side}})_+, and W_{\mathrm{side}}\ge0 allows that replacement. These identities remain valid when D, S, or the side set vanishes.

Suppress the time index and use superscripts -,+ for old and new step-end values. On a non-wholesale step the dominant mark, if any, is the same at both times. First suppose both times use Rule I and the active sets are nonempty. Adding and subtracting R_0^+\alpha^-, and using \|\alpha^-\|_1=1, gives

The last bound follows from (5.9) and (5.10), with the zero case proved in Lemma 5.1. If the active sets are empty at both times the hole change is zero. A change between empty and nonempty is wholesale and is treated below.

If both times use Rule II, the positive-part map is 1-Lipschitz, so (5.18) gives

For the first line, the change in the side-hole total is at most \|\Delta\omega\|_1; the other copy is the change of the side vector itself. For the second, use \Delta(Dw)=D^+\Delta w+(\Delta D)w^- and \|w^-\|_1\le C_w. Inserting or deleting a side causes no extra term because these vectors have been extended by zero.

At an I-to-II switch, S^+<D^+/2, so (5.9) and T^+\le D^+/c_D show R_0^+\le C D^+. The new hole total is at most \max\{R_0^+,C_wD^+\}\le C D^+. The old total is R_0^-, which is at most R_0^++|\Delta R_0|. Nonnegativity of the two hole vectors therefore yields

At an II-to-I switch, S^+>2D^+, whence D^+\le S^+/2 and R_0^+\le C S^+. The old total is at most R_0^-+C_wD^-, while the new total is R_0^+. Using R_0^-\le R_0^++|\Delta R_0| and D^-\le D^++|\Delta D| gives

These two arguments bound the full change across a switch without requiring the unused rule to have held at the preceding inputs.

Finally, positive part is 1-Lipschitz in (5.1), and therefore

Combining all the non-wholesale cases gives one useful pointwise bound, with a single copy of the parent movement:

Only defined tracker terms are included. In particular they are zero for an empty active set, and the side term is zero without sides or a dominant child.

At a wholesale step use the actual output domination directly:

There is no per-child or per-epoch initialization charge here; the sum of sizes is exactly the wholesale quantity already paid. Take expectations and sum (5.25) over non-wholesale steps and (5.26) over wholesale steps. The fine cap budget (3.25), the proportion budget (4.18), the coarse budget (3.21), and (5.12) give (5.16). Cap movement is added once; it is never used as an input to a potential having an O(\ell) input slope. The coefficient of the parent variation in (5.25) is one, which proves the claimed absolute bound on C_{\mathrm{par}}.□

Proof. Testing capacity at p=s gives 0\le z_s\le1. For each pair with d(s,s')<5\sigma r, the separation condition is exactly the closed equation z_sz_{s'}=0. Thus \mathcal Z_r is a closed subset of the finite cube [0,1]^Y, containing zero. It is compact, and the objective is continuous. Although this set need not be convex, a minimum therefore exists.

At every point p, the weights of all centers in B(p,D_*r) sum to at most one, because G_s(p)=0 there. Every center contributing to a_s(p) or b_s(p) lies in that ball. It follows that

These inequalities give the bound 514=2+512 for the integrand, its nonnegativity, and the lower bound in (6.6). Taking z=0 gives the upper bound for the minimum.

If d(p,q)\le r, every center contributing at either endpoint belongs to B(p,(2R+1)r)\subset B(p,D_*r), so all its weights together sum to at most one. The residual term in (6.4) consequently has Lipschitz bound (L+2/\sigma)/r, and the surcharge term has bound 1024/(\sigma r). If d(p,q)>r, the bound 514 on the range already implies the claimed Lipschitz bound, since \Lambda\ge1026. Finally, if b_s(p) and b_{s'}(p) are both positive, then d(s,s')<4\sigma r, contrary to separation for two positive weights.

For nonnegative measures \mu_0,\mu_1 and 0\le\theta\le1, every feasible z satisfies

Taking the minimum proves concavity. Convexity of \mathcal Z_r was not used.□

Proof. We perform the calculations in units of r; integrals of F therefore omit the common factor r in the potential.

Deleting a middle-distance site. For \sigma/4\le d(s,x)/r\le R/2 and p\in B(x,\gamma r), the distance d(s,p)/r is at least \sigma/4-\gamma and less than R. Consequently

The support of b_s is inside B(x,D_1r). The coefficient of z_s in the integral objective is therefore at least

Decreasing a weight preserves both constraints in (6.3). A positive such weight would contradict minimality, proving the first assertion.

Inserting a unit site. Clear all weights at centers in B(x,5D_*r), and put weight one at x. Separation holds, since every retained center is farther than 5D_*r. To check capacity, consider a test point p where the new site’s contribution is positive. Then d(p,x)<2D_*r. Every old center contributing positively at that test satisfies d(s',p)<2D_*r, because z_{s'}\le1 and G_{s'}(p)<z_{s'}. Such a center lies in B(x,4D_*r) and has been cleared. The single new contribution is at most one. At other tests the new site contributes zero and weights have only been removed. Thus the competitor is feasible.

There is at most one positive old site within \sigma r/4 of x by separation; denote its weight by Z, taking Z=0 if it does not exist. On the entire inner ball its b value is one. Every other positive site has distance greater than Rr/2 from x by the first assertion, so its b value is zero on the inner ball. The old residual is thus 1-Z there, and the old integrand is at least 1-Z. The new integrand there is at most 512(d(x,p)/r)^2/\sigma^2, whose integral is at most 512M\gamma t/\sigma^2.

All changed bumps are supported in B(x,(5D_*+2R)r)\subset B(x,D_1r). Outside the inner ball the increase is at most 514 pointwise, by Lemma 6.1. Minimality of the old vector gives

Here both last summands are at most 1/8 by (6.8). This proves existence, uniqueness, the weight bound, and the deficit bound in (6.10).

Relocating that site and repairing capacity. Write s for this near site and z=z_s. The case w=0 already has the desired displacement bound. For w>0, move its weight from s to x. Simultaneously replace every other weight z_i with center in B(x,5D_*r) by (z_i-q)_+, where

If s\ne x, the old weight at x is zero by the just-proved uniqueness. Every other positive center lies beyond Rr/2 from x, so the moved site preserves separation.

For a capacity test p, put

When A'\le A, capacity can only improve. Otherwise A'>0, and A'-A\le q by the Lipschitz constant of G. The same distance calculation as above puts every center contributing to B within 4D_*r of x, hence among the reduced centers. If b_i=(z_i-G_i(p))_+, its contribution decreases by exactly \min\{q,b_i\}. For any nonnegative finite family (b_i),

Indeed, a summand with b_i\ge q proves the inequality immediately; if none exists, the left side is \sum_i b_i. If B\ge q, the reductions pay the increase A'-A. If B<q, all the other contributions vanish and the remaining contribution satisfies A'\le z\le1. This verifies every capacity test, with no dependence on the number of sites.

For p in the inner ball put u=d(s,p)/r and v=d(x,p)/r. Both are less than \sigma, so the moved site’s old and new a values are u^2/\sigma^2 and v^2/\sigma^2. The triangle inequality gives u^2\ge w^2-2wv+v^2: if v\le w, square u\ge w-v; if v>w, the right side (w-v)^2 follows from u\ge v-w. Consequently, using L\gamma\le1,

The near site’s b value stays one there; all other b values stay zero; and reducing other weights can only lower their surcharges. The integral gain on the inner ball is therefore at least

For completeness, the pointwise loss outside the inner ball has a bound proportional to w, rather than a constant per changed site. Moving the near site’s center changes its residual contribution by at most 2zw/\sigma, and its surcharge by at most 256z(4/\sigma+L)w. Thus its total increase is at most zK_0w, where

The reduction of other weights can only increase the residual. Since their positive b supports are disjoint, the residual increase is at most 2q at every point. All changes vanish outside B(x,(5D_*+2R)r). The shell loss is therefore at most Mh(zK_0+2/D_*)w. Combining this with (6.15) and minimality, and dividing by the positive quantity 256zMw/\sigma^2, gives

For the middle inequality, use z\ge1/2, \sigma\le1, D_*\ge2560, and 1026/256+4/(256D_*)<5. This proves the last local structural estimate.

Positive slope at the request. Put v=d(x,y)/r<\sigma/8. The near site’s b is one at both points, and all other positive sites have b=0 at both points. The residual part of F_z^g(x)-F_z^g(y) is consequently at most L(1-z)v. Writing u=d(s,y)/r, the near-site surcharge difference has positive part at most

because (w^2-u^2)_+\le2w|w-u|. Every other center contributing an a value at either endpoint is within (2R+\sigma/8)r<D_*r of x. Capacity at x, including the near site, bounds the total of these other weights by 1-z. Their surcharge difference has absolute value at most 1024(1-z)v/\sigma. Altogether,

Finally (6.13) and \gamma\le\sigma/64 give 1-z\le(514+8/\sigma)(h+t), and the displacement bound proves (6.11) with the stated constant.□

Proof. Let z^{(j)} minimize the old objective at radius r_j and write F_j=F_{z^{(j)}}^{g_j}. Evaluating the new minimum at this vector yields

If e_x=0, the probability measure \nu is supported at x and the two counting measures agree. Assume henceforth e_x>0.

The radii smaller than 2e_x/\gamma contribute at most

by \tau\ge2 and (6.7). At every remaining radius, domination by \mu^- and the definition of e_x give

This is a consecutive range of coarse radii. Define h_j,t_j there as in (6.9) with \mu=\mu^-.

We record both scale sums explicitly. Set A_j=\mu^-(B(x,D_1r_j))=(1+h_j)M_j. For u\ge0,

For 0\le u\le1 this follows from the chord between the endpoint values of the concave function \log(1+u), and for u\ge1 it follows from monotonicity. Since \tau^{p_0}\gamma\ge D_1, the mass A_j is at most M_{j-p_0} whenever that coarser index is in the range. Assigning the value k to missing coarser masses gives

All interior logarithms cancel; at most p_0 boundary differences remain, each between masses in [1/2,k]. This is also the instance of Lemma 2.3 needed here. Thus

For the moment sum only, order the same radii increasingly as \rho_1<\cdots<\rho_n, with \rho_{i+1}=\tau\rho_i, and set m_i=\mu^-(B(x,\gamma\rho_i)), m_0=0, and \Delta_i=m_i-m_{i-1}. Partitioning the jth inner ball into the successive differences of these balls gives

The first difference includes the entire first ball; hence this bound also accounts for any atom already inside that ball. Since m_j\ge m_i for j\ge i, interchanging two finite sums gives

Indeed the first ratio \Delta_1/m_1 is one, and, for i\ge2, \Delta_i/m_i\le\int_{m_{i-1}}^{m_i}du/u. Empty scale ranges require no estimate.

Call a remaining radius bad if h_j>\delta. Because \delta<1, (6.22) bounds the number of bad radii by p_0\log(2k)/(\delta\log2). The global Lipschitz bound gives at most \Lambda e_x in (6.18) at each one. At a good radius apply Lemma 6.2 to points with d(x,y)<\sigma r_j/8. Their total contribution, summed over good radii and integrated against \nu, is at most

Here h_j=\min\{1,h_j\} on good radii. For each fixed exceptional point y, with d(x,y)\ge\sigma r_j/8, use boundedness instead:

Integrating proves that all exceptional terms together cost at most 8224e_x/\sigma. This bound has no factor counting scales. Combining the estimates, using 1+\log(2k)\le2\ell and \ell\ge1, gives precisely (6.16) with (6.17).□

Proof. Let \mu_{t-1} be the previous post-step posterior counting measure. The posterior identity is

For every old, \mathcal F_{t-1}-measurable function g=g_{t-1,\alpha,j}, concavity gives

One can see this directly without any assumption on convexity of site vectors: choose a minimizing vector at \mu_{t-1}, use it as a competitor for each refined posterior, and take its conditional expectation. Its objective is linear in the measure and therefore returns exactly the old objective.

Write \Phi_{t-1} for the weighted total potential after the preceding step, \Phi_t^- for its value after filtering at old g’s, and \widehat\Phi_t for its value after drift, still at old g’s. Write \Phi_t for its value after the edits. The three established bounds are

All these potentials are nonnegative and at most 2kA\sum_jr_j. The same statements hold for a countable family: finite partial sums give the filtering inequality by convergence of nonnegative bounded sums, and the absolute bound by 2kr_j\omega_\alpha for each potential makes the signed differences summable. The drift bound sums because its weighted constants sum to B.

Taking expectations, summing in t, and using \E\sum_t e_x=Q proves \E\sum_t c_t\le B\ell Q+\E\Phi_0-\E\Phi_T. Dropping the nonnegative terminal value and applying (6.6) yields (6.25). In particular, (6.26) was summed over all steps. It was never conditioned on the event that a later edit was selected.□

Proof. Let \psi be the clipped increasing ramp on [9,10]. For each member at p, add the auxiliary potential r\psi(d(p,\mathcal H)/r). Sum it over members and levels, and telescope along actual hidden trajectories from one step end to the next. Its initial value is at most k\sum_jr_j and it is nonnegative. We bound an edit charge plus the full-step change of this potential.

Consider first a stationary member p at an update. If d(p,x)\le3r and an old center lies within 10r of p, both the old and new heavy balls contain p. Their intersection forces reuse, so its key does not change and its potential does not increase. If no such old center exists, its old potential is r and its new potential is zero, paying a possible charge of r. Outside this inner ball, all affected old or new balls and all changing ramps lie in B(x,120r): a removed center is within 100r, its ball has radius at most 20r, and its ramp has range at most 10r. The charge plus potential increase is at most 2r, supported in E_x(r).

For the designated mover y\to x, its final potential at an update is zero. The same argument pays its charge when d(y,x)\le3r. Otherwise the unpaid amount is at most r, and \sum_{r_j<d(x,y)/3}r_j\le C d(x,y). At a step without an update there is no edit charge. On a heavy level a final center is within 8r of x, so the final potential is again zero. Only nonheavy levels can have a positive physical-motion change; at each it is at most d(x,y), by the ramp’s Lipschitz bound. Their number is bounded in (7.5).

The conditional expected stationary counting measure equals \mu^+-\delta_x, and in particular is bounded by \mu^+. Consequently (7.4) pays the stationary errors, and the other terms sum to C\ell Q. Nonnegativity and the stated initial bound complete the telescope.□

Proof. If there were n>A such entries, the earliest of them would have at least n-1\ge A later insertions within 20r of its center, contradicting its age. Repeated centers cause no exception.□

Proof. Write n=|Y|. Applying Lemma 7.3 to each singleton shows that a tier has at most M=nK^2 chronological records of age less than K^2. Reserve a record’s label until that age cutoff, even if its actual lifetime has ended or its ball is completely shadowed by earlier structures. This convention bounds all reserved labels by M; it does not alter the partition. During a step at most one new record is inserted. The records present at any intermediate time during two consecutive steps belong to their two starting record sets and at most two new records, so their total number is at most 2M+2. A pool of 4M+4 slots suffices to choose a fresh slot outside this entire set whenever needed. A slot released on the previous step is still excluded on the current step. This is a finite implementation of the stated cooldown rule, not a growing list of all historical labels.

The heavy structure has at most n centers and one insertion per step, so a separate pool of 4n+4 slots works by the same rule, with reuse allowed precisely for the unique intersected ball. Use disjoint pools for different tiers and the heavy structure, and n additional fixed singleton labels. Pool sizes are chosen for every level in advance and do not depend on the realized center schedule. A chronological record that persists keeps its label and center even while shadowed. Thus any common slot can only change its anchor by the explicit heavy reuse.

Heavy and tier keys are anchored at their centers, and singleton keys at their points. Every key cell is a subset of its defining ball, whose radius is at most 20r; restricting by precedence only shrinks it. The diameter and anchor bounds follow. Heavy precedence further implies that a heavy key’s region is its entire ball. Empty key regions cause no difficulty; their reserved anchors and slots are still defined.□

Proof. Condition on all presences, leaving the radii independent. For a center c, put a=\min\{d(c,x),d(c,y)\} and p_a=\Pr(V\ge a). The two distances differ by at most d, so separation requires V\in[a,a+d], up to endpoints of probability zero. If r\le a\le2r, direct integration of (7.7) gives

The density is decreasing, hence

For a<r, use the maximum density at r and p_a=1; for a>2r, the left side is zero. Thus the same bound holds when an interval crosses a support endpoint.

List the present balls in chronological order and let q_i be the probability all balls preceding ball i miss both points. The event that ball i hits at least one has probability p_{a_i}, so independence gives

Every potentially hitting center lies within 2r of one of the points. Those centers have diameter at most 4r+d<5r, and all present entries have age less than K^2. There are therefore at most K^2 candidates by Lemma 7.3. Multiplying (7.8) by q_i and summing gives

Finally \lambda=\log(1+K^2)\le Ch, since C_K is an absolute constant and h\ge1. The bound is uniform in the conditioned presences, so it also holds without that conditioning.□

Proof. For each level and tier use the nonnegative potential

ignoring all other structures in the definition of coverage. Telescope from step end to step end, so the potential includes physical movement. The sum of initial values is at most k|\mathcal H_k|\sum_jr_j, an allowed fixed initialization bound.

If there is no insertion, the roster has no edit. Stationary members give zero potential change, and only the mover y\to x can increase the potential. This requires y covered and x uncovered. It is impossible in a qualified tier, by guaranteed coverage. In an unqualified tier, Lemma 7.5 gives expected positive increase at most Chd(x,y) when r>4d(x,y). For r\le4d(x,y), the bound follows from the trivial increase at most r\le4h d(x,y). Unqualification says h<L_j(x), and

Thus all noninsertion increases cost at most C\ell Q.

At an insertion, let C_a\in\{0,r\} be a member’s overall key charge caused by this tier edit at its old position. Let U_- be old tier noncoverage at that position and U_+ final tier noncoverage at its final physical position. In particular U_+=0 for the mover, because the newly inserted ball covers x. The following table accounts for the entire quantity C_a+r(U_+-U_-).

For the first row, new entries are appended after all existing ones, so a surviving first coverer keeps the tier key unchanged. Other structures are held fixed during this edit. For the second row, an overall key can change only if this previously uncovered point becomes covered by the tier. These facts also hold when an earlier structure shadows the tier, in which case its charge may simply be zero.

There is a further zero-error case at a heavy level. If the old position lies in B(x,\gamma_Hr), the final heavy ball already covers it during all tier edits. Hence C_a=0. The new tier ball covers that position if it is stationary, and covers the final point x if it is the mover. Thus U_+=0 and no retirement error is needed in this inner ball.

We next bound the probability of the exceptional retirement row. Fix the full true input and a point p. Conditional on the old realized presences and radii, a pre-edit first coverer at a noncompulsory age can be removed on this step only by its fresh independent trial, of probability at most 1/K. For compulsory removal use an unconditional bound over the tape. At most K^2 chronological candidates of age less than K^2 have centers within 2r of p. A candidate reaching age K^2 must previously have survived the K^2-K trials at ages K,\ldots,K^2-1. Consequently

The last inequality follows, for example, from K^2(1-1/K)^{K^2-K}\le K^2e^{-(K-1)}\le C/K. If d(p,x)>22r, no covering entry can have its age incremented: its center is within 2r of p but would have to be within 20r of x. The retirement probability is then zero. The compulsory part of (7.11) is not asserted conditional on an observed surviving old roster; it averages over the independent tape with the chronological schedule fixed.

For an insertion at time t, level j, and tier h, write

Although the value at a fixed step and level does not depend on h, the indices specify the insertion being charged. The stationary errors are confined to this region, since D_H>22, and the heavy inner ball has zero error. Average (7.11) first over the tape with the full input fixed, and then over input continuations given the true prefix. The insertion event and W_{t,j,h} are fixed by that prefix. The expected stationary counting measure is \mu^+-\delta_x\le\mu^+. Thus the expected stationary error is at most CrW_{t,j,h}/K. This averaging statement is conditional only on the true prefix, not on the complete partition tape in \mathcal F_t.

At a nonheavy insertion, the mover’s error is also covered by CrW_{t,j,h}/K, since W_{t,j,h}\ge\mu^+(\{x\})\ge1. At a heavy insertion, its remaining error is at most Cr/K and only occurs if d(y,x)>\gamma_Hr. For each tier,

Here the fixed factor 1/\gamma_H is absorbed into C. These mover errors therefore cost at most CQ. It remains to prove

An auxiliary short roster. We need a potential drop at an insertion to pay the remaining insertion charge. The insertion test excludes young records near x, but an older surviving ball may still cover x. A potential built from the actual surviving centers would therefore have no guaranteed change there. Instead we use an auxiliary roster containing only entries of age less than K. The insertion test then forces a vacant neighborhood of x before the new entry arrives. Random retirement before the age cutoff keeps the expected increases elsewhere small.

This auxiliary roster uses the same deterministic insertion records and ages. An entry starts present at age zero, has independent retirement probability 1/\sqrt K at each subsequent age increment, and retires compulsorily at age K. Its sole output is the deterministic expected function below; it does not enter the partition. Let \rho_L be the clipped increasing ramp on [1/8,1/4], taking value one at infinity, and set

where \mathcal S is the set of surviving hypothetical centers. The expectation is over these auxiliary lifetimes, given the chronological schedule. The function g lies in [0,1] and has r\Lip(g)\le8; it is a deterministic function of the true prefix, and is unchanged at noninsertions.

At an insertion the test excludes all old centers of age less than K within r/2 of x. Every hypothetical survivor has age less than K. Hence before insertion g=1 throughout B(x,r/8), while the new age-zero entry gives g=0 there afterward. Elsewhere couple old and new hypothetical lifetimes by continuing the old trials. If the old ramp at p can increase, a nearest surviving center within r/4 of p, selected by a fixed tie rule, must retire. Its noncompulsory fresh trial has probability 1/\sqrt K. There are at most K possible compulsory candidates within r/4 of p by Lemma 7.3, and a candidate reaching age K must have survived K-1 previous trials. Thus

The last bound follows by comparing the second term with K\exp(-(K-1)/\sqrt K); its ratio to K^{-1/2} is bounded over integers K\ge2. Only centers within 20r of x change age. Therefore positive changes of g are supported in

The auxiliary estimate is O(K^{-1/2}), whereas the bound used for actual retirements is O(K^{-1}). The exponentially large choice of K_h will make the auxiliary error small enough compared with the insertion gain.

The insertion gain in the pilot. Fix an insertion, abbreviate W=W_{t,j,h}, and let z be an old minimizer of the second-template pilot at \mu^+ and g_{\mathrm{old}}. Its residual R_z(p)=1-\sum_s z_s b_s(p) lies in [0,1]. The change of its objective when g is edited is exactly

At a nonheavy level, its positive part is at most CrW/\sqrt K. Indeed the residual increase is supported in B(x,21r). Any increasing-coefficient site lies in that same ball, and its surcharge support lies in B(x,(21+2R)r)\subset B(x,D_Lr). At any test point the weights of all sites with nonzero a_s sum to at most one, by the pilot capacity constraint and 2R<D_*. Now apply (7.15) to both terms of (7.17).

At a heavy level the same bound holds with the annular definition of W, rather than the possibly much larger inner mass. To see this, every possible increasing-coefficient site satisfies r/8<d(s,x)\le21r. Since 1/8-\gamma_H>\sigma and 21+\gamma_H<R, its bump a_s equals one throughout B(x,\gamma_Hr). Its b_s-support lies inside B(x,D_Hr). Writing M_H=\mu^+(B(x,\gamma_Hr)), the coefficient of z_s in the old objective, divided by r, is at least

Deleting that weight preserves both capacity and separation constraints, so optimality forces z_s=0. Hence no surcharge increases in (7.17); the residual increases only in (7.16), a subset of the heavy annulus in (7.12). Its positive contribution is again at most CrW/\sqrt K.

It remains to exhibit the negative contribution. Put M_L=\mu^+(B(x,\gamma_Lr)). Qualification and the definition of W give, in both the heavy and nonheavy cases,

There are two exhaustive cases.

If some site s within 3\sigma r of x has z_s\ge1/2, then g(s) drops from one to zero because 3\sigma<1/8. On the entire heavy annulus \gamma_Hr<d(p,x)\le D_Hr, the bump a_s(p) equals one: the lower distance is greater than \gamma_H-3\sigma>\sigma in scale units, and the upper distance is less than D_H+3\sigma<R. Its surcharge drop is at least 128rW when the request is heavy. When it is nonheavy, failure of (7.3) says that this annulus has mass greater than \delta_H M_H\ge\delta_H M_L. The drop is then at least 128\delta_HrM_L\ge128\delta_Hre^{-h}W.

If no such site exists, then for every p\in B(x,\gamma_Lr), any contributing b_s(p) has its center within (2\sigma+\gamma_L)r<3\sigma r of x, and has weight less than 1/2. At most one positive site contributes there, since two centers within 2\sigma r of the same point would violate their 5\sigma r separation. It follows that R_z(p)\ge1/2 on this inner ball. The unit drop of g(p) there gives a residual decrease at least rM_L/2\ge re^{-h}W/2.

Combining either negative contribution with the established positive error, and using the old optimum as a candidate for the new minimum, gives absolute c,C>0 such that

Choose C_K sufficiently large, once and for all, that for every h\ge1,

Since K\ge e^{C_Kh}, multiplying (7.19) by e^{-h} yields

For each tier apply Corollary 6.4 with its held function (7.14) and fixed weight e^{-h}. The template and Lipschitz constants are the same for all tiers, and \sum_{h\in\mathcal H_k}e^{-h}\le\sum_{n\ge1}e^{-n}<\infty. Thus the filtering and summed drift budgets remain C\ell Q, with no factor equal to the number of tiers. At noninsertions there is no parameter edit. At insertions (7.20) pays exactly the desired charges. The potentials are nonnegative and their total initial value is at most 2k\sum_jr_j\sum_he^{-h}. This proves (7.13).

Finally sum the per-member case table over all insertions, add the noninsertion estimate (7.10), and telescope the noncoverage potentials. The expected retirement errors are covered by (7.13) and the heavy-mover geometric sum. Their terminal nonnegative values can be discarded. This proves the lemma with an initialization bound independent of the law and horizon.□

Proof of Proposition 7.1. Let \mathcal A_j be the fixed level alphabet in Lemma 7.4, and take the tree of all prefixes of words in \mathcal A_1\times\cdots\times\mathcal A_J, including unused words. Initially the center structures are empty and the map uses singleton labels. At every step map a point to its complete string of final keys. The last-level cell diameter is at most 40r_J, less than the minimum nonzero distance of Y; hence last-level cells are singletons, giving injectivity and a requested leaf with anchor exactly equal to the actual request.

For any two words u,v,

Indeed, if their first disagreement is j, the left side is r_{j-1}=\tau r_j. For each member on each step, first edit all level keys at its old physical position, and then move it to its new position under the final map. The triangle inequality for key disagreements bounds the right side of (7.21) by the heavy edit charges, all tier edit charges, and the final-map physical disagreements. The first two have budgets C\ell Q+D by Lemmas 7.2 and 7.6. Only the designated mover has a nonzero final physical disagreement; (7.9), applied after fixing the true input and hence that member’s old position, bounds its expected charge by C\ell d(x,y). Averaging over inputs and summing proves (7.2); \tau is absolute.

All initialized potentials above are bounded by fixed multiples of k(1+|\mathcal H_k|)\sum_jr_j. Their number of time updates never enters the bound. The finite pools and the full prefix tree likewise depend only on Y,k and the chosen absolute constants. Consequently the additive constant is uniform over input laws and horizons.□

Proof. Taking differences in (8.1) and using the triangle inequality gives

The root term in the first sum vanishes because its allocation is always k. This proves (8.3), including the root’s parked mass. The bound q_{t,v}\le C_0m_{t,v} implies m_{t,v}>0 whenever q_{t,v}>0. Since Y is finite, some point mapped below v then has positive posterior counting mass. It is a witness. The anchor-distance assertion is part of Lemma 7.4: a level key is a heavy ball of radius at most 20r_j, a smaller roster ball, or a singleton.□

Proof. The payment is a tangent gap, equivalently the Bregman divergence for the convex function s\log s [9]. For u,s\in[1,k+1], the tangent at u to f(s)=-s\log s is

It is affine in s, with slope of absolute value at most \ell. A refresh u\to s releases

For completeness, if s\ge u the left side equals \int_u^s(s-z)z^{-1}\,dz, and if s\le u it equals \int_s^u(z-s)z^{-1}\,dz. Bounding the denominator by \max(s,u) gives the inequality. At failure of (8.9), |s-u|\ge(1-\rho^{-1})\max(s,u), so

We check the input budget for the weighted sum of these tangents. Let N_{t,j,\lambda}^{\rm key} be the actual number of hidden members whose level-j key at time t is \lambda. Filtering replaces \E[N_{t-1,j,\lambda}^{\rm key}\mid\mathcal F_{t-1}] by \E[N_{t-1,j,\lambda}^{\rm key}\mid\mathcal F_t], using the old map and old reference. Its signed contribution has conditional expectation zero. Drift then replaces this old hidden count by the new count, with both conditioned on \mathcal F_t.

If a member’s two mapped leaves first differ at level j_0, the radius sum of its possible level-key disagreements is at most

At one level a member changes at most two heavy-slot indicators, one for the departing key and one for the arriving key. Applying this pathwise to the coupled hidden trajectory and then taking conditional expectations gives

Thus the tangents’ expected total signed input increase is at most 2\ell P.

The tangents need not be nonnegative. Their endpoint values nevertheless have a uniform bound:

Write L_H=\sum_j r_j|\Lambda_j^H|, a finite quantity fixed before the input law or horizon is chosen. The absolute value of the summed tangent potential is at most (k+1)(1+\ell)L_H at both endpoints. Telescoping its signed changes over every step, and using (8.13), proves (8.10), for example with C=288 and D_{\rm size}=288(k+1)(1+\ell)L_H. Filtering is included on all steps before the decision to refresh; it is not restricted to the adaptively chosen refresh events.□

Proof. Call the levels in the sum selected, and abbreviate their numerator to b_j. Distinct heavy centers at one level are separated by more than 100r_j, proving uniqueness. Their radii are at least 16r_j; therefore the selected heavy ball contains B(y,r_j). Heavy precedence and the size comparison imply

Here \mu is the posterior counting measure of the fixed state.

We also have, for every level j, the cumulative capacity estimate

To prove it, consider each positive park counted on the left. At its depth i, a validity witness lies within 20r_i of its anchor, hence within 27r_i of y. Group all these parks by their depth-j ancestor v. Their sum in each group is at most q_v by (8.2). The group has at least one witness z within 27r_i\le27r_j of y. Every point with prefix v shares its level-j cell with z, and that cell has diameter at most 40r_j. All such points therefore belong to B(y,67r_j). Regions of distinct depth-j prefixes are disjoint, so their posterior counts sum to at most \mu(B(y,67r_j)). Summing q_v\le C_0m_v proves (8.19).

For an explicit scale summation put, at every level,

Both are between 1 and k+1. Extend B_j=k+1 for j\le0. Since \tau\ge2, the fixed offset p=7 satisfies \tau^p\ge67, and hence A_j\le B_{j-p}. It follows that

The final inequality cancels the common middle terms; at most p uncancelled positive terms remain, each at most \log(k+1), and the remaining terms are nonpositive. This includes J<p.

There are at most p\log(k+1)/\log2 levels with A_j>2B_j. Their contribution is O(\ell) by (8.16). Partition the remaining selected levels into groups

For a nonempty group let j_a be its smallest, hence coarsest, index. By (8.18), every denominator in this group is at least 2^{a-1}/\rho. By (8.19),

Its total coefficient is consequently at most 4\rho C_0. There are at most 1+\log_2(k+1) groups, proving (8.17). All these statements hold for each individual state and point, with no averaging and no conditioning on a future request.□

Proof of Proposition 8.2. Use the clipped ramp

For a completed state define

This is the posterior expectation of the sum of the same terms over the hidden members assigned to each key. The ramp measures mass away from the anchor. When a heavy label is reused at a new request, the concentrated mass is far from its old anchor and close to its new one, so the anchor change decreases the potential. Dividing by the held key size makes this decrease comparable to r_jb_{t,j,\lambda}, the travel charge, rather than to its product with comparator mass.

The potential is nonnegative. Moreover, at a completed state the normalized integral is at most \rho, so

The last inequality follows from (8.2), since each park occurs at just one depth and r_j\le r_0.

We now decompose the change of (8.21) in a specified order. This is an accounting order: the current partition and allocation are already available from the fractional history. Old parameters are held until their indicated substep.

Filtering with old membership and all old parameters. In the hidden-member expression for \Phi_{t-1} retain the old locations, old key map, old anchors, old parks, and old references. Replace conditioning on \mathcal F_{t-1} by conditioning on \mathcal F_t. The coefficients and the old map are \mathcal F_{t-1}-measurable. Thus the tower property makes this signed potential change have conditional expectation zero. We perform this comparison on every step, before any refresh or anchor event is selected.

Drift to new membership and new locations. Use the coupled hidden trajectory, now conditioned on \mathcal F_t, but continue to hold all anchors, parks, and size references at their old values. For a member whose level key changes, its total possible positive change among heavy slots is at most C r_j, by (8.16) and 0\le\kappa\le1. Summing (8.14) over members and steps pays these terms by CP in expectation. This includes changes to heavy membership caused by partition edits, regardless of physical movement.

For unchanged membership in a heavy key, the same old anchor appears in both ramp terms. If the old location is y and the new one is z, then

Indeed \kappa is 1/3-Lipschitz and cannot increase from a point where it already equals one. Lemma 8.4 bounds the sum of the coefficients on the right by C\ell, for every old point y and the old fractional state. This pointwise bound remains valid when that y is sampled in the coupling conditional on the new history; we require no independence between the old mover and the new request. Only the designated comparator mover changes physical position on this step. Summing (8.23) therefore costs at most C\ell e_x conditionally, and at most C\ell Q in total expectation. The entire drift budget is C(P+\ell Q).

Refreshing the size references. At this point each integral uses the new key membership and new posterior locations, but still the old anchor. For one label write this integral as I, its new size as M, and s=1+M. Always 0\le I\le M. At a refresh from u=\widehat m^{\rm old} to s the change is

If s\ge u this is nonpositive. If s<u, its positive part is at most r_jb^{\rm old}I/s\le r_jb^{\rm old}. The old completed state gives b^{\rm old}\le\rho C_0 u by (8.16). Hence all positive refresh jumps are at most a constant times the charge in (8.10). This argument does not assume that the new integral is controlled by the old denominator.

Updating the parked amounts. The new size references now satisfy \widehat m^{\rm new}\ge(1+M)/\rho, whether refreshed or retained. Consequently I/\widehat m^{\rm new}\le\rho. Replacing b^{\rm old} by b^{\rm new} changes the potential by at most \rho r_j|\Delta b| in absolute value. Equations (8.5) and (8.3) give the expected total budget

Updating anchors and collecting the travel payment. An absent final key has zero integral and zero new parked mass, so choosing its placeholder anchor costs nothing. A newly present key had b^{\rm old}=0: the fresh-label rule ensures that it was absent from the preceding map. Its anchor initialization can increase the potential by at most

which is another copy of the variation budget (8.24). A retained key with unchanged anchor contributes zero.

It remains to consider a retained moving heavy label at an update for the request x, at radius r=r_j. Its new anchor is x, its old anchor a satisfies d(a,x)>8r, and its new key region is the entire new heavy ball C. Put

The served comparator contains x, so H\ge1. The new heavy ball contains this inner ball and is contained in B(x,D_Hr). The heavy condition (7.3) therefore gives

The last inequality is exactly where the inner mass H\ge1 is needed; it accounts for the added one in the normalization.

On B(x,\gamma_Hr) the old ramp is one because d(a,z)>(8-\gamma_H)r>7r, and the new ramp is zero because d(x,z)\le\gamma_Hr<4r. Outside this inner ball but inside C, the ramp can increase by at most one, and that region has mass at most \delta_H H. Hence changing a to x changes the unnormalized integral by at most -(1-\delta_H)H. With the new park and new reference already in place, (8.25) shows that the potential decreases by at least

Here we used the absolute choices \gamma_H<1/100 and \delta_H<1/100. Thus this payment is uniform even when the retained park remains at exactly the same tree vertex.

Combining the five substeps, summing signed changes over all times, and taking expectations yields

The filtering contributions have vanished by conditional expectation; the size-refresh estimate pays their later adaptively selected consequences. Use (8.22) and \ell\ge1 to obtain (8.8), with an additive constant bounded by C(D_{\rm size}+kr_0). Finally, (8.6) proves the asserted bound for actual anchor displacement.

The only scale summations used were the geometric sum (8.14) and the fixed-offset and dyadic sums in Lemma 8.4. Their constants are independent of the height. The finite label pools enter only the endpoint constant D_{\rm size}, and their persistent tracker states ensure that no initialization allowance is charged again when a label is recycled.□

Proof. All expectations in this proof are taken under the given joint distribution; no independence assumption is made. Set l_i=\lfloor b_i\rfloor and u_i=\lceil b_i\rceil. Clip X_i into [l_i,u_i], obtaining Y_i. For each coordinate,

Indeed, if a_i\le b_i, upper clipping is impossible. Lower clipping either does nothing, or l_i>\lfloor a_i\rfloor, in which case every possible X_i is at most l_i and its expected cost is l_i-a_i\le b_i-a_i. If a_i\ge b_i, the symmetric argument applies to upper clipping. This includes integral targets and equality of endpoints. Summing (9.3) gives \E\|Y-X\|_1\le T.

For each state, adjust Y within the integer intervals [l_i,u_i] until its sum equals the actual value of N, obtaining Z. The adjustment is always possible: the sums of allowed vectors comprise every integer between \sum_i l_i and \sum_i u_i, and both endpoint integers of \sum_i b_i lie in that interval. Increasing coordinates only, or decreasing coordinates only, as needed, costs exactly |N-\sum_iY_i|. A fixed coordinate order makes this choice deterministic. Thus, writing L=\E\|Z-X\|_1,

Only the means of Z may now be wrong. Requiring \E[X'_i\mid N]=b_i would force N=\sum_i b_i on every positive-probability event. We instead repair the means under the given joint law while preserving each state’s actual total.

To construct this repair by finite optimization, let

An allowed vector is specified by a subset A\subseteq H of coordinates rounded upward. Its cardinality is N-\sum_i l_i, and hence is either s or s+1. If \sum_{i\in H}f_i is integral, only s occurs. The preliminary vector Z specifies such a subset A_0 in each original state.

For every original state \omega=(X,N) of positive probability, consider all probability distributions on subsets of the required cardinality for that state. Their product is a nonempty compact finite-dimensional set. A choice in this product is precisely a randomized kernel that keeps the observed total N fixed. Minimize on it

Here |A\mathbin{\triangle}A_0| is the number of coordinates changed; it equals the \ell_1 change of the associated integer vectors. A minimum exists by continuity. Let p_i=\Pr(i\in A) at a minimizer. Since every outcome has the required total,

Consequently, if a discrepancy remains, there are distinct indices i,j with p_i>f_i and p_j<f_j.

First suppose that a supported state-and-subset pair has i\in A, j\notin A. On a sufficiently small amount \varepsilon>0 of its probability mass replace A by A\setminus\{i\}\cup\{j\}. This preserves that state’s total. Choose \varepsilon no larger than the two discrepancies and the mass of this state-and-subset pair. The sum of marginal discrepancies falls by 2\varepsilon, whereas the first term in (9.5) rises by at most 2\varepsilon. This contradicts minimality.

In the remaining case, no supported subset contains i without j. Because p_i>f_i>0, some supported subset A contains both. Because p_j<f_j<1, some supported subset B contains neither. Their cardinalities differ by at most one. There must therefore be an index h\in B\setminus A: otherwise B\subseteq A\setminus\{i,j\} would give |B|\le|A|-2. On equal sufficiently small probability masses \varepsilon of these two state-and-subset pairs, make the changes

Each change occurs within its own original state and preserves that state’s total. The marginal of h does not change, the marginal of i decreases by \varepsilon, and that of j increases by \varepsilon. The Hamming cost in (9.5) rises by at most 4\varepsilon, by the triangle inequality for symmetric difference. The discrepancy penalty falls by 20\varepsilon. Again this is a strict improvement. This argument allows the two subsets to belong to different original states and different values of the rounded parent; it does not alter their probabilities or totals.

Thus every minimizer has p_i=f_i for all i\in H. The other coordinates are fixed integers, so the corresponding vector X' has all required means. Comparison with the kernel that always keeps A_0 gives

Combining with (9.4) proves

For initialization, choose in each state N any allowed subset of the required size, and minimize the same objective relative to that subset. The exchange argument still proves that the minimum has the desired means; it used only the correct mean and the two possible values of N. If H is empty, N=\sum_i b_i and the sole allowed vector is b itself, so no repair is needed. This proves the initialization assertion as well.□

Proof. We first prove the movement estimate in the tree. For an internal vertex v and time t, define

The local lemma, conditional on \mathcal F_t, gives

Since p_v^\circ=q_v-\sum_iq_i,

Multiply by r_{|v|}, sum over internal vertices and times, and take expectations. Every nonroot vertex occurs once as an ordinary child, and \Delta q_{\rm root}=0. Thus

The same weighting of the parent terms gives

because the root count is fixed and the internal nonroot vertices are a subset of all nonroot vertices. Dropping the nonnegative parking movements from the local left-hand sides now yields the exact recurrence

All sums are finite. For \tau\ge22 this gives N_{\rm rnd}\le(128+64/\tau)V\le132V, proving (9.7). In particular, initialization of the rounding does not introduce a new additive variation term. The same absolute \tau can satisfy this threshold and the allocation theorem’s absorption threshold.

We next describe the matching in the tree. Give the edge entering a nonroot vertex v length r_{|v|-1}. The consistency identities in (9.1) imply that n_v(t) is the total number of integer parks in the subtree at v. First match \min\{c_v(t-1),c_v(t)\} old and new copies at every identical vertex v. The unmatched copies define integer supplies and demands with equal total. Starting at the leaves, cancel supplies against demands whenever they meet, and carry the uncancelled copies to the parent. At the edge entering v, the number of copies carried is exactly |\Delta n_v(t)|: the signed imbalance in that subtree is \Delta n_v(t), and after cancellation all remaining copies have the same sign. The root has zero final imbalance. Following each matched pair’s path therefore gives total tree length exactly

This also proves the lower bound for any matching, since each subtree’s net imbalance must cross its entering edge. Fixing orders for cancellations makes the chosen matching a function of the current and previous rounded states.

Every occupied vertex has a current validity witness. Indeed c_v(t)>0 implies p_v^\circ(t)>0, since the only balanced rounding of zero is zero. Hence q_v(t)>0, and the allocation domination q_v(t)\le C_0m_v(t) implies m_v(t)>0. Some point of Y must then have the prefix defining v. This is also the witness assertion of Lemma 8.1. At a nonroot vertex of depth j, its witness is within 20r_j of the vertex’s current anchor, by Lemma 7.4.

Consider a matched old vertex u and new vertex v with u\ne v. Let their last common prefix be w of depth j. If j\ge1, choose an old witness y_- for u and a new witness y_+ for v. Write a_-(z) and a_+(z) for an anchor before and after the step, respectively. Both witnesses use the same depth-j key at w in the two consecutive maps. By the fixed-alphabet construction, its two anchors are either equal or related by an explicit heavy-ball reuse, and in either case

The witnesses are within 20r_j of the corresponding anchors at w. They are also within 20r_{|u|} and 20r_{|v|} of the anchors of their own endpoints. Since both endpoint radii are at most r_j, the triangle inequality gives

The tree path between distinct endpoints passes through an edge of length r_j: this remains true when w=u or w=v, since then the path starts with the edge to the next depth. Thus (9.13) is at most 120 times this path’s tree length. If j=0, both anchors belong to Y, so their distance is at most \diam(Y)=r_0. Their path crosses an edge of length r_0, also when one endpoint is the root. The same bound follows. Only occupied vertices were used in this reasoning; no assertion about distances associated with nonexistent prefixes is needed.

It remains to pay for the copies matched at one and the same vertex. The root anchor is fixed, so it contributes zero. For a nonroot vertex v of depth j, put h_v=\min\{c_v(t-1),c_v(t)\}. If its anchor moves while both copies are occupied, its last label is retained across the step. Only heavy labels can move in this way, and the displacement is at most 40r_j. Write E_{t,j,\lambda} for the event that label \lambda is retained and moves at this step. This event and both anchors are \mathcal F_t-measurable. Since h_v\le c_v(t), regardless of any correlations created by the matching,

Summing first over all depth-j vertices with last label \lambda turns the right-hand side into b_{t,j,\lambda}\one_{E_{t,j,\lambda}}, in the notation of Section 8. Summing over labels, levels and times pays the expected cost of all these coincident-vertex matches by 40T_{\rm anchor}. Together with (9.12) and the bound for distinct vertices, this proves (9.8).

Finally let x be the current request. Its assigned leaf has q_v\ge1 by Theorem 3.1, so balancedness gives c_v=n_v\ge1. At level J, a point assigned to a ball key is within 20r_J of that key’s center. Since 40r_J is smaller than the least positive distance in Y, this point equals the center. A fallback key is anchored at its point as well. The anchor of the request leaf is therefore exactly x, and the simulated configuration serves it. The claimed final estimate now follows from (9.7), (9.8), and Proposition 8.2.□

Proof of Proposition 2.2. Fix the finite metric Y, the server number k and the initial tuple s. Choose the absolute separation factor once, sufficiently large for Theorem 3.1 and with \tau\ge22. Fix the scales and the finite alphabets from Lemma 7.4. These choices depend only on Y,k and the absolute construction parameters. For a given finite-support input law at a finite horizon, choose its hidden optimal trajectory and carry out the partition, allocation, anchor and rounding constructions. Their interfaces give absolute constants C_P,C_A,C_T and finite remainders D_P,D_A,D_T such that

In particular the conditional laws used by the allocation are those of the hidden members under the final online map. Filtering keeps the old map with the old hidden variable, and drift uses the coupled old and new maps, exactly as required by the first two estimates. Rounding neither changes those observations nor supplies information to the partition rules.

Here is a census of the fixed objects and their possible endpoint charges in (9.14). Let \mathcal T be the full finite prefix tree, let d_v be the number of children of an internal vertex, and let L_j be the number of label slots at level j. These numbers can be large. They are fixed before the law and horizon are chosen.

1. 1.

   At each fixed vertex and rank, the elementary tracking potential is p(1-p)+(p-p^\circ)^2\in[0,1]. There are finitely many such rank, flag and endpoint-function trackers, indexed by the k ranks of the fixed vertices, with the fixed finite number of versions used in the allocation construction. Their tolerances, including the tolerances of order 1/\ell, have already been fixed. The resulting initialization and endpoint charges are finite functions of k and the vertex index, rather than of a trajectory’s number of resets.

   At an internal vertex, the sizes, core sums and cap scales are bounded by fixed multiples of k. The proportion variables have the fixed simplex or bounded-\ell_1 domains used in their definitions. The primitive bounds in Section 4 therefore bound the absolute values of both proportion potentials by a finite quantity, for example C\ell k(d_v+1) after increasing an absolute constant. The switching potential is bounded by Ck. Initial size and epoch charges likewise involve only these bounded sizes. Multiplying these finitely many bounds by their fixed star weights r_{|v|} and by the fixed coefficients in the local estimates gives a finite common choice of D_A.

2. 2.

   At scale r_j, each pilot potential lies in [0,2r_jk]. There is one heavy template and a finite number of tier templates, the latter with their fixed weights e^{-h}. The heavy distance-ramp and the tier noncoverage potentials lie in [0,r_jk] for each template. Their initial and terminal contributions are bounded by the corresponding finite sums of 2r_jk and r_jk over levels and tiers, with the fixed coefficients from Section 7. Hence D_P can be chosen uniformly.

3. 3.

   Each held key size in Section 8 is in [1,k+1]. The affine tangent potential to -s\log s, evaluated at an argument and reference in that interval, has absolute value at most C(k+1)\ell. The normalized travel potential for a level-j label is nonnegative and at most Cr_jk, because its parked-mass coefficient b/\widehat m is bounded by an absolute constant and its counting integral is at most k. The sums

   \sum_{j=1}^J L_j r_j(k+1)\ell \quad\hbox{and}\quad \sum_{j=1}^J L_j r_jk

   therefore bound all relevant endpoint terms up to fixed coefficients. They give a finite common choice of D_T, including its size-tracker initialization charges.

4. 4.

   The rounding process has no additional variation remainder, by (9.7). Its initial configuration S_0 is a multiset of k points in Y. Consequently the initial minimum matching distance from s to S_0 is at most k\diam(Y), for every rounding outcome.

This list uses persistent state at every fixed slot. A rank or key tracker continues through absence and later reappearance of its label; no new initialization allowance is charged when a slot is reused. Epoch changes and normalization refreshes are paid transitions in the preceding estimates. The alphabets have bounded size because each tier and scale has at most |Y|K^2 relevant roster entries, with fixed additional slots for the label exclusion rule. Fresh random draws at successive insertions do not create fresh tree vertices or fresh potentials. Thus the finite endpoint bounds above hold uniformly over all possible histories, and are summed over slots and templates once. The number of histories, the number of label reuses and the horizon do not enter D_P,D_A,D_T.

To make the final combination explicit, put

Proposition 9.2 and (9.14) give

where \ell\ge1 was used in the last line. Apply Lemma 2.1 from the actual labeled tuple s. It yields a causal strongly lazy policy serving the same requests, with expected cost at most this simulated movement plus the initial matching mismatch. Thus Proposition 2.2 holds with the absolute constant

and, for example, the finite nonnegative constant

All three remainders can be enlarged to nonnegative uniform bounds from the census above. Formula (9.15) consequently depends only on the fixed metric, k, the start and the fixed construction; it is independent of the input law and horizon. Repeated starting positions cause no change, since both simulated configurations and the matching simulation treat repeated points as separate copies.□

Proof. Write Q=\E_{\lambda}\OPT_s(\sigma). We first make the episode length deterministic without changing Q. Let

Extend each nonempty sequence to length L by repeating its last request; extend an empty sequence by L repetitions of s_1. Denote the resulting law on Y^L by \bar\lambda. For every original sequence \sigma and its extension \bar\sigma,

Indeed, restriction of any service of \bar\sigma to its original prefix gives the lower bound. An optimal service of a nonempty \sigma ends with a server at its last request and can serve the extension at zero extra cost. An empty sequence and its extension both have optimum zero. A causal policy designed for L requests can be run on the original sequence and stopped when that sequence ends; its actions on this prefix are identical to its actions on the extension. Thus it is enough to prove the claim for \bar\lambda and then truncate. The policy need not be told the actual stopping time in advance.

If Q=0, every sequence of positive probability has optimum zero. An optimum is attained because there are only k^L possible strings of server labels. A zero-cost service cannot move any server to a different point, so every request lies among s_1,\ldots,s_k. Any strongly lazy policy therefore has zero cost on the law, proving (10.2). We henceforth assume Q>0.

Set

The distinct starting points ensure \Delta>0. The reset word is R consecutive copies of (s_1,\ldots,s_k), of length Rk. For every \rho=(x_1,\ldots,x_L)\in\supp\bar\lambda, choose one optimal labeled service from s, resolving ties by the lexicographic order of its chosen server labels. Write C_t(\rho)\in Y^k for its configuration after request t, and j_t(\rho) for its chosen label. Here C_0(\rho)=s; a label is designated even when the move is zero. Define its reverse word to be

Starting at C_L(\rho), this word can be served by moving labels j_L,j_{L-1},\ldots,j_1 in that order. Before undoing step t the configuration is exactly C_t(\rho), and its designated move returns it to C_{t-1}(\rho). This verifies legality and returns the labeled tuple exactly to s, at total cost \OPT_s(\rho). The assertion also covers zero moves. The reset word then has zero comparator cost.

Fix an integer N\ge1. Sample N independent words \rho_1,\ldots,\rho_N from \bar\lambda, and concatenate, for each i, its forward word \rho_i, its reverse word \rho_i^{\leftarrow}, and the reset word. This is a finite-support law on words of the fixed length N(2L+Rk). All its requests are functions of the sampled forward words and the fixed optimal services; in particular, the law is fixed independently of the online policy’s randomness. Following the chosen optimal service and then its reverse in every episode gives

Proposition 2.2, followed if necessary by Lemma 2.1 with zero initial mismatch, gives a strongly lazy causal policy \mathcal A_N for this experiment with

As usual, specify arbitrary causal strongly lazy continuation rules at histories having probability zero under the experiment law.

Let F_i, H_i, and Z_i be the costs of \mathcal A_N during the forward word, reverse word, and reset word of episode i, respectively. Let A_i be its configuration at the end of that reset word, and define

We claim, pathwise, that

If a complete reset cycle has zero movement, the configuration stays constant throughout that cycle and covers every one of the k distinct points s_1,\ldots,s_k. Since there are exactly k servers, its multiset of positions is the starting multiset. Strong laziness keeps this multiset fixed throughout all remaining reset cycles. Consequently, if M_i>0, every reset cycle contains a positive move. Each such move has length at least \delta, because all positions are in Y. Therefore

If M_i=0, (10.7) follows from nonnegativity. The argument requires equality only of multisets, not of the labels occupying the distinct starting points.

We extract a policy for one forward word. Before receiving any actual requests, choose I uniformly from \{1,\ldots,N\}. Conditional on I=i, generate i-1 fictitious independent forward words from \bar\lambda, together with their fixed reverse and reset words. Using fresh internal randomness independent of these words, simulate \mathcal A_N from s through that entire fictitious prefix. This produces its internal state and a virtual configuration at the start of forward episode i. For each actual request, now give that request to the virtual policy as its next request. Follow its virtual configurations from the real initial tuple s by the strongly lazy simulation in Lemma 2.1.

This defines a causal policy: the fictitious prefix is internal randomness independent of the actual input, the boundary of episode i is known from i, L, and R, and the virtual continuation uses only the actual requests already received. Neither the remainder of the actual word nor its reverse word needs to be generated. After L actual requests, an arbitrary strongly lazy rule extends this policy to all longer inputs.

When the actual forward word is sampled from \bar\lambda, conditional on I=i, the virtual evolution through that word has the same law as the evolution of \mathcal A_N through forward episode i in the experiment. The true simulation starts with mismatch M_{i-1} under this identification, where M_0=0 for i=1. Lemma 2.1 and (10.7) give

In the third line, the charged forward and preceding reset blocks are disjoint parts of the experiment; reverse-block costs and the last reset-block cost are nonnegative uncharged terms. Truncating to an original unpadded sequence can only reduce this expected cost.

Finally take

Then (10.8) is at most (2a+1)\ell^2Q, as asserted. This is a finite choice of N for the given law; no limiting policy is used here. The metric-dependent numbers R and N affect only the auxiliary experiment and not the coefficient in (10.2).□

Proof. There is nothing to prove for an empty collection. Otherwise let Y be the finite submetric containing all starting points and all points appearing in the sequences. It has positive diameter. Every server position during a legal service is an initial position or a previously requested point: each permitted move is to the current request. Therefore passing from X to Y changes neither the legal label strings nor their costs, and

Let \mathcal H_0 be the finite set of decision histories whose request prefix is a nonempty prefix of some \sigma_i, with every possible previous label string included. This is the finite distributional minimax principle associated with Yao [29], applied to excess cost. A deterministic policy on this set is a map \pi:\mathcal H_0\to[k]. There are finitely many such maps; write their set as \mathcal D. For each \pi\in\mathcal D, put

The set K\subseteq\R^m is compact, being the continuous image of a finite-dimensional compact simplex, and is convex.

We claim K\cap(-\R_{\ge0}^m)\ne\varnothing. If not, minimize the continuous function

over K, and let z_* be a minimizer. Put w_i=\max((z_*)_i,0). The supposed disjointness implies w\ne0. For every z\in K the segment z_*+t(z-z_*), 0\le t\le1, lies in K. The right derivative of f along this segment at t=0 is nonnegative. Since the scalar function u\mapsto\max(u,0)^2 is differentiable, including at zero, this says

It follows that

Normalize w to the probability weights \lambda_i=w_i/(\sum_jw_j) on the target sequences. Lemma 10.1, applied on Y, supplies a randomized causal policy with nonpositive expected excess cost for this law.

Every randomized causal policy, restricted to this finite history set, has its vector of expected excess costs in K. To see this directly, fix its internal random tape, independent of requests. Run the fixed tape on each of the finitely many request prefixes. This determines a deterministic rule at histories compatible with those runs; assign arbitrary choices at incompatible histories. The resulting member of \mathcal D reproduces its actions on every \sigma_i. There are only finitely many possible rules, so their probabilities form a convex combination of the vectors v(\pi). Each event defining such a rule is a finite combination of events for choices on fixed finite inputs and is measurable. Consequently the expected excess for the law with weights \lambda_i is strictly positive by (10.11), a contradiction. This proves the claim. Choose weights \theta_\pi whose convex combination lies in the nonpositive orthant. Sampling \pi with these weights at the start would give (10.9).

For later compactness we convert this finite mixture to behavioral choices, without placing any law on requests. This is the perfect-recall conversion of mixed to behavioral strategies [22]; the formula below makes its request-independent meaning explicit. At a history h=((x_1,\ldots,x_t),(j_1,\ldots,j_{t-1}))\in\mathcal H_0, let

If Z(h)>0, define

If Z(h)=0, choose any probability vector, for example one concentrated on label 1. Induction along a fixed request sequence shows that the probability of each label prefix under these choices is the total \theta-weight of policies consistent with that prefix. Indeed, when this weight is positive the next factor in (10.12) is exactly the ratio of the extended prefix weight to the old weight; when it is zero the prefix is unreachable. Thus the complete label strings, and therefore their costs, have the same law as in the original mixture on each \sigma_i. Set p_h arbitrarily at histories outside \mathcal H_0 to obtain the asserted policy on all of X. Formula (10.12) conditions only on consistency of past choices along a specified request prefix, not on an assumed distribution of requests.□

Proof. The set of all decision histories is

Let

Thus a point of \mathcal P specifies a behavioral policy at all histories. Each factor \Delta_k is compact, so Tychonoff’s theorem makes \mathcal P compact in the product topology [19, Chapter 5, Theorem 13]; see also [28]. This application uses the usual set-theoretic choice principle and permits an arbitrary index set \mathcal H.

First record the exact dependence of a fixed-input expected cost on these coordinates. For \sigma=(x_1,\ldots,x_m) and a label string j=(j_1,\ldots,j_m)\in[k]^m, let c_s(\sigma,j) be its deterministic service cost from s. Explicitly, begin with the tuple s, replace coordinate j_t by x_t at step t, and sum the distances replaced. These costs are finite, even when X is unbounded, since a fixed input and the starting tuple contain only finitely many points. For p\in\mathcal P the expected cost is

For the empty sequence this is zero. For any fixed nonempty sequence, it is a polynomial in finitely many coordinates of p, hence a continuous function of those coordinates. Consequently the constraint

is closed in those finitely many factors.

For each finite input \sigma, let

These sets are closed by the finite-coordinate continuity just proved. Every finite subcollection has nonempty intersection by Lemma 10.2: that lemma supplies a behavioral policy defined on all histories which satisfies all the selected constraints. The finite-intersection property in the compact space \mathcal P therefore gives

Choose p in this intersection. No bound on the diameter or cardinality of X enters this argument. Boundedness is needed only for the cost of one fixed finite input, which was established before Equation (10.14).

It remains to realize these choices as one randomized online policy. At each request use the current history h and choose the next label with probabilities p_h(1),\ldots,p_h(k). For example, take independent uniform random numbers in [0,1) and choose the first label whose cumulative probability exceeds the next number. Only the revealed request prefix and past labels enter this rule. One can also implement all times on the single probability space [0,1) with Lebesgue measure: subdivide its current interval into half-open pieces with relative lengths p_h(1),\ldots,p_h(k), choose the piece containing the initial uniform point, and continue within that piece. Pieces of length zero are empty. On a fixed finite input, the set of seeds giving any specified label prefix is an interval whose length is the product of the corresponding probabilities. Therefore each label choice and the finite total cost are measurable, and their expectation is precisely (10.14).

In particular, the policy is defined for every history before any input or horizon is chosen. Measurability here is exactly that required for each fixed oblivious input; no probability distribution on the request space, or joint measurability in a random request variable, enters the construction. The inequalities already proved for p give (10.13).□

Proof of Theorem 1.1. Fix k\ge2, a metric space (X,d) with at least k+1 points, and any labeled starting tuple s\in X^k, allowing repetitions. Choose a tuple u\in X^k of distinct points, and put

Such a tuple exists by the cardinality assumption. The number D is finite, even in an unbounded metric, since it is the minimum of finitely many finite sums.

For every finite input \sigma, choose an optimal legal trajectory from s. Its existence follows from the finitely many label strings for that input. Apply Lemma 2.1 to follow this trajectory from the initial tuple u. This gives a legal service from u of cost at most \OPT_s(\sigma)+D. This use of the lemma is a pathwise comparison of offline services and does not require computing that trajectory online. Consequently

By Lemma 10.3, one online policy A_u from u satisfies (10.13) for every finite input. Run this policy virtually, and follow its configurations from s by Lemma 2.1. The resulting policy A is causal and can be strongly lazy. Minimum matchings can be selected by a fixed order on the finite set of label permutations, so this simulation also preserves measurability on each fixed input. Pathwise it adds at most D to the virtual cost, and therefore

The explicit additive constant

depends only on the metric, k, and the fixed choices of starting tuples. It is independent of the input and its length. When s already has distinct entries we may take u=s, giving D=B=0.

Finally, for k\ge2 we have \log(k+1)\ge\log3>1 and hence

Thus (10.18) proves the theorem with the single absolute constant C=4(2a+1) and the finite B in (10.19). All policy choices were fixed for the specified metric and initial tuple, so the same policy serves every finite sequence and every horizon.□