import Determinize.Proof.Semantics.Ordinarynamespace Determinize.Proof.Paperopen MeasureTheory ProbabilityTheory Determinize.Spec.Paperopen SymbolicSoundness.TargetSafetyopen scoped ENNRealprivate noncomputable abbrev paperStepKernel := MeasurableActionFamily.stepKernel primitiveLawsprivate theorem returned_add_running_eq_step_mass (depth : Nat) (typed : Typed [] expression (.float affinity)) : Cumulative.outputMeasure depth expression Set.univ + runningProbabilityAt depth expression = nStepMeasure paperStepKernel depth expression Set.univ := by induction depth generalizing expression with | zero => by_cases value : expression.isValue = true · obtain ⟨r, rfl⟩ := Typing.typed_real_value typed value simp [Cumulative.outputMeasure, runningProbabilityAt, nStepMeasure, Expr.isValue] · cases expression <;> simp_all [Cumulative.outputMeasure, runningProbabilityAt, nStepMeasure, Expr.isValue] | succ depth ih => by_cases value : expression.isValue = true · rw [nStepMeasure_univ_eq_one_of_value paperStepKernel _ _ value] obtain ⟨r, rfl⟩ := Typing.typed_real_value typed value have output : ∀ n, Cumulative.outputMeasure n (.real r) = Measure.dirac r := by intro n induction n with | zero => rfl | succ n ih => simpa [Cumulative.outputMeasure, reduce] using ih simp [output, runningProbabilityAt, Expr.isValue] · simp only [runningProbabilityAt, value, Bool.false_eq_true, ↓reduceIte] have actionTyped := Typing.reduce_typed_closed typed cases reduction : reduce expression with | stuck => rw [nStepMeasure_succ_eq_firstStep, paperStepKernel.kernel_eq_stepMeasure] simp [stepMeasure, reduction, Action.measure, Cumulative.outputMeasure] | next next => rw [reduction] at actionTyped cases actionTyped with | next nextTyped => rw [nStepMeasure_succ_next_univ paperStepKernel _ _ _ reduction] simpa [Cumulative.outputMeasure, reduction] using ih nextTyped | sample site fiber continuation => rw [reduction] at actionTyped cases actionTyped with | sample continuationTyped => have hm : Measurable (fun r ↦ Cumulative.outputMeasure depth (continuation r) Set.univ) := (Measure.measurable_coe MeasurableSet.univ).comp (measurable_sample_cumulative depth expression site fiber continuation reduction) change Cumulative.outputMeasure (depth + 1) expression Set.univ + (∫⁻ r, runningProbabilityAt depth (continuation r) ∂fiber) = _ rw [Cumulative.outputMeasure, reduction, Measure.bind_apply MeasurableSet.univ (measurable_sample_cumulative depth expression site fiber continuation reduction).aemeasurable, ← lintegral_add_left hm, nStepMeasure_succ_sample_univ paperStepKernel _ _ _ _ reduction] exact lintegral_congr fun r ↦ ih (continuationTyped r)private theorem total_antitone (expression : Expr) : Antitone (fun n ↦ nStepMeasure paperStepKernel n expression Set.univ) := by apply antitone_nat_of_succ_le intro n rw [nStepMeasure, Measure.bind_apply MeasurableSet.univ paperStepKernel.kernel.aemeasurable] calc (∫⁻ current, paperStepKernel.kernel current Set.univ ∂nStepMeasure paperStepKernel n expression) ≤ ∫⁻ _, 1 ∂nStepMeasure paperStepKernel n expression := lintegral_mono fun current ↦ paperStepKernel.mass_le_one current _ = _ := lintegral_one/-- At finite depth, returned and still-running probability exhaust all mass. -/theorem returned_add_running (depth : Nat) (typed : Typed [] expression (.float affinity)) (safe : DomainSafeAt depth expression) : Cumulative.outputMeasure depth expression Set.univ + runningProbabilityAt depth expression = 1 := (returned_add_running_eq_step_mass depth typed).trans ((domainSafeAt_iff_nStepMeasure_univ_eq_one paperStepKernel depth expression typed).mp safe)private theorem output_mass_eq_iSup_cumulative (expression : Expr) : Determinize.Spec.Paper.bigStepMeasure expression Set.univ = ⨆ depth, Cumulative.outputMeasure depth expression Set.univ := by rw [Determinize.Spec.Paper.bigStepMeasure, Measure.sum_apply _ MeasurableSet.univ] simp_rw [cumulativeOutputMeasure_eq_sum, Measure.finsetSum_apply] exact ENNReal.tsum_eq_iSup_nat' (Filter.tendsto_add_atTop_nat 1)private theorem running_eq_sub (depth : Nat) (typed : Typed [] expression (.float affinity)) (safe : DomainSafe expression) : runningProbabilityAt depth expression = 1 - Cumulative.outputMeasure depth expression Set.univ := ENNReal.eq_sub_of_add_eq' (by simp) (by simpa only [add_comm] using returned_add_running depth typed (safe depth))theorem runningProbabilityAt_antitone (typed : Typed [] expression (.float affinity)) (safe : DomainSafe expression) : Antitone (fun depth ↦ runningProbabilityAt depth expression) := by intro n m h change runningProbabilityAt m expression ≤ runningProbabilityAt n expression rw [running_eq_sub m typed safe, running_eq_sub n typed safe] exact tsub_le_tsub_left ((direct_cumulative_mono expression h) Set.univ) 1theorem return_or_diverge (affinity : Affinity) (expression : Expr) (typed : Typed [] expression (.float affinity)) (safe : DomainSafe expression) : Determinize.Spec.Paper.bigStepMeasure expression Set.univ + divergenceProbability expression = 1 := by have bounded : Determinize.Spec.Paper.bigStepMeasure expression Set.univ ≤ 1 := by rw [output_mass_eq_iSup_cumulative] apply iSup_le intro depth calc Cumulative.outputMeasure depth expression Set.univ ≤ Cumulative.outputMeasure depth expression Set.univ + runningProbabilityAt depth expression := le_self_add _ = 1 := returned_add_running depth typed (safe depth) rw [divergenceProbability] simp_rw [running_eq_sub _ typed safe] rw [← ENNReal.sub_iSup (by simp), ← output_mass_eq_iSup_cumulative] exact add_tsub_cancel_of_le boundedprivate theorem return_diverge_le_total (typed : Typed [] expression (.float affinity)) (n : Nat) : Determinize.Spec.Paper.bigStepMeasure expression Set.univ + divergenceProbability expression ≤ nStepMeasure paperStepKernel n expression Set.univ := by rw [output_mass_eq_iSup_cumulative, ENNReal.iSup_add] apply iSup_le intro k calc Cumulative.outputMeasure k expression Set.univ + divergenceProbability expression ≤ Cumulative.outputMeasure (max k n) expression Set.univ + runningProbabilityAt (max k n) expression := add_le_add ((direct_cumulative_mono expression (Nat.le_max_left k n)) Set.univ) (iInf_le _ _) _ = _ := returned_add_running_eq_step_mass _ typed _ ≤ _ := total_antitone expression (Nat.le_max_right k n)theorem domainSafe_iff_return_or_diverge (typed : Typed [] expression (.float affinity)) : DomainSafe expression ↔ Determinize.Spec.Paper.bigStepMeasure expression Set.univ + divergenceProbability expression = 1 := by constructor · exact return_or_diverge affinity expression typed · intro conserved n apply (domainSafeAt_iff_nStepMeasure_univ_eq_one paperStepKernel n expression typed).mpr apply le_antisymm (nStepMeasure_mass_le_one paperStepKernel n expression) rw [← conserved] exact return_diverge_le_total typed nend Determinize.Proof.Paper