Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§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β)

Proved
Sennott1989.AvgCost.queue_drift_14

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

lyapunov-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-control

Consider the queueing model of Example 2 with finite moment λ(n+1)=∑iin+1pi<∞\lambda^{(n+1)}=\sum_ii^{n+1}p_i<\inftyλ(n+1)=∑i​in+1pi​<∞, a decision aaa (service rate aβa\betaaβ), a real constant AAA and the test function r(i)=Ain+1r(i)=Ai^{n+1}r(i)=Ain+1. Then there is a polynomial A\mathcal AA of degree at most nnn whose coefficient of ini^nin is

A (n+1) (λ−aβ),λ=∑iipi,A\,(n+1)\,(\lambda-a\beta),\qquad\lambda=\sum_iip_i,A(n+1)(λ−aβ),λ=i∑​ipi​,

such that for every state i≥1i\ge1i≥1 the series ∑jPij(a)(r(j)−r(i))\sum_jP_{ij}(a)\big(r(j)-r(i)\big)∑j​Pij​(a)(r(j)−r(i)) converges and

∑jPij(a)(r(j)−r(i))=A(i).(14)\sum_jP_{ij}(a)\big(r(j)-r(i)\big)=\mathcal A(i).\tag{14}j∑​Pij​(a)(r(j)−r(i))=A(i).(14)

When λ<aβ\lambda<a\betaλ<aβ the drift is eventually below any polynomial of degree nnn with larger leading coefficient, which is what the drift condition of the Corollary needs.

Formalization Note The identity is for i≥1i\ge1i≥1: state 000 has its own row (pj)(p_j)(pj​). The paper says "degree nnn"; since the coefficient of ini^nin vanishes when λ=aβ\lambda=a\betaλ=aβ, the statement records degree at most nnn together with that coefficient. The first line of the paper's display (14) carries a spurious factor AAA; the identity stated here is the correct one.

Preamble
import Mathlib
import Definitions.Def_Sennott1989_AvgCost_Assumptions
import Definitions.Def_Sennott1989_AvgCost_Queue

open scoped ENNReal NNReal
open Filter Topology
Formal statement
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
Source
Sennott, Average Cost Optimal Stationary Policies in Infinite State Markov Decision Processes with Unbounded Costs, Oper. Res. 37(4):626–633 (1989), DOI 10.1287/opre.37.4.626, §3, proof of Proposition 8, (14) and the sentence after it, p. 631
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me