import Determinize.Proof.RewardModel.Lawsimport Determinize.Proof.RewardModel.FiniteIntegrabilityimport Determinize.Finite.Reward.Solveimport Determinize.Spec.RewardModel.Resultsnamespace Determinize.Proof.RewardModelopen MeasureTheory Spec.RewardModel FiniteModelnoncomputable def momentAt (model : Model) (moment : Moment) (i : Fin model.size) : ℝ := ∫ x, moment.real x ∂model.outputAt iprivate theorem measurable_moment_real (moment : Moment) : Measurable moment.real := by cases moment <;> simp only [Moment.real] <;> fun_propprivate theorem integrable_moment_shift (μ : Measure ℝ) [IsFiniteMeasure μ] (first : Integrable (fun x : ℝ ↦ x) μ) (second : Integrable (fun x : ℝ ↦ x ^ 2) μ) (r : Rat) (moment : Moment) : Integrable moment.real (shift r μ) := by apply (integrable_map_measure (measurable_moment_real moment).aestronglyMeasurable (show AEMeasurable (fun x : ℝ ↦ x + (r : ℝ)) μ from (measurable_id.add_const _).aemeasurable)).mpr cases moment with | mass => exact integrable_const 1 | first => exact first.add (integrable_const (r : ℝ)) | second => have poly : (fun x : ℝ ↦ (x + (r : ℝ)) ^ 2) = fun x ↦ (x ^ 2 + (2 * (r : ℝ)) * x) + (r : ℝ) ^ 2 := by funext x ring change Integrable (fun x : ℝ ↦ (x + (r : ℝ)) ^ 2) μ rw [poly] exact (second.add (first.const_mul _)).add (integrable_const _)private theorem integral_shift_moment (μ : Measure ℝ) [IsFiniteMeasure μ] (first : Integrable (fun x : ℝ ↦ x) μ) (second : Integrable (fun x : ℝ ↦ x ^ 2) μ) (r : Rat) (moment : Moment) : (∫ x, moment.real x ∂shift r μ) = match moment with | .mass => ∫ x, Moment.mass.real x ∂μ | .first => (∫ x, Moment.first.real x ∂μ) + (r : ℝ) * (∫ x, Moment.mass.real x ∂μ) | .second => (∫ x, Moment.second.real x ∂μ) + 2 * (r : ℝ) * (∫ x, Moment.first.real x ∂μ) + (r : ℝ) ^ 2 * (∫ x, Moment.mass.real x ∂μ) := by rw [shift, integral_map (show AEMeasurable (fun x : ℝ ↦ x + (r : ℝ)) μ from (measurable_id.add_const _).aemeasurable) (measurable_moment_real moment).aestronglyMeasurable] cases moment with | mass => rfl | first => simp [Moment.real, integral_add first (integrable_const (r : ℝ)), integral_const, mul_comm] | second => have poly : (fun x : ℝ ↦ (x + (r : ℝ)) ^ 2) = fun x ↦ (x ^ 2 + (2 * (r : ℝ)) * x) + (r : ℝ) ^ 2 := by funext x ring simp only [Moment.real] have linear : Integrable (fun x : ℝ ↦ 2 * (r : ℝ) * x) μ := first.const_mul _ have quadratic : Integrable (fun x : ℝ ↦ x ^ 2 + 2 * (r : ℝ) * x) μ := second.add linear rw [poly, integral_add quadratic (integrable_const ((r : ℝ) ^ 2)), integral_add second linear, integral_const_mul] simp [integral_const, mul_comm]theorem momentAt_equation (model : Model) (moment : Moment) (i : Fin model.size) : momentAt model moment i = match model.kind i with | .returned b => moment.real (b : ℝ) | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ (e.probability : ℝ) * match moment with | .mass => momentAt model .mass e.target | .first => momentAt model .first e.target + (e.reward : ℝ) * momentAt model .mass e.target | .second => momentAt model .second e.target + 2 * (e.reward : ℝ) * momentAt model .first e.target + (e.reward : ℝ) ^ 2 * momentAt model .mass e.target).sum := by unfold momentAt rw [outputAt_equation] cases kind : model.kind i with | returned b => simp | rejected => simp | transient => have integrable (e : Edge model.size) : Integrable moment.real (ENNReal.ofReal (e.probability : ℝ) • shift e.reward (model.outputAt e.target)) := (integrable_moment_shift (model.outputAt e.target) (integrableMoments model e.target).1 (integrableMoments model e.target).2 e.reward moment).smul_measure (by simp) rw [integral_list_sum (model.edges i) (fun e ↦ ENNReal.ofReal (e.probability : ℝ) • shift e.reward (model.outputAt e.target)) moment.real (fun e _ ↦ integrable e)] apply congrArg List.sum apply List.map_congr_left intro e he rw [integral_smul_measure, ENNReal.toReal_ofReal (by exact_mod_cast model.nonnegative i e he), integral_shift_moment _ (integrableMoments model e.target).1 (integrableMoments model e.target).2] rfltheorem eq_of_linear_equations (model : Spec.FiniteModel.Model) (paths : Paths model) (valid : paths.Valid model) (rhs v w : Fin model.size → ℝ) (hv : ∀ i, v i = rhs i + if model.kind i = .transient then ∑ j, (model.transition i j : ℝ) * v j else 0) (hw : ∀ i, w i = rhs i + if model.kind i = .transient then ∑ j, (model.transition i j : ℝ) * w j else 0) : ∀ i, v i = w i := by have zero := paths_unique model paths valid (fun i ↦ v i - w i) (by intro i rw [hv i, hw i] split_ifs · simp only [mul_sub, Finset.sum_sub_distrib] ring · simp) intro i exact sub_eq_zero.mp (zero i)private theorem eq_of_edge_equations (model : Model) (paths : Paths model.control) (valid : paths.Valid model.control) (terminal : Rat → ℝ) (extra : Edge model.size → ℝ) (v w : Fin model.size → ℝ) (hv : ∀ i, v i = match model.kind i with | .returned b => terminal b | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ (e.probability : ℝ) * (v e.target + extra e)).sum) (hw : ∀ i, w i = match model.kind i with | .returned b => terminal b | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ (e.probability : ℝ) * (w e.target + extra e)).sum) : ∀ i, v i = w i := by let rhs := fun (i : Fin model.size) ↦ match model.kind i with | .returned b => terminal b | .rejected => 0 | .transient => ((model.edges i).map fun (e : Edge model.size) ↦ (e.probability : ℝ) * extra e).sum have convert (u : Fin model.size → ℝ) (eqs : ∀ i, u i = match model.kind i with | .returned b => terminal b | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ (e.probability : ℝ) * (u e.target + extra e)).sum) : ∀ i, u i = rhs i + if model.control.kind i = .transient then ∑ j, (model.control.transition i j : ℝ) * u j else 0 := by intro i rw [eqs i] cases kind : model.kind i <;> simp [rhs, Model.control, kind, mul_add, List.sum_map_add, sum_controlWeight_mul_real, add_comm] exact eq_of_linear_equations model.control paths valid rhs v w (convert v hv) (convert w hw)private theorem values_real_eq (model : Model) (values : Moment → Fin model.size → Rat) (valid : MomentEquations model values) (moment : Moment) (i : Fin model.size) : (values moment i : ℝ) = match model.kind i with | .returned b => moment.real (b : ℝ) | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ (e.probability : ℝ) * match moment with | .mass => (values .mass e.target : ℝ) | .first => (values .first e.target : ℝ) + (e.reward : ℝ) * (values .mass e.target : ℝ) | .second => (values .second e.target : ℝ) + 2 * (e.reward : ℝ) * (values .first e.target : ℝ) + (e.reward : ℝ) ^ 2 * (values .mass e.target : ℝ)).sum := by have h := congrArg (fun q : Rat ↦ (q : ℝ)) (valid moment i) cases kind : model.kind i <;> cases moment <;> simpa [kind, translatedValue, Moment.rational, Moment.real, Rat.cast_list_sum, List.map_map, Function.comp_def] using htheorem momentAt_eq_values (model : Model) (paths : Paths model.control) (pathsValid : paths.Valid model.control) (values : Moment → Fin model.size → Rat) (valid : MomentEquations model values) : ∀ moment i, momentAt model moment i = (values moment i : ℝ) := by have mass : ∀ i, momentAt model .mass i = (values .mass i : ℝ) := by apply eq_of_edge_equations model paths pathsValid (fun _ ↦ 1) (fun _ ↦ 0) · intro i have h := momentAt_equation model .mass i cases kind : model.kind i <;> simpa [kind, Moment.real] using h · intro i have h := values_real_eq model values valid .mass i cases kind : model.kind i <;> simpa [kind, Moment.real] using h have first : ∀ i, momentAt model .first i = (values .first i : ℝ) := by apply eq_of_edge_equations model paths pathsValid (fun b ↦ (b : ℝ)) (fun e ↦ (e.reward : ℝ) * (values .mass e.target : ℝ)) · intro i have h := momentAt_equation model .first i cases kind : model.kind i <;> simpa [kind, Moment.real, mass] using h · intro i have h := values_real_eq model values valid .first i cases kind : model.kind i <;> simpa [kind, Moment.real] using h have second : ∀ i, momentAt model .second i = (values .second i : ℝ) := by apply eq_of_edge_equations model paths pathsValid (fun b ↦ (b : ℝ) ^ 2) (fun e ↦ 2 * (e.reward : ℝ) * (values .first e.target : ℝ) + (e.reward : ℝ) ^ 2 * (values .mass e.target : ℝ)) · intro i have h := momentAt_equation model .second i cases kind : model.kind i <;> simpa [kind, Moment.real, mass, first, add_assoc] using h · intro i have h := values_real_eq model values valid .second i cases kind : model.kind i <;> simpa [kind, Moment.real, add_assoc] using h intro moment cases moment · exact mass · exact first · exact secondtheorem integrable_outputMeasure (model : Model) : Integrable (fun x : ℝ ↦ x) model.outputMeasure ∧ Integrable (fun x : ℝ ↦ x ^ 2) model.outputMeasure := integrableMoments model model.initialtheorem solution_statistics (model : Model) (solution : Determinize.Finite.Reward.Solution model) : solution.statistics.Matches model.outputMeasure := by let values := fun (moment : Moment) ↦ match moment with | .mass => solution.mass | .first => solution.first | .second => solution.second have correct := momentAt_eq_values (cut model solution.boundary.dead) solution.paths solution.paths_valid values solution.moments_valid have moments (moment : Moment) : (∫ x, moment.real x ∂model.outputMeasure) = (values moment model.initial : ℝ) := by have h := correct moment model.initial unfold momentAt at h rwa [cut_outputAt model solution.boundary.dead solution.boundary.closed] at h refine ⟨inferInstanceAs (IsFiniteMeasure (model.outputAt model.initial)), (integrable_outputMeasure model).2, ?_, ?_, ?_⟩ · simpa [Moment.real, Determinize.Finite.Reward.Solution.statistics, values, integral_const] using moments .mass · exact moments .first · exact moments .secondtheorem solution_result (model : Model) (program : Spec.Paper.Expr) (matching : model.Matches program) (solution : Determinize.Finite.Reward.Solution model) : ResultMatches model program solution.statistics := ⟨matching, solution_statistics model solution⟩theorem solution_conditional_variance (model : Model) (solution : Determinize.Finite.Reward.Solution model) (positive : 0 < solution.statistics.returnMass) : ProbabilityTheory.variance id ((model.outputMeasure Set.univ)⁻¹ • model.outputMeasure) = ((solution.statistics.secondMoment / solution.statistics.returnMass - (solution.statistics.firstMoment / solution.statistics.returnMass) ^ 2 : Rat) : ℝ) := statistics_conditional_variance model.outputMeasure solution.statistics (solution_statistics model solution) positivetheorem solution_termination (model : Model) (solution : Determinize.Finite.Reward.Solution model) : (⟨solution.mass model.initial, solution.rejection model.initial, 1 - solution.mass model.initial - solution.rejection model.initial⟩ : Spec.FiniteModel.TerminationStatistics).Matches model.control := by have output : model.control.outputMeasure.real Set.univ = (solution.mass model.initial : ℝ) := by have query := query_sound (FiniteModel.cut model.control solution.boundary.dead) (fun _ ↦ 1) (fun _ ↦ 1) (fun _ ↦ by simp) solution.mass solution.mass_valid ⟨solution.paths.rank, solution.paths.next⟩ (by intro state transient apply solution.paths_valid state cases h : model.kind state <;> cases d : solution.boundary.dead state <;> simp_all) rw [FiniteModel.cut_outputMeasure _ _ solution.boundary.closed] at query simpa [integral_const] using query have rejection : model.control.rejectionProbability.toReal = (solution.rejection model.initial : ℝ) := by have query := query_sound (FiniteModel.cut model.control.rejectionModel solution.boundary.dead) (fun _ ↦ 1) (fun _ ↦ 1) (fun _ ↦ by simp) solution.rejection solution.rejection_valid ⟨solution.paths.rank, solution.paths.next⟩ (by intro state transient apply solution.paths_valid state cases h : model.kind state <;> cases d : solution.boundary.dead state <;> simp_all) rw [FiniteModel.cut_outputMeasure _ _ (rejection_closed model.control _ solution.boundary.closed)] at query simpa [integral_const, Spec.FiniteModel.Model.rejectionProbability, measureReal_def] using query refine ⟨output, rejection, ?_⟩ have balance := mass_balance model.control have finiteReturn : model.control.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.control.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.control.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.control.outputMeasure Set.univ).toReal = _ at output rw [output, rejection] at realBalance simp only [Rat.cast_sub, Rat.cast_one] linarithend Determinize.Proof.RewardModel