import Determinize.Proof.FiniteModel.Modelimport Determinize.Spec.FiniteModel.Certificatesimport Mathlib.Basic.ENNReal.BigOperatorsnamespace Determinize.Proof.FiniteModelopen Spec.FiniteModel MeasureTheorytheorem monotone_measure_iSup_apply (μ : Nat → Measure ℝ) (mono : Monotone μ) (s : Set ℝ) (hs : MeasurableSet s) : (⨆ n, μ n) s = ⨆ n, μ n s := by let ν : Measure ℝ := Measure.ofMeasurable (fun s _ ↦ ⨆ n, μ n s) (by simp) (by intro f hf hd simp_rw [measure_iUnion hd hf, ENNReal.tsum_eq_iSup_sum] rw [iSup_comm] congr 1 funext t exact (ENNReal.finsetSum_iSup_of_monotone (fun i a b hab ↦ mono hab (f i))).symm) have ν_apply (t : Set ℝ) (ht : MeasurableSet t) : ν t = ⨆ n, μ n t := Measure.ofMeasurable_apply t ht have eq : (⨆ n, μ n) = ν := by apply le_antisymm · apply iSup_le intro n apply Measure.le_iff.mpr intro t ht rw [ν_apply t ht] exact le_iSup (fun n ↦ μ n t) n · apply Measure.le_iff.mpr intro t ht rw [ν_apply t ht] exact iSup_le (fun n ↦ (le_iSup μ n) t) rw [eq, ν_apply s hs]private noncomputable def terminalBound (model : Model) : Measure ℝ := ∑ state, match model.kind state with | .returned reward => Measure.dirac (reward : ℝ) | _ => 0private theorem integrable_terminalBound (model : Model) (f : ℝ → ℝ) : Integrable f (terminalBound model) := by apply integrable_finsetSum_measure.mpr intro state _ cases model.kind state <;> simp only [integrable_zero_measure] exact integrable_dirac (by simp)private theorem transition_mass (model : Model) (state : Fin model.size) : ∑ next, ENNReal.ofReal (model.transition state next : ℝ) = 1 := by rw [← ENNReal.ofReal_sum_of_nonneg (fun i _ ↦ by exact_mod_cast model.nonnegative state i)] have h : ∑ i, (model.transition state i : ℝ) = 1 := by exact_mod_cast model.normalized state simp [h]private theorem outputWithin_bound (model : Model) (n : Nat) (state : Fin model.size) : model.outputWithin n state ≤ terminalBound model := by have terminal (state : Fin model.size) (q : Rat) (h : model.kind state = .returned q) : Measure.dirac (q : ℝ) ≤ terminalBound model := by have := Finset.single_le_sum (fun i (_ : i ∈ Finset.univ) ↦ Measure.zero_le (match model.kind i with | .returned r => Measure.dirac (r : ℝ) | _ => 0)) (Finset.mem_univ state) simpa [terminalBound, h] using this induction n generalizing state with | zero => cases h : model.kind state <;> simp only [Model.outputWithin, h] · exact Measure.zero_le _ · exact terminal state _ h · exact Measure.zero_le _ | succ n ih => cases h : model.kind state with | returned q => simpa [Model.outputWithin, h] using terminal state q h | rejected => simpa [Model.outputWithin, h] using Measure.zero_le (terminalBound model) | transient => simp only [Model.outputWithin, h] calc _ ≤ ∑ next, ENNReal.ofReal (model.transition state next : ℝ) • terminalBound model := Finset.sum_le_sum (fun next _ ↦ smul_le_smul_left _ (ih next)) _ = terminalBound model := by rw [← Finset.sum_smul, transition_mass, one_smul]noncomputable def outputAt (model : Model) (state : Fin model.size) : Measure ℝ := ⨆ n, model.outputWithin n statetheorem integrable_outputAt (model : Model) (state : Fin model.size) (f : ℝ → ℝ := id) : Integrable f (outputAt model state) := (integrable_terminalBound model f).mono_measure (iSup_le (fun n ↦ outputWithin_bound model n state))/-- Finite terminal rewards bound the output law, including for nonabsorbing models. -/theorem integrable_outputMeasure (model : Model) : Integrable id model.outputMeasure := integrable_outputAt model model.initialprivate theorem outputAt_transient (model : Model) (state : Fin model.size) (h : model.kind state = .transient) : outputAt model state = ∑ next, ENNReal.ofReal (model.transition state next : ℝ) • outputAt model next := by have shift : outputAt model state = ⨆ n, model.outputWithin (n + 1) state := by apply le_antisymm · exact iSup_le (fun n ↦ (outputWithin_mono model state (Nat.le_succ n)).trans (le_iSup (fun n ↦ model.outputWithin (n + 1) state) n)) · exact iSup_le (fun n ↦ le_iSup (fun n ↦ model.outputWithin n state) (n + 1)) ext s hs rw [shift, monotone_measure_iSup_apply _ (by intro a b hab; exact outputWithin_mono model state (Nat.add_le_add_right hab 1)) s hs] simp only [Model.outputWithin, h, Measure.finsetSum_apply, Measure.smul_apply, smul_eq_mul] simp_rw [outputAt, monotone_measure_iSup_apply _ (outputWithin_mono model _) s hs, ENNReal.mul_iSup] symm apply ENNReal.finsetSum_iSup_of_monotone intro i a b hab exact mul_le_mul_right (outputWithin_mono model i hab s) _theorem outputAt_equations (model : Model) (state : Fin model.size) (f : ℝ → ℝ := id) : (∫ value : ℝ, f value ∂outputAt model state) = match model.kind state with | .returned reward => f (reward : ℝ) | .rejected => 0 | .transient => ∑ next, (model.transition state next : ℝ) * (∫ value : ℝ, f value ∂outputAt model next) := by cases h : model.kind state with | returned reward => simp [outputAt, returned_outputWithin model state reward h] | rejected => simp [outputAt, rejected_outputWithin model state h] | transient => rw [outputAt_transient model state h] rw [integral_finsetSum_measure (f := f) (s := Finset.univ) (μ := fun next ↦ ENNReal.ofReal (model.transition state next : ℝ) • outputAt model next) (fun next _ ↦ (integrable_outputAt model next f).smul_measure (by simp))] simp only [integral_smul_measure, smul_eq_mul] apply Finset.sum_congr rfl intro next _ rw [ENNReal.toReal_ofReal (by exact_mod_cast model.nonnegative state next)]end Determinize.Proof.FiniteModel