import Determinize.Proof.Corollariesimport Determinize.Proof.Semantics.Terminationnamespace Determinize.Proofopen MeasureTheory ProbabilityTheory Spec Spec.Paperopen scoped ENNRealtheorem normalized_probability {α : Type*} [MeasurableSpace α] (μ : Measure α) [IsFiniteMeasure μ] (positive : μ Set.univ ≠ 0) : IsProbabilityMeasure ((μ Set.univ)⁻¹ • μ) := by constructor simp [Measure.smul_apply, ENNReal.inv_mul_cancel positive (measure_ne_top μ Set.univ)]theorem normalized_variance (μ : Measure ℝ) [IsFiniteMeasure μ] (positive : μ Set.univ ≠ 0) (moment : MemLp id 2 μ) : variance id ((μ Set.univ)⁻¹ • μ) = (∫ x, x ^ 2 ∂μ) / (μ Set.univ).toReal - ((∫ x, x ∂μ) / (μ Set.univ).toReal) ^ 2 := by have := normalized_probability μ positive rw [variance_eq_sub (moment.smul_measure (ENNReal.inv_ne_top.mpr positive))] simp only [integral_smul_measure, ENNReal.toReal_inv, smul_eq_mul, Pi.pow_apply, id_eq] simp only [div_eq_mul_inv, mul_comm]local instance (program : Expr) : IsFiniteMeasure (Spec.Paper.bigStepMeasure program) := by rw [← Traces.correspondence program] infer_instancenamespace Papertheorem returned_expectation_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < Spec.Paper.bigStepMeasure program Set.univ) (integrable : Integrable id (Spec.Paper.bigStepMeasure program)) : 0 < Spec.Paper.bigStepMeasure program.determinize Set.univ ∧ IsProbabilityMeasure (returnedLaw program) ∧ IsProbabilityMeasure (returnedLaw program.determinize) ∧ Integrable id (returnedLaw program) ∧ Integrable id (returnedLaw program.determinize) ∧ (∫ x, x ∂returnedLaw program.determinize) = ∫ x, x ∂returnedLaw program := by have positive := positive.ne' have mass := output_mass_soundness program typed safe have targetPositive : Spec.Paper.bigStepMeasure program.determinize Set.univ ≠ 0 := by rwa [mass] obtain ⟨_, targetIntegrable, mean⟩ := finite_expectation_soundness program typed safe integrable refine ⟨pos_iff_ne_zero.mpr targetPositive, normalized_probability _ positive, normalized_probability _ targetPositive, integrable.smul_measure (ENNReal.inv_ne_top.mpr positive), targetIntegrable.smul_measure (ENNReal.inv_ne_top.mpr targetPositive), ?_⟩ simp only [returnedLaw, returnProbability, integral_smul_measure, mass, ← mean]theorem conditional_variance_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < Spec.Paper.bigStepMeasure program Set.univ) (moment : MemLp id 2 (Spec.Paper.bigStepMeasure program)) : 0 < Spec.Paper.bigStepMeasure program.determinize Set.univ ∧ MemLp id 2 (Spec.Paper.bigStepMeasure program.determinize) ∧ variance id (returnedLaw program.determinize) ≤ variance id (returnedLaw program) := by have positive := positive.ne' have mass := output_mass_soundness program typed safe have targetPositive : Spec.Paper.bigStepMeasure program.determinize Set.univ ≠ 0 := by rwa [mass] obtain ⟨targetMoment, second, -⟩ := variance_soundness program typed safe moment obtain ⟨-, -, mean⟩ := finite_expectation_soundness program typed safe (moment.integrable one_le_two) refine ⟨pos_iff_ne_zero.mpr targetPositive, targetMoment, ?_⟩ unfold returnedLaw returnProbability rw [normalized_variance _ targetPositive targetMoment, normalized_variance _ positive moment, mass, ← mean] exact sub_le_sub_right (div_le_div_of_nonneg_right second ENNReal.toReal_nonneg) _theorem conditional_extended_expectation_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < Spec.Paper.bigStepMeasure program Set.univ) (defined : HasExpectation (Spec.Paper.bigStepMeasure program)) : 0 < Spec.Paper.bigStepMeasure program.determinize Set.univ ∧ HasExpectation (Spec.Paper.bigStepMeasure program.determinize) ∧ ((Spec.Paper.bigStepMeasure program.determinize Set.univ).toReal⁻¹ : EReal) * extendedExpectation (Spec.Paper.bigStepMeasure program.determinize) = ((Spec.Paper.bigStepMeasure program Set.univ).toReal⁻¹ : EReal) * extendedExpectation (Spec.Paper.bigStepMeasure program) := by have mass := output_mass_soundness program typed safe obtain ⟨targetDefined, expectation⟩ := extended_expectation_soundness program typed safe defined exact ⟨by rwa [mass], targetDefined, by rw [mass, ← expectation]⟩/-- Probability preservation: the target is domain-safe, the source returns or diverges, andboth return, and diverge, with the same probabilities. -/theorem probability_preservation (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) : DomainSafe program.determinize ∧ Spec.Paper.bigStepMeasure program Set.univ + divergenceProbability program = 1 ∧ Spec.Paper.bigStepMeasure program.determinize Set.univ = Spec.Paper.bigStepMeasure program Set.univ ∧ divergenceProbability program.determinize = divergenceProbability program := by have targetSafe := (Traces.meanOnTraces_determinize .E program typed safe).1 have source := return_or_diverge .E program typed safe have mass := output_mass_soundness program typed safe have target := return_or_diverge .E program.determinize (typed_determinize typed) targetSafe rw [mass, ← source] at target have finite : Spec.Paper.bigStepMeasure program Set.univ ≠ ∞ := ne_top_of_le_ne_top ENNReal.one_ne_top (source ▸ le_self_add) exact ⟨targetSafe, source, mass, (ENNReal.add_right_inj finite).mp target⟩end Papernamespace Tracestheorem conditional_variance_soundness (program : Expr) (typed : Typed [] program (.float .E)) (safe : DomainSafe program) (positive : 0 < Spec.Paper.bigStepMeasure program Set.univ) (moment : MemLp id 2 (Spec.Paper.bigStepMeasure program)) : Integrable (fun trace ↦ variance id ((Spec.Traces.traceAndOutputLaw program).condKernel trace)) ((Spec.Paper.bigStepMeasure program Set.univ)⁻¹ • Spec.Traces.traceLaw program) ∧ variance id (returnedLaw program) = variance id (returnedLaw program.determinize) + ∫ trace, variance id ((Spec.Traces.traceAndOutputLaw program).condKernel trace) ∂((Spec.Paper.bigStepMeasure program Set.univ)⁻¹ • Spec.Traces.traceLaw program) := by have positive := positive.ne' have mass := Paper.output_mass_soundness program typed safe have targetPositive : Spec.Paper.bigStepMeasure program.determinize Set.univ ≠ 0 := by rwa [mass] obtain ⟨targetMoment, -, -⟩ := Paper.variance_soundness program typed safe moment obtain ⟨-, -, mean⟩ := Paper.finite_expectation_soundness program typed safe (moment.integrable one_le_two) obtain ⟨integrable, decomposition⟩ := variance_soundness program typed safe moment refine ⟨integrable.smul_measure (ENNReal.inv_ne_top.mpr positive), ?_⟩ rw [variance_id_eq_moments moment, variance_id_eq_moments targetMoment, ← mean, measureReal_def, measureReal_def, mass] at decomposition unfold returnedLaw returnProbability rw [normalized_variance _ positive moment, normalized_variance _ targetPositive targetMoment, mass, ← mean, integral_smul_measure, ENNReal.toReal_inv, smul_eq_mul] have second : (∫ x : ℝ, x ^ 2 ∂Spec.Paper.bigStepMeasure program) = (∫ x : ℝ, x ^ 2 ∂Spec.Paper.bigStepMeasure program.determinize) + ∫ trace, variance id ((Spec.Traces.traceAndOutputLaw program).condKernel trace) ∂Spec.Traces.traceLaw program := by linarith rw [second] ring/-- Both marginals of the joint law have the joint law's total mass, the return probability. -/theorem total_masses (program : Expr) : Spec.Traces.traceLaw program Set.univ = Spec.Traces.traceAndOutputLaw program Set.univ ∧ Spec.Traces.traceAndOutputLaw program Set.univ = Spec.Paper.bigStepMeasure program Set.univ := by refine ⟨?_, ?_⟩ · rw [Spec.Traces.traceLaw, Measure.map_apply measurable_fst MeasurableSet.univ, Set.preimage_univ] · rw [← correspondence program, Measure.map_apply measurable_snd MeasurableSet.univ, Set.preimage_univ]/-- A nonnegative integral over the output law, taken first over the conditional law given thetrace and then over the trace law. -/theorem lintegral_along_traces (program : Expr) {f : ℝ → ℝ≥0∞} (measurable : Measurable f) : ∫⁻ value, f value ∂Spec.Paper.bigStepMeasure program = ∫⁻ trace, ∫⁻ value, f value ∂(Spec.Traces.traceAndOutputLaw program).condKernel trace ∂Spec.Traces.traceLaw program := by rw [← correspondence program, lintegral_map measurable measurable_snd] conv_lhs => rw [← (Spec.Traces.traceAndOutputLaw program).disintegrate (Spec.Traces.traceAndOutputLaw program).condKernel] rw [Measure.lintegral_compProd (f := fun output ↦ f output.2) (measurable.comp measurable_snd)] rfl/-- The expectation conditioned on returning, with the positive and negative parts of the outputeach integrated first over the conditional law given the trace and then over the trace law. -/theorem returned_expectation_along_traces (program : Expr) : returnedExpectation program = ((returnProbability program).toReal⁻¹ : EReal) * (((∫⁻ trace, posPartIntegral ((Spec.Traces.traceAndOutputLaw program).condKernel trace) ∂Spec.Traces.traceLaw program : ℝ≥0∞) : EReal) - ((∫⁻ trace, negPartIntegral ((Spec.Traces.traceAndOutputLaw program).condKernel trace) ∂Spec.Traces.traceLaw program : ℝ≥0∞) : EReal)) := by unfold returnedExpectation extendedExpectation posPartIntegral negPartIntegral rw [lintegral_along_traces program ENNReal.measurable_ofReal, lintegral_along_traces program (f := fun value ↦ ENNReal.ofReal (-value)) (ENNReal.measurable_ofReal.comp measurable_neg)]end Tracesend Determinize.Proof