Theorem LL.2 (Little's Law over [0, T]), p. 539 — L = λW for every sample path observed over [0, T], 0 < T < ∞
ProvedLittleLaw50.FiniteWindow.theorem_LL2Consider one sample path of a queuing system observed over a finite window with . Items arrive at times and leave at times . Items may already be in the system at time and may still be there at time (such an item is given any departure time ). Let
- be the number of items in the system at time , and ;
- be the cumulative number of items in the system over : the items present at plus the items arriving in ;
- be the time item spends in the system during ;
- , , and the average of over the counted items.
Then
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, ; an item arriving exactly at is counted in once, as an arrival in . The family may contain items never present during ; they are not counted and contribute nothing. is the average of the truncated times in window, never defined as ; that equality is the content of the theorem. The hypothesis (an item leaves no earlier than it arrives) is the paper's . If , then , the paper's is undefined, Lean's value is , and both sides are .
import Mathlib import Definitions.Def_KellyStochasticNetworks_Migration import Definitions.Def_LittleLaw50_FiniteWindow_Window
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.