gen_k_server_uniform_one_server_competitive_one
With one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with gen_k_server_uniform_is_rand_alg P whose expected cost on every request list ρ is at most gen_k_server_uniform_opt a ρ.
Statement
theorem gen_k_server_uniform_one_server_competitive_one (m : ℕ) (a : Fin 1 → Fin m) :
∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin 1 → Fin m),
gen_k_server_uniform_expected_cost P a ρ ≤ (gen_k_server_uniform_opt a ρ : ℝ)- Source
- Smallest case k = 1 of OP-613 (arXiv:2610.37192, Sec. 6): with one server the request determines the configuration, so following the requests is optimal
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…
- gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…
- 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…
The proof, explained
To prove that the 1-server problem has a 1-competitive online algorithm, we consider the deterministic greedy policy P_det that moves the single server directly to the requested position at each arrival. For a single server (k = 1), any configuration serving request r must equal r because the server index set Fin 1 is a singleton; therefore, the only sequence of configurations that can service request list ρ is ρ itself. Consequently, the offline optimal cost opt(a, ρ) is uniquely attained by ρ and equals the direct path cost path_cost(a, ρ). Since the deterministic algorithm follows exactly this sequence of transitions, its expected cost also equals path_cost(a, ρ), achieving a competitive ratio of 1.
The transition probabilities P_det are non-negative. automation
For any past history, request r, and current configuration x, the probability P_det past r x y is defined as 1 if y = r and 0 otherwise. Splitting on whether y = r gives either 1 or 0, both of which are non-negative by linear arithmetic.
intro past r x refine ⟨?_, ?_, ?_⟩ · intro y dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] split_ifs <;> linarith
The transition probabilities from any configuration sum to 1.
Summing the indicator of y = r over all configurations y in the universe collapses to 1 using sum_ite_eq', since the target request r is an element of the universe (mem_univ, ite_true).
uses
sum_ite_eq',mem_univ,ite_true· dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] simp only [sum_ite_eq', mem_univ, ite_true]
Any transition with positive probability serves the requested configuration.
If P_det past r x y ≠ 0, then y must equal r since the probability is 0 otherwise. In the 1-server setting, server 0 satisfies y(0) = r(0), which witnesses that y serves r.
· intro y hy dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] at hy split_ifs at hy with h · subst h exact ⟨0, rfl⟩ · contradiction
Base case: on an empty request list, the expected cost equals the path cost (both are 0).
We proceed by induction on the request list ρ. When ρ = [], both gen_k_server_uniform_expected_cost_from and gen_k_server_uniform_path_cost are 0 by definition.
induction ρ generalizing past x with | nil => simp [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost]
The expected cost of serving the first request r starting from configuration x is hammingDist(x, r).
For request list r :: rs, the one-step expected cost sums over x' and y the initial distribution (a point mass at x), the transition probability P_det(x' → y), and the Hamming distance from x' to y. Since the initial distribution is 0 for x' ≠ x and 1 for x' = x, the sum over x' isolates x using one_mul, zero_mul, and sum_const_zero. The sum over y of the indicator of y = r times hammingDist(x, y) collapses via sum_ite_eq', mem_univ, and ite_true to hammingDist(x, r).
uses
one_mul,zero_mul,sum_const_zero,sum_ite_eq',mem_univ,ite_true| cons r rs ih => simp only [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost] have h1 : (∑ x', ∑ y, (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ)) = (hammingDist x r : ℝ) := by have : (fun x' => (∑ y, (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ))) = (fun x' => if x' = x then (∑ y, gen_k_server_uniform_one_server_competitive_one_P_det past r x y * (hammingDist x y : ℝ)) else 0) := by ext x' split_ifs with h · subst h simp only [one_mul] · simp only [zero_mul, sum_const_zero] rw [this, sum_ite_eq' univ x] simp only [mem_univ, ite_true] dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] have : (fun y => (if y = r then (1:ℝ) else 0) * (hammingDist x y : ℝ)) = (fun y => if y = r then (hammingDist x r : ℝ) else 0) := by ext y split_ifs with h · subst h; ring · ring rw [this, sum_ite_eq' univ r] simp only [mem_univ, ite_true]After serving request r, the updated server distribution is the point mass at r.
The distribution on configurations after the transition assigns to each y the probability ∑_{x'} δ_x(x') P_det(x' → y). The sum over x' collapses to P_det(x → y) using sum_ite_eq', mem_univ, and ite_true, which equals 1 if y = r and 0 otherwise.
uses
sum_ite_eq',mem_univ,ite_truehave h2 : (fun y => ∑ x', (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) = (fun y => if y = r then (1:ℝ) else 0) := by ext y have : (fun x' => (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) = (fun x' => if x' = x then gen_k_server_uniform_one_server_competitive_one_P_det past r x y else 0) := by ext x' split_ifs with h · subst h; ring · ring rw [this, sum_ite_eq' univ x] simp only [mem_univ, ite_true] dsimp [gen_k_server_uniform_one_server_competitive_one_P_det]
Inductive step: the expected cost on r :: rs equals the total path cost on r :: rs.
Substituting the first-step cost hammingDist(x, r) and the updated state distribution δ_r into the recursive formula, the future expected cost matches the path cost from r on rs by the induction hypothesis. Adding hammingDist(x, r) gives the full path cost on r :: rs.
rw [h1, h2, ih (past ++ [r]) r] push_cast rfl
For a single server, any configuration o serving request r must be identical to r.
Configuration o serves r if o(i) = r(i) for some server index i ∈ Fin 1. Since Fin 1 has only one element, any index j satisfies j = i by Subsingleton.elim, so o(j) = r(j) for all j, establishing o = r by function extensionality.
uses
Subsingleton.elimobtain ⟨i, hi⟩ := h funext j have : j = i := Subsingleton.elim j i rw [this] exact hi
Any configuration sequence that serves request list ρ step-by-step is identical to ρ.
By induction on the relation List.Forall₂: the empty sequence can only match the empty sequence. For a cons step, the head configuration serves the head request and thus equals it by gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves, while the tails are identical by the induction hypothesis.
uses
gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_servesinduction h with | nil => rfl | cons h1 h2 ih => rw [gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves h1, ih]
The request sequence ρ validly serves itself.
By induction on ρ: the empty list serves itself via List.Forall₂.nil. For r :: rs, configuration r serves request r at server 0 (since r(0) = r(0)), and combining this with the induction hypothesis via List.Forall₂.cons completes the proof.
uses
List.Forall₂.nil,List.Forall₂.consinduction ρ with | nil => exact List.Forall₂.nil | cons r rs ih => exact List.Forall₂.cons ⟨0, rfl⟩ ih
For 1 server, the offline optimal cost opt(a, ρ) equals the path cost path_cost(a, ρ).
By definition, opt(a, ρ) is the infimum of path costs over all sequences serving ρ. Serving ρ with itself (gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl) shows path_cost(a, ρ) is achievable, so opt(a, ρ) ≤ path_cost(a, ρ) by Nat.sInf_le. Conversely, any valid sequence must equal ρ by gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves, making path_cost(a, ρ) a lower bound for all valid costs and giving the reverse inequality by le_csInf. Antisymmetry (le_antisymm) yields equality.
uses
gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl,le_antisymm,Nat.sInf_le,le_csInf,gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_servesdsimp [gen_k_server_uniform_opt] have h_mem : gen_k_server_uniform_path_cost a ρ ∈ {c | ∃ os, List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c} := by exact ⟨ρ, gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl ρ, rfl⟩ apply le_antisymm · exact Nat.sInf_le h_mem · apply le_csInf ⟨_, h_mem⟩ rintro c ⟨os, hos, rfl⟩ rw [gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves hos]
Algorithm P_det is a valid randomized algorithm whose expected cost on any request sequence ρ is at most the offline optimum opt(a, ρ).
We provide P_det as witness, which is valid by gen_k_server_uniform_one_server_competitive_one_is_rand_alg. Unfolding gen_k_server_uniform_expected_cost and rewriting with gen_k_server_uniform_one_server_competitive_one_expected_cost_from shows the expected cost is path_cost(a, ρ), while gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost shows the offline optimum is also path_cost(a, ρ). Since path_cost(a, ρ) ≤ path_cost(a, ρ), the 1-competitiveness bound holds.
uses
gen_k_server_uniform_one_server_competitive_one_is_rand_alg,gen_k_server_uniform_one_server_competitive_one_expected_cost_from,gen_k_server_uniform_one_server_competitive_one_opt_eq_path_costuse gen_k_server_uniform_one_server_competitive_one_P_det refine ⟨gen_k_server_uniform_one_server_competitive_one_is_rand_alg m, ?_⟩ intro ρ dsimp [gen_k_server_uniform_expected_cost] rw [gen_k_server_uniform_one_server_competitive_one_expected_cost_from, gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost]
sum_ite_eq'- The sum over a finite set s of an indicator term (which is b(x) when x = a and 0 otherwise) equals b(a) if a ∈ s, and 0 otherwise.
mem_univ- In any finite type, every element belongs to the universal finite set Finset.univ.
ite_true- An if-then-else expression whose condition is True evaluates to its then-branch.
one_mul- Multiplying any element by 1 on the left leaves it unchanged (1 * a = a).
zero_mul- Multiplying any element by 0 on the left yields 0 (0 * a = 0).
sum_const_zero- The sum of the constant zero function over any finite set is 0.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves- For a single server (k = 1), if a configuration o serves request r (i.e. agrees with r at some server index), then o = r.
List.Forall₂.nil- The pointwise relation List.Forall₂ R holds vacuously between two empty lists.
List.Forall₂.cons- If R(a, b) holds and R holds pointwise between lists l₁ and l₂, then R holds pointwise between a :: l₁ and b :: l₂.
gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl- Every request sequence ρ of 1-server configurations serves itself step-by-step.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- The infimum (minimum) of a set of natural numbers is less than or equal to any element in the set.
le_csInf- In a conditionally complete lattice, any lower bound of a non-empty set is at most the infimum of the set.
gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves- For a single server (k = 1), any configuration sequence os that serves request sequence ρ step-by-step is identical to ρ.
gen_k_server_uniform_one_server_competitive_one_is_rand_alg- The transition probability function P_det defines a valid randomized algorithm (probabilities are non-negative, sum to 1, and only transition to configurations serving the request).
gen_k_server_uniform_one_server_competitive_one_expected_cost_from- Under transition function P_det, the expected cost on request sequence ρ from an initial point-mass distribution at configuration x equals the deterministic path cost from x along ρ.
gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost- For a single server (k = 1), the offline optimal cost opt(a, ρ) from initial configuration a equals the direct path cost path_cost(a, ρ).
- In Step 1 (lines 9–13), the tactic split_ifs <;> linarith automatically verifies that the indicator function values (1 and 0) are non-negative using linear real arithmetic.
- Configurations are represented as functions Fin k → Fin m. For k = 1, the server index domain Fin 1 is a singleton, so any two server indices are identical via Subsingleton.elim, reducing configuration equality to equality on the single server.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetdef gen_k_server_uniform_one_server_competitive_one_P_det {k m : ℕ} : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ := fun _past r _x y => if y = r then 1 else 0lemma gen_k_server_uniform_one_server_competitive_one_is_rand_alg (m : ℕ) : gen_k_server_uniform_is_rand_alg (gen_k_server_uniform_one_server_competitive_one_P_det (k := 1) (m := m)) := by intro past r x refine ⟨?_, ?_, ?_⟩ · intro y dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] split_ifs <;> linarith · dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] simp only [sum_ite_eq', mem_univ, ite_true] · intro y hy dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] at hy split_ifs at hy with h · subst h exact ⟨0, rfl⟩ · contradictionlemma gen_k_server_uniform_one_server_competitive_one_expected_cost_from {k m : ℕ} (past : List (Fin k → Fin m)) (x : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : gen_k_server_uniform_expected_cost_from gen_k_server_uniform_one_server_competitive_one_P_det past (fun z => if z = x then 1 else 0) ρ = (gen_k_server_uniform_path_cost x ρ : ℝ) := by induction ρ generalizing past x with | nil => simp [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost] | cons r rs ih => simp only [gen_k_server_uniform_expected_cost_from, gen_k_server_uniform_path_cost] have h1 : (∑ x', ∑ y, (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ)) = (hammingDist x r : ℝ) := by have : (fun x' => (∑ y, (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y * (hammingDist x' y : ℝ))) = (fun x' => if x' = x then (∑ y, gen_k_server_uniform_one_server_competitive_one_P_det past r x y * (hammingDist x y : ℝ)) else 0) := by ext x' split_ifs with h · subst h simp only [one_mul] · simp only [zero_mul, sum_const_zero] rw [this, sum_ite_eq' univ x] simp only [mem_univ, ite_true] dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] have : (fun y => (if y = r then (1:ℝ) else 0) * (hammingDist x y : ℝ)) = (fun y => if y = r then (hammingDist x r : ℝ) else 0) := by ext y split_ifs with h · subst h; ring · ring rw [this, sum_ite_eq' univ r] simp only [mem_univ, ite_true] have h2 : (fun y => ∑ x', (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) = (fun y => if y = r then (1:ℝ) else 0) := by ext y have : (fun x' => (if x' = x then (1:ℝ) else 0) * gen_k_server_uniform_one_server_competitive_one_P_det past r x' y) = (fun x' => if x' = x then gen_k_server_uniform_one_server_competitive_one_P_det past r x y else 0) := by ext x' split_ifs with h · subst h; ring · ring rw [this, sum_ite_eq' univ x] simp only [mem_univ, ite_true] dsimp [gen_k_server_uniform_one_server_competitive_one_P_det] rw [h1, h2, ih (past ++ [r]) r] push_cast rfllemma gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves {m : ℕ} {o r : Fin 1 → Fin m} (h : ∃ i : Fin 1, o i = r i) : o = r := by obtain ⟨i, hi⟩ := h funext j have : j = i := Subsingleton.elim j i rw [this] exact hilemma gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves {m : ℕ} {os ρ : List (Fin 1 → Fin m)} (h : List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ) : os = ρ := by induction h with | nil => rfl | cons h1 h2 ih => rw [gen_k_server_uniform_one_server_competitive_one_fin_one_eq_of_serves h1, ih]lemma gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl {m : ℕ} (ρ : List (Fin 1 → Fin m)) : List.Forall₂ (fun o r => ∃ i, o i = r i) ρ ρ := by induction ρ with | nil => exact List.Forall₂.nil | cons r rs ih => exact List.Forall₂.cons ⟨0, rfl⟩ ihlemma gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost (m : ℕ) (a : Fin 1 → Fin m) (ρ : List (Fin 1 → Fin m)) : gen_k_server_uniform_opt a ρ = gen_k_server_uniform_path_cost a ρ := by dsimp [gen_k_server_uniform_opt] have h_mem : gen_k_server_uniform_path_cost a ρ ∈ {c | ∃ os, List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c} := by exact ⟨ρ, gen_k_server_uniform_one_server_competitive_one_forall₂_serves_refl ρ, rfl⟩ apply le_antisymm · exact Nat.sInf_le h_mem · apply le_csInf ⟨_, h_mem⟩ rintro c ⟨os, hos, rfl⟩ rw [gen_k_server_uniform_one_server_competitive_one_os_eq_of_forall₂_serves hos]theorem gen_k_server_uniform_one_server_competitive_one (m : ℕ) (a : Fin 1 → Fin m) : ∃ P, gen_k_server_uniform_is_rand_alg P ∧ ∀ ρ : List (Fin 1 → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ (gen_k_server_uniform_opt a ρ : ℝ) := by use gen_k_server_uniform_one_server_competitive_one_P_det refine ⟨gen_k_server_uniform_one_server_competitive_one_is_rand_alg m, ?_⟩ intro ρ dsimp [gen_k_server_uniform_expected_cost] rw [gen_k_server_uniform_one_server_competitive_one_expected_cost_from, gen_k_server_uniform_one_server_competitive_one_opt_eq_path_cost]