Source lean/Determinize/Proof/FiniteModel/IndexedReplay.lean
import Determinize.Proof.FiniteModel.Replaynamespace Determinize.Finiteopen Spec.FiniteModel Checkingopen Spec.Paper (Core)deriving instance DecidableEq for Edgeprivate def rowMass (candidate : Candidate) (i : Fin candidate.states.size) (target : Nat) : Rat :=  ((candidate.row i).edges.toList.map fun edge ↦    if edge.target = target then edge.probability else 0).sumdef indexedMass (outcomes : List (Rat × State)) (indices : Nat → Nat) (target : Nat) : Rat :=  (outcomes.zipIdx.map fun (outcome, k) ↦ if indices k = target then outcome.1 else 0).sumdef Candidate.IndexedRowReplays (candidate : Candidate) (indices : Nat → Nat)    (i : Fin candidate.states.size) : Prop :=  match step (candidate.state i) with  | .error _ => False  | .ok (.returned reward) => (candidate.row i).kind = .returned reward  | .ok .rejected => (candidate.row i).kind = .rejected  | .ok (.next _ successors) =>    (candidate.row i).kind = .transient ∧    (∀ outcome ∈ successors, 0 ≤ outcome.1) ∧    (∀ k : Fin successors.length, 0 < successors[k].1 →      candidate.states[indices k.val]? = some successors[k].2 ∧        ∃ edge ∈ (candidate.row i).edges.toList, edge.target = indices k.val) ∧    (∀ edge ∈ (candidate.row i).edges.toList,      rowMass candidate i edge.target = indexedMass successors indices edge.target)instance (candidate : Candidate) (indices : Nat → Nat) (i : Fin candidate.states.size) :    Decidable (candidate.IndexedRowReplays indices i) := by  unfold Candidate.IndexedRowReplays  split <;> infer_instancetheorem indexedRow_weights (candidate : Candidate) (indices : Nat → Nat)    (i j : Fin candidate.states.size) (evidence : Evidence) (successors : List (Rat × State))    (action : step (candidate.state i) = .ok (.next evidence successors))    (replay : candidate.IndexedRowReplays indices i) :    candidate.weight i j = indexedMass successors indices j.val := by  have valid := replay  simp only [Candidate.IndexedRowReplays, action] at valid  by_cases present : ∃ edge ∈ (candidate.row i).edges.toList, edge.target = j.val  · obtain ⟨edge, member, target⟩ := present    simpa only [rowMass, Candidate.weight, target] using valid.2.2.2 edge member  · have leftZero : candidate.weight i j = 0 := by      apply List.sum_eq_zero      intro q member      obtain ⟨edge, inEdges, rfl⟩ := List.mem_map.mp member      have different : edge.target ≠ j.val := fun h ↦ present ⟨edge, inEdges, h⟩      simp [different]    rw [leftZero]    symm    apply List.sum_eq_zero    intro q member    obtain ⟨⟨outcome, k⟩, inZip, rfl⟩ := List.mem_map.mp member    have position := List.mem_zipIdx' inZip    by_cases positive : 0 < outcome.1    · obtain ⟨edge, memberEdge, target⟩ := (valid.2.2.1 ⟨k, position.1⟩        (by simpa [position.2] using positive)).2      have different : indices k ≠ j.val := fun h ↦ present ⟨edge, memberEdge, target.trans h⟩      simp [different]    · have zero : outcome.1 = 0 := le_antisymm (le_of_not_gt positive)        (valid.2.1 outcome (List.fst_mem_of_mem_zipIdx inZip))      simp [zero]def Candidate.IndexedReplayValid (candidate : Candidate) (source : Core) (subject : Subject)    (indices : Fin candidate.states.size → Nat → Nat) : Prop :=  candidate.rows.size = candidate.states.size ∧ candidate.initial < candidate.states.size ∧    candidate.states[candidate.initial]? = some (initialState source subject) ∧    Proof.FiniteModel.Binding.Scoped 0 source ∧    candidate.MatrixValid ∧ (∀ i, candidate.EdgesValid i) ∧    (∀ i, candidate.IndexedRowReplays (indices i) i)instance (candidate : Candidate) (source : Core) (subject : Subject)    (indices : Fin candidate.states.size → Nat → Nat) :    Decidable (candidate.IndexedReplayValid source subject indices) :=  inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _ ∧ _ ∧ _ ∧ _))theorem indexedReplay_valid (candidate : Candidate) (source : Core) (subject : Subject)    (indices : Fin candidate.states.size → Nat → Nat)    (valid : candidate.IndexedReplayValid source subject indices) : candidate.GraphValid :=  ⟨valid.2.1, valid.2.2.2.2.1, valid.2.2.2.2.2.1⟩private theorem sum_edge_weights {n : Nat} (edges : List Edge)    (bounded : ∀ edge ∈ edges, edge.target < n) :    (∑ j : Fin n, (edges.map fun edge ↦ if edge.target = j.val then edge.probability else 0).sum) =      (edges.map Edge.probability).sum := by  induction edges with  | nil => simp  | cons edge edges ih =>    have bound := bounded edge (by simp)    have rest := ih (fun e h ↦ bounded e (by simp [h]))    simp only [List.map_cons, List.sum_cons, Finset.sum_add_distrib, rest]    congr 1    have eq (j : Fin n) : edge.target = j.val ↔ (⟨edge.target, bound⟩ : Fin n) = j := by      constructor      · intro h; apply Fin.ext; exact h      · intro h; exact congrArg Fin.val h    simp [eq]private theorem matrix_of_sparse (candidate : Candidate)    (edges : ∀ i, candidate.EdgesValid i)    (normalized : ∀ i, ((candidate.row i).edges.toList.map Edge.probability).sum = 1)    (terminal : ∀ i, (candidate.row i).kind ≠ .transient →      (candidate.row i).edges = #[⟨i.val, 1⟩]) : candidate.MatrixValid := by  refine ⟨?_, ?_, ?_⟩  · intro i j    apply List.sum_nonneg    intro q member    obtain ⟨edge, present, rfl⟩ := List.mem_map.mp member    split    · exact le_of_lt ((edges i).2 edge present).2    · exact le_rfl  · intro i    exact (sum_edge_weights (candidate.row i).edges.toList      (fun edge present ↦ ((edges i).2 edge present).1)).trans (normalized i)  · intro i isTerminal j    simp [Candidate.weight, terminal i isTerminal, Fin.ext_iff]def Candidate.IndexedStateValid (candidate : Candidate)    (indices : Fin candidate.states.size → Nat → Nat) (i : Fin candidate.states.size) : Prop :=  (((candidate.row i).edges.toList.map Edge.probability).sum = 1) ∧    ((candidate.row i).kind ≠ .transient → (candidate.row i).edges = #[⟨i.val, 1⟩]) ∧    candidate.EdgesValid i ∧ candidate.IndexedRowReplays (indices i) iinstance (candidate : Candidate) (indices : Fin candidate.states.size → Nat → Nat)    (i : Fin candidate.states.size) : Decidable (candidate.IndexedStateValid indices i) :=  inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _))theorem indexedStates_valid (candidate : Candidate) (source : Core) (subject : Subject)    (indices : Fin candidate.states.size → Nat → Nat)    (initial : candidate.rows.size = candidate.states.size ∧      candidate.initial < candidate.states.size ∧      candidate.states[candidate.initial]? = some (initialState source subject) ∧      Proof.FiniteModel.Binding.Scoped 0 source)    (rows : ∀ i, candidate.IndexedStateValid indices i) :    candidate.IndexedReplayValid source subject indices := by  have edges := fun i ↦ (rows i).2.2.1  exact ⟨initial.1, initial.2.1, initial.2.2.1, initial.2.2.2,    matrix_of_sparse candidate edges (fun i ↦ (rows i).1) (fun i ↦ (rows i).2.1),    edges, fun i ↦ (rows i).2.2.2⟩end Determinize.Finite