Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem LL.2 (Little's Law over [0, T]), p. 539 — L = λW for every sample path observed over [0, T], 0 < T < ∞

Proved
LittleLaw50.FiniteWindow.theorem_LL2

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

littles-lawp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-theory

Consider one sample path of a queuing system observed over a finite window [0,T][0, T][0,T] with 0<T<∞0 < T < \infty0<T<∞. Items i=1,…,Mi = 1, \dots, Mi=1,…,M arrive at times aia_iai​ and leave at times di≥aid_i \ge a_idi​≥ai​. Items may already be in the system at time 000 and may still be there at time TTT (such an item is given any departure time di>Td_i > Tdi​>T). Let

  1. n(t)n(t)n(t) be the number of items in the system at time ttt, and A=∫0Tn(t) dtA = \int_0^T n(t)\,dtA=∫0T​n(t)dt;
  2. S(T)S(T)S(T) be the cumulative number of items in the system over [0,T][0, T][0,T]: the items present at t=0t = 0t=0 plus the items arriving in [0,T][0, T][0,T];
  3. wi(T)=max⁡(0,min⁡(di,T)−max⁡(ai,0))w_i(T) = \max(0, \min(d_i, T) - \max(a_i, 0))wi​(T)=max(0,min(di​,T)−max(ai​,0)) be the time item iii spends in the system during [0,T][0, T][0,T];
  4. L(T)=A/TL(T) = A/TL(T)=A/T, λ(T)=S(T)/T\lambda(T) = S(T)/Tλ(T)=S(T)/T, and W(T)W(T)W(T) the average of wi(T)w_i(T)wi​(T) over the S(T)S(T)S(T) counted items.

Then

L(T)=λ(T) W(T).L(T) = \lambda(T)\, W(T).L(T)=λ(T)W(T).

This is Little's Law over a finite window with permissible initial and final queues. It holds exactly for every sample path, whether or not the system is ever empty (§2.2.3, Corollary (1)) and whether or not there is any service operation (Corollary (2)); no stationarity, queue discipline or limit is involved. Theorem LL.1 is its special case for a window empty at both ends.

Formalization Note Presence is half-open, [ai,di)[a_i, d_i)[ai​,di​); an item arriving exactly at 000 is counted in S(T)S(T)S(T) once, as an arrival in [0,T][0, T][0,T]. The family may contain items never present during [0,T][0, T][0,T]; they are not counted and contribute nothing. W(T)W(T)W(T) is the average of the truncated times in window, never defined as A/S(T)A/S(T)A/S(T); that equality is the content of the theorem. The hypothesis ai≤dia_i \le d_iai​≤di​ (an item leaves no earlier than it arrives) is the paper's Wi≥0W_i \ge 0Wi​≥0. If S(T)=0S(T) = 0S(T)=0, then A=0A = 0A=0, the paper's W(T)W(T)W(T) is undefined, Lean's value is 000, and both sides are 000.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Migration
import Definitions.Def_LittleLaw50_FiniteWindow_Window
Formal statement
namespace LittleLaw50.FiniteWindow

/-- **Theorem LL.2** (Little's Law over `[0, T]`; Little 2011, p. 539). For any sample path
observed over `[0, T]` with `0 < T`, possibly with items present at `0` and at `T`,
`L(T) = λ(T) W(T)`, with `L(T) = A/T`, `λ(T) = S(T)/T` and `W(T)` the average over the `S(T)`
counted items of their time in the system during `[0, T]`. -/
theorem theorem_LL2 {M : ℕ} (a d : Fin M → ℝ) (T : ℝ) (hT : 0 < T)
    (had : ∀ i, a i ≤ d i) :
    Lw Finset.univ a d T = lamw Finset.univ a d T * Ww Finset.univ a d T := by sorry

end LittleLaw50.FiniteWindow
Source
Little, Little's Law as Viewed on Its 50th Anniversary, Oper. Res. 59(3) (2011), DOI 10.1287/opre.1110.0940, p. 539, Theorem LL.2
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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