Source lean/Determinize/Proof/FiniteModel/Termination.lean
import Determinize.Spec.FiniteModel.Terminationimport Determinize.Proof.FiniteModel.Statisticsnamespace Determinize.Proof.FiniteModelopen Spec.FiniteModel MeasureTheorytheorem survival_nonnegative (model : Model) (n : Nat) (state : Fin model.size) :    0 ≤ model.survivalWithin n state := by  induction n generalizing state with  | zero => simp [Model.survivalWithin]; split <;> norm_num  | succ n ih =>    simp only [Model.survivalWithin]    split    · exact Finset.sum_nonneg fun next _ ↦ mul_nonneg (model.nonnegative state next) (ih next)    · exact le_rfltheorem within_mass_balance (model : Model) (n : Nat) (state : Fin model.size) :    model.outputWithin n state Set.univ + model.rejectionModel.outputWithin n state Set.univ +      ENNReal.ofReal (model.survivalWithin n state : ℝ) = 1 := by  induction n generalizing state with  | zero => cases h : model.kind state <;> simp [Model.outputWithin, Model.survivalWithin, h]  | succ n ih =>    cases h : model.kind state with    | returned r => simp [Model.outputWithin, Model.survivalWithin, h]    | rejected => simp [Model.outputWithin, Model.survivalWithin, h]    | transient =>      simp only [Model.outputWithin, Model.survivalWithin, h, ↓reduceIte, Rat.cast_sum,        Rat.cast_mul, Measure.finsetSum_apply, Measure.smul_apply, smul_eq_mul]      change        (∑ next, ENNReal.ofReal (model.transition state next : ℝ) *          model.outputWithin n next Set.univ) +        (∑ next, ENNReal.ofReal (model.transition state next : ℝ) *          model.rejectionModel.outputWithin n next Set.univ) +        ENNReal.ofReal          (∑ next, (model.transition state next : ℝ) * (model.survivalWithin n next : ℝ)) = 1      rw [ENNReal.ofReal_sum_of_nonneg (fun next _ ↦ mul_nonneg        (by exact_mod_cast model.nonnegative state next)        (by exact_mod_cast survival_nonnegative model n next))]      have cast_mul (next : Fin model.size) (r : ℝ) :          ENNReal.ofReal ((model.transition state next : ℝ) * r) =            ENNReal.ofReal (model.transition state next : ℝ) * ENNReal.ofReal r :=        ENNReal.ofReal_mul (by exact_mod_cast model.nonnegative state next)      simp_rw [cast_mul]      rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]      simp_rw [← mul_add, ih, mul_one]      rw [← ENNReal.ofReal_sum_of_nonneg        (fun next _ ↦ by exact_mod_cast model.nonnegative state next)]      have total : ∑ next, (model.transition state next : ℝ) = 1 := by        exact_mod_cast model.normalized state      simp [total]theorem mass_balance (model : Model) :    model.outputMeasure Set.univ + model.rejectionProbability + model.divergenceProbability =      1 := by  have complements (n : Nat) :      model.outputWithin n model.initial Set.univ +        model.rejectionModel.outputWithin n model.initial Set.univ =        1 - ENNReal.ofReal (model.survivalWithin n model.initial : ℝ) :=    ENNReal.eq_sub_of_add_eq (by simp) (within_mass_balance model n model.initial)  have sumMass : model.outputMeasure Set.univ + model.rejectionProbability =      1 - model.divergenceProbability := by    rw [Model.outputMeasure, Model.rejectionProbability, Model.outputMeasure,      monotone_measure_iSup_apply _ (outputWithin_mono model _) _ MeasurableSet.univ,      monotone_measure_iSup_apply _ (outputWithin_mono model.rejectionModel _) _ MeasurableSet.univ,      ENNReal.iSup_add_iSup_of_monotone        (fun a b h ↦ outputWithin_mono model model.initial h Set.univ)        (fun a b h ↦ outputWithin_mono model.rejectionModel model.initial h Set.univ)]    simp only [complements, Model.divergenceProbability, ENNReal.sub_iInf]  rw [sumMass]  apply tsub_add_cancel_of_le  apply (iInf_le (fun n ↦ ENNReal.ofReal (model.survivalWithin n model.initial : ℝ)) 0).trans  simp only [Model.survivalWithin]  split <;> norm_numtheorem rejection_closed (model : Model) (dead : Fin model.size → Bool)    (closed : ClosedDivergence model dead) : ClosedDivergence model.rejectionModel dead := by  intro state h  refine ⟨?_, (closed state h).2⟩  simp [(closed state h).1]abbrev rejectionQuery (model : Model) (dead : Fin model.size → Bool) :=  rewards (cut model.rejectionModel dead) (fun _ ↦ 1)structure TerminationCertificate (model : Model) where  output : MomentCertificate model  rejection : Fin model.size → Ratdef TerminationCertificate.Valid (model : Model) (certificate : TerminationCertificate model) :    Prop :=  certificate.output.Valid model ∧    ValueEquations (rejectionQuery model certificate.output.dead) certificate.rejectioninstance (model : Model) (certificate : TerminationCertificate model) :    Decidable (certificate.Valid model) :=  inferInstanceAs (Decidable (_ ∧ _))def TerminationCertificate.statistics (model : Model) (certificate : TerminationCertificate model) :    TerminationStatistics :=  let p := certificate.output.values .mass model.initial  let r := certificate.rejection model.initial  ⟨p, r, 1 - p - r⟩private def EquationAt (model : Model) (values : Fin model.size → Rat)    (state : Fin model.size) : Prop :=  values state = match model.kind state with    | .returned r => r | .rejected => 0    | .transient => ∑ next, model.transition state next * values nextprivate instance (model : Model) (values : Fin model.size → Rat) (state : Fin model.size) :    Decidable (EquationAt model values state) := inferInstanceAs (Decidable (_ = _))def TerminationCertificate.StateValid (model : Model) (certificate : TerminationCertificate model)    (state : Fin model.size) : Prop :=  (certificate.output.dead state = true → model.kind state = .transient ∧    ∀ next, 0 < model.transition state next → certificate.output.dead next = true) ∧  ((cut model certificate.output.dead).kind state = .transient →    0 < model.transition state (certificate.output.next state) ∧      certificate.output.rank (certificate.output.next state) < certificate.output.rank state) ∧  (∀ moment, EquationAt (certificate.output.model model moment)    (certificate.output.values moment) state) ∧    EquationAt (rejectionQuery model certificate.output.dead) certificate.rejection stateinstance (model : Model) (certificate : TerminationCertificate model) (state : Fin model.size) :    Decidable (certificate.StateValid model state) := inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _))theorem terminationStates_valid (model : Model) (certificate : TerminationCertificate model)    (states : ∀ state, certificate.StateValid model state) : certificate.Valid model := by  exact ⟨⟨fun state ↦ (states state).1, fun state ↦ (states state).2.1,    fun moment state ↦ (states state).2.2.1 moment⟩, fun state ↦ (states state).2.2.2⟩theorem terminationCertificate_sound (model : Model) (certificate : TerminationCertificate model)    (valid : certificate.Valid model) : (certificate.statistics model).Matches model := by  have output := (momentCertificate_sound model certificate.output valid.1).mass  have rejection :      model.rejectionProbability.toReal = (certificate.rejection model.initial : ℝ) := by    have query := query_sound (cut model.rejectionModel certificate.output.dead) (fun _ ↦ 1)      (fun _ ↦ 1) (fun _ ↦ by simp) certificate.rejection valid.2      ⟨certificate.output.rank, certificate.output.next⟩ (by        intro state transient        apply valid.1.2.1 state        cases h : model.kind state <;> cases d : certificate.output.dead state <;> simp_all)    rw [cut_outputMeasure _ _ (rejection_closed model _ valid.1.1)] at query    simpa [integral_const, Model.rejectionProbability, measureReal_def] using query  refine ⟨output, rejection, ?_⟩  have balance := mass_balance model  have finiteReturn : model.outputMeasure Set.univ ≠ ⊤ := by    exact ne_top_of_le_ne_top (by simp)      ((le_add_right le_rfl).trans ((le_add_right le_rfl).trans_eq balance))  have finiteReject : model.rejectionProbability ≠ ⊤ := by    exact ne_top_of_le_ne_top (by simp)      ((le_add_left le_rfl).trans ((le_add_right le_rfl).trans_eq balance))  have finiteDiverge : model.divergenceProbability ≠ ⊤ := by    exact ne_top_of_le_ne_top (by simp) ((le_add_left le_rfl).trans_eq balance)  have realBalance := congrArg ENNReal.toReal balance  rw [ENNReal.toReal_add (ENNReal.add_ne_top.mpr ⟨finiteReturn, finiteReject⟩) finiteDiverge,    ENNReal.toReal_add finiteReturn finiteReject, ENNReal.toReal_one] at realBalance  change (model.outputMeasure Set.univ).toReal = _ at output  rw [output, rejection] at realBalance  simp only [TerminationCertificate.statistics, Rat.cast_sub, Rat.cast_one]  simp only [MomentCertificate.statistics] at realBalance  linarithend Determinize.Proof.FiniteModel