Documentation

Determinize.Proof.Corollaries

Corollaries of trace soundness #

Jensen's inequality between the source and target output laws, preservation of expectations in the extended reals, preservation of the output mass and hence of the expectation conditioned on acceptance, and the law of total variance along traces with its consequence that determinization does not increase the variance. All follow from a TraceFactorization alone: trace by trace, the target output is the mean of the source output fiber.

The two output laws behind MeanOnTraces: the source output is the mixture of the fibers over the trace law and the target output is the pushforward of the trace law along output.

Under a trace factorization the two output laws have the same mass, the mass of the trace law: every fiber is a probability measure.

Output mass is preserved along the traces.

The expectations conditioned on acceptance agree: the unnormalized mean and the output mass are both preserved, so their quotient is.

theorem Determinize.Proof.Traces.MeanOnTraces.lintegral_convex_le {source target : Spec.Paper.Expr} (sound : MeanOnTraces source target) {φ : ℝ → ℝ} (convex : ConvexOn ℝ Set.univ φ) (nonneg : ∀ (value : ℝ), 0 ≤ φ value) :

Jensen's inequality along the traces.

theorem Determinize.Proof.Traces.lintegral_ofReal_sub_le {α : Type u_1} [MeasurableSpace α] (ν : MeasureTheory.Measure α) (a b : α → ℝ) (hb0 : ∀ (x : α), 0 ≤ b x) :
∫⁻ (x : α), ENNReal.ofReal (a x - b x) ∂ν ≤ ∫⁻ (x : α), ENNReal.ofReal (a x) ∂ν

∫⁻ (a - b)⁺ ≤ ∫⁻ a⁺ when b is nonnegative.

theorem Determinize.Proof.Traces.lintegral_ofReal_le_sub_add {α : Type u_1} [MeasurableSpace α] (ν : MeasureTheory.Measure α) {a b : α → ℝ} (ha : Measurable a) (hb : Measurable b) :
∫⁻ (x : α), ENNReal.ofReal (a x) ∂ν ≤ ∫⁻ (x : α), ENNReal.ofReal (a x - b x) ∂ν + ∫⁻ (x : α), ENNReal.ofReal (b x) ∂ν

∫⁻ a⁺ ≤ ∫⁻ (a - b)⁺ + ∫⁻ b⁺.

theorem Determinize.Proof.Traces.ereal_sub_lintegral_eq {α : Type u_1} [MeasurableSpace α] (ν : MeasureTheory.Measure α) {a b : α → ℝ} (ha : Measurable a) (hb : Measurable b) (ha0 : ∀ (x : α), 0 ≤ a x) (hb0 : ∀ (x : α), 0 ≤ b x) (finite : ∫⁻ (x : α), ENNReal.ofReal (a x) ∂ν ≠ ⊤ ∨ ∫⁻ (x : α), ENNReal.ofReal (b x) ∂ν ≠ ⊤) :
↑(∫⁻ (x : α), ENNReal.ofReal (a x) ∂ν) - ↑(∫⁻ (x : α), ENNReal.ofReal (b x) ∂ν) = ↑(∫⁻ (x : α), ENNReal.ofReal (a x - b x) ∂ν) - ↑(∫⁻ (x : α), ENNReal.ofReal (b x - a x) ∂ν)

For nonnegative a, b, the extended-real difference ∫⁻ a - ∫⁻ b equals ∫⁻ (a - b)⁺ - ∫⁻ (a - b)⁻ as soon as one of the two integrals is finite.

theorem Determinize.Proof.Traces.integral_sub_sq_eq_moments {μ : MeasureTheory.Measure ℝ} [MeasureTheory.IsFiniteMeasure μ] (memLp : MeasureTheory.MemLp id 2 μ) (m : ℝ) :
∫ (value : ℝ), (value - m) ^ 2 ∂μ = ∫ (value : ℝ), value ^ 2 ∂μ - 2 * m * ∫ (value : ℝ), value ∂μ + μ.real Set.univ * m ^ 2

The second moment about m of a real law with a finite second moment, through its first two moments and its mass.

theorem Determinize.Proof.Traces.variance_id_eq_moments {μ : MeasureTheory.Measure ℝ} [MeasureTheory.IsFiniteMeasure μ] (memLp : MeasureTheory.MemLp id 2 μ) :
ProbabilityTheory.variance id μ = ∫ (value : ℝ), value ^ 2 ∂μ - 2 * (∫ (value : ℝ), value ∂μ) ^ 2 + μ.real Set.univ * (∫ (value : ℝ), value ∂μ) ^ 2

Mathlib's variance of a real law with a finite second moment, through its first two moments and its mass; the law need not be normalized.

The law of total variance along a trace factorization, through the second moments: the target output law has a finite second moment, the fiber variances are integrable over the trace law, and the source second moment is the target second moment plus the mean fiber variance.

The law of total variance along a trace factorization: the fiber variances are integrable over the trace law and the source output variance is the target output variance plus the mean fiber variance. Both output laws have the same mass and the same mean, so Mathlib's variance needs no normalization.

Determinization does not increase the second moment or the variance of the output law.

theorem Determinize.Proof.Paper.jensen_soundness (program : Spec.Paper.Expr) (typed : Spec.Paper.Typed [] program (Spec.Paper.Ty.float Spec.Paper.Affinity.E)) (sourceSafe : Spec.Paper.DomainSafe program) (φ : ℝ → ℝ) (convex : ConvexOn ℝ Set.univ φ) (nonneg : ∀ (value : ℝ), 0 ≤ φ value) :

Jensen's inequality between the two output laws, from operational trace soundness.

Output mass preservation, from operational trace soundness.

Preservation of the expectation conditioned on acceptance, from operational trace soundness.