Theorem 6, p. 16 — exp(θΦ) is a geometric Lyapunov function and the stationary tail of Φ decays exponentially
ProvedGJNSteadyState.Interchange.theorem_6Let be the time- transition kernel of a Markov process on with stationary distribution , and let be a measurable Lyapunov function with drift size and exception parameter , with . Suppose satisfies
Then:
- is a geometric Lyapunov function with geometric drift size , drift time and exception parameter ;
- for every ,
Combined with Proposition 3 this gives the exponential tail bound of Theorem 7 on the scaled stationary workload.
Formalization Note The page prints the factor in (29). Its proof (p. 24) applies (27) to , whose geometric drift size is by the first part; (27) then gives (the proof mislabels the drift size as ). The corrected factor is stated. The hypothesis is added: Remark 6 derives , needed for the drift size to lie in as Definition 2 requires, by taking a supremum over this set. The Markov process enters through its time- transition kernel and the invariance of . Condition (28) is read in .
import Mathlib import Definitions.Def_GJNSteadyState_Interchange_Lyapunov open MeasureTheory ProbabilityTheory
namespace GJNSteadyState.Interchange
/-- Theorem 6 (p. 16): let `π` be a stationary distribution of a Markov process with time-`t₀`
transition kernel `κ`, and `Φ` a Lyapunov function with parameters `γ, t₀, K` such that
`{Φ > K}` is nonempty. If `θ > 0` satisfies (28) `θ L₂(θ, t₀) ≤ γ`, then `exp(θΦ)` is a
geometric Lyapunov function with geometric drift size `1 − γθ/2`, drift time `t₀` and exception
parameter `e^{θK}`, and (29) `P_π(Φ(Ξ(0)) > s) ≤ (γθ/2)⁻¹ L₁(θ, t₀) e^{−θ(s − K)}` for every
`s > K`. The page prints the factor `(1 − γθ/2)⁻¹` in (29); applying (27) to the geometric drift
size `1 − γθ/2` of the first part gives `(1 − (1 − γθ/2))⁻¹ = (γθ/2)⁻¹`, which is stated here. -/
theorem theorem_6 {X : Type*} [MeasurableSpace X] (κ : Kernel X X) [IsMarkovKernel κ]
(π : Measure X) [IsProbabilityMeasure π] (hπ : κ.Invariant π)
(Φ : X → NNReal) (hΦ : Measurable Φ) (γ K : ℝ)
(hlyap : IsLyapunov (kernelExp κ) Φ γ K) (hne : ∃ x, K < (Φ x : ℝ))
(θ : ℝ) (hθ : 0 < θ) (h28 : ENNReal.ofReal θ * L2 (kernelExp κ) Φ θ ≤ ENNReal.ofReal γ) :
IsGeomLyapunov (kernelExp κ) (fun x => Real.toNNReal (Real.exp (θ * Φ x)))
(1 - γ * θ / 2) (Real.exp (θ * K)) ∧
∀ s : ℝ, K < s →
π {x | s < (Φ x : ℝ)} ≤
(ENNReal.ofReal (γ * θ / 2))⁻¹ * L1 (kernelExp κ) Φ θ *
ENNReal.ofReal (Real.exp (-(θ * (s - K)))) := by sorry
end GJNSteadyState.Interchange
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.