diff 3d9cbca..f985ea4 k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt
index e69de29..2c2abc9 100644
--- a/k_server_squared_log_v2.txt
+++ b/k_server_squared_log_v2.txt
@@ -0,0 +1,3995 @@
+========================================================================
+  RANDOMIZED K-SERVER IN THE PLANE... NO WAIT, IN ANY SPACE AT ALL:
+  WHY THE BEST GUARANTEE IS ABOUT (LOG K) SQUARED
+  A friendly, complete tour for a smart high-school reader
+========================================================================
+
+by way of explanation of the paper
+  "Squared-logarithmic randomized k-server on arbitrary metrics"
+(the main theorem, the ideas, and the proof architecture)
+
+This document is written so that a curious high-school student can
+read it from beginning to end and understand what the paper proves
+and how it proves it. Every technical term is defined when it first
+appears. Nothing is hand-waved. A short glossary at the end repeats
+the notation.
+
+If you know what a set is, what distance means on a number line,
+what an average is, what log base 2 means, and what "power of 2"
+means, you can read this. You do NOT need to know any graduate
+mathematics.
+
+All logarithms in the original paper are natural logarithms (base e).
+Changing to base 2 multiplies every log by a fixed number 1/ln 2 and
+does not change any "order of growth" statement. Where a reader may
+prefer base 2, we say so.
+
+------------------------------------------------------------------------
+CONTENTS
+------------------------------------------------------------------------
+ 0. A 60-second summary
+ 1. What is the k-server problem?
+ 2. Competitive ratio: how we grade an online strategy
+ 3. Randomness, and the oblivious adversary
+ 4. The history: from k to (2k-1) to log k to log^2 k
+ 5. The main theorem, stated in plain English
+ 6. The big picture: how the proof is built
+ 7. The game board: metrics, servers, costs
+ 8. Lazy simulation: why we can copy a virtual solution
+ 9. Hidden optimal solutions and their shadow (posterior measure)
+10. The tree: approximations by hierarchically separated trees
+11. The allocation theorem: sharing k units up a tree
+12. The pilot potential: a brake for changing partitions
+13. Online partitions: heavy balls and chronological rosters
+14. Parked mass and moving anchors: paying for reused labels
+15. Rounding: from fractional mass to integer servers
+16. Transfer: from one law to one policy on any space
+17. Assembling the final bound: where each log lives
+18. Honest limits: what the paper does NOT claim
+19. A one-page glossary
+20. A how-to-read-the-paper map
+
+------------------------------------------------------------------------
+0. A 60-SECOND SUMMARY
+------------------------------------------------------------------------
+
+Imagine k taxi drivers in a city. Customers call in one at a time
+and each call must be sent a taxi. You must drive some taxi to the
+customer and every meter driven costs you. You do NOT know future
+calls. You must decide online.
+
+The k-server problem is the clean mathematical form of this. The
+"city" is any metric space (any set with a distance function obeying
+the triangle inequality). You have k "servers" at points of that
+space. A request arrives at a point of the space, and one server
+must visit it, moving any distance. The total distance moved is the
+cost.
+
+The paper answers a fundamental question. If an all-knowing referee
+had seen the entire request sequence in advance, they could have
+planned the cheapest possible set of taxi trips. Call their total
+cost OPT. The paper shows:
+
+  There is ONE randomized online strategy such that, for ANY metric
+  space, ANY starting positions of the k servers, and ANY sequence
+  of requests, the expected cost is at most
+
+      C * (1 + log(k+1))^2 * OPT   +   B,
+
+  where C is a fixed absolute number (not depending on the metric,
+  on k, on the starting positions, on the sequence, or on its
+  length), and B is a finite number that may depend on the metric,
+  k, and the starting positions, but not on the requests. If the
+  starting positions are distinct, B can be taken to be 0.
+
+That is the headline. The rest of this document explains what every
+word in that sentence means, why the exponent 2 is correct (it is
+the best possible in the worst case; a lower bound of the same
+shape is known), and how the proof is built.
+
+------------------------------------------------------------------------
+1. WHAT IS THE K-SERVER PROBLEM?
+------------------------------------------------------------------------
+
+1.1 Metrics.
+
+A "metric space" is a pair (X, d). Here X is any set of "points" and
+
+    d : X x X -> [0, +infinity)
+
+is a function called the "distance" that satisfies three rules, for
+every x, y, z in X:
+
+  (M1) d(x, y) = 0  if and only if  x = y.
+       (Two different points are at positive distance.)
+
+  (M2) d(x, y) = d(y, x).
+       (Distance does not care which end is which.)
+
+  (M3) d(x, z) <= d(x, y) + d(y, z).
+       (The "triangle inequality": going straight is never more
+        expensive than going via a detour.)
+
+Examples:
+
+  - The real line, d(x, y) = |x - y|.
+  - The plane with ordinary straight-line distance.
+  - A graph with edge weights, where distance is the length of the
+    shortest path between two vertices.
+  - The "paging metric" with K + 1 points: one special "origin" and
+    K "slots". The distance between any two different slots is 1;
+    the distance from a slot to the origin is 1; the origin to itself
+    is 0. Every pair of distinct points is at distance 1.
+    (This is called a "uniform metric".)
+  - The paging metric can also be seen as a "star": the origin is the
+    center and the K slots are leaves.
+
+The problem works in ANY metric. That is remarkable: the SAME
+strategy is proved to work everywhere.
+
+1.2 Servers.
+
+Fix an integer k >= 2. Imagine k identical "servers". Each server
+sits at a point of X. So the current "configuration" of the system
+is an ordered tuple
+
+    s = (s_1, s_2, ..., s_k)  with each s_i in X.
+
+The label i runs from 1 to k. Repetitions are allowed: several
+servers may stand on the same point.
+
+1.3 Requests and service.
+
+Requests arrive one at a time. A request is a point r_t of X
+("the t-th customer is at r_t"). To serve the request, you must
+designate one server, say the i-th, and move it from its current
+position to r_t. The cost of this move is d(s_i, r_t). All other
+servers stay put. If some server is already at r_t, you may serve
+the request with it at cost 0 ("lazy" service).
+
+Repeat for t = 1, 2, ..., H, where H is the number of requests.
+
+The total cost of your service is the SUM of all move distances over
+the whole sequence.
+
+1.4 Offline optimum.
+
+Suppose you COULD see the future. That is, someone hands you the
+whole request sequence r_1, ..., r_H in advance, and you get to
+plan every move knowing what will happen. Given the same starting
+configuration s, what is the smallest possible total cost?
+
+Call that number OPT(s, r_1, ..., r_H). It is a well-defined
+finite number; the minimum is taken over all legal sequences of
+choices of which server to move at each step. (There are only k
+choices per step, so the number of candidate schedules is finite:
+at most k^H.)
+
+OPT is the benchmark. It is the "if you had magic foresight" cost.
+No online strategy can beat OPT; the question is how close it can
+get without foreknowledge.
+
+1.5 Online strategy.
+
+An "online strategy" (also called an algorithm or policy) must,
+at each step t, choose which server to move BEFORE seeing request
+t + 1, t + 2, and so on. It knows:
+
+  - the current configuration,
+  - the requests r_1, ..., r_t up to now.
+
+It must be causal: its choice at step t may depend only on the
+data available through step t. The future is silent.
+
+The k-server problem is the study of the best online strategies.
+
+1.6 Three classic versions of the problem.
+
+  - Paging. X is the "uniform metric" above. A paging system has
+    K slots of physical memory ("the K servers") and calls for one
+    of K+1 "pages" (the origin is the special request that some
+    page is not in memory). Bringing a missing page into memory
+    costs 1; serving a present page costs 0. Classic.
+
+  - Weighted paging. Each page has a "size". Bringing it in costs
+    its size. Slightly more general.
+
+  - Metrical task systems. A broader setting where you also pay a
+    "service cost" that depends on the current state. The paper
+    works in the simplest version (only movement costs) and gets
+    the best known bound there.
+
+  - Metrical service systems. Several tasks at once. Out of scope.
+
+The math paper is written entirely in the language of metric spaces
+and does not privilege any particular real-world story. But taxis
+and paging are exactly what the abstraction is modeling.
+
+------------------------------------------------------------------------
+2. COMPETITIVE RATIO: HOW WE GRADE AN ONLINE STRATEGY
+------------------------------------------------------------------------
+
+2.1 A single number to compare online to offline.
+
+An online strategy A is called "c-competitive" (with an "additive
+term" B) if, for every starting configuration s and every finite
+request sequence sigma = (r_1, ..., r_H),
+
+       cost_{A, s}(sigma)   <=   c * OPT(s, sigma)   +   B.
+
+Read this formula. On the left, what you can actually achieve with
+a causal strategy A. On the right, c times what a magic-foresight
+referee could achieve, plus a small correction B that is allowed to
+depend on the metric, on k, and on the starting configuration, but
+NOT on the request sequence or its length.
+
+The smaller c is, the better the strategy. "c" is called the
+competitive ratio.
+
+If B can be taken to be 0, the strategy is called "c-competitive
+without an additive term" (or "strictly c-competitive").
+
+If c is a function of k, say c = f(k), we say A has competitive
+ratio f(k). The whole game is: how slowly can f grow with k?
+
+2.2 Why we care about k at all.
+
+Here's the surprise. On an adversarial sequence of requests, an
+online strategy with only k servers cannot possibly match a magic
+referee, because the referee can deliver taxis straight to where
+customers WILL be while the online strategy keeps driving away from
+where customers are about to appear. The competitive ratio measures
+exactly how much this foresight gap costs.
+
+Question: is there a function of k that bounds the gap for ALL
+metric spaces simultaneously?
+
+Yes. That's the entire point of the field. But finding the exact
+slowest-growing such f(k) is the hard part.
+
+2.3 The very first theorem: a lower bound.
+
+Manasse, McGeoch and Sleator (1988 / 1990) proved a clean fact:
+
+  For any metric space with MORE THAN k points, no DETERMINISTIC
+  online strategy is better than k-competitive.
+
+That is: for any deterministic strategy A and any such metric,
+there exists a request sequence on which A pays at least k times
+the offline cost (for k = 2 this is a factor 2; for k = 100 it is
+a factor 100). So deterministically, you cannot do better than k.
+
+This was surprising - can the worst case really be as bad as the
+number of servers? And if so, can we do exactly k? Manasse,
+McGeoch and Sleator conjectured that k is achievable.
+
+2.4 The "competitive k-server conjecture".
+
+Conjecture (1988). Every metric space admits a deterministic
+k-competitive online strategy.
+
+Status: 27 years of work; then Koutsoupias and Papadimitriou (1995)
+proved that a specific beautiful strategy works with ratio
+(2k - 1) instead of k. And recently (2026 preprint) Coester,
+Koutsoupias, Zbysinski announced a k-competitive analysis of
+essentially the same algorithm. Either way, the entire deterministic
+range is roughly "a constant times k".
+
+So if you want much less than k, determinism is not enough. You
+have to flip coins.
+
+2.5 The "competitive ratio of a metric" and the metric's geometry.
+
+The worst-case competitive ratio as we vary the metric is a
+geometric property of the metric. For example, the "uniform
+metric" (the paging metric) admits randomized ratio exactly the
+H_k = 1 + 1/2 + 1/3 + ... + 1/k harmonic number. On the real line,
+or on any tree, the situation is dramatically easier.
+
+But the head-line question is: over ALL metric spaces simultaneously,
+what is the best function of k?
+
+2.6 "Worst case over every metric".
+
+The paper's theorem is the following kind of statement:
+
+        for every metric space (X, d),
+        for every k,
+        for every starting tuple s,
+        there is some randomized online strategy A_{X,k,s}
+
+whose expected cost is at most
+
+        C * (1 + log(k+1))^2 * OPT(s, sigma) + B
+
+for every sequence sigma. By "the same strategy works for all
+sequences", we mean: ONE strategy A_{X,k,s}, fixed up front, works
+for every sequence simultaneously. It does not get to be different
+for different problems.
+
+"Expected cost" means: we average over the strategy's internal
+coin flips, treating the request sequence as fixed and chosen
+independently of those flips (see Section 3).
+
+------------------------------------------------------------------------
+3. RANDOMNESS, AND THE OBLIVIOUS ADVERSARY
+------------------------------------------------------------------------
+
+3.1 Why coin flips help.
+
+A DETERMINISTIC strategy can be predicted by an adversary: the
+adversary sees your strategy's code, knows what you will do, and
+picks a request sequence that punishes you. A RANDOMIZED strategy
+can be harder to attack because the adversary cannot see your coins
+in advance.
+
+But we must be precise about who the adversary is and what they can
+observe. This is not a small detail: different "adversary models"
+give completely different strengths of result.
+
+3.2 Three adversary models (only one is used here).
+
+  - Oblivious adversary. The request sequence is chosen ONCE,
+    in advance, independent of the strategy's random tape. It may
+    even depend on the strategy's source code and the starting
+    configuration, but it may NOT depend on the actual coin flips
+    the strategy will use. This is the model in which we ask about
+    "expected cost".
+
+  - Adaptive adversary. The adversary chooses each request knowing
+    the strategy's past random results (but not the next flips).
+    Stronger than oblivious.
+
+  - Adaptive-offline. The adversary is simultaneously playing
+    against you and against an offline "ghost" who is allowed to
+    also adapt. The strongest.
+
+The paper uses the OBLIVIOUS model. This matters in every place
+where the proof uses "conditional expectation". The math paper
+repeats this many times: filtering estimates are made with old
+parameters and BEFORE any adaptive choice. This is why.
+
+3.3 Expected competitive ratio.
+
+Say A is a randomized strategy. Its "cost on a fixed sequence
+sigma" is a random variable (it depends on the coins). Define:
+
+     Expected cost = the probability-weighted average over all the
+     strategy's coin outcomes.
+
+A is "c-competitive with additive B" if, for every sequence sigma,
+
+     E[ cost_{A, s}(sigma) ]   <=   c * OPT(s, sigma)   +   B.
+
+For an oblivious adversary, this is the natural and standard notion.
+
+3.4 The paging special case.
+
+For paging (uniform metric on K+1 points with k servers) the problem
+is exactly the paging problem: you have k slots in fast memory and
+K+1 possible pages.
+
+  - Deterministically, the best ratio is exactly k. (Manasse-
+    McGeoch-Sleator lower bound plus a matching algorithm.)
+
+  - Randomized, the best achievable ratio is exactly the harmonic
+    number
+
+        H_k = 1 + 1/2 + 1/3 + ... + 1/k.
+
+    This is remarkable and clean.
+
+The upper bound is Fleming, Karp, Luby, McGeoch, Sleator, Young
+(1991): a randomized marking algorithm is 2H_k. The exact H_k is
+McGeoch and Sleator (1991).
+
+3.5 What is the harmonic number H_k?
+
+A useful fact from calculus:  H_k is at most 1 + ln k. More precisely:
+
+        ln(k) + 1/k   <=  H_k  <=  ln(k) + 1.
+
+So H_k "is logarithmically large in k" and no bigger.
+
+By convention, the paper of interest uses l = 1 + ln(k+1), and
+everything is stated in terms of l. So O(log k) really means
+O(l).
+
+3.6 The moral.
+
+Randomization can beat k deterministically. For paging it beats k
+all the way down to log k. A natural guess is that on EVERY metric,
+randomization can attain O(log k). That was the "folklore conjecture"
+for about three decades. We will see: it is true that O(log k) works
+as a UNIVERSAL LOWER bound (you cannot do better), but it is FALSE
+that O(log k) works as an upper bound for every metric. Some
+metrics need log^2 k.
+
+------------------------------------------------------------------------
+4. THE HISTORY: FROM K TO (2K-1) TO LOG K TO LOG^2 K
+------------------------------------------------------------------------
+
+This section is the "who proved what" that motivates the main
+theorem. Every fact has a citation in the paper's references at the
+end. You can skip to Section 5 if you just want the statement.
+
+4.1 Deterministic era (1988 - 1995).
+
+  - 1988, 1990. Manasse, McGeoch, Sleator. Introduced the problem.
+    Proved the deterministic lower bound k for metrics with > k
+    points. Conjectured k is achieved.
+  - 1995. Koutsoupias, Papadimitriou. Proved that the "work
+    function algorithm" achieves ratio (2k - 1). Stunning result:
+    one algorithm, all metrics, essentially the same constant for
+    every metric.
+  - 2026 (preprint, Sept). Coester, Koutsoupias, Zbysinski.
+    Announced a k-competitive analysis of the work-function
+    algorithm. This would prove the original conjecture.
+
+4.2 Randomization: paging is easy (1991).
+
+  - 1991. Fleming, Karp, Luby, McGeoch, Sleator, Young. A
+    harmonic lower bound H_k on uniform metrics, and a randomized
+    marking algorithm achieving 2 H_k.
+  - 1991. McGeoch, Sleator. Improved the upper bound to exactly
+    H_k, matching the lower bound.
+
+So paging is completely solved: exact ratio H_k.
+
+4.3 Weighted paging reaches log k (2012).
+
+  - 2012. Bansal, Buchbinder, Naor. Weighted paging in O(log k)
+    competitive ratio, via a fractional primal-dual algorithm plus
+    an online rounding. This is exactly the order achieved by the
+    marking algorithm in the unweighted case, but for a harder
+    problem.
+
+These paging successes fueled the folklore conjecture: "randomized
+k-server should be O(log k) on any metric".
+
+4.4 General-metric upper bounds, polylog (2010 - 2018).
+
+  - 2010 (SODA). Bansal, Buchbinder, Naor. First (fractional)
+    result for general finite metrics after a tree embedding.
+  - 2015 (JACM). Bansal, Buchbinder, Madry, Naor. The first
+    POLYLOGARITHMIC upper bound for arbitrary finite metrics. The
+    bound is
+
+        O( (log^2 k) * (log^3 n) * (log log n) ),
+
+    where n is the number of points in the finite metric. So this
+    factors a log(k)-squared piece (good) and many log(n) factors
+    (not good: not in k alone).
+
+  - 2018 (STOC). Bubeck, Cohen, Lee, Lee, Madry. Improved the
+    bound on "hierarchically separated trees" (HSTs) to
+
+        O(log^2 k),
+
+    using "multiscale entropic regularization". But on general
+    n-point metrics, the STATIC embedding reduction only gives
+
+        O(log^2 k * log n),
+
+    which is not a bound in k alone. The log n factor is the
+    obstruction.
+
+  - 2018 (FOCS). James Lee. Attempted an "evolving, fusible HST"
+    framework that changes the tree as requests arrive. The
+    general competitive-ratio claim was WITHDRAWN in 2021 by an
+    erratum in Section 5.3.2. But the METHOD - "heavy-ball
+    protection" and "accounting for changing partitions" - is
+    the conceptual ancestor of the paper we are explaining.
+
+  - 2026 (ICALP). Coester and Cosson. Made the HST / finite-metric
+    bounds POLYNOMIAL TIME, with total number of random bits
+    independent of the request length. But their general finite
+    metric ratio retains a log n factor.
+
+4.5 Lower bounds (1994 - 2023).
+
+  - 1994 - 2005. Karloff-Rabani-Ravid, Blum-Karloff-Rabani-Saks,
+    Bartal-Bollobas-Mendel, Bartal-Linial-Mendel-Naor. Developed
+    metric decomposition / Ramsey methods, weakening randomized
+    k-server lower bounds upward.
+  - 2023 (STOC). Bubeck, Coester, Rabani. THE RANDOMIZED
+    K-SERVER CONJECTURE IS FALSE. Two main results:
+      (i)  Theorem 11 + Proposition 8. There exist metrics with
+           only (k+1) points requiring competitive ratio
+           Omega(log^2 k), even allowing a FIXED additive constant.
+           This is the sharp negative answer to the folklore
+           conjecture.
+      (ii) Corollary 20. Universal lower bound Omega(log k) on
+           EVERY metric with more than k points. (This matches
+           the paging lower bound and is not contradicted by
+           (i): (i) says SOME metrics need log^2 k, which is
+           more than log k; (ii) says no metric can be easier than
+           log k.)
+
+4.6 What is left? The puzzle of the two logs.
+
+After 2023, the situation is:
+
+  - NO metric has a lower bound worse than log^2 k (BCR).
+  - SOME metric has a lower bound as bad as log^2 k (BCR).
+  - NO constructed strategy for general metrics achieves the
+    log^2 k order. The best constructions retain a log n factor
+    from the static embedding.
+
+The obvious question: can we prove an upper bound of O(log^2 k)
+matching the BCR lower bound? On EVERY metric, not just HSTs?
+
+The paper we are explaining proves exactly this.
+
+4.7 The main theorem in one sentence.
+
+  On every metric, one randomized online strategy has expected
+  competitive ratio O((log(k+1))^2), with a finite additive
+  correction. When starting positions are distinct, no additive
+  correction is needed.
+
+The additive correction is unavoidable when two of the initial
+servers start on the same point, because a "shadow" simulation
+(line 8.3) needs to bridge the gap. In every other case, the bound
+is exact in every input.
+
+------------------------------------------------------------------------
+5. THE MAIN THEOREM, STATED IN PLAIN ENGLISH
+------------------------------------------------------------------------
+
+Here is the paper's headline theorem, fully precise.
+
+Theorem (main). There is a fixed absolute constant C < infinity with
+this property. For every integer k >= 2, every metric space (X, d)
+containing at least k+1 points, and every starting tuple
+s = (s_1, ..., s_k) in X^k, there exist:
+
+  a randomized online strategy A      (one strategy), and
+  a finite number B >= 0              (an additive correction),
+
+such that for every finite request sequence sigma,
+
+        E[ cost_{A, s}(sigma) ]
+              <= C * (1 + log(k+1))^2 * OPT(s, sigma) + B.
+
+The following important caveats are all part of the theorem's
+statement in the paper and are crucial to what the theorem actually
+means:
+
+  (C1) C is an ABSOLUTE constant. It does not depend on the metric,
+       on k, on the starting tuple, on the sequence, or on its
+       length. It is a fixed number that the proof could, in
+       principle, compute explicitly. It is not small; it is
+       "like 4 * (2a + 1)" for some a defined in the proof - some
+       finite astronomical number. The theorem does not try to
+       make it look tight.
+
+  (C2) B may depend on the metric, on k, and on the starting tuple.
+       It may be huge; it may be infinite in principle for an
+       infinite metric. But B is a CONSTANT once the metric, k,
+       and the starting tuple are fixed. It does NOT depend on
+       the request sequence or on its length. So for very long
+       sequences B is negligible compared to the OPT term.
+
+  (C3) The SAME strategy A works for every finite request sequence
+       simultaneously. It is not a sequence-by-sequence strategy.
+
+  (C4) The SAME strategy A works for every horizon H. There is no
+       "the strategy is different for different horizons" caveat.
+
+  (C5) If the initial servers are at DISTINCT points of X, one can
+       take B = 0. Then the competitive ratio is C(1+log(k+1))^2
+       with no additive term at all.
+
+  (C6) The metric space may be INFINITE, UNBOUNDED, or both. There
+       is no finiteness, no compactness, no bounded-diameter
+       assumption.
+
+  (C7) There is NO complexity / efficiency claim. The strategy is
+       mathematically well-defined. The proof does not claim you
+       can run it in polynomial time. (Polynomial-time versions
+       do exist in separate work; Coester and Cosson 2026 is the
+       relevant reference in the bibliography.)
+
+So the theorem's content, morally, is:
+
+  randomization reduces the ratio from "roughly k" (deterministic,
+  across all metrics) all the way down to "(log k)^2", and no
+  better is possible in the worst case (BCR 2023 lower bound),
+  and this is done with ONE strategy on EVERY metric.
+
+The constant of proportionality is fixed once, for all inputs.
+That is the sharp order of the problem in the worst case over
+metric spaces.
+
+Let us double check what "no better is possible" means. The BCR
+lower bound says: there exists a metric on k+1 points forcing any
+randomized strategy to pay at least c' * (log k)^2 * OPT for some
+absolute c' > 0 (up to a fixed additive term). So the upper bound
+ours and the lower bound theirs disagree at most in the absolute
+constant. In that sense the theorem is order-tight.
+
+------------------------------------------------------------------------
+6. THE BIG PICTURE: HOW THE PROOF IS BUILT
+------------------------------------------------------------------------
+
+At the very highest level, the proof has seven steps. Each step is
+an idea you could explain to a friend. Each subsequent section fills
+in the details. You can read this section first, then read
+subsequent sections, and you will always know where you are.
+
+6.1 Step 1: fix a "hidden optimal solution" and watch its shadow.
+
+Idea. Pretend we cannot see the future, but SOMEONE can. Let that
+someone choose, for each possible future, the best sequence of
+server labels. Treat that chosen sequence as a hidden random
+variable "Z" determined by the request sequence. From the revealed
+prefix we can compute the CONDITIONAL DISTRIBUTION of Z. That
+conditional distribution is called the "posterior".
+
+Think of the posterior as a "shadow" of the hidden optimal solution
+projected onto the current observed history. The shadow is what we
+can actually see.
+
+This is a standard trick in online algorithms and it is central to
+the paper. It converts the online problem into:
+
+   "Track the posterior distribution of a hidden optimal solution
+    online."
+
+The posterior is a probability distribution over configurations of
+k labeled servers. It is the thing we want to stay close to.
+
+Now, catching up with a DISTRIBUTION is much harder than catching
+up with a POINT. The whole engineering of the paper is about
+representing the distribution in a compact, trackable form. This is
+where tree embeddings, partitions, and rounding all come in.
+
+6.2 Step 2: reduce the true metric to a fixed tree.
+
+Idea. On a tree, moving servers is easy to analyze. On a general
+metric, it is not. Standard theory says: any finite metric can be
+approximated by a tree with O(log n) distortion - and if you are
+careful and change the tree adaptively, you can hope to keep the
+distortion to log k instead of log n.
+
+But the paper does NOT use an approximation of the metric in a naive
+way. It uses something subtler. It builds ONE fixed finite object
+called a "prefix tree of label strings" whose leaves correspond to
+the points of the metric (approximately), and whose edges carry
+"semantic" weights.
+
+The point of the tree is that the posterior distribution's "serving"
+problem on the tree can be solved and tracked by a fractional
+algorithm, and then realized back in the metric.
+
+6.3 Step 3: allocate fractional server mass on the tree.
+
+Idea. On the tree, we want to keep some real-valued "amount of
+serving mass" q_v at each vertex v, with these rules:
+
+  (i)   The root holds q_root = k, exactly.
+  (ii)  The children of any vertex v hold amounts that sum to at
+        most q_v. (We "spend" all mass going down, or "park" any
+        leftover at v itself.)
+  (iii) For every vertex v, q_v is at most a constant times the
+        posterior expected number of hidden servers in v's
+        subtree. So mass is dominated by the shadow.
+  (iv)  The leaf of every request in the CURRENT tree holds at
+        least 1. So the request is always "servable".
+
+If we can maintain such q_v whose CHANGES stay small (sum of
+r_{depth} * |change| is O(log k) times the shadow's movement), and
+we then round it, we get a strong online algorithm.
+
+This is the content of what the paper calls the "allocation
+theorem". It is the hardest single technical component of the
+paper. It uses:
+
+  - rank coordinates (the probability that a subtree contains fewer
+    than a hidden servers);
+  - convex "rank functions" l^beta(p) with parameters tuned to subtree
+    sizes;
+  - a "simplex tracker" to make proportions vary slowly;
+  - a "side tracker" to handle near-dominant children;
+  - hysteresis to choose between two output rules.
+
+We will explain the conceptual role of each in Section 11.
+
+6.4 Step 4: choose tree partitions that adapt to local mass.
+
+Idea. The tree structure needs to be built from the metric. It
+cannot follow the fastest-changing ball-mass ratios at every scale,
+because doing so would cost another factor of log. Two structures
+solve this:
+
+  - "Heavy balls": balls around requests where the mass is very
+    concentrated. Only ONE change per request per level.
+  - "Chronological rosters": a small list of balls per level,
+    chosen by a deterministic age rule, with a random subroster.
+    Changes cost less on average because of the random retire.
+
+Both structures use the pilot potential (Section 6.5) to PAY for
+changes.
+
+The clever bit is that the coefficient on changes is a LOCAL mass
+ratio, not a global worst case. When the ball-mass ratio is small
+(very concentrated), changes are cheap. When it is large, there are
+few such levels (a telescoping "ball-mass" argument controls the
+sum). This local-ratio trick is the reason the log-n factor
+disappears.
+
+6.5 Step 5: pilot potential - a brake for changes.
+
+Idea. Whenever a partition changes, the allocation q_v will likely
+change too. We want to charge those q-changes to something. The
+"pilot potential" is a compact variational object that gives a
+NUMERICAL potential value small enough that its decreases pay for
+the changes, yet large enough that its increases are bounded by
+O(log) times the hidden mover's physical cost.
+
+Concretely, at each scale r, define a function L_r(mu, g) of a
+measure mu and a function g, as the MINIMUM over certain "vector
+of sites" z of a linear functional. Two properties are proved:
+
+  - L_r is concave in mu, so filtering (revealing more of the
+    history) cannot increase it in conditional expectation.
+  - Its DRIFT (physical movement of the hidden mover at scale r)
+    is at most O(log k) times the mover's distance, by a local
+    concentration argument.
+
+The concavity and drift together make L_r a legitimate potential
+that can be "spent" on partition edits without paying more than
+O(log k) per unit of hidden movement, uniformly in scale.
+
+The "local concentration" step is where the extra log comes from.
+When a scale is "concentrated", the integrator's optimal site is
+almost AT the request, so moving it is cheap. When a scale is "not
+concentrated", the potential is trivially bounded and only a few
+such scales exist by the ball-mass telescope.
+
+6.6 Step 6: real-metric rounding and moving representatives.
+
+Idea. The q_v from Step 3 are REAL NUMBERS. We need k INTEGERS on
+the tree (one per tree vertex, summing to k) whose values stay
+close to q_v in conditional expectation. Also, since the actual
+points of X are represented by tree anchors, we must pay whenever a
+retained tree vertex's anchor moves to a new nearby anchor.
+
+Both are handled by clean local arguments:
+
+  - "Balanced rounding with prescribed random total" gives an
+    integer n_v with the right mean and with |change| at most 32
+    times the fractional changes plus 11 times a small dependence
+    on the parent.
+
+  - "Retained-anchor travel" pays moving anchors using a normalized
+    potential, with a size tracker that resets only when a key's
+    posterior size drifts by a factor of 6/5.
+
+Both are local: no horizon-dependent factor.
+
+6.7 Step 7: transfer from one law to one policy.
+
+Idea. Steps 1-6 prove the theorem for a FIXED finite metric and a
+FIXED finite probability distribution on finite request sequences.
+We need to get rid of that.
+
+Three ingredients in the paper:
+
+  - "Episode amplification". Cleverly concatenate forward, reversed,
+    and reset blocks so that the ADDITIVE term gets amortized away
+    over N episodes. Choose N large enough. This gives a policy
+    with no additive term on a fixed finite metric, distinct start.
+
+  - "Finite separation via Yao". Using the finite minimax theorem,
+    turn "for every single sequence there exists some strategy" into
+    "there is ONE strategy for every sequence in a finite family".
+
+  - "Tychonoff compactness". Take the product of all decision-point
+    simplices (one simplex per possible history). The product of
+    compact simplices is compact. The "for every finite input there
+    is a policy" constraint defines closed subsets of this product.
+    Finite-intersection property says ONE policy works for ALL
+    finite inputs simultaneously.
+
+Together, these remove every dependence on the input law, the
+horizon, and the size of the metric. What remains is exactly the
+main theorem's statement.
+
+------------------------------------------------------------------------
+7. THE BOARD: NOTATION WE WILL USE EVERYWHERE
+------------------------------------------------------------------------
+
+Let us line up symbols that recur in every later section of the
+paper. Learning them now saves confusion later.
+
+7.1 Configurations.
+
+A "configuration" is a multiset of k points of X, one per labeled
+server. That is: a tuple (c_1, ..., c_k). We always allow
+repetitions: two servers can be on the same physical point.
+
+7.2 Matching distance between two configurations.
+
+If A = (a_1, ..., a_k) and C = (c_1, ..., c_k) are two
+configurations, define their "matching distance":
+
+    M(A, C) =  min over permutations pi of {1, ..., k}
+               of  sum_{i=1}^k d(a_i, c_{pi(i)}).
+
+Meaning: if we do not care which server has which label, what is the
+cheapest way to match each a to a distinct c? M(A, C) is the total
+cost of that matching. It ignores labels but respects positions.
+
+Note: M(A, C) is not necessarily d(A, C) - labels sometimes have to
+be "renamed". This is crucial for compositions and for lazy
+simulation.
+
+7.3 Strong laziness.
+
+A strategy is "strongly lazy" if it does nothing when a server is
+already at the request, and otherwise moves EXACTLY ONE server to
+the request. Equivalently: it does not move any server except to
+serve a request, and it moves only one such server.
+
+7.4 Constants and little ell.
+
+Define the "little ell":
+
+    ell = 1 + log(k + 1)          (log is natural)
+
+So ell >= 1 for every k >= 2. "Order O(log k)" and "order O(ell)"
+are the same order.
+
+7.5 Metric geometry convenience.
+
+Fix a FINITE metric Y with n = |Y| points for the main body of
+the argument. It has:
+
+    diam(Y) = max_{y, z in Y} d(y, z)      ("diameter")
+    delta   = min_{y != z in Y} d(y, z)    ("minimum gap")
+
+The minimum gap is positive because Y is finite, so delta > 0.
+
+7.6 Scales (levels).
+
+Fix an absolute "separation" parameter tau >= 2 large enough for
+several later requirements. Define r_0 = diam(Y) and
+
+    r_j = r_0 * tau^(-j),       1 <= j <= J,
+
+where J is chosen so that 40 r_J < delta. In words: r_0 is the
+coarsest scale (about the diameter), each subsequent r_j divides by
+tau, and we stop at depth J when the scale is much finer than the
+smallest point-to-point gap.
+
+There are J + 1 scales. They divide the "interesting" range of
+distances into logarithmic bands.
+
+7.7 The probability law and the horizon.
+
+For most of the paper we work with:
+
+  - a fixed finite metric Y of positive diameter,
+  - a fixed finite horizon H (number of requests),
+  - a fixed probability law on request sequences of length H.
+
+Everything is conditioned on that law. It is an "input law" on
+Y^H. Later, Section 16 removes this law.
+
+7.8 The optimum.
+
+For each realized sequence sigma, choose ONE optimal service
+schedule of the k labeled servers. There are finitely many candidate
+schedules (k^H of them), so, given sigma, some optimum exists;
+resolve ties deterministically. Call the chosen optimum "Z". It has
+k components (one per label) at every time.
+
+The conditional distribution of Z given the prefix sigma_{1..t}
+is the "posterior". It is a probability measure on configurations.
+
+7.9 Counting measure of the posterior.
+
+Think of the posterior as a random configuration Z. Its "expected
+counting measure" mu_t on Y is defined by
+
+    mu_t(S) = E[ number of servers in the set S at time t | prefix ]
+
+for every subset S of Y. Equivalently:
+
+    mu_t = sum_{labels i = 1}^{k} P(Z_t^i in .  | prefix )
+
+Each label contributes one "atom" of a unit of probability at its
+position. The total mass of mu_t is exactly k.
+
+This object replaces "the hidden servers" with something we can
+actually compute and reason about.
+
+------------------------------------------------------------------------
+8. LAZY SIMULATION: A FREE WAY TO COPY A VIRTUAL SOLUTION
+------------------------------------------------------------------------
+
+Here is a beautiful elementary lemma that appears implicitly in
+Manasse-McGeoch-Sleator and is proved cleanly in the paper. It lets
+us run a "virtual" simulated policy and lift its cost to a REAL
+policy for the original k-server problem.
+
+Statement (lazy simulation). Let C_0, C_1, ..., C_H be a causal
+sequence of configurations, each containing the request r_t at
+time t. Let A_0 be any actual starting configuration. There is a
+strongly lazy strategy on the actual servers with
+
+  cost(A_0; r_1, ..., r_H)
+       <= M(A_0, C_0)  +  sum_{t = 1}^H M(C_{t-1}, C_t).
+
+In words: the actual cost is at most the initial matching distance
+from A_0 to C_0 PLUS the total "movement" of the simulators
+measured by matching distance between consecutive C's.
+
+Why is this true? Here is the proof idea, in detail.
+
+At each step, after seeing C_t (the simulated configuration at
+time t, which is a function of the history so far and hence is
+available causally), do this:
+
+  - Take a minimum matching m_t from the CURRENT actual
+    configuration A_{t-1} to C_t. This tells us which actual server
+    "plays the role" of which simulated server.
+
+  - If A_{t-1} already covers r_t (some server is at r_t), do not
+    move anything. Otherwise move the actual server matched to
+    whichever occurrence of r_t in C_t we choose, and drive it
+    straight to r_t.
+
+After this step, we get an updated actual configuration A_t that
+still contains r_t. Now consider the quantity
+
+       "actual cost so far"  +  M(A_t, C_t).
+
+By an elementary comparison (the server we just moved was matched
+to a specific occurrence of r_t in C_t, and after the move the
+SAME matching still matches A_t to C_t, so the two distances agree
+up to the moved amount), we get the pathwise inequality
+
+       cost_t  +  M(A_t, C_t)  <=  M(A_{t-1}, C_t).
+
+Now the composition property of minimum matchings:
+
+       M(A_{t-1}, C_t)  <=  M(A_{t-1}, C_{t-1})  +  M(C_{t-1}, C_t).
+
+Summing over t and dropping the nonnegative final matching term
+gives the lemma.
+
+Why do we need strong laziness? Because of what happens if the
+request is ALREADY covered: no move is required, and the matching
+data does not accumulate cost. Without laziness, the actual
+strategy might be forced to shuffle servers unnecessarily and pick
+up extra cost.
+
+Why do we need CAUSALITY? Because C_t must be known at time t, so
+the strategy can be run online. If C_t depends on future requests,
+we cannot use the lemma to build an online policy - we only get an
+offline comparison. The paper uses the lemma in two flavors: for
+online policies (needs causality) and for offline comparisons (does
+not).
+
+Counting: the initial matching distance M(A_0, C_0) is a one-time
+cost. In every application of the lemma in the paper, this is
+either zero (C_0 = A_0) or a bounded quantity (for the repeated-
+starting-position case at the end).
+
+Reduction to "cost of the simulation". The paper's strategy will
+compute simulated configurations C_t satisfying the requirements.
+By the lazy simulation lemma, the actual cost on the real servers
+is at most the sum of matching distances of the simulators. So
+every subsequent budget about "sum_{t} M(C_{t-1}, C_t)" IS a budget
+on the real algorithm's cost. Good.
+
+Similarly: the paper sometimes compares two OFFLINE optima
+(solution Z vs. solution Z'). Then only the pathwise inequality is
+used, not causality. This is fine because offline comparisons are
+just for identifying which configuration is cheaper.
+
+------------------------------------------------------------------------
+9. THE POSTERIOR SHADOW AND ITS TWO-PART UPDATE
+------------------------------------------------------------------------
+
+Recall the setting from Section 7. There is a finite metric Y, a
+finite horizon H, a fixed probability law on Y^H, and we have
+chosen one optimal hidden labeled service Z of the k servers. mu_t
+is the expected counting measure (mass k total).
+
+The strategy of the proof is essentially:
+
+   "Maintain an online proxy for mu_t, using only the observed
+    history up to time t, then convert the proxy into actual
+    servers."
+
+To do this we need to understand how mu_t changes across a single
+step. It changes in two logically different ways, which the paper
+insists on separating.
+
+9.1 Filtering (filtration) vs. drift.
+
+Say the request at time t is x = r_t, and we have just observed it.
+We used to know the prefix up to time t-1; now we know the prefix
+up to time t. That is: F_{t-1} -> F_t. The "filtration" has grown.
+
+For any random variable depending on the past (say, the position
+of some hidden server just before time t), its CONDITIONAL LAW
+changes from "given F_{t-1}" to "given F_t". We call that change
+"filtering" - it is a change of information, not a change of the
+underlying random object.
+
+The "drift" is different: after conditioning on the new prefix, the
+underlying random variable itself MOVES (because the hidden optimum
+actually moved some labeled server at time t). Drift changes the
+OBJECT, not just what we know about it.
+
+The paper separates every change of every potential into these two
+parts:
+
+   L(Z_{t-1} | F_{t-1})  ---[filtering]-->  L(Z_{t-1} | F_t)
+                          ---[drift]--->    L(Z_t | F_t)
+
+Here "L" denotes "probability law of". The first arrow is "what we
+know has changed". The second arrow is "the object has changed".
+
+9.2 Why the order matters, and why we never condition on events
+    that depend on the new information.
+
+Most quantities we will track are AFFINE in the posterior measure.
+An affine functional has conditional expected value the SAME
+before and after filtering:
+
+       E[ affine(Z_{t-1}) | F_t ]   =   affine( mu^- )   and
+       E[ affine(Z_{t-1}) | F_{t-1} ] =   affine( mu^{old} ),
+
+and, by the tower property of conditional expectations,
+
+       E[ affine(Z_{t-1}) | F_{t-1} ]
+             =  E[ E[ affine(Z_{t-1}) | F_t ]  | F_{t-1} ].
+
+So an affine functional's expected filtering change is ZERO. Nice.
+
+A concave functional has conditional expected value that does NOT
+increase under filtering. (Because E[f(X)|more info] >= f(E[X|less
+info]) for concave f, up to the Jensen inequality direction.)
+
+A convex functional has conditional expected value that does not
+DECREASE under filtering.
+
+These one-sided differences are exactly what we need: they say
+"filtering cannot hurt" (for concave functionals) or "filtering
+cannot help" (for convex functionals).
+
+CRUCIAL: all such statements are made with OLD parameters. That
+is, we take the OLD definition of the functional (the one from
+F_{t-1}-measurable data) and evaluate its conditional expectation
+under the new filtration. We do NOT take the new potential and try
+to say anything about its expectation relative to the old. And we
+do NOT condition on any downstream event (like "did a reset
+happen?") that itself depends on the choice made at time t.
+
+Every time the paper uses filtering, it says this explicitly: the
+concavity (or affinity) argument is over ALL steps, including
+zero-probability-of-reset ones, and only afterwards do we use the
+potential-drop credit to pay for specific adaptive events. This is
+what makes the bound valid for an OBLIVIOUS adversary.
+
+9.3 The exact measure update.
+
+Here is the payoff. Fix a request x = r_t. The chosen optimum's
+k-th move designates a specific labeled server j_t (deterministically
+by our tie-breaking). Denote by mu^- the posterior measure on
+F_{t-1}-observations after the filter, and mu^+ after the drift to
+time t. Let nu be the LAW of the designated server's old position,
+conditioned on F_t. This is a probability measure: it puts mass 1
+across all possible old positions of the designated mover.
+
+Then:
+
+    mu^+  =  mu^-  -  nu  +  delta_x,
+    nu  <=  mu^-,      (domination: nu is a submeasure of mu^-)
+    nu(Y) = 1,         (unit mass)
+    e_x = int_Y d(x, y) dnu(y),   (the "expected mover distance")
+
+and:
+
+    mu^+ has at least one unit of mass at x, always.
+    E[mu^- | F_{t-1}]  =  mu^{old}.
+    sum over t of E[e_{r_t}]  =  Q := E[ OPT ],
+    where Q is the expected offline optimum on the input law.
+
+The last identity is the key economic statement: the sum of "expected
+mover distances" telescopes, in expectation, to the expected cost of
+the offline optimum. That is: e_x is exactly the per-request offline
+cost, and summing it gives the benchmark.
+
+Moral: the "cost" of the hidden optimum, in mol-unit form, is the
+sum of the e_x's. Any potential that pays for these e_x's is
+implicitly paying for OPT.
+
+9.4 Why "mu^+ has a unit at x" is important.
+
+It says: whatever the conditioning, the posterior "sees" the
+request. Later we will demand that our tree allocation and our
+rounding both have a "leaf with at least one unit" at x. This is
+exactly what lets us assign one simulated server to the request at
+every time, which then makes the simulated configurations legal.
+
+9.5 Who cares about the "stationary" part mu^+ - delta_x?
+
+The measure mu^+ has k total mass. It sits at x plus elsewhere. The
+"elsewhere" part is what remains at the previously designated
+positions after we have pulled one unit into x. That "stationary"
+part is exactly (mu^- - nu), which is dominated by mu^+, so no new
+mass appears; we can always find it if we look only where mu^+ is
+positive.
+
+This is used at the leaf end: the requested leaf gets a unit because
+the "elsewhere" mass does not vanish.
+
+9.6 The ball-mass telescope (a tiny but crucial lemma).
+
+One silent workhorse in the proof: a scale sum over logarithms
+telescopes because the same measure is used at all scales. Here is
+the exact statement.
+
+Fix constants 0 < a < b. Let mu be a nonnegative measure on Y and
+c_0 >= 0 an offset. On a consecutive finite range of scales suppose
+
+    c  <=  A_j := c_0 + mu(B(x, a r_j))
+       <=  B_j := c_0 + mu(B(x, b r_j))  <=  K,
+
+with c > 0. Let p >= 1 be an integer with tau^p a >= b. Then
+
+    sum over j of  log( B_j / A_j )   <=   p * log(K / c).
+
+Why? Balls are nested: B(x, b r_j) is contained in B(x, a r_{j-p})
+because tau^p a >= b. So B_j <= A_{j-p}. Then
+
+    log(B_j / A_j)  <=  log(A_{j-p}/A_j).
+
+Summing this over j gives a "shifted sum of logs": sum_j log A_{j-p}
+minus sum_j log A_j. Interior terms cancel. Only p "left edge" terms
+and p "right edge" terms survive, each pair contributing at most
+log(K/c). So the total is at most p log(K/c).
+
+This is the local-ratio trick. As a reader, notice this one small
+lemma is the reason "logarithms telescope" over scales in the
+partition construction, avoiding the log-n factor.
+
+Takeaway for the rest of the proof:
+
+    every place we compare fine-scale and coarse-scale masses,
+    this telescope controls the sum with an ell-sized bound.
+
+------------------------------------------------------------------------
+10. THE TREE: A FIXED FINITE OBJECT THAT MIMICS THE METRIC
+------------------------------------------------------------------------
+
+The next big move in the paper is to replace the true metric Y by a
+balanced tree structure. The tree is chosen ONCE, is independent of
+the request sequence, and its vertices and edges have fixed
+weights. What changes over time is only the assignment of points of
+Y to leaves (labels) and the posterior measures on leaves.
+
+10.1 Why a tree at all?
+
+Three reasons:
+
+  - Movement on a tree is summable across levels. The "edge entering
+    a vertex of depth j" has weight r_{j-1} which decreases
+    geometrically with depth, matching the ball radii.
+  - A tree's subnetworks are disjoint: they let us decompose the
+    "how much mass is below this vertex?" question hierarchically.
+  - Posterior subtree counts are natural on a tree: N_v(t) is just
+    "the number of hidden servers whose leaf is below v". There
+    is a clean inequality (superadditivity) linking parent's "rank
+    distribution" to children's, which is what the allocation
+    theorem exploits.
+
+10.2 The prefix tree.
+
+Fix alphabets A_1, A_2, ..., A_J. Each A_j is finite. Let T be
+the tree whose vertices at depth j are the words w_1 ... w_j of
+letters w_i in A_i (including w_j itself). The root is the empty
+word (depth 0). Leaves are depth-J words.
+
+Vertex depths are 0, 1, ..., J. The "child" relation is the obvious
+one: append one letter. This is a complete (possibly huge but
+finite) tree.
+
+10.3 Edge weights.
+
+The edge entering a nonroot vertex v of depth |v| = j has weight
+
+    weight of the edge entering v = r_{|v| - 1} = r_{j-1}.
+
+Equivalently: the "top" vertex (depth 0, root) has no incoming edge.
+Depth-1 vertices connect to root by edges of weight r_0. Depth-2
+vertices connect to depth-1 parent by edges of weight r_1. And so on
+down to depth-J leaves with incoming edges of weight r_{J-1}.
+
+10.4 The leaf metric on T.
+
+Define a distance d_T between leaves of T:
+
+    d_T(leaf_1, leaf_2) = r_{LCA_depth(leaf_1, leaf_2)}
+
+where LCA_depth is the depth of the lowest common ancestor of the
+two leaves. Equivalently: d_T(leaf_1, leaf_2) = r_j when the first
+letter at which the two leaves disagree is level j + 1.
+
+This is the "standard HST metric" (Hierarchically Separated Tree):
+each level scales down by tau, and the distance between two leaves
+is the scale at which they merge.
+
+10.5 How points of Y map to leaves (the labelled map).
+
+At every time t there is an online random map
+
+    xi_t : Y -> A_1 x A_2 x ... x A_J
+
+that assigns each point of Y a full word of labels (a leaf of T).
+The map is chosen from the revealed prefix; it is independent of
+the future request stream (this is a key causality property).
+
+Properties required (Lemma "fixed alphabet" in the paper):
+
+  - xi_t is INJECTIVE. Distinct points of Y get distinct leaves at
+    level J. (Because level-J cells are singletons.)
+  - Every point with a given current level-j label lies within
+    20 r_j of a fixed "anchor" for that label. Equivalently: the
+    level-j cell has an "anchor" point a_{j, lambda} with
+    d(y, a_{j, lambda}) <= 20 r_j for all y in the cell.
+  - Cell diameter is at most 40 r_j. (Two points in the same
+    level-j cell are at distance <= 40 r_j.)
+  - If the same label survives from step t-1 to step t, the anchor
+    is either UNCHANGED or was moved by at most 40 r_j via the
+    heavy-ball reuse (Section 13).
+
+10.6 Labels: how many are there?
+
+A subtle point: Y can be very large, and used labels can be many.
+But two constraints make the label sets finite and fixed in advance:
+
+  - At each level and each construction, at most n K^2 histories
+    can appear "active" at once (n = |Y|, K a parameter of the
+    chronological roster, Section 13).
+  - A generous pool of size at most 4 n K^2 + 4 per level suffices:
+    reserve each active label, and choose a fresh label outside the
+    entire currently active set and the previous step's set.
+
+The pooled labels are FIXED in advance, independent of the metric
+size beyond n or of the horizon. This avoids the "the label set
+grows with each step" trap that would make the final bounds depend
+on horizon.
+
+10.7 The maps' cost.
+
+Define
+
+    P  :=  E sum_t sum_{a=1}^k
+              d_T( xi_{t-1}(X_{t-1}^a), xi_t(X_t^a) )
+
+where X_t^a is the position of the a-th hidden comparator server
+at time t. In words: P is the expected total distance moved by the
+comparator when we measure its motion on the TREE.
+
+The upshot of Section 13 (the partition construction) will be:
+
+    P   <=   C * ell * Q   +   D_part,
+
+where D_part is a finite constant independent of the input law and
+horizon. In other words, changing the partitions adds only a
+logarithmic factor per unit of comparator movement, plus a fixed
+initialization cost.
+
+10.8 What "fixed tree" buys us.
+
+Because T is fixed once the metric and the constants are chosen,
+subsequent tracking and allocation algorithms run on a FIXED
+combinatorial object. The only thing that changes with time is
+where the k comparator servers sit in the tree, and how the
+online map labels the points of the metric. The rest of the proof
+is entirely about the tree.
+
+There is no approximation-theoretic loss from T's distortion in
+the final bound. Rough intuition: P (movement on T) is exactly
+what the partition construction charges, and every step of the
+metric-to-tree passage is compensated by choosing the anchors so
+that they never move more than the ball sizes, which is what P
+already accounts for.
+
+------------------------------------------------------------------------
+11. THE ALLOCATION THEOREM: SHARING K UNITS UP THE TREE
+------------------------------------------------------------------------
+
+This is the technical heart of the paper. We solve a self-contained
+problem on the fixed tree T. The solution is one of the two
+logarithms in the final bound.
+
+11.1 The problem, stated cleanly.
+
+Run the hidden comparator on the tree T. At each time t there are k
+labeled hidden servers at k leaves, and one leaf x_t is the request
+(every hidden server's tree position is one of the k leaves; the
+request is the leaf of the current r_t under xi_t, i.e. the leaf of
+the labelled map at time t applied to r_t).
+
+N_v(t) = number of hidden servers at time t whose leaf is in the
+subtree rooted at v.
+m_v(t) = E[ N_v(t) | F_t ]. These are the "posterior expected
+subtree counts".
+
+Subtree counts have these properties, for every t and every
+internal vertex v:
+
+    m_root(t) = k,
+    m_v(t) = sum over children i of m_i(t),   for every internal v,
+    0 <= m_v(t) <= k,
+    at the request leaf x_t: m_{x_t}(t) >= 1,
+    m_v(t) is affine in the posterior,
+    sum over t of |m_v(t) - (filtered m_v)(t)| has a controlled sum.
+
+The last line is exactly the "rank drift bound"; Section 11.3
+spells it out.
+
+The allocation problem is to produce NONNEGATIVE REAL amounts q_v(t)
+satisfying, at every time t:
+
+    (A1)  q_root(t) = k.
+    (A2)  sum_{i child of v} q_i(t) <= q_v(t)       for every internal v.
+    (A3)  q_v(t) <= C_0 * m_v(t)                    for every v, some absolute C_0.
+    (A4)  q_{x_t}(t) >= 1.
+
+The first condition says all k "serving units" start at the root.
+The second says children get at most what the parent provides
+(leftover mass "parks" at v itself). The third says the allocation
+never exceeds a constant times what the shadow has. The fourth
+ensures the request leaf is servable.
+
+Additionally we want the ALLOCATION to move slowly, meaning: define
+
+    V  :=  E sum over t, over nonroot vertices v
+              r_{|v|-1} * | q_v(t) - q_v(t-1) | .
+
+We want V bounded by a small multiple of the comparator's motion on
+the tree, plus a fixed initialization constant. Precisely:
+
+    (A5)  V  <=  C_1 * ell * P  +  D_T,
+
+for absolute C_1 and a fixed finite D_T (depending only on the fixed
+tree, radii, and k; independent of the input law and horizon).
+
+The theorem claims you can produce such q_v(t) causally, using only
+the observed prefix (and the revealed posterior), starting from any
+initial allocation (no initial conditions are required).
+
+11.2 Why this is hard.
+
+Consider the naive rule: "Set q_v(t) = m_v(t) at every v." Then
+(A1)-(A4) hold (with C_0 = 1). But the movement V is E sum r |Delta
+m_v|, and that can be BIG by a factor of the number of levels: the
+posterior moves one unit across the entire tree, which cascades into
+changes of m_v at EVERY level. That's not what we want. In fact m_v
+is not "stable enough": a single unit moving from one leaf to another
+changes m_v on the entire path between them, at every scale.
+
+The repair is to introduce "slack". We allow q_v to be strictly less
+than m_v (a factor C_0 < infinity above) as long as it exceeds a
+LOWER BOUND L_v(t) which is a "rank function" of the posterior.
+The lower bound is chosen so that it tracks m_v, but in a way that
+changes slowly when m_v changes fast.
+
+11.3 Rank coordinates and their drift.
+
+For each vertex v and each threshold a in {1, 2, ..., k}, define:
+
+    p_{va}(t)   = Pr( N_v(t) < a  | F_t ).
+    p^-_{va}(t) = Pr( N_v(t-1) < a | F_t ).
+
+Then:
+    p_{va}(t)   is the "posterior probability that v's subtree
+                contains at most a-1 hidden servers".
+    p^-_{va}(t) is the "filtered" version: same count, but with the
+                pre-drift variable.
+
+The tower property gives
+    E[ p^-_{va}(t) | F_{t-1} ]   =   p_{va}(t-1).
+
+So the "drift" delta_t p_{va}  :=  p_{va}(t) - p^-_{va}(t) is the
+only thing a change of the hidden trajectory contributes to a rank
+coordinate at time t. The rest of |p_{va}(t) - p_{va}(t-1)| is a
+"filtering change" whose sum is zero in expectation.
+
+The local drift budget E_v at an internal vertex v is
+
+    E_v := E sum over t of [  sum_{i child of v} sum_a |delta_t p_{ia}|
+                            + sum_a |delta_t p_{va}|  ] .
+
+The paper proves a clean coupling inequality:
+
+    sum over internal vertices v of r_{|v|} E_v   <=   6 P.
+
+Here P is the comparator's tree-movement from Section 10.7. The
+reason: if one hidden server moves between two leaves whose last
+common ancestor is at depth j, its contribution to |delta_t p_{va}|
+is one on each of the two paths strictly below depth j. Weighted by
+r_{|v|} and summed over such vertices, that telescopes to at most
+6 r_j, which is exactly 6 times the comparator movement at that
+step. Sum over t and take expectations.
+
+Moral:  "rank coordinates in total drift at most 6 times the
+comparator's tree movement." This is the coupon we have to spend in
+later steps.
+
+11.4 The rank functions l^beta.
+
+For each parameter beta in [3, 3 + epsilon_*] (epsilon_* = 1/100),
+the paper constructs a function  l^beta : [0, 1] -> [0, 1]  with:
+
+  (RF1)  l^beta is CONVEX and NONINCREASING on [0, 1].
+  (RF2)  l^beta(p) = 1 - beta p  on [0, p_*]  (p_* = 1/24).
+  (RF3)  l^beta(p) > 0 on [0, s_*) with s_* = 5/8.
+  (RF4)  l^beta(p) = 0 on [s_*, 1].
+  (RF5)  l^beta is AFFINE and NONINCREASING in beta.
+  (RF6)  sqrt(l^beta) has a common absolute Lipschitz constant.
+  (RF7)  If g = -d/dbeta l^beta, then
+            (1/96) l^beta(p) <= g(p) <= l^beta(p)
+         on [p_*/4, 1].
+
+There is an EXPLICIT formula:
+
+    l^{3+z}(p)  =
+       1 - (3+z) p,                                    0 <= p <= p_*,
+       (s_* - p)^2 [ A_* - z (c_*' + d_*' (p - p_*)) ],
+                                                  p_* <= p <= s_*,
+       0,                                              s_* <= p <= 1,
+
+with A_* = 18/7, c_*' = 6/49, d_*' = 1152/343. All pieces meet
+with matching values and (first) derivatives at p_*.
+
+Two properties make this the right family:
+
+  - The pieces are convex quadratics on the middle interval, so
+    (RF1) holds.
+  - The parameter beta lets us stretch the function "down" at rate
+    proportional to beta. The derivative g controls HOW MUCH does
+    l^beta change when beta changes: it's exactly the slope in
+    beta. (RF7) says this slope is comparable to l^beta itself,
+    uniformly.
+
+Also now we have TWO families in play. Two "rank function" objects
+per vertex:
+
+    L_v^beta := sum_{a=1}^k l^beta(p_{va})
+    M_v      := sum_{a=1}^k l^{siz}(p_{va}),
+                l^{siz}(p) := (3/4 - p)_+^2 / (3/4)^2,
+
+where l^{siz} is the "size" function (a broader quadratic cutoff).
+Note L_v^beta and M_v are both sums of k terms, each in [0, 1],
+so both are in [0, k]. Also M_v is essentially a smooth "how mass
+distributed" measure at v.
+
+11.5 Superadditivity.
+
+Here is the key structural lemma. For any internal vertex v, its
+children i, and its rank function (either family), the following
+inequality holds WITHOUT assuming independence between children:
+
+    sum_{i child of v} L_i^beta  <=  L_v^beta,
+    sum_{i child of v} M_i       <=  M_v     <=  m_v.
+
+Why? Two facts:
+
+  - Convexity of l^beta and l^{siz}, plus an "increasing hinge"
+    majorization argument (Karamata's inequality applied to convex
+    hinges (b - p)_+): the sum of a convex function over child
+    rank probabilities is at most its value on the parent's rank
+    probabilities, adjusted by (d - 1)k padding ones for "missing"
+    children.
+  - m_v counts "how many servers are below v on average", and
+    M_v dominates m_v via l^{siz}(p) <= 1 - p (convexity + endpoint
+    values) and sum_a (1 - p_{va}) = m_v.
+
+So superadditivity says: the "budget" L_v^beta at a parent covers
+the sum of the L_i^beta at its children. Good.
+
+11.6 The parameter beta_v.
+
+Define for each vertex the parameter
+
+    beta_v  =  3 + (c_beta / ell) * log( k / max(M_v, c_*) ).
+
+Here c_beta > 0 is a small absolute constant, c_* = 10^-4. This is
+a "size-adapted" rank function parameter: when M_v is small (v's
+mass is spread out), beta_v becomes larger (function drops faster);
+when M_v is large (v's mass is concentrated), beta_v is closer to 3.
+
+Key facts about beta_v:
+
+    beta_v is in [3, 3 + epsilon_*/2].
+
+    In terms of the invariant (below),
+    "L_v^{beta_v} <= L_v^{beta_i}" whenever i is a child of v,
+    because M_i <= M_v implies beta_i >= beta_v, and l^beta is
+    decreasing in beta.
+
+Superadditivity plus the "beta_i >= beta_v" fact shows that the
+child lower bounds at their own beta_i are consistent with the
+parent bound at its beta_v. That's the "compatible lower bounds"
+property.
+
+The INVARIANT we will maintain:
+
+    (INV)  q_v(t)  >=  L_v^{beta_v(t)}    for every v at every t.
+
+Then:
+    q_root(t) >= L_root^{beta_root} = k (all ranks zero at root,
+                                         so L_root^beta = k).
+    q_{x_t}(t) >= L_{x_t}^{beta_{x_t}} >= 1 (leaf rank zero, so
+                                            rank function = 1).
+
+So (A1) and (A4) hold automatically from the invariant and the
+initial value q_root = k plus superadditivity. And (A3) requires
+q_v <= C_0 m_v; the theorem's choice of C_0 charges that separately
+via the M_v <= m_v domination.
+
+11.7 Core vs. noncore ranking.
+
+To make the rank functions move SLOWLY, we need some slack that
+does not depend on the exact current value of p_{va}. The paper
+introduces a binary classification of ranks:
+
+  - Use an "absolute threshold tracker" with threshold p_*/8 on
+    every rank value. Let the tracked value be the HELD reference;
+    refresh it only when the ACTUAL rank moves by more than p_*/8.
+  - A rank is called CORE if its held value is <= p_*/2.
+  - After an update: a core rank has p <= 5 p_*/8; a noncore rank
+    has p > 3 p_*/8. A rank with p < p_*/4 is always core.
+
+Effect on the rank function: core ranks lie in the LINEAR part
+l^beta(p) = 1 - beta p (affine in p, so affine in the posterior
+measure), so they are cheap to track. Noncore ranks are strictly
+above p_*/4 and lie in the quadratic middle, where l^beta changes
+smoothly with p.
+
+Let, at child i:
+    n_i       = number of current core ranks,
+    B_i       = sum of their current p values,
+    S         = sum_i B_i,
+    f_i^beta  = sum over noncore ranks of l^beta(p_{ia}).
+
+Then:
+    L_i^beta  =  n_i - beta B_i + f_i^beta,
+    n_i + sup_beta f_i^beta  <=  C M_i           for absolute C.
+
+The first identity decomposes the child lower bound into core count
+n_i, core sum B_i, and flex f_i^beta. The second bounds the total
+by a constant times M_i, using that a core rank contributes at
+least a fixed amount to M_i. Consequences:
+    if M_i <= 10 c_*, then n_i = 0 and L_i^beta = f_i^beta = 0.
+    if the core flags are held while ranks filter and drift,
+    B_i <= n_i^{old}.
+
+11.8 Coarse data: sizes, dominant marks, and gaps.
+
+We need to run a small "size tracker" at each child. Track
+M_i(t) with tolerance delta_s = 10^-3. Let hat M_i be the tracked
+value. Then introduce a_i(t), the "held size":
+
+  - INACTIVE (a_i = 0). Turn on when hat M_i >= 5 c_* (set a_i =
+    hat M_i). Turn off from active when hat M_i <= 2 c_*.
+  - ACTIVE. While active, hold a_i until factor 1+delta_s
+    comparison with hat M_i fails; then update a_i := hat M_i.
+
+The result:
+    0.9 M_i <= a_i <= 1.1 M_i   at active children,
+    M_i >= c_*                 if active,
+    M_i >= 10 c_*              implies active.
+
+Now pick a DOMINANT child if it exists: the index o such that
+a_o >= 0.85 A where A = sum_i a_i (the active total). It is unique.
+If no dominant child exists, all active children are "regular".
+
+The complexity: a dominant child makes the algebra awkward because
+its "gap" beta_o - beta_v might be small. Introduce these "epoch"
+notions. An epoch is a period during which:
+
+  - beta^+ (the tracked upper bound on beta_v) is constant,
+  - the dominant mark is constant,
+  - the cumulative l1 variation of the held size vector since the
+    epoch started is at most A_start / 100.
+
+At the start of each epoch we may reorganize; within an epoch the
+"shape" of the star stays stable.
+
+Also define:
+    h_i = 1 + max(0, log(A / a_i))     for regular i,
+    h_o = u := U / A                   for dominant o,
+    U   = side total (sum of a_i over non-dominant children),
+    A   = total active size.
+
+These h_i are the "gap weights". The parameter gap lemma shows, for
+absolute c_g > 0,
+    beta_i - beta_v  >=  (c_g h_i) / ell.
+
+So bigger "mass disparity" h_i gives more room to fit the child's
+lower bound under the parent.
+
+11.9 Fine caps.
+
+The static reduction is: figure out how much reduction is needed
+to fit the parent. We will remove "excess" = sum_i d_i - q_v from
+children via proportion vectors. For that we need caps d_i above the
+lower bound but not too loose.
+
+Caps d_i = n_i + b_i, with n_i the core count and b_i a "flex
+estimate" chosen so that:
+
+    f_i^{beta_i}  <=  b_i  <=  f_i^{beta_v}     for regular i,
+    T := f_o^{beta_v}  <=  b_o  <=  (1 + epsilon_b / ell) T
+                                                for dominant o,
+    c_D T <= D <= C_D T                          (D is the coarse
+                                                 flex estimate),
+
+where D is tracked separately (an old l^3 sum on noncore ranks of
+o) and epsilon_b > 0 is a small absolute constant. The caps are
+maintained by a relative tracker with tolerance rho / ell on every
+rank function value, interpolated in beta.
+
+Bound: |Delta d_i| in total across all children is at most
+C ell E_v + fixed, on non-wholesale steps. So the FINE TRACKING
+costs a factor ell but no extra potential slope.
+
+Important: the fine tracking is NOT fed back into the potential
+slopes. Otherwise we would get an extra ell. Keeping fine caps
+out of the proportion potentials is what makes only ONE ell appear
+per star (from coarse variation), not two.
+
+11.10 Removing excess: proportions.
+
+At the end of a star's local updates, before knowing the parent's
+current q_v, we have caps d_i, core count n_i, core sum B_i, total
+S = sum_i B_i, and D (dominant flex estimate). The required
+reduction is
+
+    R_0  :=  ( sum_i d_i  -  q_v )_+  >=  0.
+
+We will remove R_0 in proportions alpha_i:
+
+    q_i  :=  d_i  -  R_0 * alpha_i                     for all active i.
+
+Feasibility requirement: for each child i, the removed amount plus
+the parent's own lower bound must still meet the child lower bound
+L_i^{beta_i}. This translates to:
+
+    alpha_i  >=  0,
+    sum_i alpha_i  =  1,
+    S alpha_i  <=  (1 + eta_i) B_i     where eta_i := c_t h_i / ell,
+                                       c_t > 0 small absolute.
+
+The last inequality is a per-child upper bound. When S = 0, we have
+S alpha_i = 0 = B_i at every child, and the constraint is trivial.
+
+We want alpha_i to change SLOWLY when B and S change rapidly. That
+is what the simplex tracker is for.
+
+11.11 The simplex tracker (main case).
+
+The simplex tracker produces alpha^t+1 from alpha^t by a global
+minimization:
+
+    alpha^1  :=  argmin over alpha in the simplex
+                    { G^alpha(alpha; B_t)  +  S_t * ||alpha - alpha^0||_1 }
+
+where the primitive is a sum over coordinates:
+
+    g_i^alpha(a; B)  :=  C_alpha * ell *
+                          int_0^a   ( S - (1+eta_i) B_i / s )
+                                    /  F_i(log(1/s))         ds
+
+    for regular i, and
+
+    g_o^alpha(a; B)  :=  C_alpha * ell *
+                          int_1^a   ( S - (1+eta_o) B_o / s )
+                                    /  F_o(log(1/s))         ds
+
+    for dominant o.
+
+Here:
+    F_i(y) = (h_i + y)^2 / h_i                        for regular i,
+    F_o(y) = u + H y (1 + y),  H = 1 + log(1/u)        for dominant o.
+
+The denominators are checked to have the bound
+
+    int_0^\infty dy / F_i(y)  <=  C    uniformly in h_i, u,
+
+which is the only property we actually need.
+
+The lemma says: at a global minimizer alpha^1,
+
+    (feasibility) S alpha^1_i <= (1+eta_i) B_i for every child i,
+    (payment)     S ||alpha^1 - alpha^0||_1  <=  G^alpha(alpha^0; B)
+                                                -  G^alpha(alpha^1; B).
+
+Two intuitive points about the formula:
+
+  - If S alpha_i is too big (violating the feasibility constraint),
+    then d g_i^alpha / da > 0 at that coordinate, meaning the
+    potential DECREASES if we reduce alpha there. So pulling mass
+    to some coordinate paying 2S in movement cost is worth it.
+  - The integral is set up so that the "payoff rate" of reducing
+    alpha is at least 2S when infeasible, matching the l1 penalty
+    coefficient S. That is exactly why the payment works.
+
+The dominant coordinate's denominator F_o(y) = u + H y (1 + y)
+handles the near-dominant case. As u -> 0 (dominant child holds
+almost all mass), the integral is still bounded by an absolute
+constant. The base point 1 is chosen so that changing u is charged
+to the side sizes, not the dominant's mass.
+
+11.12 The side tracker (near-dominant case).
+
+Even with the simplex tracker, the simplex-based Rule I has to be
+abandoned when the dominant child nearly fills the parent. The
+reason: the ratio S / D (child-core total over dominant flex
+total) can be so small that the "error" e_o = b_o - f_o^{beta_v}
+cannot be paid by simplex proportions. So when S <= 2D, we switch
+to Rule II which is a DIFFERENT output rule based on side reductions.
+
+Side vector w: nonnegative entries indexed by side children,
+with sum_i w_i <= C_w for fixed absolute C_w. Two feasibility
+requirements:
+
+    D w_i  <=  (beta^+ + theta_i) B_i          always,
+    D w_i  >=  beta^+ B_i  -  theta_i z_i D    if S <= 2D,
+
+where theta_i = c_w h_i / ell and z_i = a_i / (A h_i). And a
+"side potential"
+
+    G^w(w; B, D) = sum_i g_i^w(w_i; B_i, D),
+
+    g_i^w(s; B_i, D) = C'_w * int_0^s
+                          (D s' - (beta^+ + theta_i/2) B_i
+                            + D theta_i z_i / 2)
+                       /  (theta_i (s' + z_i))       ds'.
+
+The side tracker's minimization is
+
+    w^1  :=  argmin over w in the side domain
+                { G^w(w; B, D)  +  D * ||w - w^0||_1 }.
+
+Lemma: at the minimizer, feasibility holds, and
+
+    D ||w^1 - w^0||_1  <=  G^w(w^0; B, D) - G^w(w^1; B, D).
+
+The proof is similar to the simplex tracker: any upper violation
+makes the potential's derivative positive (so decreasing is
+profitable); any lower violation (when S <= 2D) makes the derivative
+negative (so increasing is profitable).
+
+11.13 Rule I vs. Rule II (hysteresis).
+
+The output rule:
+
+  RULE I.  When S >= D/2.
+    q_i  :=  d_i  -  R_0 * alpha_i               for all i in I.
+
+  RULE II. When S <= 2D and there is a dominant child o.
+    q_i  :=  d_i  -  D * w_i                     for i != o,
+    q_o  :=  min{ d_o, q_v - sum_{i != o} q_i }.
+
+The two ranges overlap (D/2 <= S <= 2D), and the strategy uses
+HYSTERESIS: stay on the current rule until it leaves its range.
+
+Switching costs are controlled by a "switch potential":
+
+    Psi_v  =  D   if a dominant child exists and we are on Rule I,
+              S   if a dominant child exists and we are on Rule II,
+              0   otherwise.
+
+The analysis (coupled with the coarse budgets and the ball-mass
+telescope) gives a total expected switching cost of at most
+C ell E_v + a fixed constant. Same as everything else, no extra log.
+
+11.14 Feasibility.
+
+Combining everything, the outputs q_i are nonnegative, satisfy
+L_i^{beta_i} <= q_i <= d_i <= C M_i <= C m_i, and satisfy
+sum_i q_i <= q_v (because we removed R_0 from the cap sum, and
+each rule removes exactly R_0 or less).
+
+For the requested leaf: its m_v >= 1, and the leaf has exactly
+one member with p_{v, 1} = 0, so L_v^{beta_v} >= 1. By the
+invariant, q_x >= 1 at the request leaf.
+
+11.15 Assembling the movement bound.
+
+Local star movement:
+
+    E sum_t sum_{i child of v} |q_i(t) - q_i(t-1)|
+       <= C_par  E sum_t |q_v(t) - q_v(t-1)|  +  C ell E_v
+                                                +  D_v^{out}.
+
+The parent term at vertex v is NOT part of the "budget" but is
+recursively traced up. Multiply both sides by r_{|v|} and sum over
+internal vertices. The left side becomes V (the tree allocation
+movement). Each nonroot vertex appears once as a child. The
+parent-side term contributes weight r_{|v|} per (parent, child) pair,
+but total = sum over parents' own r-weighted parent-differences.
+Each parent term appears on the right side at depth |v|, so
+
+    V  <=  C_par / tau * V  +  C ell sum over internal v r_{|v|} E_v
+                            +  D_tree.
+
+Use  sum_v r_{|v|} E_v <= 6 P. Choose tau >= max(2, 2 C_par).
+Then:
+
+    V  <=  12 C ell P  +  2 D_tree,
+
+which is (A5) with C_1 = 12 C, D_T = 2 D_tree.
+
+Done. Note that this is exactly the ONE ell that comes from the
+allocation theorem. Section 13 will give another ell from the
+partition construction. Together they form ell^2.
+
+------------------------------------------------------------------------
+12. THE PILOT POTENTIAL: A BRAKE FOR CHANGING PARTITIONS
+------------------------------------------------------------------------
+
+We now build the second major tool: a potential that pays for
+"edits" of the label map and its associated structures. Two dozen
+lemmas in the paper rest on this potential. Here is the concept.
+
+12.1 The problem this solves.
+
+The labelled map xi_t (of Section 10) changes over time. Old labels
+are dropped, new labels appear, and their anchor points move. Each
+of these events can cause the tree allocation q_v (Section 11) to
+change too. In the worst case that is unbounded.
+
+We need a potential PHI such that:
+
+  (P1)  When a label-map update strictly improves the fit to the
+        posterior, PHI drops by at least some amount proportional
+        to the "ideal" size of the edit.
+
+  (P2)  PHI's INCREASES, on physical movement of the comparator,
+        are bounded by O(log k) times the movement magnitude,
+        summed over all scales.
+
+Property (P1) makes PHI a "credit line" for edits: decreasing PHI
+pays for making good edits. Property (P2) ensures the credit line
+grows slowly enough that the total credit spent is bounded by
+O(ell) times the comparator's own cost.
+
+Everything rests on a compact variational definition of PHI as a
+MINIMUM over "site patterns" z. The minimum makes PHI concave in
+the underlying measure, which is what makes filtering free (Section
+9.2).
+
+12.2 The "template".
+
+A "template" consists of three numbers:
+
+    sigma in (0, 1],     R >= 256,     L >= 0.
+
+From these, define the scales D_* = 10 R and D_1 = 100 R. These are
+"multiples of local radius" where transitions happen.
+
+Also, define three "bump" functions of a nonnegative scalar v
+(thought of as distance divided by local radius r):
+
+    b(v) = max(0, min(1, 2 - v/sigma)).
+
+       Reading: b(v) = 1 for v <= sigma, decreases linearly to 0
+       at v = 2 sigma, zero beyond. Width ~ 2 sigma. Lipschitz 1/sigma.
+
+    a(v) = min(v^2/sigma^2, 1)                for 0 <= v <= R,
+           2 - v/R                            for R <= v <= 2R,
+           0                                  for v >= 2R.
+
+       Reading: a(v) rises quadratically from v = 0 to v = sigma,
+       stays at 1 until v = R, decreases to 0 at v = 2R, zero
+       beyond. Lipschitz ~ 2/sigma.
+
+    G(v) = max(0, min(1, v/D_* - 1)).
+
+       Reading: G(v) = 0 for v <= D_*, rises linearly to 1 at
+       v = 2 D_*, stays at 1 beyond. Lipschitz 1/D_*.
+
+All distances are dimensionless, measured in units of the local
+radius r.
+
+12.3 "Sites" and their feasibility constraints.
+
+A "site vector" z is an assignment of nonnegative weights to points
+of Y. Write z_s for the weight at s.
+
+The site vector must lie in the feasible set Z_r, defined by:
+
+    z_s >= 0                              for every s,
+    sum_s (z_s - G_s(p))_+  <=  1         for every point p in Y,
+    d(s, s') >= 5 sigma r                 whenever z_s z_{s'} > 0.
+
+The second condition is the "capacity" one: at any point p, the
+LOCAL amount of s-weight (weight above the G cutoff) is at most 1.
+The idea is that locally, the total mass "nearby" any point p is at
+most 1, so a site pattern can use mass at most 1 in a neighbourhood.
+
+The third condition is "separation": any two sites with positive
+weight are at least 5 sigma r apart. This is a structural
+assumption that makes the surcharge construction work: the positive
+support of the b-bumps at two positive sites is DISJOINT.
+
+12.4 The integrand.
+
+Given a site vector z in Z_r and a function g : Y -> [0, 1] (the
+"edit indicator"), define the integrand at p:
+
+    F_z^g(p)  =  (1 + g(p)) * ( 1 - sum_s z_s b_s(p) )
+              +  256 * sum_s z_s * (1 + g(s)) * a_s(p).
+
+Here b_s(p) := b(d(s, p)/r), a_s(p) := a(d(s, p)/r), and similarly
+for G.
+
+What do the two terms represent?
+
+  - The residual term (1 - sum z_s b_s(p)) is "1 minus the amount
+    of b-mass installed near p". It is at least 0 and at most 1
+    (from the capacity constraint). This is the amount of "not yet
+    handled mass" at p.
+  - The surcharge term 256 * sum z_s (1+g(s)) a_s(p) charges
+    256 times (1 + g(s)) per unit of s-weight that a_s touches p.
+    It "punishes" sites that are not exactly at concentrations of
+    mass: if a site is at distance more than R r from a point with
+    significant mass, but less than 2R r (so a_s is still positive
+    there), the surcharge adds cost.
+
+The temptation to help at a concentrated point: a site at a point
+s = x with local mass >= 1. Then 1 - sum z_s b_s(x) can be near
+zero if z_x is near 1 (b_x(x) = 1). And the surcharge at x from its
+own site is 256 * z_x * (1+g(x)) * 1 = 256 z_x (1+g(x)), which is
+a fixed penalty per unit weight. So a site pattern near a concentrated
+point does improve the residual always, but the surcharge bounds
+how much.
+
+12.5 The potential.
+
+Define
+
+    L_r(mu, g)   :=   r * min_{z in Z_r}  int_Y F_z^g(p) dmu(p).
+
+This is the template's potential at scale r, for a measure mu and a
+"g" function. The factor r carries the scale dimension.
+
+Basic facts (Lemma "compactness, concavity, and uniform bounds"):
+
+  (L1) The minimum exists. Z_r is a closed subset of a compact
+       cube [0, 1]^Y, so the objective is continuous on a compact
+       set.
+
+  (L2) L_r is CONCAVE in mu. This is exactly why filtering only
+       decreases it in expectation. (Do NOT confuse: concavity of
+       the potential as a function of mu; the feasible set Z_r is
+       NOT convex, so the argument does NOT use convexity of Z_r.)
+
+  (L3) 0 <= L_r(mu, g) <= 2 r mu(Y).
+       The upper bound is by taking z = 0. The lower bound is
+       obvious since F >= 0.
+
+  (L4) Every feasible integrand satisfies
+           0 <= F_z^g <= 514,    r Lip(F_z^g) <= L + 1026/sigma.
+       The "514" comes from (1 + 1) + 256 + 256, but with constants
+       stripped it is 514 = 2 + 512.
+
+  (L5) The positive support of the b_s's at two distinct positive
+       sites is DISJOINT. (Follows from the separation condition.)
+
+The 514 is a big constant. It is not small, but "a fixed absolute
+constant" is all the argument needs. It reappears everywhere.
+
+12.6 The local structure lemma.
+
+The crucial property of L_r is that, at a concentrated request, it
+has a "near site" and a small positive slope. The paper states this
+cleanly. Let me recast it as a story.
+
+Fix a request x, a template, and small constants
+    gamma <= min{sigma/64, 1/(1+L)},    delta <= 1/4112.
+These are "concentration" thresholds. Let mu be a nonnegative
+measure, M := mu(B(x, gamma r)) > 0 the mass in a small inner ball
+around x. Define:
+
+    h  =  mu(B(x, D_1 r) \ B(x, gamma r)) / M
+
+      "shell ratio": how much more mass sits in the annulus between
+      the small inner ball and the wider D_1 r ball. If h = 0, all
+      mass is concentrated in the inner ball. If h >= 1, the
+      concentration is not strong.
+
+    t  =  (1/M) * int_B(x, gamma r) d(x, p)/r dmu(p)
+
+      "inner moment": the average distance to x (normalized by r)
+      of the inner ball's mass. If t = 0, all inner mass sits at x.
+
+Both h and t are nonnegative and can be small without any of them
+being zero.
+
+Lemma (local structure). If h <= delta, and z is any minimizer of
+the potential at scale r, then:
+
+  (A) Any site s with sigma r/4 <= d(s, x) <= R r/2 has z_s = 0.
+      (Sites strictly in the middle distance shell are excluded.)
+
+  (B) There is a UNIQUE positive site s with d(s, x) < sigma r/4.
+      Its weight z_s and normalized displacement w = d(s, x)/r
+      satisfy
+          z_s >= 3/4,
+          1 - z_s <= (512 gamma / sigma^2) t + 514 h,
+          w <= (5 + L) (h + t).
+
+  (C) If d(x, y) < sigma r/8, then the "positive slope" bound
+          [F_z^g(x) - F_z^g(y)]_+ <= C_loc (h+t) d(x,y)/r
+      holds, where C_loc is an explicit absolute constant like
+          (L + 1024/sigma)(514 + 8/sigma) + 1024(5+L)/sigma^2.
+      Roughly, at a concentrated point, the integrand can only
+      change by O(h+t) per unit of distance.
+
+Rough conceptual proof:
+
+  (A) A site in the middle shell would have a_s ~ 1 on the whole
+      inner ball (distance at least sigma/4 from a centre where the
+      a bump would peak, still well within a's heavy-support
+      region). So it would pay surcharge of about 256 * mu(inner)
+      but save the residual of at most 2 * mu(inner). Net cost
+      positive => cannot beat z = 0 on that coefficient.
+
+  (B) If we wiped the ball B(x, 5 D_* r) and placed a unit site
+      at x, then the mass in the inner ball (mass M) would witness:
+      old integrand >= 1 - Znew (because the old sites are all
+      outside, so residual there is 1 minus the one near-site
+      weight which is at most Znew). New integrand <= 512 t^2/sigma^2
+      there. Bounding the rest gives the weight deficit.
+
+  (C) Once you have (B), you move the near site from s to x by
+      paying relocation cost: the b bump is 1 at both, the a bump
+      moves from u^2/sigma^2 to v^2/sigma^2, surcharge change is
+      controlled by |w^2 - u^2| <= 2w|w-u|, applied pointwise. The
+      resulting positive-part bound is exactly C_loc(h+t) * d(x,y)/r.
+
+12.7 The drift bound.
+
+This is the potential's key feature. At each scale r_j, we have a
+g-function g_j (fixed for the step) and a measure update
+mu^- -> mu^+ = mu^- - nu + delta_x. We want:
+
+    sum over j of [ L_{r_j}(mu^+, g_j) - L_{r_j}(mu^-, g_j) ]_+
+        <= C_dr * ell * e_x.
+
+Where e_x = int d(x,y) dnu(y) is the expected mover distance.
+
+Sketch of the proof:
+
+  - For each scale, evaluate the new minimum at the OLD minimizer
+    z^(j). Then
+
+        L_{r_j}(mu^+, g_j) - L_{r_j}(mu^-, g_j)
+             <= r_j * int (F_j(x) - F_j(y)) dnu(y).
+
+    (Because the minimum at mu^+ is at most its value at z^(j),
+    and by linearity the difference is the integral of the difference.)
+    Take the positive part.
+
+  - At "small" scales, use F <= 514 always:
+        r_j < 2 e_x / gamma  =>  contribution <= 514 * sum r_j,
+        which sums to ~ (2056/gamma) e_x.
+
+  - At "large" scales, use inner mass >= 1/2:
+        M_j := mu^-(B(x, gamma r_j)) >= nu(B(x, gamma r_j)) >= 1 - e_x/(gamma r_j) >= 1/2.
+
+    Then Lemma pilot-local applies: either the scale is "good"
+    (h_j <= delta), in which case C_loc*(h_j + t_j) is small at
+    nearby points; or it is "bad" (h_j > delta), in which case only
+    Lambda e_x is paid at that scale.
+
+  - Sum over good scales uses TWO telescopes:
+        sum_j min{1, h_j} <= (p_0/log 2) log(2k)     (ball-mass telescope)
+        sum_j t_j         <= 2 gamma (1 + log(2k))   (moment telescope)
+    Both give ell-sized sums.
+
+  - Sum over bad scales: number of bad scales is
+        <= p_0 log(2 k) / (delta log 2) = O(ell).
+    Each bad scale contributes at most Lambda e_x. So total bad
+    contribution is O(ell) * e_x.
+
+  - Sum over far scales (where d(x,y) >= sigma r_j/8) can be
+    bounded geometrically: sum over such r_j of 514 r_j <=
+    (8224/sigma) d(x,y). Integrating against nu gives
+    (8224/sigma) e_x.
+
+  Combined:
+    C_dr = 2056/gamma + 8224/sigma + 2 Lambda p_0/(delta log 2)
+           + 2 C_loc (p_0/log 2 + 2 gamma).
+
+The headline: sum over ALL J scales of the positive drift is
+O(ell) * e_x. No log(J) factor. The number of levels NEVER
+appears. That is the beauty of the local concentration argument.
+
+12.8 The telescoping corollary.
+
+Here is how you actually USE the potential. Consider a family of
+templates indexed by some alpha, each with a nonnegative "weight"
+omega_alpha. Assumption:
+
+    A := sum_alpha omega_alpha < infinity,
+    B := sum_alpha omega_alpha C_dr_alpha < infinity.
+
+At each time step:
+
+  1. Reveal the new request. Do FILTERING with the OLD g-functions
+     (one per template). By concavity, the expected total potential
+     does NOT increase.
+
+  2. DRIFT to the new posterior. By the drift bound, the total
+     potential increases by at most B * ell * e_x.
+
+  3. EDIT: update the label maps and their associated g-functions.
+     Suppose the total potential DROPS by at least a charge c_t
+     (where c_t = 0 on steps without an edit).
+
+Then:
+
+    E sum over all t of c_t
+        <= B * ell * Q  +  sum_alpha 0.5 * (initial potential)
+
+    and the trailing term is <= 2 k A sum_j r_j  =  O(k A r_0 / (tau-1)).
+
+Two important sub-points:
+
+  - Filtering is summed over ALL steps, before any conditional
+    selection of edits. This is why we can bound expectation of
+    c_t unconditionally: no event-dependent conditioning.
+
+  - The COUNTABLY INFINITE index set alpha is allowed (for
+    example, alpha ranging over all tiers h = 1, 2, 4, ...), as
+    long as the weights are summable and the drift constants are
+    summable. This is essential for handling infinitely many tiers
+    with a fixed bound.
+
+12.9 Paying for an edit specifically.
+
+To apply this in a concrete structure, one checks the EDIT HYPOTHESIS:
+
+    L_r(mu^+, g_old) - L_r(mu^+, g_new) >= (desired charge).
+
+The paper uses the trick: if z is the OLD minimizer at the NEW
+measure mu^+, then
+
+    L_r(mu^+, g_old) - L_r(mu^+, g_new)
+       >= r * int (F_z^{g_old} - F_z^{g_new}) dmu^+.
+
+So we just need to LOWER-BOUND how much the old z "improves" when
+we pass from g_old to g_new. Which is exactly what the concrete
+edit structures show.
+
+12.10 Why the local structure lemma matters.
+
+You might wonder what forces the potential to have SMALL drift
+rather than paying 514 * e_x per scale. The answer: at good
+scales (small shell ratio h and small inner moment t), the near
+site sits very close to the request. Moving the request by d(x,y)
+moves the near site by at most d(x,y), which costs at most
+O(h+t) d(x,y)/r per unit of scaling factor r, and after multiplying
+by r the drift is O(h+t) * d(x,y).
+
+The sum over good scales of O(h+t) d(x,y) is O(ell) d(x,y) by the
+two telescopes.
+
+At bad scales we pay O(ell) e_x once, and the number of bad scales
+is O(ell).
+
+Everything telescopes neatly. That's the whole point.
+
+------------------------------------------------------------------------
+13. ONLINE PARTITIONS: HEAVY BALLS AND CHRONOLOGICAL ROSTERS
+------------------------------------------------------------------------
+
+Fix the pilot template with concrete constants. We will use TWO
+templates in this section: a "heavy" template (coarse sub-structure)
+and a "tier" template (fine sub-structure). The drift corollary
+of Section 12.8 is applied to each template separately, giving
+each template its own absolute drift constant C_dr.
+
+The goal of Section 13 is to construct the labelled maps
+xi_t : Y -> (A_1 x ... x A_J) and prove:
+
+    P  <=  C ell Q  +  D_part,
+
+where P is the tree-comparator movement. Recall from Section 10.7
+that P is E sum_t sum_a d_T(xi_{t-1}(X_{t-1}^a), xi_t(X_t^a)).
+
+13.1 The structures, top-down.
+
+The full map xi_t is built by stacking THREE sub-structures at each
+level j, with precedence from top to bottom:
+
+  1. HEAVY STRUCTURE. A set H_t^j of "heavy balls" at level j.
+     Any point in a heavy ball gets that ball's label.
+  2. TIER STRUCTURE. For each tier h in {1, 2, 4, ..., 2^b}, a
+     set of ball centers with radii from [r_j, 2 r_j], with
+     retirement lifetimes. A point not in any heavy ball gets the
+     label of its earliest-present covering tier ball.
+  3. SINGLETON. If neither covers the point, the point gets a
+     singleton label.
+
+Heavy has precedence over every tier. A tier with smaller h has
+precedence over a tier with larger h. This is the "when in doubt,
+small h is more important" priority.
+
+Both structures use the LOCAL posterior mass mu^+ at the request x.
+They are driven only by qualification conditions and chronological
+age. They never inspect the request stream's future.
+
+13.2 Heavy structure.
+
+Fix the heavy template: sigma = 1, R = 512, L = 1, so D_H = D_1 =
+100 R = 51200. Choose gamma_H in (0, 1/100) and delta_H in
+(0, 1/100) sufficiently small to satisfy the local structure lemma
+concentration requirements.
+
+A request x at scale r is called HEAVY at scale r if
+
+    mu^+(B(x, D_H r))  <=  (1 + delta_H) mu^+(B(x, gamma_H r)).
+
+Intuition: the mass in a small ball around x captures almost all
+mass in a much bigger ball around x. So the mass is very
+concentrated at x.
+
+At every step, process the following. The current request x is at
+some scale r = r_j.
+
+  1. If x is heavy AND the current heavy-center set H has no center
+     within 8 r of x: remove all centers within 100 r of x, then
+     insert x. The new center gets a fresh independent random
+     radius U ~ Uniform[16 r, 20 r], held until eventual removal.
+
+  2. If x is heavy AND some center is already within 8 r of x: do
+     not insert.
+
+  3. If x is not heavy: do not look at the heavy structure.
+
+The invariant: heavy centers are pairwise at distance > 100 r.
+(An insertion removes all within 100 r, and new one is at distance
+> 8 r > 100 r - 16 r from any neighbor after insertion.)
+
+For each level j, define the g-function that will be used in the
+pilot potential:
+
+    g_Hj(p)  =  rho_H( d(p, H_j) / r_j ),
+
+where rho_H is a clamped ramp increasing from 0 to 1 on [3, 4]. It
+detects centers within 3 r to 4 r. At a heavy update, the potential
+drop is at least 127 r mu^+(E_x(r)), where E_x(r) is the annulus
+(3 r, 120 r] around x. That pays for the update. So the total
+EXPECTED edit cost for heavy updates at level j is bounded by
+C ell Q + D_H'.
+
+13.3 Roster structure.
+
+For each level j and each tier h in H_k = {1, 2, 4, ..., 2^b},
+maintain a chronological roster: a growing list of insertion events.
+Each entry has:
+  - A center c (where it was inserted).
+  - An AGE (number of subsequent insertions of the same level-tier
+    whose center is within 20 r of c).
+  - A LIFETIME (random, described below).
+  - A RADIUS V drawn from [r, 2 r] with a specific density.
+
+Set K_h = ceil(e^{C_K h}) for an absolute constant C_K chosen
+large enough that, for every h >= 1, the two inequalities
+e^{-K_h / 2} <= (c/2) e^{-h} and e^{-K_h} <= (c/2) e^{-2h}
+hold simultaneously, where c > 0 is a fixed small absolute
+constant. The point is that tier-h retirement probabilities
+fall off fast enough in h that the two telescoping payments of
+Section 13.5 work uniformly over every h.
+
+A request x QUALIFIES in tier h at level j if
+
+    mu^+(B(x, D_L r_j))  <=  e^h  mu^+(B(x, gamma_L r_j)),
+
+where gamma_L < 1/100 is small (and D_L = 100 R = 400 D_H tier
+template constants). Higher h means WEAKER concentration threshold
+(more permissive). Tier 2^b (the last) always qualifies.
+
+INSERTION RULE. Insert x into tier h at level j if x qualifies
+and there is no existing entry of CURRENT AGE < K_h within r/2
+of x. If there is such an entry, do nothing (the "parent" already
+handles that neighbourhood).
+
+Note: age is measured purely CHRONOLOGICALLY (by counting later
+insertions), not randomly. It is deterministic given the request
+stream and the insertion schedule.
+
+RETIREMENT. An entry is DETERMINISTICALLY PRESENT at ages 0, 1,
+..., K_h - 1. At each subsequent age K_h, K_h + 1, ..., K_h^2 - 1,
+the entry RETIRES with fresh independent probability 1/K_h. At age
+K_h^2 it RETIRES COMPULSORILY.
+
+RADIUS. Each entry draws V from [r, 2 r] with density
+
+    f(v)  =  (lambda / r) * e^{-lambda (v/r - 1)} / (1 - e^{-lambda}),   r <= v <= 2 r,
+
+where lambda = log(1 + K_h^2). (This is roughly an exponential tilted
+toward r, with tail scale r / lambda.) All draws independent.
+
+THE KEY: because the insertion rule depends only on AGES (not on
+whether prior entries have retired), the insertion schedule is
+DETERMINISTIC given the request stream, and radii are independent.
+This is what makes the probability arguments in Section 13.4 work.
+
+13.4 The first-hit lemma.
+
+Now comes the probability estimate we need for separation. Fix a
+level j, a tier h, and two points x, y with d(x, y) = d << r.
+Consider the earliest present covering ball of either point in the
+tier's roster. Let
+
+    BAD = "the earliest present ball covers one of x, y but not
+          the other"
+
+(In other words, it SEPARATES x and y.)
+
+Then:  Pr(BAD)  <=  C h d / r.
+
+Where C is a fixed absolute constant and expectations are over the
+STRICTLY INDEPENDENT random radii.
+
+The proof is elegant: for a fixed center c with distances
+   a = min{ d(c, x), d(c, y) }
+   and given that a single present ball is "first", the two
+   distances differ by at most d. The ball separates x from y
+   only if V lies in a small window of width d, which under the
+   density f has probability at most
+
+       (2 lambda d / r) * (p_a + 1/(e^lambda - 1))
+
+   where p_a is the tail probability Pr(V >= a). Multiply by the
+   probability that all earlier balls MISS both points, sum over
+   the possible candidates (at most K_h^2 of them, by Lemma roster-
+   count), and use sum_i q_i p_{a_i} <= 1 (probability that SOME
+   higher ball hits one of the points is at most 1).
+
+The total is at most 2 lambda d / r. And lambda = log(1 + K_h^2) is
+at most C h (since C_K is fixed). So Pr(BAD) <= C h d / r.
+
+13.5 The two telescopes for the rosters.
+
+The map xi_t looks at heavy first, then at the earliest covering
+tier ball. Two "cost" quantities that we need to bound:
+
+  (i) PHYSICAL MOVEMENT. Each request x is compared to the previous
+      request y (the previous hidden comparator position of the
+      SAME label). We pay d(x, y) when a tier ball fires at one
+      point but not the other. Total contribution:
+
+           sum over levels j and tiers h <= h_*(j)
+             of R_j * Pr(BAD)  <=  R_j * C h_j d / r_j
+                                 = C d * h_*(j).
+
+      Where h_*(j) is the first qualifying tier level. Wait, but
+      we must sum across tiers. The set of queried tiers at a
+      level is those where the point QUALIFIES. That gives a
+      bound of the form
+             sum over these h of h * d / r_j
+           = O( (1 + h_*(j)) * log(2) ) * d / r_j
+           = O( h_*(j) ) * d / r_j.
+
+      Where h_*(j) is roughly log of mass ratio at level j.
+
+  (ii) INSERTIONS. Each insertion into tier h at level j costs
+       O(r_j / K_h) times its "W mass" (see next) and we want to
+       sum these. The "W mass" is defined as
+
+           W_{t,j,h} = mu^+(B(x, D_L r_j))  if nonheavy,
+                       mu^+(annulus gamma_H r_j < d(p,x) <= D_H r_j)  if heavy.
+
+       So the insertion charge is r_j * W_{t,j,h} / K_h. Bounding
+       sum over insertions of this by C ell Q + fixed is what the
+       auxiliary short roster below is for.
+
+13.6 Short roster - paid by the pilot potential.
+
+The insertion charges are paid as follows. For each level j and
+tier h, we build an "auxiliary" roster with the SAME deterministic
+insertion schedule but different random lifetimes:
+
+    - An entry is present at age 0.
+    - At each subsequent age increment up to age K_h, it retires
+      with fresh probability 1 / sqrt(K_h).
+    - At age K_h it retires compulsorily.
+
+The auxiliary roster's function is
+
+    g(p)  =  E_auxiliary [ rho_L( d(p, S) / r ) ],
+
+where rho_L is a clamped ramp on [1/8, 1/4] and S is the current
+set of surviving auxiliary centers. This is the EXPECTED version of
+a ramp. Note: the auxiliary roster's g function is DETERMINISTIC
+given the request stream, because the auxiliary lifetimes are
+averaged out.
+
+BOUND on retirement effect: at any p, an increase in g can only
+happen if the old nearest auxiliary center retires. Retirement
+probability per age increment is at most 1/sqrt(K_h), and the
+number of possible compulsory retirements over a neighbourhood is
+at most K_h (by the roster count lemma). So
+
+    Pr(old nearest retires) <= K_h^{-1/2} + K_h (1 - K_h^{-1/2})^{K_h - 1}
+                              <= C / sqrt(K_h).
+
+Positive support of g-changes is contained in
+B(x, 21 r) \ B(x, r/8) - within the shell.
+
+AT INSERTION: the positive change of g at x is 1 (it was 1 before
+the insertion in the ball B(x, r/8), and the new entry covers x at
+any radius in [r, 2r], making g(x) = 0). So the g function "drops"
+at x during the insertion. That drop drives the pilot potential's
+decrease.
+
+Let z be the OLD minimizer of the pilot potential at the new
+measure mu^+. The pilot drop when we edit g_old -> g_new is at
+least r * int (F_z^{g_old} - F_z^{g_new}) dmu^+. The paper
+estimates this from below as (c e^{-h} - C/sqrt(K_h)) r W.
+
+With K_h = ceil(e^{C_K h}) and C_K large enough, the C/sqrt(K_h)
+error is absorbed by the c e^{-h} leading term The final inequality:
+r W / K_h <= e^{-h} * (pilot potential drop).
+
+So the pilot potential provides at least r W / K_h of drop per
+insertion. By Corollary 12.8 (with weights e^{-h} on all tiers,
+which are summable), this gives
+
+    E sum over all insertions of r_j W_{t,j,h} / K_h
+        <= (weighted template drift) ell Q + fixed
+        = C ell Q + D_ins.
+
+13.7 Two structures combined.
+
+Combining the heavy-edit budget (C ell Q + fixed) and the roster
+edit budget (C ell Q + fixed), and adding the physical-motion
+budget from the two structure's separation estimates (C ell * Q
+via the scale sum), we get:
+
+    P  <=  C ell Q  +  D_part.
+
+This is the statement we needed to plug into Section 11's
+allocation theorem. The whole partition construction is thus
+budgeted with a SINGLE factor of ell above the offline optimum Q,
+plus a fixed initialization term.
+
+Note: the "log number of levels" trap is avoided by the ball-mass
+telescope (Section 9.6), applied to the ratios of inner-to-outer
+masses at each scale.
+
+------------------------------------------------------------------------
+14. PARKED MASS AND MOVING ANCHORS: PAYING FOR REUSED LABELS
+------------------------------------------------------------------------
+
+The allocation theorem gives us real masses q_v on tree vertices.
+Section 15 will round to integers. Before that, we need to solve a
+DIFFERENT problem: the masses are represented in the true metric by
+ANCHORS (one anchor per active tree vertex). When a tree vertex
+retains its label from step to step but its anchor moves - because
+of heavy-ball reuse - the "parked mass" at that vertex must be
+"carried" to the new anchor. We must pay for that.
+
+14.1 Parked mass.
+
+Recall the allocation: q_v is the mass at vertex v, with
+q_root = k and sum_children q_i <= q_v. The "parked mass" at v:
+
+    p_{t,v}^circ  :=  q_{t,v}  -  sum_{i child of v} q_{t,i}.
+
+The mass that is "redistributed to children's subtrees" plus the
+"parked at v itself" equals q_v. At leaves there are no children,
+so p_{t,leaf}^circ = q_{t,leaf}. The whole subtree sums to q_v:
+
+    sum over w descendant of v of p_{t,w}^circ = q_{t,v},
+    sum over all v of p_{t,v}^circ = k.
+
+14.2 Variation of parked masses.
+
+By taking differences and using the triangle inequality (a short
+computation), one gets
+
+    sum_v r_{|v|} |Delta p_v^circ|  <=  (1 + 1/tau) V,
+
+where V is E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|. So if
+the q_v's move by V, the parked masses move by at most (1+1/tau) V.
+No extra factor.
+
+14.3 Validity witnesses.
+
+If q_{t,v} > 0, then p_{t,v'}^circ > 0 for some descendant v' of v.
+In particular, some point of Y has a leaf below v (so its complete
+word has prefix v). Call such a point a "witness". Also, by the
+fixed-alphabet property (Section 10.5), every witness for v is
+within 20 r_{|v|} of v's last key's anchor.
+
+14.4 Anchor travel cost.
+
+We need to pay for anchor MOVEMENT when a retaining key survives
+but its anchor changes. Precisely, per fixed heavy label slot
+lambda at level j, define:
+
+    b_{t,j,lambda}  =  sum over depth-j vertices v whose last key
+                       is lambda of p_{t,v}^circ.
+
+    M_{t,j,lambda}  =  mu_t(C_{t,j,lambda})   (label region mass).
+
+Also define the retention condition:
+
+    E_{t,j,lambda} = "label lambda is present at BOTH times t-1
+                      and t, and its anchor moved."
+
+The total anchor travel cost is
+
+    T_anchor  :=  E sum_{t, j, lambda} r_j b_{t,j,lambda} 1_{E_{t,j,lambda}}.
+
+Note: the factor r_j times b is the "mass times tree-radius"
+quantity that pricing an anchor move at scale r_j requires. By the
+fixed-alphabet property (Section 10.5), an anchor move is by at
+most 40 r_j. So actual displacement in the metric is at most
+40 T_anchor.
+
+14.5 What we want.
+
+Proposition (retained-anchor travel). There is an absolute C and a
+finite D_anchor, both independent of the input law and horizon,
+such that
+
+    T_anchor  <=  C (V + ell P + ell Q)  +  D_anchor.
+
+This is the last piece before rounding. Combined with V <= C ell P
++ D_T and P <= C ell Q + D_part, it becomes
+
+    T_anchor  <=  C ell^2 Q  +  D_anchor',
+
+which is exactly the needed order.
+
+14.6 The size tracker.
+
+To pay for anchor movement we need a "per-key normalization" that
+stays roughly constant while the underlying key's posterior size
+evolves. Fix a heavy label slot lambda at level j. Define
+
+    s_{t,j,lambda}  :=  1 + M_{t,j,lambda},
+
+a positive number in [1, k + 1]. Track it by a held reference
+mhat_{t,j,lambda} in [1, k+1]: refresh when a factor rho = 6/5
+comparison with the actual s fails. The reference runs all the time,
+even while the label is absent, and recycled labels do NOT restart
+the tracker. This is essential: no new initialization allowance can
+be charged when a label reappears.
+
+The lemma: the total expected refresh cost satisfies
+
+    E sum_{t,j,lambda} r_j (mhat_{t-1} + mhat_{t}) 1_{refresh}
+       <=  C ell P  +  D_size.
+
+The proof uses an entropy trick: the affine tangent of
+f(s) = -s log s at u is T_u(s) = u - (1 + log u) s, and the
+"return" from u to s at a refresh is
+
+    T_u(s) - T_s(s)  >=  (s + u) / 144,
+
+because the refresh condition implies |s - u| >= (1 - 1/rho)
+max(s,u). Then the input contribution to the tangent sum is
+O(ell P) via the key-count drift of Section 10.5. And the endpoint
+values of the tangent sum are bounded by (k+1)(1+ell) times the
+finite number of label slots. So the total refresh charge is
+C ell P + D_size.
+
+14.7 The pointwise coefficient bound.
+
+Anchor travel is charged via a potential with COEFFICIENT
+b_{t,j,lambda} / mhat_{t,j,lambda}. We need this coefficient to be
+summable over scales. The following lemma does it, using both ball
+masses in the metric.
+
+Lemma (pointwise parked coefficients). Fix a completed fractional
+state (a specific time t) and any y in Y. Let, at each level j with
+a heavy center within 7 r_j of y, lambda_j be its (unique) label.
+Then
+
+    sum over selected j of  b_{j, lambda_j} / mhat_{j, lambda_j}  <=  C ell.
+
+Where "selected" means "a heavy center within 7 r_j of y".
+
+Idea of proof. At a selected level, the heavy ball (radius >= 16 r_j)
+contains B(y, r_j), so mhat_j >= (1 + mu(B(y, r_j))) / rho, which
+gives a lower bound on the denominator. At the numerator side, use:
+
+    sum over selected i >= j of b_i  <=  C_0 mu(B(y, 67 r_j)),
+
+because for each i, all witnesses lie within 27 r_i <= 27 r_j of y,
+and their subtrees have prefix-masses in a set of disjoint depth-j
+cells, all within B(y, 67 r_j).
+
+Then the ratio b_j / mhat_j is bounded by
+
+    (mu(B(y, 67 r_j)) - previous) / (1 + mu(B(y, r_j))).
+
+Summing this over j is exactly a "ball mass ratio" sum, and the
+ball-mass telescope (Section 9.6) bounds it by O(ell). The paper
+organizes the details into a dyadic partition of the levels by A_j /
+B_j magnitudes. Result: at most 1 + log_2(k+1) dyadic groups, each
+contributing at most C.
+
+Consequence: the total coefficient of a point-wise normalized
+potential grows only like ell across scales. That is why anchor
+travel can be paid by O(V + ell P + ell Q), without a log(J) factor.
+
+14.8 The anchor travel potential.
+
+Define, at each completed state,
+
+    Phi_t  :=  sum_{j, lambda} r_j ( b_{t,j,lambda} / mhat_{t,j,lambda} )
+                 * int_{C_{t,j,lambda}} kappa( d(a_{t,j,lambda}, z) / r_j ) dmu_t(z),
+
+where kappa is a clamped ramp:
+
+    kappa(u)  =  0                     for u <= 4,
+                 (u - 4) / 3           for 4 <= u <= 7,
+                 1                     for u >= 7.
+
+Interpretation: at each heavy label, we integrate mu (the posterior
+counting measure) over its region C, weighted by a normalized ramp
+that is 0 near the anchor and 1 for points far from it (>= 7 r_j
+away). The pre-factor b / mhat normalizes by the "current size" of
+the key.
+
+Bound on Phi: since 0 <= kappa <= 1 and |int| <= M <= mhat, we have
+0 <= Phi <= sum r_j b_j <= k r_0 (using that sum of parks over all
+vertices is k and each park at depth j has radius r_j <= r_0).
+
+14.9 Decomposing the change of Phi.
+
+The change Phi_{t-1} -> Phi_t is decomposed in five sub-steps,
+each handled separately:
+
+  1. FILTERING (old parameters held): by concavity, the expected
+     change is at most 0.
+
+  2. DRIFT (physical movement, still at old anchor, old reference,
+     old park). If the level key changes, we pay at most C r_j by
+     |b / mhat| <= C_0 and 0 <= kappa <= 1. Summing over the key
+     disagreement stops per member and over all members gives CP
+     in expectation. If the key is UNCHANGED, only one hidden
+     mover moves, and the pointwise coefficient bound (14.7)
+     charges its small physical movement to at most C ell e_x per
+     step. Total ell Q.
+
+  3. REFRESH size references. When the reference changes r_j b I
+     (1/s - 1/u), the positive part (only when s < u) is at most
+     r_j b^{old} <= rho C_0 u times (1/mhat_old before change).
+     This is at most a constant times the refresh charge, i.e.
+     C ell P + D_size.
+
+  4. UPDATE park amounts. |Delta b| charged by park variation
+     (14.2): rho (1 + 1/tau) V.
+
+  5. UPDATE anchors. A freshly present key had b^{old} = 0, so its
+     new anchor contribution is rho r_j b^{new} = rho r_j |Delta b|,
+     again part of the park variation budget. A retained-and-moved
+     heavy anchor: at a heavy update, the concentration condition
+     gives a strong inner-mass comparison, and the potential
+     DECREASES by at least (1/4) r_j b^{new}_{j,lambda}. THIS is
+     the payment for the specific event we care about.
+
+The last line is the crux. Let's see the details:
+
+At a retained-and-moved heavy label at scale r = r_j:
+- The new anchor a_new = x (request).
+- Old anchor a_old has d(a_old, x) > 8 r.
+- Inner ball B(x, gamma_H r) has mu^+ mass H >= 1 (comparator
+  covers x).
+- New heavy-ball mass satisfies mu^+(C) in [H, (1+delta_H) H].
+- New size tracker mhat_new <= rho (1 + mu^+(C)) <= rho (2 + delta_H) H.
+- Old ramp kappa(d(a_old, z)/r): for z in B(x, gamma_H r), the
+  distance d(a_old, z) > (8 - gamma_H) r > 7 r, so kappa = 1.
+- New ramp kappa(d(x, z)/r): for z in B(x, gamma_H r), d(x, z) <=
+  gamma_H r < 4 r, so kappa = 0.
+- Change in the ramp at z: -1.
+- Extra mass outside the inner ball but inside C contributes at
+  most delta_H H to the other direction (a bounded increase).
+- Net decrease of the potential at this label: at least
+  (1 - delta_H) H / (rho (2 + delta_H)) * r b_new.
+
+With gamma_H < 1/100 and delta_H < 1/100 and rho = 6/5, this is at
+least (1/4) r b_new.
+
+So the event's charge is paid in full by the potential drop. No
+extra log, no extra scale factor.
+
+14.10 Putting it together.
+
+Summing the five sub-steps over all t:
+
+    Phi_0 - Phi_T  +  C (V + ell P + ell Q)  +  D_size  >=  (1/4) T_anchor.
+
+Using 0 <= Phi <= k r_0, we get the proposition.
+
+14.11 The role in the final bound.
+
+Combined with Section 11's V <= C ell P + D_T and Section 13's
+P <= C ell Q + D_part, we get:
+
+    T_anchor  <=  C ell^2 Q  +  D_anchor'.
+
+So anchor travel is "the same order as the rest". This is the last
+piece needed before rounding.
+
+------------------------------------------------------------------------
+15. ROUNDING: FROM FRACTIONAL MASS TO INTEGER SERVERS
+------------------------------------------------------------------------
+
+Everything so far produces REAL masses q_v on the tree, and REAL
+parks p_v^circ = q_v - sum_children q_i. But actual servers are
+DISTINCT; there are exactly k of them; each occupies ONE tree
+vertex. We need to round.
+
+15.1 The problem.
+
+Find integer quantities n_v(t) and c_v(t) at each vertex, with:
+
+    n_root(t) = k
+    n_v(t) = c_v(t) + sum_children n_i(t)         for internal v
+    c_leaf(t) = n_leaf(t)                         (leaves have no children)
+    n_v(t) in {floor(q_v(t)), ceil(q_v(t))}       (balanced rounding)
+    c_v(t) in {floor(p_v^circ(t)), ceil(p_v^circ(t))}
+    E[n_v(t) | F_t] = q_v(t),     E[c_v(t) | F_t] = p_v^circ(t)
+
+The first four are unconditional properties of ROUNDING; the last
+three are EXPECTATION identities (unbiased at every vertex).
+
+The integer "parks" c_v(t) tell us how many servers occupy vertex v
+at time t. Total across all v is exactly k. Children inherit their
+subtree counts from c_v.
+
+15.2 A local rounding lemma (the key building block).
+
+This one lemma is the crown jewel of the rounding section. Here is
+the exact statement.
+
+Lemma (balanced rounding with prescribed random total). Let
+a = (a_1, ..., a_d) and b = (b_1, ..., b_d) be nonnegative real
+vectors. Let X be a random integer vector with
+
+    X_i in {floor(a_i), ceil(a_i)}     for every i,
+    E X_i = a_i                        for every i.
+
+Let M = sum_i X_i. Also, N is any random integer with
+
+    N in {floor(sum b_i), ceil(sum b_i)},
+    E N = sum b_i.
+
+Then there is a randomized kernel from (X, N) to integer vectors X'
+such that for EVERY state (X, N) and EVERY outcome of the kernel,
+
+    X'_i in {floor(b_i), ceil(b_i)},
+    sum_i X'_i = N,
+    E[X'_i] = b_i                        (averaged over both X, N and the kernel).
+
+The expected L1 cost is bounded by
+
+    E ||X' - X||_1  <=  32 T + 11 I,
+
+where  T = sum_i |a_i - b_i|   and   I = E |N - M|.
+
+The heart of the proof is a "repair by exchanges" argument. Here
+is the idea:
+
+STEP 1 (clip). For each coordinate, clip X_i to [floor(b_i),
+ceil(b_i)]. Let Y be the clipped vector. Then
+
+    E |Y_i - X_i|  <=  |a_i - b_i|,
+
+because at most one side of the interval can differ from a_i's
+neighborhood. So sum over i of E |Y_i - X_i| <= T.
+
+STEP 2 (adjust to N). For each realized state (Y, N), adjust
+coordinates up or down until the sum equals the actual N, obtaining
+Z. This is always possible: the set of achievable integer sums
+within the box is every integer between sum floor(b_i) and
+sum ceil(b_i), and N lies in that set. The adjust cost is exactly
+|N - sum Y_i|, so
+
+    E ||Z - X||_1  <=  2T + I.
+
+STEP 3 (repair means). Now Z has the right fixed-total property in
+each state but the coordinate means E Z_i may not equal b_i. The
+discrepancy D := sum_i |E Z_i - b_i| <= 3T + I.
+
+To fix the means, choose a finite joint kernel p_state (a
+probability distribution on "which coords to round up" per state,
+preserving the per-state total). Consider the finite-dimensional
+convex optimization:
+
+    minimize  E[|A symdiff A_0|]  +  10 sum_i |Pr(i in A) - f_i|,
+
+where A_0 is Z's rounding-up-set (from Step 2), f_i = b_i -
+floor(b_i) is the fractional part, and A ranges over allowed
+rounding-up-sets (those of size (N - sum floor(b_i))). Compactness
+of the domain gives a minimum.
+
+If a marginal Pr(i in A) is bigger than f_i for some i and
+smaller for some j, one of two local exchanges strictly improves
+the objective:
+
+(a) If some supported pair (state, subset) has i in A and j not
+    in A: swap i out and j in, on a small mass epsilon. Total per
+    state is preserved. Sum of marginal discrepancies drops by
+    2 epsilon. Hamming cost rises by at most 2 epsilon. Strict
+    improvement, contradiction.
+
+(b) Otherwise, no supported subset has i without j. Then find one
+    with both, one with neither, one h in the second but not the
+    first (cardinalities differ by at most 1, so such an h exists),
+    and swap. Now it is i out, h in on the first subset and h out,
+    j in on the second. Sum of marginals moves in the right
+    direction on i and j and leaves h alone. Hamming cost rises by
+    at most 4 epsilon. Strict improvement, contradiction.
+
+So at a minimizer, Pr(i in A) = f_i for all i, giving E X'_i =
+b_i.
+
+STEP 4 (compare). The kernel X' equals Z everywhere up to a
+Hamming correction, with E ||X' - Z||_1 <= 10 D <= 10 (3T + I).
+Combining: E ||X' - X||_1 <= (2T + I) + 10(3T + I) = 32 T + 11 I.
+
+The lemma is self-contained, entirely finite, and needs NO
+independence assumption between X and N. Exactly what we need for
+top-down rounding.
+
+15.3 Top-down rounding through the tree.
+
+Apply the lemma recursively from the root down. At every internal
+v, treat the "star" whose coordinates are:
+
+    (children of v) x  (one coordinate for v's own park).
+
+Target vector b = (q_i)_{i child of v} x (p_v^circ). Sum of
+targets is q_v (exactly the allocation rule). Current X = previous
+step's rounded children and park. The prescribed total N is n_v(t),
+the already-generated rounded parent count.
+
+By induction, at each v we have:
+
+    sum of children counts + park count = n_v(t)  (in every state),
+    E[child i count | F_t] = q_i(t),
+    E[park count | F_t] = p_v^circ(t).
+
+At the root, n_root = k is fixed. So the sum of all parks is k in
+every realized state.
+
+15.4 Bounding the tree movement.
+
+Let N_rnd := E sum_t sum_{v != root} r_{|v|-1} |n_v(t) - n_v(t-1)|.
+
+The lemma's 32 T + 11 I structure combines with the totals over
+the tree via a simple absorption. The parent's own |Delta n_v|
+term appears with coefficient 11 at star v. The 32 factor multiplies
+the T terms at v, which are O(sum children + own park) = O(V)
+per step.
+
+Result: with tau >= 22 (a specific numerical requirement), one has
+
+    N_rnd  <=  132 V.
+
+Note the 132 is 4 x 33 roughly: it comes from (64 + 32/tau) V +
+(11/tau) N_rnd, then solving for N_rnd <= (128 + 64/tau) V <=
+132 V.
+
+15.5 Tree matching (from rounded parks to actual positions).
+
+We have integer parks c_v(t) at each vertex. Each vertex is a
+"supply" of c_v(t) units, or a "demand" if the local integer
+count declined. We want a matching cost bound per step.
+
+Match min{c_v(t-1), c_v(t)} copies AT the same vertex; these cost
+zero TREE distance (they may cost something metric if their anchor
+moved, handled separately below). The unmatched copies form an
+integer supply-demand problem on the tree.
+
+Standard tree-matching lemma:
+
+    match supplies to demands by canceling them node-by-node,
+    bottom-up, propagating uncancelled copies to the parent.
+
+The total TREE distance traveled by an integer unit is exactly the
+sum over nonroot vertices of (edge length entering v) * |Delta n_v|,
+where n_v is the total subtree count. Because the subtree imbalance
+is exactly Delta n_v, and that must cross the entering edge.
+
+So the tree matching cost per step is at most
+
+    sum over v != root of r_{|v|-1} |n_v(t) - n_v(t-1)|.
+
+15.6 Realizing on the metric space Y.
+
+We have integer "parks" at tree vertices. We now place those copies
+in the ACTUAL metric Y, using the anchors:
+
+    A copy parked at a nonroot vertex v is placed at the current
+    anchor of v's last key.
+    A copy parked at the root is placed at a fixed reference point
+    of Y.
+
+The matching of consecutive configurations in the METRIC: the tree
+matching suggests a "path" per matched copy. If two copies matched
+at the SAME vertex v are placed at its (consecutive) anchors, their
+metric distance is bounded by the anchor travel T_anchor (paid by
+Section 14). If two copies matched at DIFFERENT vertices u (old)
+and v (new), we need to bound their metric distance.
+
+Lemma (metric cost of distinct-vertex tree match). Let u (old) and
+v (new) be vertices matched by the tree matching. Let j be the
+depth of their lowest common ancestor. Then
+
+    d(a_-(u), a_+(v))  <=  120 r_j,
+
+where a_-(u) is u's old anchor and a_+(v) is v's new anchor. And
+r_j is at least the tree path length between u and v.
+
+So metric matching cost <= 120 times tree matching cost.
+
+15.7 Total rounding + realization.
+
+Combining:
+
+    E[ total simulated metric movement ]
+       <=  120 N_rnd  +  40 T_anchor
+       <=  120 * 132 V  +  40 T_anchor.
+
+Justification of the second summand: a matched pair at the SAME
+vertex v could have moved (bounded by 40 r_{|v|}, hence by T_anchor
+when paid per unit of parked mass). The 40 comes from the heavy
+reuse displacement bound (Section 10.5).
+
+15.8 Combining with Sections 11-14.
+
+Plug in:
+
+    N_rnd  <=  132 V,
+    V      <=  C_1 ell P + D_T,
+    P      <=  C_P ell Q + D_part,
+    T_anchor  <=  C_T (V + ell P + ell Q) + D_anchor.
+
+Then:
+
+    E[ total simulated metric movement ]
+       <=  C_1 * V + C_2 * ell P + C_2 * ell Q + D_{sim},
+
+for absolute C_1, C_2 and finite D_{sim}, which is exactly
+
+    <=  C_sim ell^2 Q  +  D_{sim}'.
+
+And by the lazy simulation lemma (Section 8), the ACTUAL cost on
+real servers is at most the simulated cost plus the one-time
+initial matching distance between the actual start and the initial
+simulated configuration. Giving the choice of zero initial mismatch
+(cf. the fixed-alphabet construction) or the bounded k*diam
+initial mismatch, this completes the "finite distributional
+estimate" (Proposition in Section 9).
+
+15.9 Chained bound.
+
+Combining the layers:
+
+    V            <= 12 C_A ell P       + D_A,
+    P            <= C_P ell Q          + D_P,
+    T_anchor     <= C_T (V + ell P + ell Q) + D_T,
+    N_rnd        <= 132 V,
+    sim-cost     <= 120 N_rnd + 40 T_anchor,
+    actual       <= sim-cost + initial_mismatch.
+
+Plug in from the bottom up:
+
+    sim-cost  <= C_1  V + C_2 ell P + C_2 ell Q + D_sim
+              <= C_1 (12 C_A ell P + D_A)
+                 + C_2 ell (C_P ell Q + D_P)
+                 + C_2 ell Q + D_sim
+              <= C_3 ell^2 Q + D_sim'.
+
+Where C_3 collects the coefficients. And then
+
+    actual <= C_3 ell^2 Q + D_sim' + k * diam(Y) * 1_{start not perfectly covered}.
+
+So we have a policy whose expected cost is <= C_3 ell^2 Q + D_0
+for SOME absolute C_3 and a fixed finite D_0.
+
+This is exactly Proposition (finite distributional estimate) in
+Section 9. The rest of the paper transfers this to actual policies
+on arbitrary metric spaces.
+
+------------------------------------------------------------------------
+16. TRANSFER: FROM ONE LAW TO ONE POLICY ON ANY SPACE
+------------------------------------------------------------------------
+
+Everything above proves: for a FIXED finite metric space Y, FIXED
+horizon H, FIXED probability law on Y^H, and FIXED starting tuple s,
+there is a policy with
+
+    E[cost] <= a * ell^2 * E[OPT]  +  D_0(Y, k, s),
+
+where a is an absolute constant and D_0 is a fixed finite number
+depending only on (Y, k, s), not on the law or on the horizon.
+
+We now remove the law, the horizon, the finiteness of Y, and the
+additive term. Four steps.
+
+16.1 What needs to be removed.
+
+The finite-law statement has FOUR "undesirable" dependencies:
+
+  (i)   It assumes a specific finite probability law on Y^H.
+        We want a policy that works for a single fixed sequence,
+        not just in expectation over a random one.
+
+  (ii)  It has an additive constant D_0.
+        We want D_0 = 0, at least when starting positions are
+        distinct.
+
+  (iii) It works on the specific finite metric Y.
+        We want a statement for an ARBITRARY metric space, which
+        can be infinite and have no minimum gap.
+
+  (iv)  It depends on the horizon H.
+        We want one policy that works for every finite H
+        simultaneously.
+
+Steps 16.2 through 16.5 handle these four in order.
+
+16.2 Episode amplification: remove the additive term.
+
+Fix Y finite, k >= 2, and a starting tuple s = (s_1, ..., s_k) with
+DISTINCT entries. Fix any finite-support law lambda on finite
+sequences in Y.
+
+Claim (goal of this subsection). There is a policy A_lambda, causal
+and strongly lazy, such that for every sigma in the support of
+lambda:
+
+    E[cost_{A_lambda, s}(sigma)]
+         <= alpha * OPT(s, sigma),
+    with alpha := (2a + 1) * ell^2.
+
+No additive term. Note that A_lambda does NOT depend on sigma, but
+it DOES depend on lambda. This is a "finite-law" policy.
+Later (Section 16.3) we upgrade to a single policy independent of
+lambda.
+
+THE PADDED WORD. Let L = max(1, max |sigma| over support of
+lambda). Extend every sequence sigma in the support to a padded
+word rho of exactly L requests, by repeating its last request. (If
+sigma is empty, use L repetitions of s_1.)
+
+Padding does NOT change OPT:
+    OPT(s, rho)  =  OPT(s, sigma),
+because:
+  - Restricting a legal service of rho to its first |sigma| slots
+    already serves sigma, so OPT(s, sigma) <= OPT(s, rho).
+  - An optimal service of sigma is trivially extended to rho by
+    moving nothing on the repeated request: the last request is
+    already covered. So OPT(s, rho) <= OPT(s, sigma).
+
+THE REVERSE WORD. For each padded word rho, choose (deterministic
+tie-breaking) ONE optimal service from s. Let C_t(rho) be the
+configuration chosen by that optimal service at time t, and let
+j_t be the label of the server moved at time t. Define the reverse
+word:
+
+    rho_leftarrow  :=  ( C_{L-1,j_L}(rho),  C_{L-2,j_{L-1}}(rho),
+                          ...,  C_{0,j_1}(rho) ).
+
+Interpretation: this is a length-L word that is legally served by
+the single server j_L moving first, then j_{L-1}, ..., then j_1.
+If you start from C_L(rho) and do exactly those single-server
+moves, you retrace the original optimal service BACKWARD and return
+to C_0 = s, at the same total cost OPT(s, rho).
+
+THE RESET WORD. Given the distinct starting tuple s, define the
+reset word as R repetitions of the k symbols (s_1, ..., s_k), where
+
+    R  =  floor( k * diam(Y) / delta ) + 1.
+
+Here delta is the minimum gap between distinct points of Y (defined
+in Section 7.5). The reset word is served by moving each server to
+its own starting point in order; the cost at each move is at most
+diam(Y); total reset cost is at most R * k * diam(Y), which is
+finite.
+
+THE CONCATENATED EXPERIMENT. Fix an integer N >= 1. Sample N
+independent words rho_1, ..., rho_N from lambda. Concatenate for
+each i its forward word, its reverse word, and the reset word:
+
+    sigma_N  :=  rho_1 rho_1_leftarrow (reset) rho_2 rho_2_leftarrow (reset) ... rho_N rho_N_leftarrow (reset).
+
+The total length is fixed: N * (2L + Rk). The law of sigma_N is a
+fixed finite-support probability distribution that DOES NOT DEPEND
+on the policy.
+
+AN OPTIMAL SERVICE OF sigma_N. Use the previously chosen optimal
+service on each forward word, its reverse on each reverse word,
+and the obvious reset on each reset block. The total cost obeys:
+
+    cost of this service of sigma_N
+       <= sum_i (2 OPT(s, rho_i)) + sum_i (reset cost)  (reset cost
+    is 0 at the boundary between blocks).
+    = 2 sum_i OPT(s, rho_i).
+
+In expectation over rho_1, ..., rho_N drawn from lambda:
+
+    E[ OPT(s, sigma_N) ]
+       <= 2N * E_{rho ~ lambda}[OPT(s, rho)]
+       = 2N * Q_lambda,
+
+where Q_lambda := E_{rho ~ lambda}[OPT(s, rho)].
+
+THE FINITE-LAW POLICY ON sigma_N. Apply the finite distributional
+estimate (Section 15) to sigma_N under its law. This gives a policy
+A_N, causal and strongly lazy, with
+
+    E[ cost_{A_N, s}(sigma_N) ]
+       <= a ell^2 * E[ OPT(s, sigma_N) ] + D_0(Y, k, s)
+       <= a ell^2 * (2N Q_lambda) + D_0.
+
+EXTRACTING ONE FORWARD BLOCK. Run A_N on sigma_N. Let F_i, H_i, Z_i
+be its costs on the i-th forward block, its i-th reverse block, and
+its i-th reset block. Let A_i be its configuration at end of block
+i's reset word. Set M_i := M(A_i, s) = matching distance from A_i
+to s. And M_0 := M(s, s) = 0 (the start).
+
+Claim (pathwise):  M_i <= Z_i  for every i.
+
+Why? If Z_i = 0, the actual policy did not move during the reset
+block. A full reset cycle of zero movement leaves the multiset of
+server positions unchanged. Because there are exactly k servers
+and k distinct starting points, the multiset must be exactly s. So
+M(A_i, s) = M(A_{i-1}, s) = ... = M(A_0, s) = 0, so M_i = 0 <=
+Z_i.
+
+If Z_i > 0, then during the reset cycle some server moved. Because
+the reset word visits each of s_1, ..., s_k in order and the
+policy is strongly lazy, either a move occurs (in which case
+Z_i >= shortest nonzero move distance = k * delta > k * delta/2),
+or the configuration already matches s up to permutation and M_i
+= 0. So M_i <= k delta/2 < Z_i in the positive case. Uniformly
+M_i <= Z_i holds.
+
+THE "EXTRACT A FORWARD BLOCK" CONSTRUCTION. Now:
+- Set I = uniform in {1, ..., N}.
+- Sample sigma ~ lambda.
+- Run A_N virtually on the concatenation from 1 through forward
+  block I (all the previous blocks included), starting at s.
+- Let A be the resulting policy's configuration on the current
+  forward block plus its starting history.
+
+Define the actual policy A_lambda by running this construction
+fresh at each request, always with I = "current block" and using
+the finite-law policy A_N to define the virtual evolution.
+
+Because of lazy simulation (Section 8), the actual policy's cost
+on the current forward block is at most (virtual cost through this
+block) + M_{I-1} (initial mismatch between A_{I-1} and s).
+
+Summing expectations:
+
+    E[ cost_{A_lambda, s}(sigma) ]
+       <= (1/N) sum_{i=1}^N E[ F_i + M_{i-1} ]
+       <= (1/N) sum_{i=1}^N E[ F_i + Z_{i-1} ]
+       =  (1/N) E[ (sum F_i) + (sum_{i < N} Z_i) ]
+       <= (1/N) E[ cost_{A_N, s}(sigma_N) ].
+
+The last inequality drops the H_i and Z_N terms because they are
+nonnegative.
+
+Plugging in the total bound:
+
+    E[ cost_{A_lambda, s}(sigma) ]
+       <= (1/N) [ a ell^2 * 2N Q_lambda + D_0 ]
+       =  2a ell^2 * Q_lambda + D_0 / N.
+
+Finally CHOOSE N large enough that D_0 / N <= ell^2 * Q_lambda:
+
+    N  =  max( 1, ceil( D_0 / (ell^2 * Q_lambda) ) ),
+
+and obtain
+
+    E[ cost_{A_lambda, s}(sigma) ]
+       <= (2a + 1) ell^2 * Q_lambda
+       =   alpha * OPT(s, sigma).
+
+This completes 16.2. Note: N depends on the law lambda, but NOT on
+any realization of sigma_N. The policy A_lambda itself is a fixed
+causal strategy.
+
+16.3 Finite-family separation via Yao.
+
+Now fix Y finite, k >= 2, s with distinct entries, and any FINITE
+collection sigma_1, ..., sigma_m of finite sequences in Y. We will
+construct one behavioral policy p that satisfies
+
+    E[ cost_{p, s}(sigma_i) ]
+       <= alpha * OPT(s, sigma_i)   for every i = 1, ..., m.
+
+This is the "finite minimax" lemma.
+
+THE SET OF DETERMINISTIC POLICIES IS FINITE. For any fixed finite
+set of sequences, only finitely many decision histories arise.
+Enumerating all deterministic causal policies for those histories
+gives a finite set D of policies. For each policy pi in D, define
+
+    v(pi) := ( E[cost_{pi, s}(sigma_1)] - alpha OPT(s, sigma_1),
+               ...,
+               E[cost_{pi, s}(sigma_m)] - alpha OPT(s, sigma_m) ).
+
+Each v(pi) is a vector in R^m.
+
+WE WANT A MIXTURE OF D WITH NONPOSITIVE EXCESS VECTOR. Let K =
+convex hull of { v(pi) : pi in D }.
+
+Claim: K intersects the closed negative orthant (-R_{\ge 0})^m.
+
+Proof by contradiction. Suppose K does not intersect the negative
+orthant. Then there is a separating weight vector w in the relative
+interior of the unit simplex in R^m, such that for every pi in D,
+
+    sum_j w_j * excess_{pi}(sigma_j)  >  0.
+
+(Standard convex-separation + compactness of the closed intersection
+test.) But the w_j are nonnegative and sum to 1, so they define a
+probability distribution on { sigma_1, ..., sigma_m }. Section 16.2
+applied to just this finite law (which has support within the finite
+set of the sigma_j's) gives a policy A_w with
+
+    E_{j ~ w}[ cost_{A_w, s}(sigma_j) - alpha OPT(s, sigma_j) ]  <=  0.
+
+The LEFT side is a mixture of excesses over deterministic policies?
+Not quite: A_w is potentially RANDOMIZED (from Section 16.2, it uses
+internal coins). But its cost is a probability mixture of some
+deterministic policies' costs. So the average over the deterministic
+policies must be nonpositive against the same weight w, contradicting
+"strictly positive for every pi in D".
+
+Hence K does intersect the negative orthant. That gives a MIXTURE
+theta over D with:
+
+    sum_pi theta_pi * E[cost_{pi, s}(sigma_j)]
+         <= alpha OPT(s, sigma_j) for every j.
+
+Now we have a message: "sample pi from theta at the start and run
+it". This uses ONLY the sum_j coordinate checks, and the mixture's
+cost on sigma_j is exactly the above. So the mixture works.
+
+BEHAVIORAL CONVERSION (KUHN). A mixture over D is still a
+"correlated" object: the same pi is drawn once at the start and
+used for the whole sequence. We want a "behavioral" policy, where
+AT EACH HISTORY the policy can independently flip its own coins,
+without keeping the global pi in mind. That is what a real online
+policy does.
+
+For perfect-recall games (and finite-sigma games have perfect
+recall), the mixed / behavioral distinction is empty: Kuhn's
+theorem. Concretely, at every decision history h = (prefix, label
+history), define:
+
+    Z(h)   := sum_{pi in D(h)} theta_pi,
+    p_h(j) := [sum_{pi in D(h): pi(h) = j} theta_pi] / Z(h)
+
+for j = 1, ..., k, where D(h) is the subset of D that would have
+chosen exactly the observed label history through h. If Z(h) = 0,
+put any probability vector (e.g. all mass on j = 1).
+
+Induction on t shows that at every reachable label history on
+sigma_i, the probability of reaching it under the behavioral
+policy equals its theta-mixture probability. So the LABEL
+DISTRIBUTIONS, and therefore the COSTS, are the same. The behavioral
+policy p hence satisfies
+
+    E[ cost_{p, s}(sigma_i) ]
+       <= alpha OPT(s, sigma_i)  for every i = 1, ..., m.
+
+16.4 Compactness via Tychonoff: one policy for every finite input.
+
+Now drop the finiteness of the sequence collection. Fix Y finite and
+s distinct. Let the "policy set" be the product space
+
+    P  :=  prod_{h} Delta_k,
+
+where h ranges over ALL decision histories (prefix of a sequence in
+Y and label history), and Delta_k is the k-dimensional probability
+simplex. P is a product of finitely many compact spaces, so P is
+compact by Tychonoff's theorem.
+
+For each finite sequence sigma in Y and each behavioral p in P,
+define
+
+    Phi_sigma(p) := E[cost_{p, s}(sigma)]  -  alpha OPT(s, sigma).
+
+Each Phi_sigma is a function from P to R. Compactly: at fixed
+sigma, only finitely many h matter, so Phi_sigma is a polynomial
+in the finitely many coordinates p_h it depends on. Hence
+Phi_sigma is continuous on P.
+
+For each finite collection { sigma_1, ..., sigma_m }, Section 16.3
+gives p_thetasigma with Phi_{sigma_i}(p) <= 0 for every i. So the
+closed sets { p : Phi_sigma(p) <= 0 } for all sigma simultaneously
+satisfy the finite-intersection property: every finite subfamily
+has nonempty intersection. So the whole family has nonempty
+intersection (P compact).
+
+Take p_* in that intersection. Then
+
+    E[ cost_{p_*, s}(sigma) ]
+       <= alpha OPT(s, sigma)  for every finite sigma.
+
+This is the "one behavioral policy for every finite input".
+
+REALIZATION. Take a single uniform seed omega in [0, 1). At
+each decision history h with probability vector p_h, subdivide the
+current interval into k pieces of relative lengths p_h(1), ...,
+p_h(k), choose the piece containing omega, and iterate with the
+resulting interval. This realizes p_* as a genuine randomized online
+policy, one strategy for every input, defined WITHOUT a horizon.
+
+16.5 Repeated starting positions.
+
+Now drop the distinctness of s.
+
+Fix Y finite, k >= 2, and any starting tuple s = (s_1, ..., s_k)
+in Y^k. Choose any tuple u = (u_1, ..., u_k) of k DISTINCT points
+of Y. Such u exists because |Y| >= k+1 by assumption.
+
+Let D = M(s, u), the matching distance between s and u. Since
+there are finitely many permutations of {1, ..., k}, D is finite.
+
+SERVICE COMPARISON. For any finite sigma in Y:
+
+    OPT_u(sigma) <= OPT_s(sigma) + D.
+
+Proof: Take any optimal service from s of total cost OPT_s(sigma).
+Follow this service with the SAME sequence of physical moves applied
+to servers starting at u. The MOVES (which server, where to) are
+identical; the only difference is the initial positions. So the
+overall cost is at most (initial matching distance) + OPT_s(sigma)
+<= D + OPT_s(sigma). This is a legal service from u. Hence OPT_u
+<= D + OPT_s. (The lazy simulation lemma gives the same comparison.)
+
+POLICY. Apply Section 16.4 to u: build a behavioral policy A_u
+satisfying
+
+    E[cost_{A_u, u}(sigma)] <= alpha OPT_u(sigma) for every sigma.
+
+Now run A_u VIRTUALLY. At each request, follow its configurations
+in Y from virtual start u. Lift its current configuration C_t to an
+actual configuration A_t on Y at ACTUAL start s using the lazy
+simulation lemma (Section 8): take the minimum matching from C_t to
+the CURRENT actual configuration A_{t-1}, and where a request needs
+a server at r_t, move the matched ACTUAL server to r_t.
+
+Pathwise:
+
+    cost_{A, s}(sigma) <= cost_{A_u, u}(sigma) + D.
+
+Take expectation:
+
+    E[cost_{A, s}(sigma)]
+       <= E[cost_{A_u, u}(sigma)] + D
+       <= alpha OPT_u(sigma) + D
+       <= alpha (OPT_s(sigma) + D) + D
+       =  alpha OPT_s(sigma) + (alpha + 1) D.
+
+Set B := (alpha + 1) D. This depends only on (Y, k, s) and not on
+sigma or on |sigma|. When s has distinct entries we may take u = s
+and get B = 0.
+
+16.6 Final constants and the absolute-constant statement.
+
+We have established: for Y finite, k >= 2, starting tuple s, there
+is a behavioral policy A = A_{Y, k, s} with
+
+    E[cost_{A, s}(sigma)]
+       <= (2a + 1) ell^2 OPT_s(sigma) + B,
+
+where:
+    a is an absolute constant from Section 15 (typically around
+    10^6 in the proof, but the exact value does not matter),
+    ell = 1 + log(k + 1),
+    B = (alpha + 1) D is a fixed finite number depending only on
+    (Y, k, s), and B = 0 when s has distinct entries.
+
+To absorb the "+1" in ell: since k >= 2, ell >= 1 + log 3 > 1 > 0,
+so we can write
+
+    ell^2  =  (1 + log(k+1))^2  <=  4 * (log(k+1))^2.
+
+So with C = 4 (2a + 1):
+
+    E[cost_{A, s}(sigma)]
+       <= C (log(k+1))^2 OPT_s(sigma) + B.
+
+Finally, the Y-finiteness: any finite metric statement extends to
+an arbitrary metric space X by choosing Y = support of the given
+finite sigma plus u plus s (finitely many points!) as the
+relevant finite metric, noting that the statement depends only on
+Y. The general conclusion is thus:
+
+    For every metric space X with at least k+1 points, every k >= 2,
+    and every starting tuple s in X^k, there is a behavioural
+    policy A on X with
+
+        E[cost_{A, s}(sigma)] <= C (log(k+1))^2 OPT_s(sigma) + B
+
+    for every finite sigma in X^*, where C is absolute and B is a
+    fixed finite number depending only on (X, k, s), and B = 0 when
+    the entries of s are distinct.
+
+This is the main theorem. Done.
+
+------------------------------------------------------------------------
+17. ASSEMBLING THE FINAL BOUND: WHERE EACH LOG LIVES
+------------------------------------------------------------------------
+
+This section tells the "money chain" of the proof. Each link is a
+lemma we have already explained. Read top-down for the composite;
+read bottom-up for the money flow.
+
+17.1 The three budget inequalities.
+
+The three moving pieces are:
+
+  (Chain 1) Allocation (Section 11):
+        V  <=  12 C_A ell P  +  D_A.
+        V  =  E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|.
+        The movement of the TREE ALLOCATION.
+
+  (Chain 2) Partitions (Section 13):
+        P  <=  C_P ell Q  +  D_part.
+        P  =  E sum_t sum_a d_T( xi_{t-1}(X_{t-1}^a), xi_t(X_t^a) ).
+        The movement of the hidden comparator on the tree.
+
+  (Chain 3) Anchor travel (Section 14):
+        T_anchor  <=  C_T ( V + ell P + ell Q ) + D_anchor.
+        T_anchor  =  E sum_{t,j,lambda} r_j b_{t,j,lambda} 1_{E}.
+        The expected mass-times-radius of moving anchors.
+
+Chain 1 costs ell per unit of comparator movement (P). Chain 2 costs
+ell per unit of offline optimum (Q). Chain 3 costs (V + ell P + ell Q)
+and introduces no new factor of ell.
+
+17.2 Rounding and realization (Section 15).
+
+  (R1)  N_rnd  <=  132 V,
+        where N_rnd := E sum_t sum_{v != root} r_{|v|-1} |Delta n_v|.
+
+  (R2)  E[simulated movement]  <=  120 N_rnd + 40 T_anchor.
+
+Both have fixed absolute factors. No ell and no k in them.
+
+17.3 The plugin.
+
+Substituting R1 into R2 and then Chain 1 and Chain 2:
+
+    N_rnd  <= 132 (12 C_A ell P + D_A)
+           =  132 * 12 C_A ell P + 132 D_A.
+
+    sim  <= 120 (132 * 12 C_A ell P + 132 D_A)
+            + 40 C_T (V + ell P + ell Q)
+            + 40 D_anchor
+         <= 120 * 132 * 12 C_A ell P
+            + 120 * 132 D_A
+            + 40 C_T (12 C_A ell P + D_A)
+            + 40 C_T ell P
+            + 40 C_T ell Q
+            + 40 D_anchor
+         =  [coefficient of ell P] ell P
+            + [coefficient of ell Q] ell Q
+            + [constant].
+
+Because P <= C_P ell Q + D_part:
+
+    [coefficient of ell P] ell P
+       <= [coefficient] ell (C_P ell Q + D_part)
+       =  [coefficient * C_P] ell^2 Q + [coefficient] ell D_part.
+
+Collecting:
+
+    sim  <=  C_sim ell^2 Q  +  D_sim'
+
+for absolute C_sim and finite D_sim'. Add the one-time initial
+mismatch (from lazy simulation, at most k * diam(Y)) to reach the
+ACTUAL cost:
+
+    actual  <=  C_sim ell^2 Q  +  D_0.
+
+This is the finite-distributional estimate used in Section 16.2.
+
+17.4 Where the two logarithms come from.
+
+  THE FIRST ell comes from Section 11 (allocation).
+  It is the factor C_A ell in  V <= 12 C_A ell P.
+
+  THE SECOND ell comes from Section 13 (partitions).
+  It is the factor C_P ell in  P <= C_P ell Q.
+
+Sections 12, 14, and 15 add only CONSTANT overhead on top of an
+already-log-costed quantity. They introduce no further logarithm.
+
+So the two logarithms are structurally: one for the tree
+allocation, one for the changing partitions. This is the "sharp
+squared-logarithmic" structure. Many earlier results had
+O(log^2 k * log n) or O(log^2 k * log Delta) or worse; every such
+factor was an artifact of embedding statically. Here the embedding
+CHANGES with the requests, and the pilot potential pays for each
+change.
+
+17.5 Why log n and log Delta were defeated.
+
+  - A static embedding of a metric loses a factor of log n.
+  - A changing embedding avoids that loss, but then each partition
+    edit needs payment.
+  - The PILOT POTENTIAL (Section 12) lets each edit be paid for
+    with the LOCAL mass-ratio coefficient, not a global worst case.
+  - The BALL-MASS TELESCOPE (Section 9.6) sums the local ratios
+    across scales with a coefficient that depends only on the RATIO
+    of masses, not on n.
+  - The remaining "how many levels" factor is bounded by the
+    telescoping sums as ell, not as log n or log Delta.
+
+The "agnostic" log(k) bounds with no dependence on the metric size
+or aspect ratio are therefore obtained.
+
+17.6 How the sharpness matches the lower bound.
+
+BCR 2023 gives (Corollary 20) a universal Omega(log k) lower bound on
+every metric with more than k points, and (Theorem 11 plus
+Proposition 8) a metric with only k+1 points where Omega(log^2 k)
+is required even with a fixed additive constant.
+
+Our upper bound matches the second one order-for-order. It is "sharp
+in the worst case": on SOME metric the true optimal competitive
+ratio is Theta(log^2 k), and our policy attains O(log^2 k).
+
+For SMALLER families of metrics (paging, HSTs, etc.), tighter bounds
+continue to hold; the theorem is a worst-case over metrics and does
+not claim to be tight on any particular family.
+
+17.7 The proof is explicit (in principle).
+
+Every lemma is a closed-formula object:
+  - l^beta is a convex piecewise function with explicit constants.
+  - The simplex tracker is an argmin of an explicit integral.
+  - The pilot potential is a specific finite-dimensional min.
+  - The rounding lemma is a specific local exchange.
+
+You can in principle SIMULATE every piece. The proof does not
+address complexity; polynomial-time versions require separate
+work (Coester-Cosson 2026), and the theorem we are explaining
+makes no such claim.
+
+------------------------------------------------------------------------
+18. HONEST LIMITS: WHAT THE PAPER DOES NOT CLAIM
+------------------------------------------------------------------------
+
+18.1 No efficiency.
+
+The theorem asserts EXISTENCE of a policy with the stated
+competitive ratio. It says nothing about whether you can compute
+the policy's next move in polynomial time. The compactness
+construction (Section 16.4) is thoroughly non-constructive. For
+implementations, extra work is needed, and that work belongs to
+separate literature.
+
+18.2 No tight constants.
+
+The universal constant C in the main theorem is astronomical (a
+product of many "12 C_A C_P ..." hiding several hundred digits of
+internal absolutes). The paper does not try to minimize C. It could
+be 10^50 and the theorem would still hold. The point of O(log^2 k)
+is the asymptotic growth rate in k.
+
+18.3 The additive term is real.
+
+When two starting servers occupy the SAME point, the additive term
+B cannot generally be zero. The episode amplification produces
+B = (alpha + 1) D where D = M(s, u) is the matching distance to the
+nearest DISTINCT tuple u. There is no claim to remove B in this
+case.
+
+18.4 No new lower bound.
+
+The paper proves an upper bound. It does not prove a matching lower
+bound. It uses the existing Omega(log^2 k) lower bound of BCR 2023.
+The theorem is "matches the known lower bound", not "discovered the
+true factor".
+
+18.5 No claim of "best possible for each metric".
+
+The O(ell^2) bound is tight OVER ALL METRICS. On specific metrics
+the true optimum may be smaller. The theorem does not claim to be
+tight on paging, on HSTs, on trees, or on any particular family.
+
+18.6 No "natural" online rule.
+
+The construction uses:
+  (i)  a finite distributional estimate that depends on the input
+       law;
+  (ii) episode amplification to remove that law;
+  (iii) Yao / Kuhn to reach a single behavioral policy on finitely
+        many inputs;
+  (iv) Tychonoff compactness to reach one policy for every input.
+
+At no point is there a "simple, human-improvise-this" rule. That is
+by design: the point is existence, not implementation.
+
+18.7 What "log" means.
+
+All logarithms are natural (base e). Base-2 logarithms differ by a
+fixed constant (1/ln 2), and the statement C (log)^2 with an
+absolute C is unchanged in order by switching bases.
+
+18.8 What the metric space can be.
+
+Nonempty and with at least k+1 points. Otherwise the deterministic
+lower bound "more than k points" is not present, and the offline
+game is trivial (all requests can be served at cost 0 if the metric
+has at most k points).
+
+18.9 B is finite in principle.
+
+For an infinite metric, D = M(s, u) is a minimum over FINITELY many
+permutations, and each d(s_i, u_{pi(i)}) is a finite real number by
+the metric axioms. So D is finite, so B = (alpha + 1) D is finite.
+B may be huge, but it is finite.
+
+18.10 What if the metric has no minimum gap?
+
+The "minimum gap delta > 0" is used only inside the fixed-finite-Y
+analysis (Section 7.5) to make level-J cells singletons. In the
+final theorem, Y is replaced by the finite support of the actual
+sequence: only finitely many points ever appear, so delta > 0 always
+holds there. Hence no discreteness assumption is needed at the level
+of a final theorem statement.
+
+------------------------------------------------------------------------
+19. A ONE-PAGE GLOSSARY
+------------------------------------------------------------------------
+
+SYMBOLS (alphabetical):
+
+  A, A_t       Actual labelled server configuration at time t. The
+               context distinguishes ACTUAL A from SIMULATED
+               configurations C_t.
+
+  A_s          A behavioral strategy starting from tuple s.
+
+  A_j          Alphabet at tree level j. A finite set of labels.
+
+  B            Additive correction in the main theorem. Depends only
+               on (metric, k, starting tuple). Zero when starting
+               positions are distinct.
+
+  beta_v       The rank-function parameter at tree vertex v, in
+               [3, 3 + epsilon_*]. Explicit in terms of M_v.
+
+  C            Generic absolute constant. Also C_0, C_1, C_A, C_P,
+               C_T, C_sim, C_final. All fixed numbers.
+
+  c_v(t)       Integer "park" at tree vertex v at time t: how many
+               simulated servers occupy vertex v.
+
+  C_loc        Local Lipschitz constant of the pilot integrand near
+               a concentrated request (Section 12.6).
+
+  d(x, y)      Distance in the metric.
+
+  D_*, D_1     Pilot template "outer radius" constants. Also
+  D_H, D_L     heavy-template and tier-template outer radii:
+               D_1 = 10 D_* = 100 R (heavy template),
+               D_L = 100 R = 400 D_H (tier template).
+
+  D_T, D_A,    Fixed additive constants in the budget inequalities.
+  D_P, D_part  Each depends on (tree, radii, k), never on the input
+               law, on the horizon, or on the number of histories.
+
+  diam(Y)      Diameter of the (finite) metric.
+
+  delta        Minimum nonzero distance in the finite metric.
+
+  e_x          Expected mover distance for request x:
+               int d(x, y) dnu(y). Sum over t of E[e_{r_t}] = Q.
+
+  ell          Little ell: 1 + log(k+1). Order log k.
+
+  epsilon_*    = 1/100. Upper end of the useful interval for beta.
+
+  eta_i        = c_t h_i / ell. Tolerance in the alpha feasibility
+               constraint.
+
+  F_t          Filtration at time t. Generated by r_1, ..., r_t and
+               any independent partition tape.
+
+  F_z^g        Pilot integrand:
+               (1+g(p)) (1 - sum_s z_s b_s(p))
+               + 256 sum_s z_s (1+g(s)) a_s(p).
+
+  gamma_H,     Inner radii of the heavy template and the tier
+  gamma_L      template, both < 1/100.
+
+  h_i          log(M_v / M_i). Size of child i relative to its
+               parent. Bounded in [0, C ell].
+
+  H            Horizon (number of requests). Also "H = 1 + log(1/u)"
+               in one dominant-child inequality; context names it.
+
+  H_k          Set of tiers, {1, 2, 4, ..., 2^b}, of size
+               1 + floor(log_2 log k).
+
+  K_h          = ceil(e^{C_K h}). Age threshold for tier h. Also
+               serves as the density parameter for tier-h radii.
+
+  k            Number of servers.
+
+  L            Length of a padded word in episode amplification.
+
+  l^beta       The rank function: convex, nonincreasing, equal to
+               1 - beta p on [0, p_*], and zero from s_* on.
+
+  L_v^beta     Rank aggregation sum_a l^beta(p_{va}) at vertex v.
+
+  M_v          Size aggregation sum_a l^siz(p_{va}). M_v <= m_v.
+
+  m_v(t)       = E[N_v(t) | F_t]. Posterior expected subtree count.
+
+  M(A, C)      Minimum matching distance between configurations A
+               and C (a bipartite assignment cost).
+
+  mu_t         Posterior counting measure on Y. Total mass k.
+
+  mu^-, mu^+   Filtered and drifted posterior measures just before
+               and just after observing the request at time t.
+
+  nu           Mover's law. nu <= mu^-, nu(Y) = 1.
+
+  N_v(t)       Random number of hidden servers at leaves below v.
+
+  N_rnd        = E sum_t sum_{v != root} r_{|v|-1} |Delta n_v|.
+               Total integer tree movement after rounding.
+
+  OPT, OPT_s   Offline optimum from starting tuple s.
+
+  p_{va}(t)    Pr[N_v(t) < a | F_t]. Nonincreasing in a.
+
+  p_v^circ(t)  Parked mass q_v - sum_{i child of v} q_i.
+
+  P            = E sum_t sum_a d_T(xi_{t-1}(X_{t-1}^a), xi_t(X_t^a)).
+               Expected comparator movement on the tree.
+
+  q_v(t)       Fractional tree allocation at vertex v. Root holds k.
+
+  Q            = E[OPT] on the input law. The budget for all budgets.
+
+  r_j          = r_0 tau^{-j}, j = 0, ..., J. Scales of the tree.
+
+  R            Constant in episode amplification:
+               floor(k diam(Y) / delta) + 1.
+
+  s, s_i       Starting tuple and its entries (i = 1, ..., k).
+
+  S, D, b, d   Core and flex amounts held at tree vertices, plus
+               various absolute tolerances.
+
+  sigma        Request sequence.
+
+  tau          Large absolute constant. "Separation ratio" of the
+               tree. >= 22 in Section 15 (rounding), >= 2 elsewhere.
+
+  T_anchor     = E sum_{t,j,lambda} r_j b_{t,j,lambda} 1_{E}.
+
+  T            The fixed prefix tree (Section 10). In Section 15
+               the L1 change term sum_i |a_i - b_i| of the rounding
+               lemma is ALSO called T; the context disambiguates.
+
+  u            Either the tuple with distinct entries in transfer
+               (Section 16.5), or u = U/A in the near-dominant case
+               (Section 11.13).
+
+  V            = E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|.
+               Expected fractional tree movement.
+
+  w_i          Side tracker coordinates in the near-dominant case.
+
+  Z            The chosen optimal hidden labelled service.
+
+  z            A site vector in the pilot potential.
+
+  Z_r          Feasibility set of the pilot at scale r:
+               0 <= z_s, capacity constraint, separation constraint.
+
+TERMS:
+
+  Allocator.       The q_v(t) construction of Section 11.
+
+  Anchor.          The point in Y representing a tree vertex's
+                   current label. Any member of that label's cell
+                   is within 20 r_j of the anchor.
+
+  Balanced rounding.  n_v in {floor(q_v), ceil(q_v)} with
+                   E[n_v | F_t] = q_v.
+
+  Cell.            The set of points of Y sharing a given level-j
+                   label.
+
+  Chronological roster.  Ordered list of insertion events with
+                   ages and lifetimes, used to label points of Y.
+
+  Dominant child.  At a vertex, the unique child holding more than
+                   84% of the mass (when such exists).
+
+  Drift.           Change due to the underlying object moving at
+                   step t, not merely due to information.
+
+  Filtering.       Change due to the filtration growing from F_{t-1}
+                   to F_t (information, not motion).
+
+  Heavy ball.      A ball at the current level whose inner mass is
+                   comparable to its outer mass, kept by the map.
+
+  HST.             Hierarchies of Separated Trees. The prefix tree
+                   of Section 10, with tau-separated levels.
+
+  Lazy simulation. The straight-line car-following lemma of
+                   Section 8.
+
+  Parked mass.     q_v - sum_children q_i, at vertex v.
+
+  Pilot potential. L_r(mu, g) of Section 12. A compact potential
+                   that pays for partition edits in one logarithm.
+
+  Posterior.       Distribution of Z given the observed prefix.
+
+  Rank function.   The convex l^beta of Section 11.
+
+  Side.            Any child of a vertex other than its dominant
+                   child.
+
+  Simplex tracker. The alpha update rule of Section 11.11.
+
+  Strong laziness. A strategy that does nothing when the request
+                   is already covered and otherwise moves exactly
+                   one server.
+
+  Tier.            A lifetime-based ball structure, indexed by h in
+                   {1, 2, 4, ...}.
+
+  Witness.         A point of Y whose leaf lies below a given tree
+                   vertex v. Used to define anchors and masses.
+
+------------------------------------------------------------------------
+20. A HOW-TO-READ-THE-PAPER MAP
+------------------------------------------------------------------------
+
+The paper is long. Reading order by purpose:
+
+20.1 First impression (30 minutes).
+
+  - Section 5 (main theorem, plain English) - the claim.
+  - Section 4 (history) - why anyone cares.
+  - This document's Sections 5, 6, 17 - the whole story.
+  - Stop.
+
+20.2 High-school mathematical reader (a few hours).
+
+  - Section 1 (the game).
+  - Section 2 (competitive ratio).
+  - Section 3 (randomization and paging).
+  - Section 7 (notation: M(A,C), strong laziness, ell, scales).
+  - Section 8 (lazy simulation. The proof is easy and beautiful).
+  - Section 10 (the tree, only lightly).
+  - Section 17 (the money chain).
+  - The glossary and this map.
+  - SKIP sections 11-16 on first read. Skim on second.
+
+20.3 Algorithm designer (a few days).
+
+  - Everything in 20.2.
+  - Section 11 in detail (allocation).
+  - Section 12 in detail (pilot potential).
+  - Section 13 in detail (partitions).
+  - Section 15 in detail (rounding).
+  - Section 16 (transfer).
+  - Then Section 17 to see how it fits.
+
+  Focus on:
+  - The picture of l^beta: convex, decreasing, linear on [0, p_*],
+    vanishes at s_*.
+  - The simplex tracker argument: feasibility + the payment
+    identity. Nothing else about it matters.
+  - The pilot potential as the one new trick that compresses a
+    scale sum into one logarithm.
+  - The BALL-MASS TELESCOPE (Section 9.6), the small lemma that
+    converts everything into a single log.
+
+20.4 Probabilist / proof hound (weeks).
+
+  - Sections 9 and 12 carefully. Two pillars of stochastic
+    accounting.
+  - Section 11.5-11.9. Rank-drift + rank-tracking lemmas; all the
+    potentials live here.
+  - Sections 13.5-13.7 (the two telescopes) and 14.7 (pointwise
+    coefficient).
+  - Sections 16.3 (Yao) and 16.4 (Tychonoff / compactness). The
+    clean steps that remove the input law and the metric
+    dependence.
+  - Re-read Section 11 once. The tracker makes much more sense
+    after Section 12.
+
+20.5 High-school competition problem solver.
+
+  Look at Section 8 (lazy simulation) and Section 9 (posterior as
+  filtered plus drift). These are the "that is elegant" sections:
+  a matching argument and a conditional-expectation exercise. The
+  pilot potential (Section 12) is the "that is clever" section: a
+  variational formula that behaves smoothly under two seemingly
+  different kinds of update.
+
+20.6 What to skip on a first read.
+
+  - The internal proof of the uniform denominator estimates
+    (Section 11.11). Trust it: a two-line integral plus a tail
+    bound on the dominant coordinate.
+  - The repairs in Section 13.7 (fixed alphabet, separation,
+    noncoverage). Careful bookkeeping summarized as "the
+    bookkeeping works".
+  - The detailed rounding proof (Section 15.2). Trust the
+    statement E ||X' - X||_1 <= 32 T + 11 I.
+
+20.7 Once you have read it once.
+
+  The paper is a chain of telescopes. Every nontrivial bound is a
+  sum of local positive quantities that telescopes over SCALES
+  (not over time). Every inequality has exactly one ell (not ell^2)
+  because the telescopes cancel against the geometry of balls.
+
+  Mental picture: at each scale, a "ball ratio"
+  log(outer_mass / inner_mass) contributes. By near-nestedness of
+  balls at consecutive scales, these ratios sum to about log k
+  over all scales. That is the one fact behind the ell's.
+
+  Every lemma answers one question: how do I pay for X moving by
+  Y?
+    - X = tree allocation, Y = comparator movement. Pay ell per
+      unit.
+    - X = partition, Y = comparator's request stream. Pay ell per
+      unit.
+    - X = rounding, Y = fractional change. Pay constant ~132 per
+      unit.
+    - X = nearby point in the pilot, Y = request. Pay local log
+      per unit.
+
+------------------------------------------------------------------------
+END OF DOCUMENT
+------------------------------------------------------------------------
+
+If you have read this far: the main theorem is Section 5, the proof
+sketch is Section 6, the money chain is Section 17, and the honest
+limits are Section 18. Everything else is detail in service of those
+four sections.