AFTD Auto-Formalizing Theoretical Domains

gen_k_server_uniform_expected_cost_from

def

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

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