Lemma 18, p. 14 — the tail Σ_{k=n+1}^∞ k·q^{k−1} = q^n/(1 − q)²·(1 + n − qn)
ProvedAPrioriTSP.Sampling.lemma_18a-priori-tspapproximation-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingstochastic-combinatorial-optimization
Let (including ) and . Then the series converges, and
This closed form evaluates the tail of the linear bound against the weights in the proof of Lemma 14, with and ; it produces the constant .
Formalization Note The statement is HasSum of the sequence that is for and otherwise, which asserts convergence as well as the value. Here is the product .
Differences from the source:
- encoding: the equation Σ_{k=n+1}^∞ k·q^{k−1} = q^n/(1 − q)²·(1 + n − qn) →
HasSumof k ↦ (if n + 1 ≤ k then k·q^{k−1} else 0) with that value; reason: states convergence and the value at once; ℕ subtraction k − 1 is exact for k ≥ n + 1 ≥ 1
Preamble
import Mathlib import Definitions.Def_APrioriTSP_Sampling_Setting
Formal statement
namespace APrioriTSP.Sampling
/-- Lemma 18 (p. 14): `Σ_{k=n+1}^∞ k q^{k−1} = q^n / (1 − q)² · (1 + n − q n)` for `n ∈ ℕ`,
`q ∈ (0, 1)`. -/
theorem lemma_18 (n : ℕ) (q : ℝ) (hq0 : 0 < q) (hq1 : q < 1) :
HasSum (fun k : ℕ => if n + 1 ≤ k then (k : ℝ) * q ^ (k - 1) else 0)
(q ^ n / (1 - q) ^ 2 * (1 + n - q * n)) := by sorry
end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 14, Lemma 18, Equation (21)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.