Lemma 4.1 — Chebyshev covariance bound
OpenPrivateContinualCounting.Kraft.Supplement.chebyshev_covariancecontinual-countingdifferential-privacyharmonic-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be any additive data-independent real noise process with finite second moments on a probability space. Suppose every transcript is -DP, where and . Write and . For every finite zero-based window , every and every real coefficient vector ,
Thus the covariance matrix dominates in positive semidefinite order. Coefficients may have either sign. This is the privacy-induced variance floor needed by stationarisation.
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
- generalization: Section 4 also fixes an interval envelope B → the covariance inequality is stated for every additive DP process without an interval envelope; reason: the displayed Lemma 4.1 proof never uses B; every source instance satisfies the stated hypotheses
Preamble
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_Covariance open MeasureTheory ProbabilityTheory Filter set_option autoImplicit false
Formal statement
namespace PrivateContinualCounting.Kraft.Supplement
/-- Lemma 4.1. The quadratic form is the equivalent covariance PSD bound. -/
theorem chebyshev_covariance {Ω : Type} [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P] (N : AdditiveNoise Ω P)
(ε δ : ℝ) (hε : 0 ≤ ε) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(hDP : TranscriptDP N.law ε δ) :
∀ (W : Finset ℕ) (j : ℕ), j ∈ W → ∀ b : ℕ → ℝ,
privacyConstant ε δ * (b j)^2 ≤
variance (fun ω => ∑ i ∈ W, b i * N.increment i ω) P ∧
privacyConstant ε δ * (b j)^2 ≤
∑ i ∈ W, ∑ k ∈ W, b i * covariance (N.increment i) (N.increment k) P * b k := by sorry
end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 9, PDF p. 11, Lemma 4.1