AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_expected_cost

def

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
Used by 3

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) ρ
See it in the graphDiscuss this resultChallenge it