gen_k_server_uniform_expected_cost
Generalized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. 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 start configuration a : Fin k → Fin m and a request list ρ : List (Fin k → Fin m), and returns the real number gen_k_server_uniform_expected_cost_from P [] (fun x => if x = a then 1 else 0) ρ: the expected cost of P on ρ started from the point mass at a, with no earlier requests.
Statement
noncomputable def gen_k_server_uniform_expected_cost {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℝ
- Defined in
- arXiv:2610.37192, Sec. 2: E[ALG(ρ)] for an algorithm starting in configuration a
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- gen_k_server_uniform_expected_cost_fromGeneralized k-server on k uniform metrics with m points each: both configurations and requests are functions Fin k → Fin m (one point per…
- 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_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…
- gen_k_server_uniform_competitiveGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
Read back from the Lean
gen_k_server_uniform_expected_cost defines the expected cost (as a real number) of a randomized online algorithm on an instance of a generalized $k$-server problem on $m$ points, given:
- natural numbers $k$ and $m$ (implicit);
- a transition kernel $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}$, which takes the list of past requests, the current request, the current configuration, and the next configuration, returning a real number (the transition probability/weight);
- an initial configuration $a : \text{Fin } k \to \text{Fin } m$;
- a sequence of requests $\rho : \text{List}(\text{Fin } k \to \text{Fin } m)$.
It computes this by delegating to gen_k_server_uniform_expected_cost_from with an empty history of past requests [] and the initial probability distribution $\mu$ concentrated entirely at $a$ ($\mu(x) = 1$ if $x = a$ and $0$ otherwise).
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 cost E[ALG(ρ)] of the randomized online algorithm `P` started in configuration `a`. -/ noncomputable def gen_k_server_uniform_expected_cost {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℝ := gen_k_server_uniform_expected_cost_from P [] (fun x => if x = a then 1 else 0) ρ