Reference · The Applied Higher-Order Functions catalogue

rainbow.algorithms.proofs.ahof.is-falsification

The Applied Higher-Order Functions cataloguesrc/rainbow/algorithms/proofs/ahof/is_falsification.clj3 definitions, 3 theorems

AHoF V27 Importance Sampling: estimate the probability of a rare failure event by sampling from a proposal distribution and reweighting by the importance weight, the ratio of the target density to the proposal density: importance-weight target proposal = target / proposal. The ratio reading holds only for a POSITIVE proposal density. nnrat/divide is totalised: a zero proposal is accepted and yields a junk value (its reciprocal maps the equivalent zeros 0/1 and 0/2 to 1 and 2), and that zero case lies outside the importance-weight claim. Proved: importance-weight unfolds to nnrat/divide for all inputs (by reflexivity, an unfolding and not a ratio claim), a sample drawn under proposal 1/4 for a target 1/2 carries weight 2, and a sample whose target and proposal agree (1/4, 1/4) carries weight 1. Weights are proved by cross-product equivalence. Proved native and axiom-free. Requires nnrat/divide, nnrat/equivalent (all in the D63 checkpoint). Scope (measured by the kernel): this module has 2 worked instances (statements about specific values) and 1 definitional unfoldings (true by unfolding a definition). None of its theorems is a guarantee about the algorithm for all inputs; `lein verify rainbow.algorithms.proofs.ahof.is-falsification` prints this classification.

is-weight/importance-weight :
  (x₁ x₂ : ℚ≥0)
  → ℚ≥0

is-weight/rare-event-weight :
  → ℚ≥0

is-weight/matched-weight :
  → ℚ≥0

is-weight/importance-weight-unfold :
  (target proposal : ℚ≥0)
  → accuracy/accuracy target proposal = nnrat/divide target proposal

is-weight/rare-event-weight-is-two :
  → adaptive-is/unequal-weight = 2

is-weight/matched-weight-is-one :
  → is-weight/matched-weight = 1