Operational expected oracle cost as phase occupancies
ProvedCountingLLL.ReciprocalTest.oracle_cost_expectation_eq_occupancyformalizationprobability
For the operational ReciprocalTest program, the extended expected number of oracle calls is the sum, over all execution steps, of the probabilities that the program is in an oracle-query phase. This includes nonterminating executions, for which the defined oracle cost is infinite.
Preamble
import Definitions.Def_CountingLLL_ReciprocalEncodedLaw open MeasureTheory CountingLLL.ReciprocalTest open scoped ENNReal
Formal statement
theorem CountingLLL.ReciprocalTest.oracle_cost_expectation_eq_occupancy (B : ℝ≥0∞) :
∫⁻ ω, oracleCost ω ∂(entropyLaw B) = ∑' t, entropyLaw B {ω | ∃ k : Context, (run ω t).phase = .coinOracle k} := by sorrySource
Liu, Wang, Yin, Zhang, Zhou, A Counting and Sampling Lovász Local Lemma, STOC submission #442, §6.2, Lemma 6.5. This is an operational occupancy identity used toward the expected oracle-call bound, not the bound itself.