Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem LL.1 (Little's Law), p. 537 — L = λW for a sample path observed over [0, T] that is empty at 0 and T

Proved
LittleLaw50.FiniteWindow.theorem_LL1

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 [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 did_idi​, and the system is empty at 000 and TTT: every item arrives and leaves within the window,

0≤ai≤di≤Tfor every i.0 \le a_i \le d_i \le T \quad \text{for every } i.0≤ai​≤di​≤Tfor every i.

Let n(t)n(t)n(t) be the number of items in the system at time ttt, A=∫0Tn(t) dtA = \int_0^T n(t)\,dtA=∫0T​n(t)dt, NNN the number of items arriving in [0,T][0, T][0,T], L=A/TL = A/TL=A/T the average number in the system, λ=N/T\lambda = N/Tλ=N/T the average arrival rate, and W=1N∑i(di−ai)W = \frac1N \sum_i (d_i - a_i)W=N1​∑i​(di​−ai​) the average wait of an item. Then

L=λW.L = \lambda W.L=λW.

The result holds for every sample path: no stationarity, no queue discipline and no service mechanism is assumed. It is the special case of Theorem LL.2 in which no item is present at either end of the window, and the case the paper motivates by a supermarket that is empty at opening and closing time.

Formalization Note The phrase "empty at 000 and TTT" is read as 0≤ai≤di≤T0 \le a_i \le d_i \le T0≤ai​≤di​≤T for every item of the family, the hypothesis of the published cycle identity KellyStochasticNetworks.littles_law_cycle_identity; under it N=MN = MN=M. Presence is the half-open interval [ai,di)[a_i, d_i)[ai​,di​), so an item arriving exactly at 000 is in the system at time 000; the reading therefore also admits such paths (with n(0)>0n(0) > 0n(0)>0), a slightly more permissive hypothesis than n(0)=0n(0) = 0n(0)=0 under which the same identity holds. WWW is the average of the individual waits, not A/NA/NA/N. If N=0N = 0N=0 the paper's WWW is undefined; Lean's WWW is 000 and both sides equal 000, so no hypothesis N≥1N \ge 1N≥1 is needed.

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

/-- **Theorem LL.1** (Little 2011, p. 537). A sample path observed over `[0, T]`, `0 < T`, that is
empty at `0` and `T`: every item arrives and leaves within `[0, T]`. Then `L = λ W`, with `L = A/T`
the time average of `n(t)`, `λ = N/T` and `W` the average of the waits `Wᵢ = dᵢ − aᵢ`. -/
theorem theorem_LL1 {M : ℕ} (a d : Fin M → ℝ) (T : ℝ) (hT : 0 < T)
    (hempty : ∀ i, 0 ≤ a i ∧ a i ≤ d i ∧ d i ≤ T) :
    L_LL1 a d T = lam_LL1 a T * W_LL1 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. 537, Theorem LL.1
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