Source lean/Determinize/Proof/Normalization.lean
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