Control-event count in a recursive PageRank call
ProvedNearlyOptimalPPR.Computation.recursive_control_event_countFor each call identifier and finite prefix of the operational recursive computation,
A control event is a running transition charged to that call which is neither an exterior push nor a cached solve. It includes episode entry, full solves, child creation, returns, and component completion. The root threshold is positive and the finite undirected input graph has a nonisolated seed.
This bookkeeping estimate bounds the number of control-state visits in the finite-prefix work accounting of Lemma 4.4. It does not bound the cost of each visit; row scans and solves are charged separately.
Formalization Note The constants arise from the finite control-state rank in the operational translation of Algorithms 6–9. The identity remains valid algebraically without a teleportation-range assumption.
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation open scoped ENNReal attribute [local instance] Classical.propDecidable
theorem NearlyOptimalPPR.Computation.recursive_control_event_count (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hq : 0 < q) (hs : 0 < g.graph.degree s) (ℓ : ℕ) (schedule : BlockSchedule) (T id : ℕ) :
let run := recursiveRun m g s α q ℓ schedule
(((Finset.range T).filter (fun k => controlEvent g (run k) id)).card : ℝ) ≤
9+7*((run T).episodes id : ℝ) := by sorry