§3, proof of Proposition 8, (14), p. 631 — the drift of r(i) = Ai^{n+1} is a polynomial of degree ≤ n with leading coefficient A(n + 1)(λ − aβ)
ProvedSennott1989.AvgCost.queue_drift_14Consider the queueing model of Example 2 with finite moment , a decision (service rate ), a real constant and the test function . Then there is a polynomial of degree at most whose coefficient of is
such that for every state the series converges and
When the drift is eventually below any polynomial of degree with larger leading coefficient, which is what the drift condition of the Corollary needs.
Formalization Note The identity is for : state has its own row . The paper says "degree "; since the coefficient of vanishes when , the statement records degree at most together with that coefficient. The first line of the paper's display (14) carries a spurious factor ; the identity stated here is the correct one.
import Mathlib import Definitions.Def_Sennott1989_AvgCost_Assumptions import Definitions.Def_Sennott1989_AvgCost_Queue open scoped ENNReal NNReal open Filter Topology
namespace Sennott1989.AvgCost
/-- Sennott (1989), §3, proof of Proposition 8, display (14), p. 631 (unnumbered). Consider the
queueing model of Example 2 with `λ^(n+1) = ∑_i i^{n+1} p_i < ∞`, a decision `x` (serving at
rate `a(x)β`), a real constant `A`, and the test function `r(i) = A i^{n+1}`. Then for every
state `i ≥ 1` the drift `∑_j P_{ij}(x) (r(j) − r(i))` is a (convergent) series whose value is a
polynomial `A(i)` in `i` of degree at most `n` with coefficient of `i^n` equal to
`A (n + 1)(λ − a(x)β)`, where `λ = ∑_i i p_i`.
**Formalization Note** The identity is stated for `i ≥ 1` only: state `0` has its own transition
row `(p_j)`. The paper says "of degree `n` with leading coefficient `A(n + 1)(λ − aβ)`"; when
`λ = aβ` that coefficient is `0`, so the statement records degree `≤ n` and the coefficient of
`i^n`. The paper's first line of (14) carries a spurious factor `A` (typo); the identity here is
the correct one. The paper uses `A` both for the constant and for the polynomial `A(i)`; here the
polynomial is `P`. -/
theorem queue_drift_14 {Act : Type} [Fintype Act] [Nonempty Act] (q : QueueData Act)
(hmom : Summable fun i : ℕ => (i : ℝ) ^ (q.n + 1) * (q.p i : ℝ)) (x : Act) (A : ℝ) :
∃ P : Polynomial ℝ, P.natDegree ≤ q.n ∧
P.coeff q.n = A * ((q.n : ℝ) + 1) * (q.lam - q.a x * q.β) ∧
∀ i : ℕ, 1 ≤ i →
Summable (fun j : ℕ => (q.toMDC.P i x j).toReal *
(A * (j : ℝ) ^ (q.n + 1) - A * (i : ℝ) ^ (q.n + 1))) ∧
∑' j : ℕ, (q.toMDC.P i x j).toReal *
(A * (j : ℝ) ^ (q.n + 1) - A * (i : ℝ) ^ (q.n + 1)) = P.eval (i : ℝ) := by sorry
end Sennott1989.AvgCost
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.