import Determinize.Spec.Traces.Semanticsimport Determinize.Proof.Primitives.Massimport Determinize.Proof.Symbolic.TraceLawsimport Determinize.Proof.Traces.CompactTracenamespace Determinize.Proof.Tracesopen MeasureTheory Determinize.Spec.Paper Determinize.Spec.Traces Determinize.Proof.Paperopen StepTraces (retain measurable_retain mapTraceOutput measurable_mapTraceOutput)open scoped ENNReal/-! ### The joint law as an erased detailed lawAt each depth, the joint law is the detailed law `StepTraces.exactMeasure` with each tracereduced to its general-affinity draws (`exact_eq_detailed`). -/abbrev eraseOutput : StepTraces.Output → Output := mapTraceOutput retaintheorem measurable_eraseOutput : Measurable eraseOutput := measurable_mapTraceOutput retain measurable_retaintheorem measurable_record (site : DistributionAction × Op) (value : ℝ) : Measurable (record site value) := by rcases site with ⟨kind, op⟩ cases kind with | sample affinity => cases affinity with | E => exact measurable_id | G => exact (StepTraces.measurable_draw_cons.comp (measurable_const.prodMk measurable_fst)).prodMk measurable_snd | mean => exact measurable_idtheorem exact_eq_detailed (depth : Nat) (e : Expr) : traceAndOutputLawAt depth e = (StepTraces.exactMeasure depth e).map eraseOutput := by induction depth generalizing e with | zero => cases e <;> try simp only [traceAndOutputLawAt, StepTraces.exactMeasure, Measure.map_zero] case real r => simp [Measure.map_dirac' measurable_eraseOutput, eraseOutput, mapTraceOutput, retain] | succ depth ih => by_cases value : e.isValue = true · simp [traceAndOutputLawAt, StepTraces.exactMeasure, value] · rw [traceAndOutputLawAt, StepTraces.exactMeasure, ite_eq_right value, ite_eq_right value] cases reduction : reduce e with | stuck => simp | next next => simp only [ih] rw [Measure.map_map measurable_eraseOutput (show Measurable (StepTraces.prepend none) from StepTraces.measurable_prepend.comp (measurable_const.prodMk measurable_id))] congr 1 | sample site fiber cont => have hc := (MeasurableActionFamily.stepKernel primitiveLaws).sample_continuation_measurable e fiber cont reduction have hm := (StepTraces.successorKernel (StepTraces.exactKernel depth)).kernel.measurable.comp ((StepTraces.measurable_generationEvent site).prodMk hc) simp only [Function.comp_def] at hm simp_rw [StepTraces.successorKernel_apply, StepTraces.exactKernel_apply] at hm rw [StepTraces.map_bind_fun _ _ hm _ measurable_eraseOutput] apply Measure.bind_congr_right filter_upwards [] with r rw [ih, Measure.map_map (measurable_record site r) measurable_eraseOutput, Measure.map_map measurable_eraseOutput (show Measurable (StepTraces.prepend (StepTraces.generationEvent site r)) from StepTraces.measurable_prepend.comp (measurable_const.prodMk measurable_id))] congr 1 funext p rcases site with ⟨kind, op⟩ cases kind with | sample affinity => cases affinity <;> rfl | mean => rfl/-- The kernel to which a sample site binds its fiber is measurable: it is the erased law ofthe measurable detailed kernel `StepTraces.exactKernel`, extended by the recorded draw. -/theorem measurable_traceAndOutputLawAt_continuation (depth : Nat) {expression : Expr} {site : DistributionAction × Op} {fiber : Measure ℝ} {continuation : ℝ → Expr} (reduction : reduce expression = .sample site fiber continuation) : Measurable fun value ↦ (traceAndOutputLawAt depth (continuation value)).map (record site value) := by have hc := (MeasurableActionFamily.stepKernel primitiveLaws).sample_continuation_measurable expression fiber continuation reduction have hm := (Measure.measurable_map _ measurable_eraseOutput).comp ((StepTraces.successorKernel (StepTraces.exactKernel depth)).kernel.measurable.comp ((StepTraces.measurable_generationEvent site).prodMk hc)) convert hm using 1 funext value simp only [Function.comp_apply] rw [StepTraces.successorKernel_apply, StepTraces.exactKernel_apply, exact_eq_detailed, Measure.map_map (measurable_record site value) measurable_eraseOutput, Measure.map_map measurable_eraseOutput (show Measurable (StepTraces.prepend (StepTraces.generationEvent site value)) from StepTraces.measurable_prepend.comp (measurable_const.prodMk measurable_id))] congr 1 funext p rcases site with ⟨kind, op⟩ cases kind with | sample affinity => cases affinity <;> rfl | mean => rfl/-! ### The joint law is a finite measureEvery fiber is a subprobability measure (`reduce_sample_mass_le_one`), so by induction on thenumber of reduction depths the joint law has mass at most one. The induction needs the kernelof each sample site to be measurable (`measurable_traceAndOutputLawAt_continuation`): along amap that is not almost everywhere measurable, Mathlib's pushforward, and so its bind, isunspecified. -/theorem map_univ_le {α β : Type*} [MeasurableSpace α] [MeasurableSpace β] (f : α → β) (μ : Measure α) (hf : AEMeasurable f μ) : μ.map f Set.univ ≤ μ Set.univ := by rw [Measure.map_apply_of_aemeasurable hf MeasurableSet.univ, Set.preimage_univ]theorem finset_sum_lintegral_le {α ι : Type*} [MeasurableSpace α] (μ : Measure α) (s : Finset ι) (f : ι → α → ℝ≥0∞) : ∑ i ∈ s, ∫⁻ a, f i a ∂μ ≤ ∫⁻ a, ∑ i ∈ s, f i a ∂μ := by classical induction s using Finset.induction_on with | empty => simp | insert i s hi ih => simp only [Finset.sum_insert hi] exact (add_le_add le_rfl ih).trans (le_lintegral_add _ _)/-- Through any number of reduction depths, the joint law has mass at most one: a real valuecontributes a Dirac mass at depth zero and nothing later, another value contributes nothing,and a reducible expression passes the bound of its successors through the fiber. -/theorem traceAndOutputLawAt_partial_mass_le_one (bound : Nat) (expression : Expr) : ∑ depth ∈ Finset.range bound, traceAndOutputLawAt depth expression Set.univ ≤ 1 := by induction bound generalizing expression with | zero => simp | succ bound ih => rw [Finset.sum_range_succ'] by_cases value : expression.isValue = true · simp only [traceAndOutputLawAt, value] cases expression <;> simp [traceAndOutputLawAt] · have zero : traceAndOutputLawAt 0 expression Set.univ = 0 := by cases expression <;> first | exact absurd rfl value | simp [traceAndOutputLawAt] rw [zero, add_zero] simp only [traceAndOutputLawAt, value] cases reduction : reduce expression with | next next => exact ih next | stuck => simp | sample site fiber continuation => calc ∑ depth ∈ Finset.range bound, (fiber.bind fun value ↦ (traceAndOutputLawAt depth (continuation value)).map (record site value)) Set.univ ≤ ∑ depth ∈ Finset.range bound, ∫⁻ value, traceAndOutputLawAt depth (continuation value) Set.univ ∂fiber := Finset.sum_le_sum fun depth _ ↦ (Measure.bind_apply_le (measurable_traceAndOutputLawAt_continuation depth reduction).aemeasurable MeasurableSet.univ).trans (lintegral_mono fun value ↦ map_univ_le _ _ (measurable_record site value).aemeasurable) _ ≤ ∫⁻ value, ∑ depth ∈ Finset.range bound, traceAndOutputLawAt depth (continuation value) Set.univ ∂fiber := finset_sum_lintegral_le _ _ _ _ ≤ ∫⁻ _, 1 ∂fiber := lintegral_mono fun value ↦ ih (continuation value) _ = fiber Set.univ := by simp _ ≤ 1 := reduce_sample_mass_le_one reductiontheorem traceAndOutputLaw_mass_le_one (program : Expr) : traceAndOutputLaw program Set.univ ≤ 1 := by rw [traceAndOutputLaw, Measure.sum_apply _ MeasurableSet.univ] exact ENNReal.tsum_le_of_sum_range_le fun bound ↦ traceAndOutputLawAt_partial_mass_le_one bound program/-- The joint law of trace and output is a finite measure, as Mathlib's disintegration`Measure.condKernel` requires of it (`Theorems.lean`). -/instance isFiniteMeasure_traceAndOutputLaw (program : Expr) : IsFiniteMeasure (traceAndOutputLaw program) := ⟨(traceAndOutputLaw_mass_le_one program).trans_lt ENNReal.one_lt_top⟩instance isFiniteMeasure_traceLaw (program : Expr) : IsFiniteMeasure (traceLaw program) := inferInstanceAs (IsFiniteMeasure ((traceAndOutputLaw program).map Prod.fst))end Determinize.Proof.Traces