Source lean/Determinize/Proof/Traces/CompactTrace.lean
import Determinize.Proof.Symbolic.TraceGenerationimport Determinize.Spec.Traces.Semantics/-!# Compact tracesThe compact trace of a detailed step trace retains its general-affinity draws (`retain`), and themeasurable structure of compact traces is generated by their length and coordinates.-/namespace Determinize.Proof.StepTracesopen MeasureTheory ProbabilityTheory Determinize.Spec.Paper Determinize.Proof.StepTracesopen Determinize.Proof.Paperopen scoped ProbabilityTheorynoncomputable sectionabbrev DrawTrace := Determinize.Spec.Traces.Tracetheorem measurable_draw_length : Measurable (List.length : DrawTrace → Nat) :=  measurable_fst.comp (comap_measurable _)theorem measurable_draw_event (i : Nat) :    Measurable (fun trace : DrawTrace ↦ trace.getD i (.uniform, 0)) := by  have h : Measurable (fun trace : DrawTrace ↦      (trace.length, fun j : Nat ↦ trace.getD j (.uniform, 0))) := comap_measurable _  exact (measurable_pi_apply i).comp (measurable_snd.comp h)theorem measurable_draw_cons :    Measurable (fun p : (Op × ℝ) × DrawTrace ↦ p.1 :: p.2) := by  apply measurable_comap_iff.mpr  refine Measurable.prodMk ((measurable_draw_length.comp measurable_snd).add_const 1) ?_  apply Measurable.of_eval  intro i  cases i with  | zero => exact measurable_fst  | succ i => exact (measurable_draw_event i).comp measurable_sndtheorem measurable_draw_tail : Measurable (List.tail : DrawTrace → DrawTrace) := by  apply measurable_comap_iff.mpr  refine Measurable.prodMk ?_ ?_  · simpa using measurable_draw_length.sub_const 1  · apply Measurable.of_eval    intro i    simpa using measurable_draw_event (i + 1)/-- Put an event's draw, if it has one, in front of a compact trace. -/def emitDraw (event : Event) (trace : DrawTrace) : DrawTrace :=  match event with | none => trace | some draw => draw :: tracetheorem measurable_event_elim {α β : Type*} [MeasurableSpace α] [MeasurableSpace β]    (empty : α → β) (draw : (Op × ℝ) × α → β)    (he : Measurable empty) (hd : Measurable draw) :    Measurable (fun p : Event × α ↦ p.1.elim (empty p.2) (fun d ↦ draw (d, p.2))) := by  let f : (Sum (Op × ℝ) PUnit) × α → β := fun p ↦    match p.1 with | .inl d => draw (d, p.2) | .inr _ => empty p.2  have hf : Measurable f := by    convert (hd.sumElim (he.comp measurable_snd)).comp      (MeasurableEquiv.sumProdDistrib (Op × ℝ) PUnit α).measurable using 1    funext ⟨e, a⟩    cases e <;> rfl  have h := hf.comp    ((comap_measurable (Equiv.optionEquivSumPUnit.{0} (Op × ℝ))).prodMap (measurable_id (α := α)))  convert h using 1  funext ⟨e, a⟩  cases e <;> rfltheorem measurable_emitDraw : Measurable (fun p : Event × DrawTrace ↦ emitDraw p.1 p.2) := by  convert measurable_event_elim id (fun p ↦ p.1 :: p.2) measurable_id measurable_draw_cons using 1  funext ⟨e, a⟩  cases e <;> rfl/-- The compact trace of the first `n` events of a detailed trace. -/def retainWithin : Nat → Trace → DrawTrace  | 0, _ => []  | n + 1, trace => emitDraw (trace.headD none) (retainWithin n trace.tail)theorem measurable_retainWithin (n : Nat) : Measurable (retainWithin n) := by  induction n with  | zero => exact measurable_const  | succ n ih =>    exact measurable_emitDraw.comp      (measurable_trace_head.prodMk (ih.comp measurable_trace_tail))/-- The compact trace of a detailed trace: exactly its G-affinity draws, in order. -/def retain (trace : Trace) : DrawTrace := trace.filterMap idtheorem retain_eq (trace : Trace) : retain trace = retainWithin trace.length trace := by  induction trace with  | nil => rfl  | cons head tail ih => cases head <;> simp_all [retain, retainWithin, emitDraw]theorem measurable_retain : Measurable retain := by  rw [funext retain_eq]  have h : Measurable (fun p : Nat × Trace ↦ retainWithin p.1 p.2) :=    measurable_from_prod_countable_right measurable_retainWithin  exact h.comp (measurable_trace_length.prodMk measurable_id)endend Determinize.Proof.StepTraces