How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Approximate-DP kernels admit a nearby pure-DP kernel on standard-Borel targets
Statement
Assume AC. Let and be measurable spaces measurably isomorphic to Polish spaces, let be a probability measure on , and let be probability kernels from to . Let and . Suppose that for -almost every , both inequalities
hold for every measurable . Then there is a probability kernel from to such that for -almost every and every measurable ,
and
where over measurable events.
Statement references
Facts & Assumptions
Given: AC, standard-Borel spaces , probability measure , probability kernels , , , and the two event inequalities for -almost every and every measurable event.
Axiom of Choice is assumed by the jointly measurable RN-kernel and countable-algebra suppliers.
Standard-Borel spaces are measurable spaces in the stated standard-Borel class.
Probability kernels have probability-measure sections and measurable event evaluations.
Joint RN derivatives: for standard-Borel source and target, kernels dominated sectionwise almost everywhere by a reference kernel have a product-measurable density representing every event on one common conull set.
Countable determining algebra: a standard-Borel target has a countable algebra generating its sigma-algebra and determining finite measures.
Kernel integration measurability: integrating a nonnegative product-measurable function against a probability kernel gives a measurable function of the source point.
Density measures: integrating a nonnegative measurable section over events defines a measure.
Measurable sections: every section of a product-measurable function is measurable.
Borel composition preserves measurability; in particular finite-valued replacements and the clipping and correction functions below remain measurable.
At , The exponential is positive and satisfies gives , hence . Then The exponential function is strictly increasing gives for , and the reciprocal identity gives .
Proof
Let , which is a probability kernel by [F2]. For every , implies , so both sections are absolutely continuous with respect to . Apply [F3] twice to obtain jointly measurable densities. Replace any value by in each density; this Borel operation preserves measurability by [F8] and changes no section measure on the common conull representation set, since each density has integral one. Call the resulting finite-valued functions and . Let be the countable generating algebra in [F4], containing . Define to be the set of for which, for every , both and hold, and both DP inequalities hold for . By [F2], [F5], and countability of , is measurable. It has full -measure by the joint representation property and the hypothesis. For , [F6] and [F7] make the density integrals finite measures; they agree with and on , so [F4] gives the density representations on every measurable event.
For fixed , put , a finite measure. Let be the measurable sets approximable in -measure by members of . Complements preserve symmetric-difference measure, and proves closure under finite unions. If and , put and , for . The are disjoint and , so countable additivity and finiteness of give . Approximate each of the first sets closely enough that their finite union has arbitrarily small symmetric-difference measure from . Thus is a sigma-algebra containing , so it is the full target sigma-algebra. For any measurable , choose with . Then both and , so the two inequalities on pass to every measurable .
Write and by [F9]. On , set , , and . These quantities are finite and measurable in by [F5] and [F8]. The sets and are measurable by [F7]. Step 2.1 and the density identities give and . Also , so . Hence .
Define a corrected density on as follows. If , let and . Its denominator is positive and because , so and . If , let and . Here and because , so and . If , set . These formulas are product-measurable by [F8], and in every case and . Set off and define . By [F5], this is measurable in for each ; for each it is a probability measure by [F6] and the normalization, and for it equals the probability measure . Thus is a probability kernel. For , integrate and use the density representation of L to obtain the claimed two-sided pure-DP inequalities.
For , clipping changes by total integral , while correction moves in one direction and changes its integral by . Thus . For probability densities with equal integral, : every event integral is bounded by the positive-part integral and attains it. Hence on . This TV function is measurable: applying the approximation argument of step 2.1 to shows its supremum may be taken over , whose kernel evaluations are measurable. Since is conull, integration proves the asserted bound.
Depends on
- Differential privacy, databases, and add/remove adjacency
- Standard Borel spaces
- The Axiom of Choice
- Measure kernel and probability kernel
- Jointly measurable Radon–Nikodym derivatives for probability kernels
- Measurability of integration against a kernel
- Standard borel spaces have countable generating and measure determining algebras
- The indefinite integral of a nonnegative measurable function is a measure
- Every section of a product-measurable function is measurable
- Composition with a Borel measurable outer map preserves measurability
- The exponential function is strictly increasing
- The exponential is positive and satisfies $\exp(-x)=1/\exp(x)$
Used by
Dependency tree · two levels
47 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy (standard reference, not scraped)
- Salil Vadhan, The Complexity of Differential Privacy, 2017 manuscript (standard reference, not scraped)