gen_k_server_uniform_expected_cost_from
Generalized k-server on k uniform metrics with m points each: both configurations and requests are functions Fin k → Fin m (one point per server). With k m : ℕ implicit, the function takes, in this order, transition probabilities P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ, a list past : List (Fin k → Fin m) of requests already served, a function μ : (Fin k → Fin m) → ℝ (the distribution of the current configuration), and a list rs : List (Fin k → Fin m) of remaining requests, and returns a real number, defined by recursion on rs: 0 for the empty list; for r :: rs it is (∑ over x, ∑ over y in Fin k → Fin m, of μ x * P past r x y * (hammingDist x y : ℝ)) plus the value of the function itself at past ++ [r], the new distribution (fun y => ∑ over x of μ x * P past r x y), and rs.
Statement
noncomputable def gen_k_server_uniform_expected_cost_from {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : List (Fin k → Fin m) → ((Fin k → Fin m) → ℝ) → List (Fin k → Fin m) → ℝ
- Defined in
- arXiv:2610.37192, Sec. 2: E[ALG(ρ)], the expected movement cost of a randomized online algorithm; auxiliary recursion over the remaining requests
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- gen_k_server_uniform_is_rand_algGeneralized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are…
- Used by 3
- gen_k_server_uniform_one_server_competitive_oneWith one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with…
- gen_k_server_uniform_expected_costGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
- gen_k_server_uniform_log_competitiveFor every k ≥ 1, every m and every start configuration a : Fin k → Fin m of generalized k-server on k uniform metrics with m points each…
Read back from the Lean
Given natural numbers $k$ and $m$, this definition recursively defines the function gen_k_server_uniform_expected_cost_from:
It takes:
1. A function $P : \text{List}(\text{Fin } k \to \text{Fin } m) \to (\text{Fin } k \to \text{Fin } m) \to (\text{Fin } k \to \text{Fin } m) \to (\text{Fin } k \to \text{Fin } m) \to \mathbb{R}$ (representing transition weights/probabilities given a history of requests, a current request, a current state, and a next state),
2. A list $\mathit{past} : \text{List}(\text{Fin } k \to \text{Fin } m)$ of past requests,
3. A function $\mu : (\text{Fin } k \to \text{Fin } m) \to \mathbb{R}$ (representing current state weights/probabilities),
4. A list of requests in $\text{List}(\text{Fin } k \to \text{Fin } m)$.
It returns a real number defined recursively on the request list:
- If the request list is empty [], it returns $0$.
- If the request list is $r :: rs$, it returns the sum of:
- The immediate expected cost: $\sum_{x : \text{Fin } k \to \text{Fin } m} \sum_{y : \text{Fin } k \to \text{Fin } m} \mu(x) \cdot P(\mathit{past}, r, x, y) \cdot \text{hammingDist}(x, y)$ (where $\text{hammingDist}(x, y)$ is cast to $\mathbb{R}$),
- and the recursive call on the remaining requests $rs$, with updated history $\mathit{past} ++ [r]$ and updated weight function $y \mapsto \sum_{x : \text{Fin } k \to \text{Fin } m} \mu(x) \cdot P(\mathit{past}, r, x, y)$.
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 (unit distances, Hamming distance between configurations) of serving the remaining requests, given the earlier requests and the current distribution of the configuration. -/ noncomputable def gen_k_server_uniform_expected_cost_from {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : List (Fin k → Fin m) → ((Fin k → Fin m) → ℝ) → List (Fin k → Fin m) → ℝ | _, _, [] => 0 | past, μ, r :: rs => (∑ x, ∑ y, μ x * P past r x y * (hammingDist x y : ℝ)) + gen_k_server_uniform_expected_cost_from P (past ++ [r]) (fun y => ∑ x, μ x * P past r x y) rs