randomized_submod_tester_accept_prob
def
The probability that a randomized tester accepts an input function f, given by the expected acceptance over its decision trees.
Statement
noncomputable def randomized_submod_tester_accept_prob {n k q : ℕ} (A : RandomizedSubmodTester n k q) (f : CubeFunc n k) : ℝ
- Defined in
- arXiv:2611.02374, Def. 2.5
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 3
- CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
- RandomizedSubmodTesterA randomized tester making at most q queries, modeled as a finite probability distribution over deterministic decision trees of depth at…
- submod_query_tree_evalEvaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.
Read back from the Lean
Given natural numbers n, k, and q, a randomized tester A : RandomizedSubmodTester n k q, and a function f : CubeFunc n k, randomized_submod_tester_accept_prob A f is defined as the real number equal to the sum over all i : Fin A.m of A.prob i if submod_query_tree_eval (A.tree i) f is true, and 0 otherwise. In other words, it is the probability that the randomized tester A accepts f, computed as the sum of the probabilities of all deterministic query trees in A that accept f.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Acceptance probability of a randomized tester on an input function. -/ noncomputable def randomized_submod_tester_accept_prob {n k q : ℕ} (A : RandomizedSubmodTester n k q) (f : CubeFunc n k) : ℝ := ∑ i, if submod_query_tree_eval (A.tree i) f then A.prob i else 0