Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Additive processes, finite transcripts and Gaussian testing privacy

Definition
PrivateContinualCounting_Kraft_Supplement_Privacy

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

continual-countingdifferential-privacyharmonic-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) be a probability space. An additive data-independent counter is one measurable real process (Nt)t≥0(N_t)_{t\ge0}(Nt​)t≥0​, with N0=0N_0=0N0​=0 almost surely and finite second moments, released as Yt=St+NtY_t=S_t+N_tYt​=St​+Nt​ for every input stream. No centering, stationarity, Gaussianity or independent-increment condition is imposed. Its interval variance and zero-based increment are

VN(a,w)=Var⁡P(Na+w−Na),Di=Ni+1−Ni.V_N(a,w)=\operatorname{Var}_P(N_{a+w}-N_a),\qquad D_i=N_{i+1}-N_i.VN​(a,w)=VarP​(Na+w​−Na​),Di​=Ni+1​−Ni​.

The uniform envelope means VN(a,w)≤B(w)V_N(a,w)\le B(w)VN​(a,w)≤B(w) for every a≥0,w≥1a\ge0,w\ge1a≥0,w≥1. Source input i+1i+1i+1 is coordinate iii in the reused stream representation.

Finite-transcript (ε,δ)(\varepsilon,\delta)(ε,δ)-privacy uses the published finite-database approximate-DP predicate on each prefix input, padded by zeros. All laws here depend only on that prefix, so this is equivalent to the source's quantification over infinite streams. The referenced predicate uses exactly-one-coordinate adjacency; identical databases satisfy the inequality automatically for the nonnegative parameters in the statements.

For probability measures P,QP,QP,Q and 0≤α≤10\le\alpha\le10≤α≤1, randomized testing privacy uses

T(P,Q)(α)=inf⁡ϕ measurable, 0≤ϕ≤1∫ϕdP≤α(1−∫ϕ dQ).T(P,Q)(\alpha)=\inf_{\substack{\phi\text{ measurable},\ 0\le\phi\le1\\\int\phi\,dP\le\alpha}}\left(1-\int\phi\,dQ\right).T(P,Q)(α)=ϕ measurable, 0≤ϕ≤1∫ϕdP≤α​inf​(1−∫ϕdQ).

Every ordered adjacent transcript pair must have tradeoff at least that of N(0,1)\mathcal N(0,1)N(0,1) versus N(μ,1)\mathcal N(\mu,1)N(μ,1). Set

δμ(ε)=Φ(−ε/μ+μ/2)−eεΦ(−ε/μ−μ/2),cε,δ=1−δ4(1+eε).\delta_\mu(\varepsilon)=\Phi(-\varepsilon/\mu+\mu/2)-e^\varepsilon\Phi(-\varepsilon/\mu-\mu/2),\quad c_{\varepsilon,\delta}=\frac{1-\delta}{4(1+e^\varepsilon)}.δμ​(ε)=Φ(−ε/μ+μ/2)−eεΦ(−ε/μ−μ/2),cε,δ​=4(1+eε)1−δ​.

An admissible scale is any μ>0\mu>0μ>0 with δμ(ε)≤δ\delta_\mu(\varepsilon)\le\deltaδμ​(ε)≤δ. The scalar LTI noise and its transcript law are computed directly from the published factors and one independent standard Gaussian seed, with scale Δ/μ\Delta/\muΔ/μ. This supplies privacy and interval vocabulary; it assumes no calibration or accuracy theorem.

Formalization Note Tests are bounded, so their expectations under the probability laws used here are integrable. The feasible set of the testing infimum contains the zero test and lies in [0,1][0,1][0,1]. The predicate is used only for probability measures and α∈[0,1]\alpha\in[0,1]α∈[0,1].

Definition code
import Definitions.Def_PrivateContinualCounting_Kraft_GaussianCounter
import Definitions.Def_PrivateContinualCounting_Kraft_LTIFactors
import Definitions.Def_PrivRobustStat_Privacy

open MeasureTheory ProbabilityTheory Filter

set_option autoImplicit false

namespace PrivateContinualCounting.Kraft.Supplement

/-- A finite input padded by zero, using the published stream type. -/
def extendStream {n : ℕ} (x : Fin n → Set.Icc (0 : ℝ) 1) : Stream :=
  fun j => if h : j < n then x ⟨j,h⟩ else ⟨0, by constructor <;> norm_num⟩

/-- Privacy of every positive finite transcript. The reused finite-database definition has
exact-change adjacency; unchanged databases obey the inequality for ε,δ≥0 automatically. -/
def TranscriptDP (law : (x : Stream) → (n : ℕ) → Measure (Fin n → ℝ)) (ε δ : ℝ) : Prop :=
  ∀ n : ℕ, 0 < n → PrivRobustStat.IsApproxDP (n := n) (fun x => law (extendStream x) n) ε δ

