Lemma C.4 — exponential moment of the one-window OPAC deviation
ProvedChoicePAC.MidPoint.lemma_C4_window_mgfConsider a valid instance. There is a constant such that the following holds for every , every window of length , every admissible allocation (with and ), every with and every resource . When OPAC is applied during with allocation probabilities ,
where is the deviation of the consumption of resource from its conditional mean.
This sub-Gaussian bound on the window deviation is the basic probabilistic estimate behind the bound on the hitting time in the proof of Theorem 5.3.
Formalization Note is chosen before , , , and : the page says "independent of ", and the proof's does not depend on the others either. The page's first equality (the definition of via i.i.d. copies) is the definition of the expectation used here; conditioning on is the choice of a fixed . The standing hypotheses (IsValid) are the disclosed reading of Sec. 2.1, p. 315, Sec. 2.3, p. 317 and Sec. 5.2, p. 327: printed are , bounded nonnegative consumption and ; read in are , consumption laws that are probability measures, almost surely (the page writes on p. 317 and on p. 327; the weaker is used), measurable revenue functions, and revenue that is nonnegative and bounded by a common constant (implicit on the page, needed in App. C.4).
import Mathlib import Definitions.Def_ChoicePAC_MidPoint_Model import Definitions.Def_ChoicePAC_MidPoint_OPAC
namespace ChoicePAC.MidPoint
open MeasureTheory in
theorem lemma_C4_window_mgf {NT n m : ℕ} (I : Instance NT n m) (hI : I.IsValid) :
∃ φ : ℝ, ∀ k : ℕ, 1 ≤ k → ∀ ℓ : ℝ, 0 ≤ ℓ → ∀ p : Fin n → ℝ, I.AdmissibleProbs p →
∀ r : ℝ, |r * I.ξmax| ≤ 1 → ∀ i : Fin m,
I.opacExpect k ℓ p (fun ζ => Real.exp (r * (ζ i - I.opacMean k ℓ p i))) ≤
∏ q, Real.exp ((k : ℝ) * I.lam q * ℓ * r ^ 2 *
∑ j ∈ I.S q, p j * ∫ a, (a i) ^ 2 ∂(I.D j)) ∧
∏ q, Real.exp ((k : ℝ) * I.lam q * ℓ * r ^ 2 *
∑ j ∈ I.S q, p j * ∫ a, (a i) ^ 2 ∂(I.D j)) ≤
Real.exp ((k : ℝ) * φ * ℓ * r ^ 2) := by sorry
end ChoicePAC.MidPoint
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.