Lemma 5.3 — exact A/B/C variance at every local position
OpenPrivateContinualCounting.Kraft.Supplement.hypertree_variancecontinual-countingdifferential-privacyharmonic-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , , and use the Section 5 square-root hypertree. For every positive time let , , , , and let be the prescribed budgets. Its actual unit-noise variance is
Every published Gaussian counter whose factors and noise agree with these formulas has normalized variance as well. The equality holds at every local position; makes the middle term vanish at a super-epoch start. This is an exact law-of-the-construction equality, not a definition of the counter or an upper bound for its BLT variant.
Differences from the source:
- encoding: positive source time and stream indices → natural times with source input i+1 at coordinate i and zero-time noise zero; reason: the published base conventions are reused and every positive time and interval is retained
- encoding: the normalized variance of the constructed counter → the actual variance of the explicit seed sum, together with equality to every Gaussian-counter realization of it; reason: this states both meanings of the source variance and does not assume the identity
Preamble
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_Hypertree open MeasureTheory ProbabilityTheory Filter set_option autoImplicit false
Formal statement
namespace PrivateContinualCounting.Kraft.Supplement
/-- Lemma 5.3: actual noise variance and normalized factor variance agree with
all three exact contributions, including zero B contribution when κ=0. -/
theorem hypertree_variance (a ξ : ℝ) (ha : 0 < a) (hξ0 : 0 < ξ) (hξ1 : ξ < 1) :
∀ t : ℕ, 1 ≤ t →
let K := epoch t
let J := superEpoch K
let τ := localTime t
let κ := localEpoch K
treeVariance squareRootFamily a ξ t =
(∑ j ∈ Finset.range J, 1 / zBudget a ξ j) +
squareEnergy κ * squareEnergy (2^J) / yBudget a ξ J +
squareEnergy τ * squareEnergy (2^K) / (1-qBudget a J) ∧
∀ M : GaussianCounter TreeIndex, IsTree M squareRootFamily a ξ →
M.variance t = treeVariance squareRootFamily a ξ t := by sorry
end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 12, PDF p. 14, Lemma 5.3