/-- The Neyman–Pearson tradeoff, over measurable randomized tests. For α∈[0,1] its
feasible set is nonempty (the zero test), and objective values lie in [0,1]. -/
noncomputable def testingTradeoff {X : Type} [MeasurableSpace X]
    (P Q : Measure X) (α : ℝ) : ℝ :=
  sInf {β : ℝ | ∃ φ : X → ℝ, Measurable φ ∧
    (∀ x, φ x ∈ Set.Icc (0 : ℝ) 1) ∧
    (∫ x, φ x ∂P) ≤ α ∧ β = 1 - ∫ x, φ x ∂Q}

def TranscriptGDP (law : (x : Stream) → (n : ℕ) → Measure (Fin n → ℝ)) (μ : ℝ) : Prop :=
  ∀ n : ℕ, 0 < n → ∀ x y : Stream, Adjacent x y →
    ∀ α ∈ Set.Icc (0 : ℝ) 1,
      testingTradeoff (gaussianReal 0 1) (gaussianReal μ 1) α ≤
        testingTradeoff (law x n) (law y n) α

noncomputable def gaussianDelta (ε μ : ℝ) : ℝ :=
  (gaussianReal 0 1).real (Set.Iic (-ε / μ + μ / 2)) -
  Real.exp ε * (gaussianReal 0 1).real (Set.Iic (-ε / μ - μ / 2))

def AdmissibleGDP (ε δ μ : ℝ) : Prop := 0 < μ ∧ gaussianDelta ε μ ≤ δ

/-- An arbitrary stream-independent process. No Gaussianity, centering or stationarity. -/
structure AdditiveNoise (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) where
  noise : ℕ → Ω → ℝ
  measurable : ∀ t, Measurable (noise t)
  secondMoment : ∀ t, MemLp (noise t) 2 P
  zero : ∀ᵐ ω ∂P, noise 0 ω = 0

noncomputable def AdditiveNoise.law {Ω : Type} [MeasurableSpace Ω] {P : Measure Ω}
    (N : AdditiveNoise Ω P) (x : Stream) (n : ℕ) : Measure (Fin n → ℝ) :=
  P.map (fun ω k => prefixSum x (k.val + 1) + N.noise (k.val + 1) ω)

noncomputable def AdditiveNoise.intervalVariance {Ω : Type} [MeasurableSpace Ω] {P : Measure Ω}
    (N : AdditiveNoise Ω P) (a w : ℕ) : ℝ :=
  variance (fun ω => N.noise (a+w) ω - N.noise a ω) P

/-- Zero-based increment i is the source's D_{i+1}. -/
def AdditiveNoise.increment {Ω : Type} [MeasurableSpace Ω] {P : Measure Ω}
    (N : AdditiveNoise Ω P) (i : ℕ) (ω : Ω) : ℝ := N.noise (i+1) ω - N.noise i ω

def UniformEnvelope {Ω : Type} [MeasurableSpace Ω] {P : Measure Ω}
    (N : AdditiveNoise Ω P) (B : ℕ → ℝ) : Prop :=
  ∀ a w : ℕ, 0 < w → N.intervalVariance a w ≤ B w

noncomputable def privacyConstant (ε δ : ℝ) : ℝ :=
  (1-δ)/(4*(1+Real.exp ε))

/-- Directly defined actual LTI noise and laws; admissibility is a theorem obligation
when the raw factors are constructed, and is assumed only when already given LTI factors. -/
noncomputable def scalarNoise (d : LTIData ℝ 1) (μ : ℝ) (t : ℕ)
    (ω : ℕ × Fin 1 → ℝ) : ℝ :=
  Real.sqrt d.deltaSq / μ *
    ∑ i ∈ Finset.range t, d.l (t-1-i) 0 * ω (i,0)

noncomputable def scalarLaw (d : LTIData ℝ 1) (μ : ℝ) (x : Stream) (n : ℕ) :
    Measure (Fin n → ℝ) :=
  (gaussianSeed (ℕ × Fin 1)).map
    (fun ω k => prefixSum x (k.val+1) + scalarNoise d μ (k.val+1) ω)

noncomputable def scalarIntervalVariance (d : LTIData ℝ 1) (μ : ℝ) (a w : ℕ) : ℝ :=
  variance (fun ω => scalarNoise d μ (a+w) ω - scalarNoise d μ a ω)
    (gaussianSeed (ℕ × Fin 1))

end PrivateContinualCounting.Kraft.Supplement
Source
Kisung Park, STOC 2027 submission #86 (October 2026), p. 6, PDF p. 8, Section 2.1 and Definition 2.3; p. 9, PDF p. 11, Section 4

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me