OAI/Combinatorics/LowSpaceSubsetSum/Counting/FiniteRepetition.lean

GitHub source file

17 declarations, 0 contain sorry, 0 declared as axioms

Independent complete rounds and the fixed finite repetition schedule

The product law retains both actual outcomes, including sampler exhaustion. Repetition draws fresh complete rounds and accepts if any round accepts.

  1. def OAI.LowSpaceSubsetSum.FiniteLaw.prod line 26

    Source documentation

    Independent actual outcomes. A failure value in either coordinate does not prevent the other coordinate from being drawn.

    def prod (μ : FiniteLaw Ω) (ν : FiniteLaw Ψ) : FiniteLaw (Ω × Ψ) where
    …

    Mentions: OAI.LowSpaceSubsetSum.FiniteLaw

  2. theorem OAI.LowSpaceSubsetSum.FiniteLaw.prod_first_probability line 34
  3. theorem OAI.LowSpaceSubsetSum.FiniteLaw.prod_second_probability line 44
  4. theorem OAI.LowSpaceSubsetSum.FiniteLaw.prod_or_ge_left line 55
  5. theorem OAI.LowSpaceSubsetSum.FiniteLaw.prod_or_ge_right line 61
  6. def OAI.LowSpaceSubsetSum.FiniteLaw.pi line 68

    Source documentation

    Fresh independent draws, allowing a different finite law at each index.

    def pi {I : Type*} [Fintype I] [DecidableEq I] (A : I → Type*) [∀ i, Fintype (A i)]
        (μ : ∀ i, FiniteLaw (A i)) : FiniteLaw (∀ i, A i) where
    …

    Mentions: OAI.LowSpaceSubsetSum.FiniteLaw

  7. theorem OAI.LowSpaceSubsetSum.FiniteLaw.pi_forall_probability line 77
  8. def OAI.LowSpaceSubsetSum.FiniteLaw.iid line 93
  9. theorem OAI.LowSpaceSubsetSum.FiniteLaw.iid_forall_probability line 96
  10. theorem OAI.LowSpaceSubsetSum.FiniteLaw.iid_exists_probability line 101
  11. def OAI.LowSpaceSubsetSum.repeatAccept line 114

    Source documentation

    The executable finite OR of complete trial outcomes.

    def repeatAccept {Ω : Type*} {k : ℕ} (test : Ω → Bool) (draws : Fin k → Ω) : Bool :=
    …
  12. theorem OAI.LowSpaceSubsetSum.repeatAccept_eq_true line 117
  13. theorem OAI.LowSpaceSubsetSum.repeatAccept_sound line 122
  14. theorem OAI.LowSpaceSubsetSum.repetition_acceptance_probability line 128
  15. def OAI.LowSpaceSubsetSum.optionAccept line 142

    Source documentation

    Exhaustion is a rejecting actual outcome, without conditioning the law.

    def optionAccept {α : Type*} (test : α → Bool) : Option α → Bool
      | none => false
      | some x => test x
  16. theorem OAI.LowSpaceSubsetSum.optionAccept_eq_true line 146
  17. theorem OAI.LowSpaceSubsetSum.bounded_repetition_acceptance_probability line 150