Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1.1 — the set identity behind the fluid Little formula

Proved
PalmQueueing.Formulas.fluid_set_identity

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

fluid-queuelittles-lawpalm-calculusqueueingstationary-process

Lemma 3.1.1. Let {W(t)}\{W(t)\}{W(t)} be the stationary workload in a stable single server fluid queue. For all s<ts < ts<t, the following sets are equal:

F={u∈[s,t]  ;  W(u)>Cu,t},G={u∈[s,t]  ;  W(t)>Au,t}.F = \{u \in [s,t] \;;\; W(u) > C_{u,t}\}, \qquad G = \{u \in [s,t] \;;\; W(t) > A_{u,t}\} .F={u∈[s,t];W(u)>Cu,t​},G={u∈[s,t];W(t)>Au,t​}.

The left description says "the work still in the buffer at uuu exceeds everything the server could drain between uuu and ttt"; the right says "the work in the buffer at ttt exceeds everything that arrived since uuu". That these describe the same instants is what turns the fluid workload into an integral over the arrival measure — Property 3.1.1 on the same page reads off

W(t)=∫(−∞,t]1W(s)>Cs,tA(ds)(3.1.39)W(t) = \int_{(-\infty,t]} \mathbf{1}_{W(s) > C_{s,t}} A(ds) \tag{3.1.39}W(t)=∫(−∞,t]​1W(s)>Cs,t​​A(ds)(3.1.39)

when AAA is absolutely continuous — and that is the fluid analogue of Little's formula.

Both inclusions come from the fluid-queue representation (2.7.5) and nothing else. If u∈Fu \in Fu∈F then W(t)≥W(u)+Au,t−Cu,t>Au,tW(t) \ge W(u) + A_{u,t} - C_{u,t} > A_{u,t}W(t)≥W(u)+Au,t​−Cu,t​>Au,t​, so u∈Gu \in Gu∈G. Conversely if u∈Gu \in Gu∈G then the maximum in W(t)=max⁡(W(u)+Au,t−Cu,t,sup⁡u≤v≤t(Av,t−Cv,t))W(t) = \max(W(u) + A_{u,t} - C_{u,t}, \sup_{u \le v \le t}(A_{v,t} - C_{v,t}))W(t)=max(W(u)+Au,t​−Cu,t​,supu≤v≤t​(Av,t​−Cv,t​)) cannot be achieved by the second term, since that term is bounded above by Au,tA_{u,t}Au,t​; so W(u)+Au,t−Cu,t=W(t)>Au,tW(u) + A_{u,t} - C_{u,t} = W(t) > A_{u,t}W(u)+Au,t​−Cu,t​=W(t)>Au,t​, which implies u∈Fu \in Fu∈F.

Formalization Note. The framework of §2.7 is carried as hypotheses: AAA and CCC are the interval functions of θt\theta_tθt​-compatible non-negative random measures, and {W(t)}\{W(t)\}{W(t)} is a θt\theta_tθt​-compatible solution of the fluid-queue equation (2.7.6). The identity is stated pathwise, for every ω\omegaω, as the page's sets are.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Palm_PointProcess
import Definitions.Def_PalmQueueing_Loynes_FluidQueue
Formal statement
/-!
# Lemma 3.1.1: the set identity behind the fluid Little formula (§3.1.3, p.193)
-/

namespace PalmQueueing.Formulas

open MeasureTheory
open PalmQueueing.Palm PalmQueueing.Loynes

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Lemma 3.1.1** (p.193). Let `{W(t)}` be the stationary workload in a stable single server
fluid queue. For all `s < t`, the following sets are equal:

`F = { u ∈ [s,t] : W(u) > C_{u,t} }`,   `G = { u ∈ [s,t] : W(t) > A_{u,t} }`.

The left description says "the work still in the buffer at `u` exceeds everything the server could
drain between `u` and `t`"; the right says "the work in the buffer at `t` exceeds everything that
arrived since `u`". That these describe the same instants is what turns the fluid workload into an
integral over the arrival measure — Property 3.1.1 on the same page reads it off as
`W(t) = ∫_{(-∞,t]} 1_{W(s) > C_{s,t}} A(ds)` (3.1.39) — and that is the fluid analogue of Little's
formula.

Both inclusions come from the fluid-queue representation (2.7.5) of §2.7. If `u ∈ F` then
`W(t) ≥ W(u) + A_{u,t} − C_{u,t} > A_{u,t}`. Conversely if `u ∈ G` then the maximum in
`W(t) = max(W(u) + A_{u,t} − C_{u,t}, sup_{u≤v≤t}(A_{v,t} − C_{v,t}))` cannot be achieved by the
second term, since that term is bounded above by `A_{u,t}`; so
`W(u) + A_{u,t} − C_{u,t} = W(t) > A_{u,t}`.

The framework and the notation for fluid queues are those of §2.7, Chapter 2, so `IsFluidWorkload`
is imported rather than restated: `A` and `C` are the interval functions of `θ_t`-compatible
non-negative random measures (`IsFlowMeasure`, p.128), and `{W(t)}` is a `θ_t`-compatible
solution of the fluid-queue equation `(2.7.6)`. The non-negativity of `A` is load-bearing: with
`C ≡ 0`, `A_{u,t} = −(t − u)` and `W ≡ 0`, which solves `(2.7.6)`, `F` is empty while `G = [s,t)`. -/
theorem fluid_set_identity (θ : Flow Ω) (A C : ℝ → ℝ → Ω → ℝ)
    (hA : IsFlowMeasure θ A) (hC : IsFlowMeasure θ C) (W : ℝ → Ω → ℝ)
    (hWcomp : IsCompatible θ W) (hW : IsFluidWorkload A C W) (s t : ℝ) (hst : s < t) (ω : Ω) :
    {u : ℝ | u ∈ Set.Icc s t ∧ C u t ω < W u ω}
      = {u : ℝ | u ∈ Set.Icc s t ∧ A u t ω < W t ω} := by sorry

end PalmQueueing.Formulas
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 193, Lemma 3.1.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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