uniform_kserver_expected_cost
For a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests ρ, uniform_kserver_expected_cost k a ρ is the total expected movement cost of the randomized online tracking algorithm starting from a on request sequence ρ.
Statement
noncomputable def uniform_kserver_expected_cost (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℝ
- Defined in
- arXiv:2610.37192 Section 3.2
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 3
- uniform_kserver_weight_updateFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, and a finitely supported weight…
- uniform_kserver_total_weightFor a natural number k, a family of spaces M indexed by Fin k, and a finitely supported weight function ϕ on configurations,…
- uniform_kserver_step_expected_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, a previous finitely supported…
Read back from the Lean
uniform_kserver_expected_cost defines the total expected Hamming distance cost of a randomized online algorithm for a k-server problem variant on the product space ∀ i : Fin k, M i, starting from an initial server configuration a and processing a sequence of requests ρ : List (∀ i, M i).
The computation is a left fold over ρ maintaining an accumulator (cost, ϕ) initialized to (0, Finsupp.single a 1) (accumulated cost 0, and weight 1 concentrated at configuration a):
At each step with request r:
1. The weight distribution ϕ is updated to ϕ_next via uniform_kserver_weight_update: each configuration x in the support of ϕ with weight c keeps weight c if it serves r (i.e., x i = r i for some i : Fin k); otherwise, its weight is split equally among the k configurations obtained by updating coordinate i to r i, each receiving weight c / (2 * k) (preserving half of c in total).
2. ϕ_next is normalized by its total weight W = uniform_kserver_total_weight ϕ_next to form the distribution μ_next = (1 / W) • ϕ_next.
3. The previous distribution μ_prev is formed by normalizing acc.2 by its total weight.
4. The expected cost of the step is computed via uniform_kserver_step_expected_cost: taking the expectation over x ~ μ_prev of the expected Hamming distance hammingDist x y to the next state y ~ uniform_kserver_step_dist k r μ_next x. In that step distribution:
- if x serves r, the algorithm stays at x with probability 1;
- if x does not serve r, it transitions to x with coordinate i set to r i with probability 1 / (2 * k) for each i : Fin k (total probability 1/2), and with the remaining 1/2 probability samples a new configuration from μ_next.
5. The accumulator is updated by adding the step's expected cost to acc.1 and replacing the weight function with ϕ_next.
Finally, the function returns the accumulated real-valued expected cost (.1).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Expected movement cost of the randomized algorithm over a request sequence. -/ noncomputable def uniform_kserver_expected_cost (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℝ := (ρ.foldl (fun (acc : ℝ × ((∀ i, M i) →₀ ℝ)) (r : ∀ i, M i) => let ϕ_next := uniform_kserver_weight_update k r acc.2 let W := uniform_kserver_total_weight ϕ_next let μ_next := (1 / W) • ϕ_next let step_cost := uniform_kserver_step_expected_cost k r ((1 / uniform_kserver_total_weight acc.2) • acc.2) μ_next (acc.1 + step_cost, ϕ_next)) (0, Finsupp.single a 1)).1