AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_step_expected_cost

def

For a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, a previous finitely supported distribution μ_prev : (∀ i, M i) →₀ ℝ, and a current finitely supported distribution μ_curr : (∀ i, M i) →₀ ℝ, uniform_kserver_step_expected_cost k r μ_prev μ_curr is the expected Hamming movement distance when moving from a configuration drawn from μ_prev according to uniform_kserver_step_dist k r μ_curr.

Statement

noncomputable def uniform_kserver_step_expected_cost (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (r : ∀ i, M i) (μ_prev : (∀ i, M i) →₀ ℝ) (μ_curr : (∀ i, M i) →₀ ℝ) : ℝ
Defined in
arXiv:2610.37192 Section 3.2
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • uniform_kserver_step_distFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, a request r, a normalized finitely supported…
Used by 1
  • uniform_kserver_expected_costFor 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…

Read back from the Lean

uniform_kserver_step_expected_cost defines the expected Hamming cost of one step in a randomized $k$-server setting. Given: - a natural number $k$, - an indexed family of types $M : \text{Fin } k \to \text{Type}^*$ with decidable equality on each $M i$, - a target configuration $r : \prod_{i : \text{Fin } k} M i$, - a finitely supported function $\mu_{\text{prev}} : (\prod_{i : \text{Fin } k} M i) \to_0 \mathbb{R}$, - a finitely supported function $\mu_{\text{curr}} : (\prod_{i : \text{Fin } k} M i) \to_0 \mathbb{R}$, it computes the real number: $$ \sum_{x \in \text{supp}(\mu_{\text{prev}})} \mu_{\text{prev}}(x) \cdot \left( \sum_{y \in \text{supp}(D(x))} D(x)(y) \cdot d_H(x, y) \right) $$ where $d_H(x, y) = \#\{i : \text{Fin } k \mid x(i) \neq y(i)\}$ is the Hamming distance between $x$ and $y$, and $D(x) = \text{uniform\_kserver\_step\_dist } k\ r\ \mu_{\text{curr}}\ x$ is the transition distribution from $x$.

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 a single step of the algorithm. -/
noncomputable def uniform_kserver_step_expected_cost (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)]
    (r : ∀ i, M i) (μ_prev : (∀ i, M i) →₀ ℝ) (μ_curr : (∀ i, M i) →₀ ℝ) : ℝ := μ_prev.sum fun x px =>
    px * ((uniform_kserver_step_dist k r μ_curr x).sum fun y py => py * (hammingDist x y : ℝ))
See it in the graphDiscuss this resultChallenge it