The cube helper graphs , cube-first coverage, and the binomial sum of (17)
DefinitionCoverTime537_SpecifiedStart_Supplement_CubeHelperLet be the published hub graph of a source (the subdivided graph with vertices plus a universal hub ). For , the graph adds
- eight cube vertices indexed by three-bit strings, two of them adjacent exactly when they differ in one bit, each also adjacent to ;
- leaves, each adjacent to only.
No other edges are added. The paper uses for : the first leaves are the permanent markers and the other the probes. Thus and .
For a start , the cube-first probability is the probability that the ordinary walk on from visits all eight cube vertices strictly before its first visit to . It is the sum over of the probabilities of the disjoint events "the cube is first fully covered at time and is not visited at times ".
On the base graph , with , write for the number of departures from the hub completed by time , i.e. the number of with . For and , the summand of (17) along a walk prefix is
and its expectation restricted to ( the cover time of ) is the sum over walk prefixes that start at the chosen cube vertex and cover all of , weighted by their path probabilities. Finally
These objects state Lemmas 10 and 11, the two labelled steps of the proof of Theorem 2.
Formalization Note The graph is the symmetric closure of the listed adjacencies; the hub is the published hub vertex none of . An absolute-value version of the time- term is also defined so that absolute summability can be stated.
import Mathlib
import Definitions.Def_CoverTime537_SpecifiedStart_Construction
import Definitions.Def_CoverTime537_SpecifiedStart_Supplement_MaxCover
namespace CoverTime537.SpecifiedStart.Supplement
noncomputable section
open scoped BigOperators
open CoverTime537.SpecifiedStart
/-- Vertices of `Q_j` (§7, pp.13–14): the vertices of `G′ = hubGraph D`
(hub `none`), eight cube vertices indexed by three-bit strings, and `j` leaves.
Leaves `0, …, N−1` are the permanent markers, the rest the probes. -/
abbrev QVertex (D : Source) (j : ℕ) := HVertex D ⊕ ((Fin 3 → Bool) ⊕ Fin j)
instance (D : Source) (j : ℕ) : Nonempty (QVertex D j) := ⟨.inl none⟩
/-- Decidable equality assembled from the components (direct synthesis on the
nested sum exceeds the default instance-search budget). -/
instance (D : Source) (j : ℕ) : DecidableEq (QVertex D j) :=
haveI : DecidableEq (HVertex D) := inferInstance
haveI : DecidableEq ((Fin 3 → Bool) ⊕ Fin j) := inferInstance
inferInstance
def hub (D : Source) (j : ℕ) : QVertex D j := .inl none
def cubeV (D : Source) (j : ℕ) (a : Fin 3 → Bool) : QVertex D j := .inr (.inl a)
def leaf (D : Source) (j : ℕ) (i : Fin j) : QVertex D j := .inr (.inr i)
def IsCube {D : Source} {j : ℕ} (x : QVertex D j) : Prop := ∃ a, x = cubeV D j a
/-- Generating relation: edges of `G′`; cube edges between strings differing in
exactly one bit; hub to every cube vertex and every leaf. Nothing else. -/
def qRel (D : Source) (j : ℕ) : QVertex D j → QVertex D j → Prop
| .inl x, .inl y => (hubGraph D).Adj x y
| .inl none, .inr _ => True
| .inr (.inl a), .inr (.inl b) =>
(Finset.univ.filter (fun i : Fin 3 => a i ≠ b i)).card = 1
| _, _ => False
/-- The graph `Q_j`: the symmetric irreflexive closure of `qRel`. -/
def Q (D : Source) (j : ℕ) : SimpleGraph (QVertex D j) := SimpleGraph.fromRel (qRel D j)
/-- Probability, for the ordinary walk on `Q_j` from `x`, that the eight cube
vertices are all visited strictly before the first visit to the hub: disjoint
finite cylinders indexed by the time `t` at which cube coverage first occurs
(no hub visit at times `0..t`, every cube vertex seen by `t`, the vertex at `t`
not seen before). -/
def cubeFirstAt (D : Source) (j : ℕ) (x : QVertex D j) (t : ℕ) : ℝ := by
classical
exact ∑ w : Fin (t + 1) → QVertex D j,
if w 0 = x ∧ (∀ i, w i ≠ hub D j) ∧ (∀ a, ∃ i, w i = cubeV D j a) ∧
(∀ i : Fin (t + 1), i.val < t → w i ≠ w (Fin.last t))
then MarkovMixing.pathWeight (walk (Q D j)) w else 0
def cubeFirstProb (D : Source) (j : ℕ) (x : QVertex D j) : ℝ :=
∑' t, cubeFirstAt D j x t
/-- §8, p.16: `D = deg_{Q_N}(z) = 2N + 8` (N subdivided vertices, eight cube
vertices and N markers). -/
def hubDeg (D : Source) : ℕ := 2 * N D + 8
/-- Departures from the hub completed by time `s`: indices `0 ≤ i < s` with
`X_i = z` (a step out of the hub; returns to it are not counted). -/
def departures {D : Source} {j s : ℕ} (w : Fin (s + 1) → QVertex D j) : ℕ := by
classical
exact (Finset.univ.filter (fun i : Fin (s + 1) => i.val < s ∧ w i = hub D j)).card
/-- The summand of (17) at time `s` along a prefix `w`, with `x = D + k`:
`(D/x)^{r_s} − (2k/(x−1))·1{X_s = z}·(D/(x−1))^{r_s}`. -/
def term11 (D : Source) (k : ℕ) {s : ℕ} (w : Fin (s + 1) → QVertex D (N D)) : ℝ :=
let x : ℝ := (hubDeg D : ℝ) + k
((hubDeg D : ℝ) / x) ^ departures w -
(2 * (k : ℝ) / (x - 1)) * (if w (Fin.last s) = hub D (N D) then 1 else 0) *
((hubDeg D : ℝ) / (x - 1)) ^ departures w
/-- `E_c[ g_s · 1{s ≥ τ} ]` for the base walk on `Q_N` from `c`, with `g = term11`
(or its absolute value): `s ≥ τ` iff the prefix `X_0, …, X_s` covers `Q_N`. -/
def lemma11At (D : Source) (k : ℕ) (c : QVertex D (N D)) (abs : Bool) (s : ℕ) : ℝ := by
classical
exact ∑ w : Fin (s + 1) → QVertex D (N D),
if w 0 = c ∧ (∀ v, ∃ i, w i = v) then
MarkovMixing.pathWeight (walk (Q D (N D))) w *
(if abs then |term11 D k w| else term11 D k w)
else 0
/-- `BinomialSum(k) = Σ_{j=0}^{k} (−1)^{j+1} C(k,j) M(Q_{N+j})`, eq. (17). -/
def binomialSum (D : Source) (k : ℕ) : ℝ :=
∑ j ∈ Finset.range (k + 1),
(-1 : ℝ) ^ (j + 1) * (Nat.choose k j : ℝ) * maxCover (Q D (N D + j))
end
end CoverTime537.SpecifiedStart.Supplement