Lemma 11 — binomial sum of maximum expected cover times
OpenCoverTime537.SpecifiedStart.Supplement.lemma_11computational-complexitymarkov-chainp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be the base graph, , and let be the ordinary walk on started at a cube vertex , with cover time (start visited at time zero, hub included). Let count the departures from the hub completed by time . For every integer , with ,
and the right side converges absolutely: .
The identity cancels all contributions before the base graph is covered, which is what lets the proof of Theorem 2 isolate the walks that cover in one excursion.
Formalization Note The expectation is written as over walk prefixes with that cover every vertex of , weighted by their path probabilities; holds exactly when the prefix up to covers.
Differences from the source:
- encoding: E_c[Σ_{s≥τ} g_s] → Σ_s Σ over covering prefixes of length s+1 from c of path weight × g_s, with absolute summability as a conclusion; reason: {s ≥ τ} is the event that the prefix up to s covers; Fubini for the absolutely convergent series; summability is proved, not assumed
- encoding: a fixed cube vertex c → every cube vertex c; reason: the source fixes an arbitrary cube vertex; quantifying over all of them is the same claim
Preamble
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_CubeHelper
Formal statement
namespace CoverTime537.SpecifiedStart.Supplement
open CoverTime537.SpecifiedStart
/-- Aghazadeh, STOC 2027 submission #537, Lemma 11 and eq. (17), p.16.
For every source, every cube vertex `c` and every `k ≥ 2` (with `x = D + k`,
`D = 2N + 8`): the post-coverage series of the base walk on `Q_N` from `c` is
absolutely summable, and `BinomialSum(k)` equals its sum. -/
theorem lemma_11 (D : Source) (a : Fin 3 → Bool) (k : ℕ) (hk : 2 ≤ k) :
Summable (lemma11At D k (cubeV D (N D) a) true) ∧
binomialSum D k = ∑' s, lemma11At D k (cubeV D (N D) a) false s := by sorry
end CoverTime537.SpecifiedStart.Supplement
Source
Ryan Aghazadeh, How Hard Is It to Compute Cover Time?, STOC 2027 submission #537 (October 2026), papers/stoc2027-537/source.pdf, SHA-256 4487efe2e616b5ed1b0e9a8a4172a4b53fd492c5d9ad4717ed4921b088564fd8, Lemma 11 and eq. (17) p.16, proof pp.16–17; definitions of D, X_s, τ, r_s p.16