Source lean/Determinize/Proof/FiniteModel/SparseRow.lean
import Determinize.Proof.FiniteModel.Replaynamespace Determinize.Finite.Builderopen Spec.FiniteModeldef sparseEdges {n : Nat} (weight : Fin n → Rat) : Array Edge :=  (((List.finRange n).filter fun j ↦ decide (0 < weight j)).map fun j ↦ ⟨j.val, weight j⟩).toArraytheorem sparseEdges_weight {n : Nat} (weight : Fin n → Rat) (nonnegative : ∀ j, 0 ≤ weight j)    (j : Fin n) :    ((sparseEdges weight).toList.map fun edge ↦      if edge.target = j.val then edge.probability else 0).sum =      weight j := by  simp only [sparseEdges, List.toList_toArray, List.map_map]  rw [← List.sum_toFinset _ ((List.nodup_finRange n).filter _), List.toFinset_filter]  simp only [List.toFinset_finRange, decide_eq_true_eq]  change (∑ k ∈ Finset.univ.filter (fun k ↦ 0 < weight k),    if k.val = j.val then weight k else 0) = weight j  simp only [← Fin.ext_iff, Finset.sum_ite_eq', Finset.mem_filter, Finset.mem_univ, true_and]  split  · rfl  · rename_i h    exact (le_antisymm (le_of_not_gt h) (nonnegative j)).symmtheorem sparseEdges_valid {n : Nat} (weight : Fin n → Rat) :    ((sparseEdges weight).toList.map Edge.target).Nodup ∧      ∀ edge ∈ (sparseEdges weight).toList, edge.target < n ∧ 0 < edge.probability := by  constructor  · simp only [sparseEdges, List.toList_toArray, List.map_map]    exact ((List.nodup_finRange n).filter _).map Fin.val_injective  · intro edge member    simp only [sparseEdges, List.toList_toArray, List.mem_map, List.mem_filter,      List.mem_finRange, true_and, decide_eq_true_eq] at member    obtain ⟨j, positive, rfl⟩ := member    exact ⟨j.isLt, positive⟩theorem sum_list_comm {n : Nat} (outcomes : List (Rat × State)) (f : Fin n → Rat × State → Rat) :    (∑ j, (outcomes.map (f j)).sum) = (outcomes.map fun out ↦ ∑ j, f j out).sum := by  induction outcomes with  | nil => simp  | cons out rest ih => simp [Finset.sum_add_distrib, ih]end Determinize.Finite.Builder