Recursive PageRank budget-energy invariant
ProvedNearlyOptimalPPR.Computation.recursive_budget_energyFor every finite reachable prefix of Algorithms 6–9, each open call whose episode budget is open has clipped residual energy bounded by the sum of its episode budget and the charges received during that episode. In the source's notation, the resulting mass bound is
Here is the active residual mass, the episode's initial budget, and the accumulated incoming and activation charges. The virtual residual also accounts for earlier inactive layers. The assertion applies to every finite prefix, including a completed update that crosses the budget; it assumes neither termination nor an unexhausted current budget.
This invariant supplies the mass control used in Lemma 5.3 and the running-time analysis of Lemma 4.4.
Formalization Note The statement preserves the rowwise clipped-energy predicate; the displayed active-mass inequality is its downstream consequence. The graph has a nonisolated seed and the teleportation and root threshold are positive, with teleportation below one.
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open NearlyOptimalPPR.Computation
theorem NearlyOptimalPPR.Computation.recursive_budget_energy (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α < 1) (hq : 0 < q) (hs : 0 < g.graph.degree s)
(ℓ : ℕ) (schedule : BlockSchedule) (t : ℕ) :
BudgetEnergyInvariant g s α (recursiveRun m g s α q ℓ schedule t) := by sorry