p. 12, after (13) — the dyadic grid 𝒯 lies in 𝒟_T = {1, …, T − 1} and has |𝒯| ≤ 2 log₂ T points
ProvedCPDNetworks.Unknown.grid_cardchange-point-detectiondyadic-gridp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be the dyadic grid (13),
Then every grid point is a possible change point, , and
The cardinality bound is what the union bound over the grid costs in the threshold (15), through the factor inside the logarithm.
Formalization Note. The paper writes . The equality fails when and overlap (for , ), so only the inequality, which is what the proof of Lemma 5 uses, is stated.
Preamble
import Mathlib import Definitions.Def_HighDimProb_RandomMatrices_matrixOpNorm import Definitions.Def_CPDNetworks_Unknown_Setting open scoped Matrix open HighDimProb.RandomMatrices
Formal statement
namespace CPDNetworks.Unknown
/-- p. 12, after (13): the dyadic grid lies in `𝒟_T` and has at most `2 log₂ T` points. -/
theorem grid_card (T : ℕ) (hT : 2 ≤ T) :
((dyadicGrid T).card : ℝ) ≤ 2 * Real.logb 2 T ∧ dyadicGrid T ⊆ DT T := by sorry
end CPDNetworks.Unknown
Source
Enikeeva and Klopp, Change-point detection in dynamic networks with missing links, arXiv:2106.14470v2, p. 12, display (13) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.