Theorem 1.2 — both directions of uniform interval accuracy
OpenPrivateContinualCounting.Kraft.Supplement.uniform_interval_accuracycontinual-countingdifferential-privacyharmonic-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , and with doubling constant . Both following assertions hold.
- Every additive data-independent -DP counter on any probability space with almost surely and finite second moments obeys the necessity implication
No Gaussian, centering, stationary or independent-increment condition is imposed.
- If holds, the same real scalar canonical counter as Theorem 1.1(ii), computed from the published spectral weight , is admissible and unit-GDP, and for every ,
The supremum is over a bounded nonempty set, as also asserted. The paper writes ; its Appendix C proof supplies
This positive constant is independent of start, width and time, and covers widths as well. For every admissible , this same counter is -GDP and -DP and all interval and prefix variances are exactly divided by ; the interval envelope is divided by the same factor.
Together these characterize feasible uniform interval accuracy without imposing time invariance on the input mechanism.
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 paper's C-prime → the explicit positive Appendix C constant for each supplied doubling constant D; reason: this is the constant the source proof establishes, uniformly including widths 1 and 2
Preamble
import Definitions.Def_PrivateContinualCounting_Kraft_Supplement_GenericOuter open MeasureTheory ProbabilityTheory Filter set_option autoImplicit false
Formal statement
namespace PrivateContinualCounting.Kraft.Supplement
/-- Theorem 1.2(a)–(b). The constant is the one in Appendix C, including w=1,2. -/
theorem uniform_interval_accuracy (ε δ : ℝ) (hε : 0 ≤ ε) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(g : ℝ → ℝ) (D : ℝ) (hg : IsEnvelopeWith g D) :
(∀ {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(N : AdditiveNoise Ω P) (C : ℝ), TranscriptDP N.law ε δ →
(∀ a w : ℕ, 0 < w → N.intervalVariance a w ≤
C * (Real.log ((w:ℝ)+2))^2 * g (Real.log ((w:ℝ)+2))) → KraftCondition g) ∧
(KraftCondition g →
IsLTI (constructedData g) ∧ 0 < intervalConstant g D ∧
TranscriptGDP (scalarLaw (constructedData g) 1) 1 ∧
(∀ w : ℕ, 0 < w →
BddAbove (Set.range (fun a => scalarIntervalVariance (constructedData g) 1 a w)) ∧
sSup (Set.range (fun a => scalarIntervalVariance (constructedData g) 1 a w)) ≤
intervalConstant g D * (Real.log ((w:ℝ)+2))^2 * g (Real.log ((w:ℝ)+2))) ∧
∀ μ : ℝ, AdmissibleGDP ε δ μ →
TranscriptGDP (scalarLaw (constructedData g) μ) μ ∧
TranscriptDP (scalarLaw (constructedData g) μ) ε δ ∧
(∀ a w : ℕ, 0 < w → scalarIntervalVariance (constructedData g) μ a w =
scalarIntervalVariance (constructedData g) 1 a w / μ^2 ∧
scalarIntervalVariance (constructedData g) μ a w ≤
intervalConstant g D * (Real.log ((w:ℝ)+2))^2 * g (Real.log ((w:ℝ)+2)) / μ^2) ∧
(∀ t : ℕ, variance (scalarNoise (constructedData g) μ t)
(gaussianSeed (ℕ × Fin 1)) = (constructedData g).variance t / μ^2)) := by sorry
end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 1, PDF p. 3, Theorem 1.2; proof pp. 9-10, 20-22, PDF pp. 11-12, 22-24